A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems

Hao TONG, Leandro L. MINKU, Stefan MENZEL, Bernhard SENDHOFF, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

5 Citations (Scopus)

Abstract

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from many real-world applications, such as waste collection, road gritting, and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this article, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from the existing static CARP optimization algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from the past optimization experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms. © 1997-2012 IEEE.
Original languageEnglish
Pages (from-to)1486-1500
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume26
Issue number6
Early online date31 Jan 2022
DOIs
Publication statusPublished - Dec 2022
Externally publishedYes

Keywords

  • Dynamic capacitated arc routing problem (DCARP)
  • experience-based optimization
  • metaheuristics
  • restart strategy (RS)
  • transfer optimization

Fingerprint

Dive into the research topics of 'A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this