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

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

Authors

Colleges, School and Institutes

External organisations

  • Honda Research Institute Europe GmbH, Germany

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.

Details

Original languageEnglish
Title of host publicationGECCO '21
Subtitle of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
EditorsFrancisco Chicano
Publication statusPublished - 7 Jul 2021
EventGenetic and Evolutionary Computation Conference -
Duration: 10 Jul 202114 Jul 2021

Publication series

NameGenetic and Evolutionary Computation Conference (GECCO)
PublisherACM

Conference

ConferenceGenetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2021
Period10/07/2114/07/21