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

Slim Belhaiza, Rym M’Hallah, Ghassen Ben Brahim, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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

Original languageEnglish
Pages (from-to)485-515
Number of pages31
JournalJournal of Heuristics
Volume25
Issue number3
DOIs
Publication statusPublished - 1 Jun 2019

Keywords

  • Evolutionary search
  • Genetic algorithm
  • Local search
  • Vehicle routing problem with multiple time windows

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Three multi-start data-driven evolutionary heuristics for the vehicle routing problem with multiple time windows'. Together they form a unique fingerprint.

Cite this