A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem
Author:
Open Access
- 16 February 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (2) , 39
Abstract
The transportation of elderly and impaired people is commonly solved as a Dial-A-Ride Problem (DARP). The DARP aims to design pick-up and delivery vehicle routing schedules. Its main objective is to accommodate as many users as possible with a minimum operation cost. It adds realistic precedence and transit time constraints on the pairing of vehicles and customers. This paper tackles the DARP with time windows (DARPTW) from a new and innovative angle as it combines hybridization techniques with an adaptive large neighborhood search heuristic algorithm. The main objective is to improve the overall real-life performance of vehicle routing operations. Real-life data are refined and fed to a hybrid adaptive large neighborhood search (Hybrid-ALNS) algorithm which provides a near-optimal routing solution. The computational results on real-life instances, in the Canadian city of Vancouver and its region, and DARPTW benchmark instances show the potential improvements achieved by the proposed heuristic and its adaptability.Keywords
This publication has 23 references indexed in Scilit:
- A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windowsComputers & Operations Research, 2014
- Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problemEuropean Journal of Operational Research, 2014
- Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depotsTransportation Research Part B: Methodological, 2014
- The Dial-A-Ride Problem with TransfersComputers & Operations Research, 2014
- Hybrid column generation and large neighborhood search for the dial-a-ride problemComputers & Operations Research, 2013
- Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transportApplied Soft Computing, 2012
- Variable neighborhood search for the dial-a-ride problemComputers & Operations Research, 2010
- The dial-a-ride problem: models and algorithmsAnnals of Operations Research, 2007
- An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time WindowsTransportation Science, 2006
- A tabu search heuristic for the static multi-vehicle dial-a-ride problemTransportation Research Part B: Methodological, 2003