Publication

Abstract : Dial-a-ride problems (DARPs) have become a popular topic in logistics in recent years.They are frequently used in transportation, goods distribution, and fast delivery.The DARP is an NP-hard optimization problem in which the objective is to organize transmutations from pickup to delivery locations of geographically dispersed customers.Multiple exact and heuristic approaches have been proposed in the literature to solve the DARP.In this paper, we propose a novel algorithm that combines a variable neighborhood search with constraint propagation to solve this problem.Variable neighborhood search is a metaheuristic that iteratively modifies routes to improve the quality of an incumbent solution.Constraint propagation makes use of techniques like backtracking, forward filtering, consistency enforcement to iteratively restrict the possible routes in the problem.Combining the two approaches, one obtains an algorithm that has good properties in terms of runtime and solution quality.In simulations, the algorithm is shown to be more efficient than the basic variable neighborhood search when runtimes are small. © 2023, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.