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.