A hybrid local search framework for the dynamic capacitated arc routing problem

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

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

8 Citations (Scopus)

Abstract

The static capacitated arc routing problem (CARP) is a challenging combinatorial problem, where vehicles need to be scheduled efficiently for serving a set of tasks with minimal travelling costs. Dynamic CARP (DCARP) considers the occurence of dynamic events during the service process, e.g. traffic congestion, which reduce the quality of the currently applied schedule. Existing research mainly focused on scenarios with large changes but neglected the time limitations of the rescheduling process. In this paper, we investigate DCARP scenarios with small dynamic changes in which events only affect the properties of a few edges. We propose an efficient hybrid local search framework (HyLS) to reschedule the service plan in a short time for a DCARP instance. HyLS maintains an archive that enables it to cover more search areas than single local search algorithms, while its local search mechanisms enable it to find better solutions than meta-heuristic re-optimisation from scratch when restricted to a tight time budget. Our experiments demonstrate HyLS' effectiveness compared to existing local search strategies and meta-heuristic re-optimisation from scratch.

Original languageEnglish
Title of host publicationGECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Pages139-140
Number of pages2
ISBN (Electronic)9781450383516
ISBN (Print)9781450383516
DOIs
Publication statusPublished - 7 Jul 2021
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2021 Owner/Author.

Funding

Hao Tong gratefully acknowledges the financial support from Honda Research Institute Europe.

Keywords

  • dynamic capacitated arc routing problem
  • hybrid local search

Fingerprint

Dive into the research topics of 'A hybrid local search framework for the dynamic capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this