Towards Novel Meta-heuristic Algorithms for Dynamic Capacitated Arc Routing Problems

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

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


The Capacitated Arc Routing Problem (CARP) is an abstraction for typical real world applications, like waste collection, winter gritting and mail delivery, to allow the development of efficient optimization algorithms. Most research work focuses on the static CARP, where all information in the problem remains unchanged over time. However, in the real world, dynamic changes may happen when the vehicles are in service, requiring routes to be rescheduled. In this paper, we mainly focus on this kind of Dynamic CARP (DCARP). Some meta-heuristics solve (D)CARP by generating individuals that are sequences of tasks to be served as the individual representation. The split of this sequence into sub-sequences to be served by different vehicles needs to be decided to generate an executable solution, which is necessary for calculating individual’s fitness. However, the existing split schemes for static CARP and DCARP are not capable of getting high quality feasible solutions for DCARP. Therefore, we propose two different split schemes in this paper – an optimal and a greedy split scheme. The optimal split scheme, assisted by A-star algorithm, can obtain the best vehicle routes from an ordered list. The greedy split scheme is not guaranteed to obtain optimal splits, but it is much more efficient. More importantly, it can keep the rank information between different individuals. Our experiments show that the greedy split scheme has good relative accuracy with respect to the optimal split scheme and that the two proposed split schemes are better than the existing DCARP split scheme in terms of the obtained solutions’ quality.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature (PPSN XVI), Sixteenth International Conference, Proceedings
Number of pages14
Publication statusAccepted/In press - 27 May 2020
Event Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN XVI), 2020. - Leiden, Netherlands
Duration: 5 Sept 20209 Sept 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN XVI), 2020.


  • Dynamic CARP
  • Split scheme
  • A-star algorithm
  • Greedy search


Dive into the research topics of 'Towards Novel Meta-heuristic Algorithms for Dynamic Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this