1 Logistics & ITS, Department of Transport, Technical University of Denmark2 Department of Transport, Technical University of Denmark
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 practical Dial-a-Ride problem at a Danish transportation operator. These constraints are mainly related to a generalization of capacity to include substitution of seats to wheelchairs and beds, but also extensions to the objective to give a better view of passenger comfort are included. To enable practical use of the algorithm, it is incorporated in the developed user interface and linked with a digitized road network. The user interface is developed as generically as possible making it reuseable in all sorts of Vehicle Routing problems. The foundation of the user interface is a database for storing customers, requests, routes etc. The digitized road map is included in the developed software by use of MapX, which is a program developed and sold by MapInfo Corporation. MapX handles the visualization of the map layers, selections, and labels. The road network is read from MapX into a different network structure in memory to allow for a more intelligent calculation of shortest path between stops and vehicle positions. Unfortunately data from actual Dial-a-Ride transportation systems is not readily available, so tests are based on data generated in this project. While the algorithm performs as expected, other results such as the stable performance of the different modules in the developed software and the developement of a practical setting for solving the Dial-a-Ride problem are equally important.