A novel generalised meta-heuristic framework for dynamic capacitated arc routing problems

Hao Tong, Leandro Minku, Stefan Menzel, Bernhard Sendhoff, Xin Yao

Research output: Contribution to journalArticlepeer-review

7 Downloads (Pure)

Abstract

The capacitated arc routing problem (CARP) is a challenging combinatorial optimisation 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 paper, 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 existing static CARP optimisation 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 past optimisation 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 optimisation algorithms.
Original languageEnglish
JournalIEEE Transactions on Evolutionary Computation
DOIs
Publication statusAccepted/In press - 12 Jan 2022

Bibliographical note

Final Version of Record not yet available as of 10/05/2022.

Keywords

  • Dynamic capacitated arc routing problem
  • Experience-based optimisation.
  • Heuristic algorithms
  • Mathematical models
  • Meta-heuristics
  • Optimization
  • Restart strategy
  • Roads
  • Routing
  • Task analysis
  • Transfer optimisation
  • Vehicle dynamics

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A novel generalised meta-heuristic framework for dynamic capacitated arc routing problems'. Together they form a unique fingerprint.

Cite this