Scheduling Large-Scale Advance-Request Dial-A-Ride Systems

Abstract

This paper examines the scheduling of large-scale advance-request dial-a-ride systems, describes two algorithms that have been developed recently to solve problems in this area, and provides analysis and insights into how these algorithms are expected to perform under various operational scenarios and in comparison with one another. The algorithms examined are the GCR (Grouping/Clustering/Routing) and ADARTW (Advanced Dial-A-Ride with Time Windows) procedures. The paper gives an overview of both algorithms, emphasizes the differences in their operational scenarios, describes computational experience with both procedures and includes worst-case considerations for ADARTW. Extensions and directions for further research are also discussed.