Evolutionary algorithms for the Vehicle Routing Problem with Time Windows

Olli Bräysy; Wout Dullaert; Michel Gendreau

doi:10.1007/s10732-005-5431-6

Evolutionary algorithms for the Vehicle Routing Problem with Time Windows

Olli Bräysy^*, Wout Dullaert, Michel Gendreau

^*Corresponding author for this work

Amsterdam Business Research Institute

Research output: Contribution to Journal › Review article › Academic › peer-review

Abstract

This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.

Original language	English
Pages (from-to)	587-611
Number of pages	25
Journal	Journal of Heuristics
Volume	10
Issue number	6
DOIs	https://doi.org/10.1007/s10732-005-5431-6
Publication status	Published - Dec 2004

Keywords

Evolutionary algorithms
Genetic algorithms
Transportation
Vehicle routing

Access to Document

10.1007/s10732-005-5431-6

Persistent URL (handle)

Copy link address

Cite this

@article{08f687c93b994540a1c9e74ef1bcf983,

title = "Evolutionary algorithms for the Vehicle Routing Problem with Time Windows",

abstract = "This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.",

keywords = "Evolutionary algorithms, Genetic algorithms, Transportation, Vehicle routing",

author = "Olli Br{\"a}ysy and Wout Dullaert and Michel Gendreau",

year = "2004",

month = dec,

doi = "10.1007/s10732-005-5431-6",

language = "English",

volume = "10",

pages = "587--611",

journal = "Journal of Heuristics",

issn = "1381-1231",

publisher = "Springer Verlag",

number = "6",

}

TY - JOUR

T1 - Evolutionary algorithms for the Vehicle Routing Problem with Time Windows

AU - Bräysy, Olli

AU - Dullaert, Wout

AU - Gendreau, Michel

PY - 2004/12

Y1 - 2004/12

N2 - This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.

AB - This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.

KW - Evolutionary algorithms

KW - Genetic algorithms

KW - Transportation

KW - Vehicle routing

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

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

U2 - 10.1007/s10732-005-5431-6

DO - 10.1007/s10732-005-5431-6

M3 - Review article

AN - SCOPUS:14844363491

SN - 1381-1231

VL - 10

SP - 587

EP - 611

JO - Journal of Heuristics

JF - Journal of Heuristics

IS - 6

ER -

Evolutionary algorithms for the Vehicle Routing Problem with Time Windows

Abstract

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this