摘 要

无人机这些年逐渐兴起，为了节省运送时间及成本无人机送货也进入了物流领域。但受限于当前无人机的续航和载重问题，进行大规模大面积的无人机送货尚不现实。但是用传统货车搭载无人机进行联合送货以减少货车的送货任务就显得非常实用。这样如何规划货车和无人机的路径就显得尤为重要。

本文将无人机与货车联合调度问题一分为二。一方面是在不考虑无人机的情况下求解货车的最优TSP路径。另一方面是在考虑无人机情况下用无人机路径代替原货车部分路径以达到进一步减少配送时间的目的。基于TSP问题模型，使用人工蜂群算法求解TSP最优路径。在求得的TSP最优路径之上设计了合理分配无人机进行送货的算法，算法尽可能的使用上货车所搭载的无人机，并最终得到无人机与货车联合送货的路径图。

关键词：无人机；TSP；人工蜂群算法；联合调度

Abstract

In order to save transportation time and cost, UAV delivery has also entered the field of logistics. However, due to the current problems of UAV's endurance and load, it is not realistic to deliver large-scale UAVs. But it is very practical to use traditional truck to carry UAV for joint delivery to reduce the delivery task of truck. So the plan for the route of trucks and UAVs is pretty important.

This paper divides the joint scheduling problem of UAV and truck into two parts. On the one hand, the optimal TSP path of truck is solved without considering UAV. On the other hand, the UAV route is used to replace part of the original truck route to further reduce the delivery time. Based on the model of TSP, the optimal path of TSP is solved by using the ABC. On the basis of the optimal TSP path, the algorithm of reasonable allocation of UAV for delivery is designed. The algorithm uses the UAV carried by the truck as much as possible. Finally, the route map of joint delivery of UAV and truck is obtained.

Keywords：UAV；TSP；artificial bee colony；joint scheduling

目 录

第1章 绪论 1

1.1 设计目的及意义 1

1.2 国内外研究现状 2

第2章 旅行商问题 4

2.1 问题描述 4

2.2 交换算子与交换序列 4

2.3 有关TSP算法 5

第3章 人工蜂群算法 7

3.1 人工蜂群算法概念 7

3.2 人工蜂群算法过程 7

第4章 无人机与货车联合送货 9

4.1 模型描述 9

4.2 用于TSP的人工蜂群算法 10

4.3 邻域搜索算法k-opt 11

4.4 无人机路径规划 11

第5章 结论 13

参考文献 16

附录A 17

致谢 24

第1章 绪论

1.1 设计目的及意义

经过多年的发展，现如今的电商与快递行业的体量已经非常巨大。以2019年的双十一为例，全网交易额为4101亿元，仅天猫平台上的物流订单数就达到了12.92。 为了满足大批量，短时间，低成本的配送需求，物流配送领域也发生了深刻的变化，其中无人机配送是发展趋势之一。

最早提出无人机配送这一概念的是美国的亚马逊公司。亚马逊于2013年推出了一个使用无人机进行货物配送的项目，名叫Prime Air。这个货物配送项目能满足离配送中心十几千米内的用户配送需求^[1]。另外在2016年的时候，位于德国的DHL公司做了一次运行实验。实验的内容就是将无人机与智能货柜结合起来，验证其可行性。2019年四月，美国另一家巨头公司——谷歌，将它精心策划的Project Wing真正付诸实践。反观国内，事实上也有两家大型公司向无人机配送领域进军，他们就是顺丰快递和兼顾电商的京东。顺丰快递接触无人机快递时间比较早，跟亚马逊一样是2013年，可见国内的头部企业还是有很高的敏锐性和前瞻性的。至于京东，相较于国内的顺丰起步是滞后了的，但京东还是在2016年的时候确定了有关无人机的配送体系与物流发展方式。对于无人机送货的现实解决方案，亿航智能与德国的DHL于2019年共同向人们展示了国内首套的全自动化物流技术，同时该公司的无人机首次试飞与验证也取得成功。

无人机配送具有传统配送无可比拟的优势。首先无人机配送不受交通状况和地理因素的制约。其次，随着技术的不断改进和发展，当前无人机的飞行速度可以达到数十千米/小时，而且突破百里/小时的型号也已经被研制出来了，这丝毫不亚于汽车送货的速度。除了拥有较快的速度，无人机使得原来二维的配送过程拓展到三维，极大的提高了空间利用率，而且不受交通状况的影响，不受地理条件的制约，提升的配送效率是显而易见的。最后一个方面，货物中不乏体积小数量轻的物件，往往这种货物的数量还不在少数。如果采用货车送货就显得笨重，性价比极低。对无人机来说，它很能适应这种配送需求，轻便灵活，成本低。

但是局限于无人机的续航、载重等技术难题，完全采用无人机进行大面积配送困难重重。而在传统的配送系统中，装满包裹的货车漫无目的穿梭于一条条街道又是一个非常浪费配送资源的工作过程。综合考虑，用传统货车搭载无人机进行联合配送以期缩短配送时间、节约配送成本是非常具有现实意义。2017年UPS采用卡车与无人机结合的方式进行的投递包裹测试也证实了此种方法的可行性。这样，如何协调无人机和货车，规划出无人机和货车的路径就显得尤为重要。

1.2 国内外研究现状

在无人机技术刚出现的时候，作为一种高新科技它只是在军事领域有着应用。随着技术的不断进步，其逐渐向民用发展，如今它在物流行业有着公认的，巨大的发展潜力。从物流的角度来看无人机主要解决 “最后一公里”的问题，因此及时性和服务体验尤为重要。此外，无人机还可以节省人工成本。无人机调度灵活，配送效率可以大大提高。通过合理利用闲置的低空资源可以有效实现中短距离运输，解决了配送区域边缘送货节点如何分配的尴尬问题。

美国亚马逊可以说是无人机物流领域的开拓者，奠基者和引领者。美国亚马逊如今无论是在关键技术储备、无人机开发研究、物流系统设计完善、配套设备完善、资金投入等方面都表现出它对这一方向的重视，将其视为自己重要的战略高地，并制定了有序合理的长久发展计划。现在亚马逊也在不断完善整个无人机物流布局的各个方面，像与无人机配套的自动化仓库、智能商店以及智能商店的货物存运等。但是实现真正意义上的无人机配送还有很长的一段路要走，需要解决很多根本上的技术难题。目前亚马逊主要的配送方式还是货车加配送员这一简单模式，所以无人机加自动货车是亚马逊未来一段时间比较切合实际，比较务实的一种发展方向。