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

• DOI: 10.1007/s10732-019-09412-1
• Publication Date: 2019-04-09T01:02:33Z
• Authors: Slim Belhaiza; Rym M’Hallah; Ghassen Ben Brahim; Gilbert Laporte
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

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