Back close

Combining Variable Neighborhood Search and Constraint Programming for Solving the Dial-A-Ride Problem

Publication Type : Conference Paper

Publisher : Springer

Source : Smart Innovation, Systems and Technologies, vol 312. Springer, Singapore. (2023) DOI: 10.1007/978-981-19-3575-6_23

Url : https://www.scopus.com/inward/record.uri?eid=2-s2.0-85140773985&doi=10.1007%2f978-981-19-3575-6_23&partnerID=40&md5=4e74a861e0e803cdedc2d7e7195afa81

Campus : Amritapuri

Center : AmritaCREATE

Year : 2023

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.

Cite this Research Publication : Vamsi Krishna Munjuluri, V.S., Shankar, M.M., Vikshit, K.S., Gutjahr, G., "Combining Variable Neighborhood Search and Constraint Programming for Solving the Dial-A-Ride Problem," Smart Innovation, Systems and Technologies, vol 312. Springer, Singapore. (2023) DOI: 10.1007/978-981-19-3575-6_23

Admissions Apply Now