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 language | English |
---|---|
Title of host publication | GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion |
Publisher | Association for Computing Machinery, Inc |
Pages | 139-140 |
Number of pages | 2 |
ISBN (Electronic) | 9781450383516 |
ISBN (Print) | 9781450383516 |
DOIs | |
Publication status | Published - 7 Jul 2021 |
Externally published | Yes |
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