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

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

Keywords

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

Fingerprint Dive into the research topics of 'A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows'. Together they form a unique fingerprint.

Cite this