Optimization Approaches for the Traveling Salesman Problem with Drone
Optimization Approaches for the Traveling Salesman Problem with Drone
复制标题
DOI：
10.2139/ssrn.2639672
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Niels A. H. Agatz;P. Bouman;M. Schmidt
中科院分区：
文献类型：
--
作者：
Niels A. H. Agatz;P. Bouman;M. Schmidt
网上订购的商品快速且具有成本效益的送货上门在物流方面具有挑战性。许多公司正在寻找新的方法来跨越最后一英里到他们的客户。最近备受关注的一个技术机会是使用无人机来支持交付。一个创新的最后一英里交付概念，其中卡车与无人机合作进行交付，产生了旅行推销员问题TSP的一个新变体，我们称之为TSP与无人机。在本文中，我们将此问题建模为一个整数规划，并开发了几个快速路由优先，集群第二算法的基础上，局部搜索和动态规划。我们证明了最坏情况下的近似比的mesticistics和测试他们的性能，通过比较的解决方案的最佳解决方案的小实例。此外，我们将我们的算法应用于几个具有不同特征和大小的人工实例。我们的实验表明，大量的节省是可能的，这一概念相比，只有卡车交付。在线附录可在https://doi.org/10.1287/trsc.2017.0791上获得。
The fast and cost-efficient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last mile to their customers. One technology-enabled opportunity that recently has received much attention is the use of drones to support deliveries. An innovative last-mile delivery concept in which a truck collaborates with a drone to make deliveries gives rise to a new variant of the traveling salesman problem TSP that we call the TSP with drone. In this paper, we model this problem as an integer program and develop several fast route-first, cluster-second heuristics based on local search and dynamic programming. We prove worst-case approximation ratios for the heuristics and test their performance by comparing the solutions to the optimal solutions for small instances. In addition, we apply our heuristics to several artificial instances with different characteristics and sizes. Our experiments show that substantial savings are possible with this concept compared to truck-only delivery. The online appendix is available at https://doi.org/10.1287/trsc.2017.0791 .