Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem

You are here: Homepage > Search

Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem

Masmoudi, Mohamed Amine / Hosny, Manar / Braekers, Kris / Dammak, Abdelaziz

Highlights • A Multi-Depots Multi-Trips Heterogeneous Dial-A-Ride Problem is introduced (MD-MT-HDARP). • Three hybrid algorithms are proposed for the MD-MT-HDARP. • Algorithms are highly effective in solving newly generated instances. • Algorithms outperform current state-of-the-art algorithm on all sets of MD-HDARP instances.

Abstract The Heterogeneous Dial-a-Ride Problem (HDARP) is an important problem in reduced mobility transportation. Recently, several extensions have been proposed towards more realistic applications of the problem. In this paper, a new variant called the Multi-Depot Multi-Trip Heterogeneous Dial-a-Ride Problem (MD-MT-HDARP) is considered. A mathematical programming formulation and three metaheuristics are proposed: an improved Adaptive Large Neighborhood Search (ALNS), Hybrid Bees Algorithm with Simulated Annealing (BA-SA), and Hybrid Bees Algorithm with Deterministic Annealing (BA-DA). Extensive experiments show the effectiveness of the proposed algorithms for solving the underlying problem. In addition, they are competitive to the current state-of-the-art algorithm on the MD-HDARP.