Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. (December 2016)

• Record Type: Journal Article
• Authors: Masmoudi, Mohamed Amine; Hosny, Manar; Braekers, Kris; Dammak, Abdelaziz
• Is Part Of: Transportation research. Volume 96(2016)
• Page Start: 60
• Page End: 80
• Publication Date: 2016-12
• Subjects: Vehicle Routing Problem (VRP) -- Dial-a-Ride Problem (DARP) -- Metaheuristic -- Optimization -- Bees Algorithm (BA); Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2016.10.002
• Languages: English
• ISSNs: 1366-5545

Abstract

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.