A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection

In most Swiss municipalities, a curbside system consisting of heavy trucks stopping at almost each household is used for non-recoverable waste collection. Due to the many stops of the trucks, this strategy causes high fuel consumption, emissions and noise. These effects can be alleviated by reducing the number of stops performed by the collection vehicles. One possibility consists of selecting a subset of candidate locations that are scattered throughout the municipality to place collection points which are used by residents to bring their waste. Provided that the underlying road network is available and that the collection vehicle has a known capacity, we refer to this problem as the capacitated multi-vehicle covering tour problem on a road network (Cm-CTP-R). We propose a road-network-based mixed-integer linear programming (MILP) formulation that exploits the sparsity of the network. We compare it against the MILP formulation that results from assuming a customer-based graph, which is typically used in vehicle routing problems (VRP). To solve large instances, we develop a two-phased heuristic approach that addresses the two subproblems the Cm-CTP-R is built on: a set covering problem to select the locations and a split-delivery VRP to determine the tours. Computational experiments on instances derived from real-life data show that the road-network-based formulation is better suited. Furthermore, the proposed heuristic provides good solutions with optimality gaps below 1.7% and finds better solutions for most of the instances that the exact method is not able to solve within a given time limit.

Mots clés

combinatorial optimization; waste collection; multi-vehicle covering tour problem; mixed-integer linear programming; road network