A linearly decreasing deterministic annealing algorithm for the multi-vehicle dial-a-ride problem.

Dial a ride problem (DARP) is a complex version of the pick-up and delivery problem with many practical applications in the field of transportation. This study proposes an enhanced deterministic annealing algorithm for the solution of large-scale multi-vehicle DARPs. The proposed method always explores the feasible search space; therefore, a feasible solution is guaranteed at any point of termination. This method utilises advanced local search operators to accelerate the search for optimal solutions and it relies on a linearly decreasing deterministic annealing schedule to limit poor jumps during the course of search. This study puts forward a systematic series of experiments to compare the performance of solution methods from various angles. The proposed method is compared with the most efficient methods reported in the literature i.e., the Adaptive Large Neighbourhood Search (ALNS), Evolutionary Local Search (ELS), and Deterministic Annealing (DA) using standard benchmarks. The results suggest that the proposed algorithm is on average faster than the state-of-the-art algorithms in reaching competitive objective values across the range of benchmarks.
Competing Interests: The authors have declared that no competing interests exist.
(Copyright: © 2024 Mortazavi et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.)