A Study on the Traveling Salesman Problem with a Drone
A Study on the Traveling Salesman Problem with a Drone
复制标题
无人机旅行商问题的研究
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Paul Shaw
中科院分区：
文献类型：
--
作者：
Ziye Tang;W. V. Hoeve;Paul Shaw
未来物流网络的一个有前途的新模式涉及传统卡车和现代无人机之间的合作。无人机可以从卡车上拿起包裹，并在卡车为其他客户提供服务时通过空运将其交付。运营挑战结合了将交付地点分配给卡车或无人机，以及卡车和无人机的协调路线。在这项工作中，我们考虑了一辆卡车和一架无人机的情况，目标是最小化完成时间（或makespan）。作为我们的第一个贡献，我们证明了这个问题是强NP难的，即使在限制的情况下，无人机交付需要最佳地集成在一个给定的卡车路线。然后，我们提出了一个约束规划公式，competency代表卡车和无人机之间的操作约束。我们的计算实验表明，解决CP模型的最优性是显着快于国家的最先进的精确算法。对于较大的情况下，我们的CP为基础的启发式算法是有竞争力的一个国家的最先进的启发式方法。
A promising new model for future logistics networks involves the collaboration between traditional trucks and modern drones. The drone can pick up packages from the truck and deliver them by air while the truck is serving other customers. The operational challenge combines the allocation of delivery locations to either the truck or the drone, and the coordinated routing of the truck and the drone. In this work, we consider the scenario of a single truck and one drone, with the objective to minimize the completion time (or makespan). As our first contribution, we prove that this problem is strongly NP-hard, even in the restricted case when drone deliveries need to be optimally integrated in a given truck route. We then present a constraint programming formulation that compactly represents the operational constraints between the truck and the drone. Our computational experiments show that solving the CP model to optimality is significantly faster than the state-of-the-art exact algorithm. For larger instances, our CP-based heuristic algorithm is competitive with a state-of-the-art heuristic method.