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.
Online Re-routing for Vehicle Breakdown in Residential Waste Collection
2020-11-01
883394 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Transportation Research Record | 2021
|Mechanized Residential Solid Waste Collection
NTIS | 1974
|