Solving large-scale dial-a-ride vehicle routing and scheduling problems

Abstract

In this thesis we develop two heuristic algorithms for large-scale multi-vehicle advance-request version of the dial-a-ride problem. This problem is concerned with developing a set of routes for a fleet of vehicles serving customers who have to be picked up from specified origins and be delivered to specified destinations. In this thesis it is assumed that each customer has specified either a desired pick-up time or a desired delivery time and that customer requests for service as well as the number of available vehicles throughout the time period of interest are known well in advance of the time of actual vehicle dispatching. The first heuristic approach consists of three successive and distinct steps: "grouping", "clustering" and "routing". Grouping divides customers into "time groups" on the basis of their desired pick-up and delivery times. Clustering separates customers in each time group into "clusters" and assigns vehicles to serve each cluster. Finally routing generates routes for each individual vehicle to serve every cluster in turn and for every time group. The second algorithm, Advanced Dial-A-Ride with Time Windows (ADARTW), treats customers' desired service times as strict constraints and can guarantee prespecified standards of service quality. The service quality constraints refer to guarantees that (i) customer's ride time will not exceed a pre-specified maximum and (ii) the service time will not deviate from the most desired time by more than a pre-specified amount ("the time windows"). The algorithm builds up vehicle tours through sequential insertion of customers and uses a nonlinear objective function to guide such insertions. Variations of this basic approach are also discussed. We have tested the two algorithms on many simulated cases using computer-generated data. Computational experience with a large-scale real world dial-a-ride problem (2617 customers and 30 simultaneously operating vehicles) is also presented.