Department of Economics and Business Economics

A districting-based heuristic for the coordinated capacitated arc routing problem

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

Standard

A districting-based heuristic for the coordinated capacitated arc routing problem. / Wøhlk, Sanne; Laporte, Gilbert.

In: Computers and Operations Research, Vol. 111, 2019, p. 271-284.

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

Harvard

APA

CBE

MLA

Vancouver

Author

Wøhlk, Sanne ; Laporte, Gilbert. / A districting-based heuristic for the coordinated capacitated arc routing problem. In: Computers and Operations Research. 2019 ; Vol. 111. pp. 271-284.

Bibtex

@article{0181569b553b43bf96a1c222514f15b4,
title = "A districting-based heuristic for the coordinated capacitated arc routing problem",
abstract = "The purpose of this paper is to solve a multi-period garbage collection problem involving several garbage types called fractions, such as general and organic waste, paper and carboard, glass and metal, and plastic. The study is motivated by a real-life problem arising in Denmark. Because of the nature of the fractions, not all of them have the same collection frequency. Currently the collection days for the various fractions are uncoordinated. An interesting question is to determine the added cost in terms of traveled distance and vehicle fleet size of coordinating these collections in order to reduce the inconvenience borne by the citizens. To this end we develop a multi-phase heuristic: (1) small collection districts, each corresponding to a day of the week, are first created; (2) the districts are assigned to specific weekdays based on a closeness criterion; (3) they are balanced in order to make a more efficient use of the vehicles; (4) collection routes are then created for each district and each waste fraction by means of the FastCARP heuristic. Extensive tests over a variety of scenarios indicate that coordinating the collections yields a routing cost increase of 12.4%, while the number of vehicles increases in less than half of the instances.",
keywords = "Arc routing, Districting, Garbage collection, Heuristics, SDGCircularEconomy, SDGCircularEconomy",
author = "Sanne W{\o}hlk and Gilbert Laporte",
year = "2019",
doi = "10.1016/j.cor.2019.07.006",
language = "English",
volume = "111",
pages = "271--284",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Pergamon Press",

}

RIS

TY - JOUR

T1 - A districting-based heuristic for the coordinated capacitated arc routing problem

AU - Wøhlk, Sanne

AU - Laporte, Gilbert

PY - 2019

Y1 - 2019

N2 - The purpose of this paper is to solve a multi-period garbage collection problem involving several garbage types called fractions, such as general and organic waste, paper and carboard, glass and metal, and plastic. The study is motivated by a real-life problem arising in Denmark. Because of the nature of the fractions, not all of them have the same collection frequency. Currently the collection days for the various fractions are uncoordinated. An interesting question is to determine the added cost in terms of traveled distance and vehicle fleet size of coordinating these collections in order to reduce the inconvenience borne by the citizens. To this end we develop a multi-phase heuristic: (1) small collection districts, each corresponding to a day of the week, are first created; (2) the districts are assigned to specific weekdays based on a closeness criterion; (3) they are balanced in order to make a more efficient use of the vehicles; (4) collection routes are then created for each district and each waste fraction by means of the FastCARP heuristic. Extensive tests over a variety of scenarios indicate that coordinating the collections yields a routing cost increase of 12.4%, while the number of vehicles increases in less than half of the instances.

AB - The purpose of this paper is to solve a multi-period garbage collection problem involving several garbage types called fractions, such as general and organic waste, paper and carboard, glass and metal, and plastic. The study is motivated by a real-life problem arising in Denmark. Because of the nature of the fractions, not all of them have the same collection frequency. Currently the collection days for the various fractions are uncoordinated. An interesting question is to determine the added cost in terms of traveled distance and vehicle fleet size of coordinating these collections in order to reduce the inconvenience borne by the citizens. To this end we develop a multi-phase heuristic: (1) small collection districts, each corresponding to a day of the week, are first created; (2) the districts are assigned to specific weekdays based on a closeness criterion; (3) they are balanced in order to make a more efficient use of the vehicles; (4) collection routes are then created for each district and each waste fraction by means of the FastCARP heuristic. Extensive tests over a variety of scenarios indicate that coordinating the collections yields a routing cost increase of 12.4%, while the number of vehicles increases in less than half of the instances.

KW - Arc routing

KW - Districting

KW - Garbage collection

KW - Heuristics

KW - SDGCircularEconomy

KW - SDGCircularEconomy

UR - http://www.scopus.com/inward/record.url?scp=85068837684&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2019.07.006

DO - 10.1016/j.cor.2019.07.006

M3 - Journal article

AN - SCOPUS:85068837684

VL - 111

SP - 271

EP - 284

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -