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

  • Sanne Wøhlk
  • Gilbert Laporte, GERAD and Canada Research Chair in Distribution Management

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.

Original languageEnglish
JournalComputers and Operations Research
Volume111
Pages (from-to)271-284
Number of pages14
ISSN0305-0548
DOIs
Publication statusPublished - 2019

    Research areas

  • Arc routing, Districting, Garbage collection, Heuristics

See relations at Aarhus University Citationformats

ID: 159657771