TY - JOUR
T1 - A fast heuristic for large-scale capacitated arc routing problems
AU - Wøhlk, Sanne
AU - Laporte, Gilbert
N1 - Funding Information:
This project was funded by the Danish Council for Independent Research?Social Sciences. Project ?Transportation issues related to waste management? [grant number 4182?00021] and by the Natural Sciences and Engineering Research Council of Canada [grant number 2015?06189]. Thanks are due to the referees for their valuable comments.
Funding Information:
This project was funded by the Danish Council for Independent Research – Social Sciences. Project “Transportation issues related to waste management” [grant number 4182– 00021] and by the Natural Sciences and Engineering Research Council of Canada [grant number 2015–06189].
Publisher Copyright:
© 2018, © Operational Research Society 2018.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2018/12/2
Y1 - 2018/12/2
N2 - The purpose of this paper is to develop a fast heuristic called FastCARP for the solution of large-scale capacitated arc routing problems, with or without duration constraints. This study is motivated by a waste collection problem in Denmark. After a preprocessing phase, FastCARP creates a giant tour, partitions the graph into districts, and construct routes within each district. It then iteratively merges and splits adjacent districts and reoptimises the routes. The heuristic was tested on 264 benchmark instances containing up to 11,640 nodes, 12,675 edges, 8581 required edges, and 323 vehicles. FastCARP was compared with an alternative heuristic called Base and with several Path-Scanning algorithms. On small graphs, it was better but slower than Base. On larger graphs, it was much faster and only slightly worse than Base in terms of solution quality. It also outperforms the Path-Scanning algorithms.
AB - The purpose of this paper is to develop a fast heuristic called FastCARP for the solution of large-scale capacitated arc routing problems, with or without duration constraints. This study is motivated by a waste collection problem in Denmark. After a preprocessing phase, FastCARP creates a giant tour, partitions the graph into districts, and construct routes within each district. It then iteratively merges and splits adjacent districts and reoptimises the routes. The heuristic was tested on 264 benchmark instances containing up to 11,640 nodes, 12,675 edges, 8581 required edges, and 323 vehicles. FastCARP was compared with an alternative heuristic called Base and with several Path-Scanning algorithms. On small graphs, it was better but slower than Base. On larger graphs, it was much faster and only slightly worse than Base in terms of solution quality. It also outperforms the Path-Scanning algorithms.
KW - Arc routing
KW - Denmark
KW - districts
KW - heuristics
KW - waste collection
UR - http://www.scopus.com/inward/record.url?scp=85049054018&partnerID=8YFLogxK
U2 - 10.1080/01605682.2017.1415648
DO - 10.1080/01605682.2017.1415648
M3 - Article
AN - SCOPUS:85049054018
SN - 0160-5682
VL - 69
SP - 1877
EP - 1887
JO - Journal of the Operational Research Society
JF - Journal of the Operational Research Society
IS - 12
ER -