Online Re-routing for Vehicle Breakdown in Residential Waste Collection

Muhilan Ramamoorthy, Violet R. Syrotiuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


We model residential waste collection as a Capacitated Arc Routing Problem (CARP). Because the collection vehicles are expensive, many public works departments cannot afford extra vehicles on hand if one breaks down. A conventional solution is for the unserved streets in the route of the broken down vehicle to be served by one of the others in the fleet as an overtime job. Instead, we propose to distribute the unserved streets among all remaining operational vehicles when a breakdown occurs. We propose PROBE, an algorithm to dynamically re-route collection vehicles in the event of a breakdown, with the objective to minimize the makespan. We evaluate PROBE on the classical CARP benchmark instances GDB, VAL, EGL, and EGL-Large. Compared to the conventional solution, PROBE obtains reduced makespan, range, and discrepancies which indicate improved balance of the solution. The run time of PROBE is linear in the number of required edges suggesting good scalability.

Original languageEnglish (US)
Title of host publication2020 IEEE 92nd Vehicular Technology Conference, VTC 2020-Fall - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728194844
StatePublished - Nov 2020
Event92nd IEEE Vehicular Technology Conference, VTC 2020-Fall - Virtual, Victoria, Canada
Duration: Nov 18 2020 → …

Publication series

NameIEEE Vehicular Technology Conference
ISSN (Print)1550-2252


Conference92nd IEEE Vehicular Technology Conference, VTC 2020-Fall
CityVirtual, Victoria
Period11/18/20 → …


  • Capacitated arc routing
  • breakdown management
  • heuristics
  • vehicle rerouting

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Online Re-routing for Vehicle Breakdown in Residential Waste Collection'. Together they form a unique fingerprint.

Cite this