论文标题
在道路网络上的电容性多车涵盖旅游问题及其在废物收集中的应用
A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection
论文作者
论文摘要
在大多数瑞士城市中，一个由重型卡车组成的路边系统几乎将每个家庭停下来，用于不可恢复的废物收集。由于卡车的许多停靠点，该策略会导致高油耗，排放和噪音。可以通过减少收集车辆执行的停靠次数来缓解这些效果。一种可能性是在整个市政当局找到收集点，以便居民将浪费带到最喜欢的位置。优化问题包括选择一部分候选地点以放置这些点，以使每个家庭都将废物放置在最优选的位置。只要有基础的道路网络可用，我们将此优化问题称为道路网络（CM-CTP-R）上的电容多车程覆盖旅游问题。我们介绍了两个混合企业线性编程（MILP）配方：一种基于路线网络的配方，可利用网络的稀疏性和通常用于车辆路由问题（VRP）的基于客户的配方。为了解决大型实例，我们提出了一种两步的启发式方法，该方法解决了CM-CTP-R的两个子问题的构建：选择位置的集合问题，以选择位置和一个拆卸VRP来确定路线。小型和现实生活实例上的计算实验表明，基于道路网络的配方更适合。此外，拟议的启发式提供了良好的解决方案，分别为75％的小型和现实生活实例的最佳差距低于0.5％和3.5％，并且能够找到比许多现实生活实例的确切方法更好的解决方案。
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.
