  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 collection vehicles. One possibility consists
of locating collection points throughout the municipality such that residents
bring their waste to their most preferred location. The optimization problem
consists of selecting a subset of candidate locations to place the points such
that each household disposes the waste at the most preferred location. Provided
that the underlying road network is available, we refer to this optimization
problem as the capacitated multi-vehicle covering tour problem on a road
network (Cm-CTP-R). We introduce two mixed-integer linear programming (MILP)
formulations: a road-network-based formulation that exploits the sparsity of
the network and a customer-based formulation typically used in vehicle routing
problems (VRP). To solve large instances, we propose 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 routes. Computational experiments on both small and real-life instances
show that the road-network-based formulation is better suited. Furthermore, the
proposed heuristic provides good solutions with optimality gaps below 0.5% and
3.5% for 75% of the small and real-life instances respectively and is able to
find better solutions than the exact method for many real-life instances.
