熊兴隆，刘 佳，李 猛，马愈昭

1.中国民航大学 天津市智能信号与图像处理重点实验室，天津 300300

2.中国民航大学 电子信息与自动化学院，天津 300300

3.中国民航大学 民航空管研究院，天津 300300

在物流配送领域，传统单配送车送货存在配送成本高、效率低、延误高、环境污染等问题。随着无人机在物流领域受到越来越多的关注，提出一种新型交付概念——无人机联合配送车协同配送包裹。目前亚马逊、德国邮政、谷歌等企业已经尝试将无人机应用在其业务中以降低配送成本缩短配送时间[1-2]。无人机由于其移动消耗能量少，不受道路网络交通拥堵影响，速度快等特性，相比传统配送车送货而言可降低交付成本缩短交付时间，但考虑其载荷及续航能力问题，配送车又显得更有优势[3-5]。由于二者的互补性，将无人机整合到现有的“最后一英里”交付模式中可能产生协同效益。因此引发了“无人机-旅行商”问题（Travelling Salesman Problem with Drone，TSP-D）[6]针对无人机与配送车联合路径的研究。

2015年，Murray等人[6]首次将无人机引入TSP研究，引入混合线性规划公式求解两类问题模型，提出了一种基于先分群再排路线的启发式算法解决了10个节点的案例，该算法目前只能解决小规模节点案例。Agatz 等人[7]引入一个整数规划公式，提出了基于局部搜索和动态规划的先排路线再分群的两种启发式算法，同样只适用于小于10个节点的案例。Bouman等人[8]基于动态规划提出了一种求解TSP-D 的精确方法，能更快找到10个节点问题示例的最优解决方案。……