Towards novel meta-heuristic algorithms for dynamic capacitated arc routing problems

Hao TONG, Leandro L. MINKU, Stefan MENZEL, Bernhard SENDHOFF, Xin YAO*

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

5 Citations (Scopus)

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. © Springer Nature Switzerland AG 2020.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI : 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part II
EditorsThomas BÄCK, Mike PREUSS, André DEUTZ, Hao WANG, Carola DOERR, Michael EMMERICH, Heike TRAUTMANN
PublisherSpringer Science and Business Media Deutschland GmbH
Pages428-440
Number of pages13
ISBN (Electronic)9783030581152
ISBN (Print)9783030581145
DOIs
Publication statusPublished - 2020
Externally publishedYes
EventInternational Conference on Parallel Problem Solving from Nature 2020 - Leiden, Netherlands
Duration: 5 Sept 20209 Sept 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12270
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
PublisherSpringer
ISSN (Print)2512-2010
ISSN (Electronic)2512-2029

Conference

ConferenceInternational Conference on Parallel Problem Solving from Nature 2020
Abbreviated titlePPSN 2020
Country/TerritoryNetherlands
CityLeiden
Period5/09/209/09/20

Bibliographical note

Hao Tong gratefully acknowledges the financial support from Honda Research Institute Europe (HRI-EU).

Keywords

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

Fingerprint

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