Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach
Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach
复制标题
无人机和卡车在送货服务中的合作路线规划：双目标优化方法
DOI：
10.1080/01605682.2019.1621671
复制
发表时间：
2019
影响因子：
3.6
通讯作者：
Lu Yuwei
中科院分区：
文献类型：
--
作者：
Wang Kangzhou;Yuan Biao;Zhao Mengting;Lu Yuwei
亚马逊和阿里巴巴等几家公司最初都在尝试部署无人机来支持最后一英里的配送。无人机和卡车的互补能力构成了一种创新的交付模式。与这种新模式相关的优化问题，被称为无人机旅行推销员问题（TSP-D），旨在找到无人机和卡车的协调路线，为一组客户提供服务。在实践中，管理人员有时打算在操作成本和完成时间之间达成妥协。因此，本文将讨论一个考虑两个目标的双目标TSP-D。提出了一种改进的非支配排序遗传算法（INSGA-II）来解决这一问题。具体而言，针对该问题的特点，设计了基于标签算法的解码方法、快速非支配排序方法、拥挤距离计算过程和局部搜索组件。此外，INSGA-II获得的第一个帕累托前沿通过后优化组件得到改进。计算结果验证了该算法的竞争性能。同时，权衡分析显示了运营成本与完工时间之间的关系，为管理者设计合理的折衷路线提供了管理见解。
Abstract The deployment of drones to support the last-mile delivery has been initially attempted by several companies such as Amazon and Alibaba. The complementary capabilities of the drone and the truck pose an innovative delivery mode. The relevant optimisation problem associated with this new mode, known as the travelling salesman problem with drone (TSP-D), aims to find the coordinated routes of a drone and a truck to serve a list of customers. In practice, managers sometimes intend to attain a compromise between operational cost and completion time. Therefore, this article addresses a bi-objective TSP-D considering both objectives. An improved non-dominated sorting genetic algorithm (INSGA-II) is proposed to solve the problem. Specifically, the label algorithm-based decoding method, the fast non-dominated sorting approach, the crowding-distance computation procedure, and the local search component are devised to accommodate the features of the problem. Furthermore, the first Pareto front obtained by the INSGA-II is improved by a post-optimisation component. Computational results validate the competitive performance of the proposed algorithm. Meanwhile, the trade-off analysis demonstrates the relationship between operational cost and completion time and provides managerial insights for managers designing reasonable compromise routes.