A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

Yuichi Nagata; Olli Bräysy; Wout Dullaert

doi:10.1016/j.cor.2009.06.022

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

Yuichi Nagata^*, Olli Bräysy, Wout Dullaert

^*Corresponding author for this work

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.

Original language	English
Pages (from-to)	724-737
Number of pages	14
Journal	Computers and Operations Research
Volume	37
Issue number	4
DOIs	https://doi.org/10.1016/j.cor.2009.06.022
Publication status	Published - Apr 2010

Keywords

Memetic algorithm
Penalty function
Time windows
Vehicle routing

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.cor.2009.06.022

Persistent URL (handle)

Persistent link

Cite this

@article{809f1f67c3b94f1baa8bd2ae73a278ef,

title = "A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows",

abstract = "In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.",

keywords = "Memetic algorithm, Penalty function, Time windows, Vehicle routing",

author = "Yuichi Nagata and Olli Br{\"a}ysy and Wout Dullaert",

year = "2010",

month = apr,

doi = "10.1016/j.cor.2009.06.022",

language = "English",

volume = "37",

pages = "724--737",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Limited",

number = "4",

}

TY - JOUR

T1 - A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

AU - Nagata, Yuichi

AU - Bräysy, Olli

AU - Dullaert, Wout

PY - 2010/4

Y1 - 2010/4

N2 - In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.

AB - In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.

KW - Memetic algorithm

KW - Penalty function

KW - Time windows

KW - Vehicle routing

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

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

U2 - 10.1016/j.cor.2009.06.022

DO - 10.1016/j.cor.2009.06.022

M3 - Article

AN - SCOPUS:70350565396

SN - 0305-0548

VL - 37

SP - 724

EP - 737

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 4

ER -

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

Abstract

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this