Department of Economics and Business Economics

A fast heuristic for large-scale capacitated arc routing problems

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

A fast heuristic for large-scale capacitated arc routing problems. / Wøhlk, Sanne; Laporte, Gilbert.

In: Journal of the Operational Research Society, Vol. 69, No. 12, 2018, p. 1877-1887.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

Wøhlk, S & Laporte, G 2018, 'A fast heuristic for large-scale capacitated arc routing problems', Journal of the Operational Research Society, vol. 69, no. 12, pp. 1877-1887. https://doi.org/10.1080/01605682.2017.1415648

APA

Wøhlk, S., & Laporte, G. (2018). A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society, 69(12), 1877-1887. https://doi.org/10.1080/01605682.2017.1415648

CBE

Wøhlk S, Laporte G. 2018. A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society. 69(12):1877-1887. https://doi.org/10.1080/01605682.2017.1415648

MLA

Wøhlk, Sanne and Gilbert Laporte. "A fast heuristic for large-scale capacitated arc routing problems". Journal of the Operational Research Society. 2018, 69(12). 1877-1887. https://doi.org/10.1080/01605682.2017.1415648

Vancouver

Wøhlk S, Laporte G. A fast heuristic for large-scale capacitated arc routing problems. Journal of the Operational Research Society. 2018;69(12):1877-1887. https://doi.org/10.1080/01605682.2017.1415648

Author

Wøhlk, Sanne ; Laporte, Gilbert. / A fast heuristic for large-scale capacitated arc routing problems. In: Journal of the Operational Research Society. 2018 ; Vol. 69, No. 12. pp. 1877-1887.

Bibtex

@article{f0110b7259714640805a36d7ace0a335,
title = "A fast heuristic for large-scale capacitated arc routing problems",
abstract = "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.",
keywords = "ALGORITHMS, Arc routing, COLLECTION, DESIGN, Denmark, SEARCH, districts, heuristics, waste collection",
author = "Sanne W{\o}hlk and Gilbert Laporte",
year = "2018",
doi = "10.1080/01605682.2017.1415648",
language = "English",
volume = "69",
pages = "1877--1887",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan Ltd.",
number = "12",

}

RIS

TY - JOUR

T1 - A fast heuristic for large-scale capacitated arc routing problems

AU - Wøhlk, Sanne

AU - Laporte, Gilbert

PY - 2018

Y1 - 2018

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 - ALGORITHMS

KW - Arc routing

KW - COLLECTION

KW - DESIGN

KW - Denmark

KW - SEARCH

KW - districts

KW - heuristics

KW - waste collection

U2 - 10.1080/01605682.2017.1415648

DO - 10.1080/01605682.2017.1415648

M3 - Journal article

AN - SCOPUS:85049054018

VL - 69

SP - 1877

EP - 1887

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 12

ER -