Constructive Heuristics for Commercial Waste Collection with Time-Dependent Travel

Commercial waste collection is a vehicle routing problem with an unusually high number of stops per round — each bin at each customer is a stop, so a single urban round can run to several thousand. It also breaks assumptions that textbook formulations lean on. Retail collections often happen in pedestrian precincts where access is restricted by time of day, and many rounds run through congested high streets where travel speed depends on the time of day and where manoeuvres such as turning right onto a main road carry their own time penalty. Accurate time estimation therefore has to model time-of-day-dependent travel speeds and turning penalties, not just static point-to-point distances.

The paper investigates a cluster-first, route-second approach to construction for this problem. Rather than inserting stops one at a time, it partitions the road-network graph into geographically coherent clusters and then routes those clusters as units — visits within a cluster are ordered against the cluster’s entry and exit points. Problem instances were generated to exercise the method at realistic scale, and the reported results are promising on the instances where geographic clustering is the dominant structure.

This work was carried out with Lancaster University’s STOR-i Centre. It is the basis of the GP (graph-partition-first) constructor in Optrak’s optimisation engine: a script-level addition to the heuristic catalogue registered against the existing strategy language rather than built as an engine change. On the generated instances GP outperformed Optrak’s incumbent time-window constructor on roughly half, with the largest gains on the instances the incumbent handled worst — a specialist family for very large, geographically clustered rounds rather than a universal replacement.

Read the abstract on SpringerLink: doi.org/10.1007/978-3-031-78857-4_22

Presented at the 23rd UK Workshop on Computational Intelligence (UKCI 2024), Belfast, 2–4 September 2024, and published in Advances in Computational Intelligence Systems, Advances in Intelligent Systems and Computing vol. 1462, pp. 291–302 (Springer, 2025).