Variable neighborhood search for the dial-a-ride problem

Variable neighborhood search for the dial-a-ride problem

0.00 Avg rating0 Votes
Article ID: iaor2010992
Volume: 37
Issue: 6
Start Page Number: 1129
End Page Number: 1138
Publication Date: Jun 2010
Journal: Computers and Operations Research
Authors: , ,
Keywords: vehicle routing & scheduling, heuristics: local search
Abstract:

In dial-a-ride problems passengers have to be transported between pre-specified pickup and delivery locations under user inconvenience considerations. The problem variant considered in this paper aims at minimizing total routing costs while respecting maximum route duration limits, time windows, and maximum user ride time limits. We propose a competitive variable neighborhood search-based heuristic, using three classes of neighborhoods. The first neighborhood class uses simple swap operations tailored to the dial-a-ride problem; the second neighborhood class is based on the ejection chain idea; and the third neighborhood class exploits the existence of arcs where the vehicle load is zero, giving rise to natural sequences of requests. We report new best results for 16 out of 20 benchmark instances.

Reviews

Required fields are marked *. Your email address will not be published.