Metaheuristic approach for the heterogeneous dial-a-ride problem with multiple depots

Abstract

In this paper a metaheuristic approach for the dial-a-ride problem with heterogeneous users and vehicles (HDARP) is proposed. Several local search operators are embedded in an adaptive threshold accepting framework. Results on several sets of benchmark instances show that our algorithm is competitive with or outperforms current state-of-the-art methods. Finally, a multiple depot version of the HDARP is introduced. This extension allows to investigate possible advantages of creating depots nearby clusters of users or advantages of cooperation among several dial-a-ride service providers.