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

Yuichi Nagata, Olli Bräysy, Wout Dullaert

Research output: Contribution to JournalArticleAcademicpeer-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 languageEnglish
Pages (from-to)724-737
Number of pages14
JournalComputers and Operations Research
Volume37
Issue number4
DOIs
Publication statusPublished - Apr 2010

Fingerprint

Vehicle Routing Problem with Time Windows
Vehicle routing
Memetic Algorithm
Penalty
Capacity Constraints
Time Windows
Penalty Function
Operator
Crossover
Mathematical operators
Adjustment
Eliminate
Heuristics
Benchmark
Experimental Results
Demonstrate
Time windows
Memetic algorithm
Vehicle routing problem
Violations

Keywords

  • Memetic algorithm
  • Penalty function
  • Time windows
  • Vehicle routing

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 = "4",
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",

}

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. / Nagata, Yuichi; Bräysy, Olli; Dullaert, Wout.

In: Computers and Operations Research, Vol. 37, No. 4, 04.2010, p. 724-737.

Research output: Contribution to JournalArticleAcademicpeer-review

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

VL - 37

SP - 724

EP - 737

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 4

ER -