Variable neighborhood search for the dial-a-ride problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2010-06, Vol.37 (6), p.1129-1138
Main Authors: Parragh, Sophie N., Doerner, Karl F., Hartl, Richard F.
Format: Article
Language:English
Subjects:
Applied sciences
Benchmarking
Chains
Cost reduction
Dial-a-ride problem
Ejection
Exact sciences and technology
Heuristic
Logistics
Metaheuristic
Operational research and scientific management
Operational research. Management science
Operations research
Passengers
Routing
Searching
Studies
Transportation
Transportation problem (Operations research)
Variable neighborhood search
Vehicles
Windows (intervals)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2009.10.003