Exact Methods for the Traveling Salesman Problem with Drone
Exact Methods for the Traveling Salesman Problem with Drone
复制标题
无人机旅行商问题的精确方法
DOI：
--
复制
发表时间：
2021
影响因子：
4.6
通讯作者：
Mario Ruthmair
中科院分区：
文献类型：
--
作者：
R. Roberti;Mario Ruthmair
如今，有效处理最后一英里交付变得越来越重要。使用无人机来支持传统车辆可以改善交付时间表，只要有有效的解决方案方法来计划使用无人机的最后一英里交付。我们研究了一些变种的旅行推销员问题与无人机（TSP-D），其中一辆卡车和一架无人机联手为一组客户提供服务的精确解方法。卡车和无人机的这种组合可以利用两种车辆类型的优点：卡车容量大，但在城市地区通常行驶速度较低;无人机速度更快，不限于街道网络，但其范围和运载能力有限。我们提出了一个紧凑的混合整数线性规划（MILP）的几个TSP-D的变种，是基于及时同步卡车和无人机流量;这样的MILP是很容易实现，但仍然导致竞争力的结果相比，国家的最先进的MILP。此外，我们引入动态规划递归模型几个TSP-D的变种。我们展示了如何利用这些动态规划递归在一个确切的分支和价格的方法的基础上，使用NG-路由松弛和三级层次分支的一组分区配方。提出的分支和价格可以解决最多39个客户的实例，以最优的性能超过最先进的两倍以上的可管理的实例大小。最后，我们分析了不同的场景，并表明，即使是一个单一的无人机可以显着减少路线的完成时间时，无人机是足够快。
Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and a drone are teamed up to serve a set of customers. This combination of truck and drone can exploit the benefits of both vehicle types: the truck has a large capacity but usually low travel speed in urban areas; the drone is faster and not restricted to street networks, but its range and carrying capacity are limited. We propose a compact mixed-integer linear program (MILP) for several TSP-D variants that is based on timely synchronizing truck and drone flows; such an MILP is easy to implement but nevertheless leads to competitive results compared with the state-of-the-art MILPs. Furthermore, we introduce dynamic programming recursions to model several TSP-D variants. We show how these dynamic programming recursions can be exploited in an exact branch-and-price approach based on a set partitioning formulation using ng-route relaxation and a three-level hierarchical branching. The proposed branch-and-price can solve instances with up to 39 customers to optimality outperforming the state-of-the-art by more than doubling the manageable instance size. Finally, we analyze different scenarios and show that even a single drone can significantly reduce a route’s completion time when the drone is sufficiently fast.