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

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

Authors

Colleges, School and Institutes

External organisations

  • Honda Research Institute Europe GmbH, Germany

Abstract

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.

Details

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature (PPSN XVI), Sixteenth International Conference, Proceedings
Publication statusAccepted/In press - 27 May 2020
Event Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN XVI), 2020. - Leiden, Netherlands
Duration: 5 Sep 20209 Sep 2020

Publication series

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

Conference

Conference Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN XVI), 2020.
CountryNetherlands
CityLeiden
Period5/09/209/09/20

Keywords

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