The Dial-a-Ride problem is a Vehicle Routing problem in its most general form. The problem was formulated in the beginning of the 1970's and since then a large number of researchers have worked on developing efficient algorithms for use in automated planning of Dial-a-Ride transportation systems. In a Dial-a-Ride transportation system, passengers request a trip between two stops with either a desired time of departure from the pickup stop or a desired time of arrival at the destination. The time windows at the stops are then calculated by the operator based on additional parameters such as maximum excess ride time and allowed deviation from desired service time. All vehicles start and end at a depot, which can be different for each vehicle. The fleet of vehicles is heterogeneous meaning the vehicles can have a different capacity of passenger seats, wheelchairs and beds. The problem is then an extension of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) with the additional constraints that a pickup stop must precede a delivery stop for a passenger, and that both a pickup stop and a delivery stop related to the same passenger must be assigned to the same vehicle. The objective is to minimize the cost of operation similar to the objective for the CVRPTW, with the extension that the level of service to the passengers is considered. Several algorithms for solving the Dial-a-Ride problem have been proposed in the litterature. Because of the complexity of the Dial-a-Ride problem, most methods described in the litterature are based on various insertion techniques often coupled with some sort of clustering of stops, but since 1980 some experiments have been performed with dynamic programming, column generation and set partitioning. In recent years meta heuristics have also been applied to the problem. The metod used in this thesis is based on a clustering first insertion second technique developed at CRT in Canada in the mid 1980's. The algorithm is extended to include constraints imposed by a ...
Dial-a-Ride
2003-10-01
Jørgensen , R M 2003 , Dial-a-Ride . Technical University of Denmark , Kgs. Lyngby, Denmark .
Book
Electronic Resource
English
DDC: | 000 |
NTIS | 1974
British Library Conference Proceedings | 1993
|NTIS | 1974
NTIS | 1972
NTIS | 1973
|