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

doi:10.1007/s10732-019-09412-1

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

^*Corresponding author for this work

Engineering

Research output: Contribution to journal › Article › peer-review

23 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 language	English
Pages (from-to)	485-515
Number of pages	31
Journal	JOURNAL OF HEURISTICS
Volume	25
Issue number	3
DOIs	https://doi.org/10.1007/s10732-019-09412-1
Publication status	Published - 1 Jun 2019

Keywords

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

Access to Document

10.1007/s10732-019-09412-1

Cite this

@article{0db3b7ad6736436bb461942b8973b016,

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

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

keywords = "Evolutionary search, Genetic algorithm, Local search, Vehicle routing problem with multiple time windows",

author = "Slim Belhaiza and Rym M{\textquoteright}Hallah and {Ben Brahim}, Ghassen and Gilbert Laporte",

note = "Funding Information: This work was partly funded by the Canadian Natural Sciences and Engineering Research Council under Grant 2015-06189. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments. Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.",

year = "2019",

month = jun,

day = "1",

doi = "10.1007/s10732-019-09412-1",

language = "English",

volume = "25",

pages = "485--515",

journal = "JOURNAL OF HEURISTICS",

issn = "1381-1231",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

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

AU - Belhaiza, Slim

AU - M’Hallah, Rym

AU - Ben Brahim, Ghassen

AU - Laporte, Gilbert

N1 - Funding Information: This work was partly funded by the Canadian Natural Sciences and Engineering Research Council under Grant 2015-06189. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments. Publisher Copyright: © 2019, Springer Science+Business Media, LLC, part of Springer Nature. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2019/6/1

Y1 - 2019/6/1

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

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

KW - Evolutionary search

KW - Genetic algorithm

KW - Local search

KW - Vehicle routing problem with multiple time windows

UR - http://www.scopus.com/inward/record.url?scp=85064500885&partnerID=8YFLogxK

U2 - 10.1007/s10732-019-09412-1

DO - 10.1007/s10732-019-09412-1

M3 - Article

AN - SCOPUS:85064500885

SN - 1381-1231

VL - 25

SP - 485

EP - 515

JO - JOURNAL OF HEURISTICS

JF - JOURNAL OF HEURISTICS

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this