Adaptive algorithm for dial-a-ride problem with vehicle breakdown

Abstract

Vehicle breakdown in a centralized fleet operation can inflict large recovery costs and may damage service provider's reputation. We consider the disrupted dial-a-ride problem (DARP), where vehicle breakdown can occur at any point of time during the transportation service. The conventional method to handle vehicle breakdown is to own backup vehicles or rent additional vehicles when necessary, so that the impaired vehicles can be replaced if any vehicle breaks down. In this paper, we introduce an adaptive algorithm with GPU-acceleration, to quickly build routes and schedules for the DARP in the occurrence of unforeseen stochastic events. Computational experiments are conducted on various standard DARP instances, with realistic estimates of operational cost. The results show that the new adaptive algorithm reduces the operational cost when compared to the conventional method.