论文标题
动态车辆路线问题：蒙特卡洛方法
Dynamic Vehicle Routing Problem: A Monte Carlo approach
论文作者
论文摘要
在这项工作中，我们解决了动态车辆路由问题（DVRP）。 DVRP是对车辆路由问题的修改，在该问题中，在工作日开始时，客户的请求（城市）数字和位置可能不知道，所有请求都必须由容量有限的车队在一个工作日期间提供。在这项工作中，我们提出了一种蒙特卡洛法（McTree），该方法直接接近DVRP中到达请求的动态性质。该方法还与我们以前的两相多旋转粒子群优化（2MPSO）算法杂交（McTree+PSO）。 我们的方法基于两个假设。首先，我们知道请求可能出现的区域的边界矩形。其次，初始请求的大小和外观频率是未知客户的请求的代表。为了解决DVRP，我们将工作日划分为几个时间切片，在其中解决了一个静态问题。在我们的蒙特卡洛方法中，我们随机生成未知客户的请求，并在边界矩形上具有均匀的空间分布，并从已知的请求的尺寸中均匀地采样了“尺寸”。解决方案提案是通过应用集群算法和路线构建算法构建的。 McTree方法已在Kilby等人提出的一组基准中进行了测试。并通过应用我们以前的2MPSO算法和其他文献结果进行比较。拟议的McTree方法实现了比简单的启发式算法更好的质量权衡时光。此外，Hybrid McTree+PSO方法可以实现比2MPSO的优化时间限制更好的时间，这使混合动力车成为处理现实世界规模的商品交付问题的好候选者。
In this work we solve the Dynamic Vehicle Routing Problem (DVRP). DVRP is a modification of the Vehicle Routing Problem, in which the clients' requests (cities) number and location might not be known at the beginning of the working day Additionally, all requests must be served during one working day by a fleet of vehicles with limited capacity. In this work we propose a Monte Carlo method (MCTree), which directly approaches the dynamic nature of arriving requests in the DVRP. The method is also hybridized (MCTree+PSO) with our previous Two-Phase Multi-swarm Particle Swarm Optimization (2MPSO) algorithm. Our method is based on two assumptions. First, that we know a bounding rectangle of the area in which the requests might appear. Second, that the initial requests' sizes and frequency of appearance are representative for the yet unknown clients' requests. In order to solve the DVRP we divide the working day into several time slices in which we solve a static problem. In our Monte Carlo approach we randomly generate the unknown clients' requests with uniform spatial distribution over the bounding rectangle and requests' sizes uniformly sampled from the already known requests' sizes. The solution proposal is constructed with the application of a clustering algorithm and a route construction algorithm. The MCTree method is tested on a well established set of benchmarks proposed by Kilby et al. and is compared with the results achieved by applying our previous 2MPSO algorithm and other literature results. The proposed MCTree approach achieves a better time to quality trade-off then plain heuristic algorithms. Moreover, a hybrid MCTree+PSO approach achieves better time to quality trade-off then 2MPSO for small optimization time limits, making the hybrid a good candidate for handling real world scale goods delivery problems.
