A fast heuristic for large-scale capacitated arc routing problems. Issue 12 (2nd December 2018)

• Record Type: Journal Article
• Authors: Wøhlk, Sanne; Laporte, Gilbert
• Is Part Of: Journal of the Operational Research Society. Volume 69:Issue 12(2018)
• Page Start: 1877
• Page End: 1887
• Publication Date: 2018-12-02
• Subjects: Arc routing -- districts -- heuristics -- waste collection -- Denmark; Operations research -- Periodicals; 658.4034
• DOI: 10.1080/01605682.2017.1415648
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: The purpose of this paper is to develop a fast heuristic called Fast CARP 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, Fast CARP 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. Fast CARP 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.