Three multi-start data-driven evolutionary heuristics for the vehicle routing problem with multiple time windows

This paper considers the vehicle routing problem with multiple time windows. It introduces a general framework for three evolutionary heuristics that use three global multi-start strategies: ruin and recreate, genetic cross-over of best parents, and random restart. The proposed heuristics make use o...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2019-06, Vol.25 (3), p.485-515
Main Authors: Belhaiza, Slim, M’Hallah, Rym, Ben Brahim, Ghassen, Laporte, Gilbert
Format: Article
Language:English
Subjects:
Artificial Intelligence
Biological evolution
Calculus of Variations and Optimal Control
Optimization
Crossovers
Heuristic
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Parents
Route planning
Routing
Vehicle routing
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:This paper considers the vehicle routing problem with multiple time windows. It introduces a general framework for three evolutionary heuristics that use three global multi-start strategies: ruin and recreate, genetic cross-over of best parents, and random restart. The proposed heuristics make use of information extracted from routes to guide customized data-driven local search operators. The paper reports comparative computational results for the three heuristics on benchmark instances and identifies the best one. It also shows more than 16% of average cost improvement over current practice on a set of real-life instances, with some solution costs improved by more than 30%.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-019-09412-1