A fast heuristic for large-scale capacitated arc routing problems

Sanne Wøhlk; Gilbert Laporte

doi:10.1080/01605682.2017.1415648

A fast heuristic for large-scale capacitated arc routing problems

Sanne Wøhlk, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

19 Citations (SciVal)

101 Downloads (Pure)

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.

Original language	English
Pages (from-to)	1877-1887
Number of pages	11
Journal	Journal of the Operational Research Society
Volume	69
Issue number	12
Early online date	24 Jan 2018
DOIs	https://doi.org/10.1080/01605682.2017.1415648
Publication status	Published - 2 Dec 2018

Bibliographical note

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.

Funding

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. 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].

Keywords

Arc routing
Denmark
districts
heuristics
waste collection

ASJC Scopus subject areas

Management Information Systems
Strategy and Management
Management Science and Operations Research
Marketing

Access to Document

10.1080/01605682.2017.1415648

FastCARP revise(1)
This is an Accepted Manuscript of an article published by Taylor & Francis in Journal of the Operational Research Society on [date of publication], available online: https://www.tandfonline.com/doi/full/10.1080/01605682.2017.1415648
Accepted author manuscript, 1.9 MB

Cite this

@article{125631a18b394b3ea034f82debb734e0,

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 = "Arc routing, Denmark, districts, heuristics, waste collection",

author = "Sanne W{\o}hlk and Gilbert Laporte",

note = "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: {\textcopyright} 2018, {\textcopyright} Operational Research Society 2018. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2018",

month = dec,

day = "2",

doi = "10.1080/01605682.2017.1415648",

language = "English",

volume = "69",

pages = "1877--1887",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

publisher = "Taylor and Francis",

number = "12",

}

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 -

A fast heuristic for large-scale capacitated arc routing problems

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this