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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 '21
Subtitle of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
EditorsFrancisco Chicano
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Number of pages2
ISBN (Print)9781450383516
Publication statusPublished - 7 Jul 2021
EventGenetic and Evolutionary Computation Conference -
Duration: 10 Jul 202114 Jul 2021

Publication series

NameGenetic and Evolutionary Computation Conference (GECCO)


ConferenceGenetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2021


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