Constructive Heuristics for Commercial Waste Collection with Time-Dependent Travel

Commercial waste collection can be modelled as a vehicle routing problem with a high number of stops per route, corresponding to bins from individual customers. Retail collections may occur in pedestrian precincts, where access is restricted by time of day. Many commercial collections, particularly from retail areas, occur in highly congested zones, such as high streets. Therefore, modelling with time-of-day dependent travel speeds and turning time penalties (e.g., turning right onto a main road) is essential for accurate time estimation. This study aims to investigate heuristics to solve this problem, specifically using a cluster-first, route-second approach for construction heuristics based on graph partitioning of the road network. Problem instances have been generated, and promising results have been achieved.