电动汽车与无人机联合配送系统的实现

陈永鹏，张翠平，黄显雯

（北京信息科技大学 计算机学院，北京 100101）

1 无人机与汽车配送在物流行业的发展现状

1.1 无人机快递配送研究背景

随着科学技术的进步，快递物流等行业也获得了不断的发展，得益于经济全球化，商品从生产到消费过程中是离不开物流配送的，人们的消费水平上涨也是物流行业发展突飞猛进的主要原因之一。当顾客购买商品时，在众多取货方式如驿站自提、快递柜自提、送货上门中，送货上门方式最受顾客青睐。在本项目研究初始，调查了人们在配送时对物流公司和配送速度的喜好，发现在配送速度上只有3%的顾客希望当天就收到快递，即第一时间能拿到自己的商品，这部分人占少数；近30%的人认为第二天到也是可以接受的，人数占比适中；而62%的顾客对2～5天的配送时间也能接受，这部分人占比最多；其他少部分对配送到达时间并无强制要求。近年来，虽然诸如快递柜、菜鸟驿站、顺丰蜂巢等让客户自主取得快递的物流配送方式发展非常迅速，但82%的受访者表示心仪首选的配送方式依然是送货上门模式，也就是说，大部分人都希望将快递直接送到家门上。所以相关企业应该在此调查基础上为用户带来更好的服务体验。

近年来，与无人机相关的导航系统的开发、目标检测、环境感知以及自动避障和路径重规划等功能也日益强大，这些技术的成熟使得无人机的应用范围正逐渐扩大。比如国内的大疆公司在2012年开始将无人机应用在农业领域。从物流配送模式考虑，无人机配送的优势是明显优于汽车配送的，无人机送货可以在空中直线运输货物，从而避开了地面交通封路或者堵车的风险，传统的配送方式会因此受到严重影响。并且无人机采用了将电力作为动力，比经典车辆配送模式下减少了更多的二氧化碳排放。少了环境污染的同时还能提高配送效率，这一构思值得深入去探讨。综合前述成果的分析可知，本文拟将尝试去研究1辆电动汽车搭配2架无人机联合配送的车辆路径规划问题。

1.2 配备无人机的车辆路径问题国内外研究现状

虽然无人机联合汽车的物流配送模式的研究处于早期阶段，但在近几年，相关的研究和测试正持续增加。Sundar等人共同研究了无人机为多个顾客服务和配送，并且在动力不足时可以回到交付区域的充电仓进行充电。Wang等人提出了一个普遍的无人机车辆路径问题（VRPD），该问题考虑多辆卡车和无人机，目标是将交付任务的总持续时间最小化。虽然并未给这个问题提供优化框架，但是工作的重点是测试几个最坏的情况，如电力不足、信号不良、飞行路线不对等。先从目标问题入手解决，以确定无人机和电动汽车联合配送比传统的汽车配送节约的最大时长。Agatz等人深度研究无人机旅行商问题，并以物流中产生的成本为目标，构建了一个整数规划模型，再在动态规划和局部搜索的基础上研究路径、集群的优先级，研发了对应的启发式算法。

在国内，徐剑等人提出基于遗传算法的多无人机路径规划，设计了新的编码、解码方法和具有明确物理意义的适应度评价函数，以加快实时的运算速度和提高运算精度。仲筱艳等人对典型的多无人机协同任务的问题进行了任务规划建模，并设计了一种基于整数编码的混合遗传算法来进行任务分配。

1.3 城市末端配送研究现状

在末端配送研究时，孟繁宇提出一种外卖+快递的切换作业配送模式，研究认为国内的快递企业可以与各外卖平台合作，在外卖员空闲时间段转变为快递配送，并且拟用这种转变配送方式，解决如双十一、六一八等给各快递企业带来的快递订单激增问题，这种新型配送模式可以达到整合社会劳动力、提高配送效率、减少物流服务总配送时长、进一步提升配送准时准点率、增加外卖员收入的效果。李伟等人提出在满足客户实际配送时间要求的前提下，建立带有软时间窗的城市末端物流配送路径优化模型，并运用节约里程算法对问题进行求解，最后以某配送中心配送为实例，结果表明，以拥堵成本最低为前提选择路径的模式，可使配送过程中的成本降到最低。邱晗光等人以配送数量最大化和配送成本最小化为目标，构建了自提柜选址—时间窗分配—路径规划多目标联合优化问题模型，刻画了自提柜距离、配送时间误差对顾客配送服务需求的影响，优化设计了多目标粒子群算法的编码和初始种群构建方法并发现Pareto解集中无法分离出配送数量最大化和配送成本最小化均占优的解。

在车辆路径问题和无人机联合电动汽车参与的物流快递配送的研究中，无人机搭配电动汽车的配送方式，研究成果还不多见，并且当无人机配送完成后，如何返回服务点或所搭配车辆处理的问题，研究得也比较少。

2 无人机-电动汽车联合配送项目的研究内容

2.1 对配备无人机的车辆路径问题进行分析和研究并设计路径优化模型

车辆路径问题，通常是为了解决最短位移或最短路程问题，是一种很常见的优化问题。问题一般定义为：组织多种配送车辆，通过合适的运输路线，将各个货物逐一从配送中心送至每一位购买者手中，满足其需求，然后再返回配送中心重新取货配送，在这一配送模式过程中，以配送路线的最短、或者是配送成本最低、或者是碳排放量最少等作为研究目的。

从客户的满意度进行探讨研究，同时考虑到无人机配送的优势和电动汽车搭配2架无人机的猜想，提出了电动汽车搭配2架无人机进行联合配送的配送模式，并对该模式设计出对应的路径优化模型，作为未来的物流配送企业的新模式。

2.2 利用遗传算法进行算例解析

在算法的选择中，有精确算法和启发式算法两种。其中，精确算法是可以求出最优解的方法（类似算法分析中的各种优化算法），但若脱离对应的数学模型，这种算法就难以进行。在实际应用中，一般计算量都会很大，只能先从局部最优解开始推求，找到合适的小规模数学模型。该算法在规模较大的模型中就没有那么容易求解，适应性差。现有4种算法，即：割平面法、分支界限法、动态规划法和网络流算法中，分支界限法和动态规划法有着较强的实用性，且都属于精确算法。

启发式算法是通过总结失败的经验，由此出发来找到方法解决问题，但在解决小规模规划问题时，却略逊于精确算法。研究发现在大规模问题中，精确算法的适应性过差，往往难于求解，而对于实际问题而言，多数问题又都是大规模的，所以国内外学者都在探寻搜索一种新型的启发式算法，在无法求解大规模问题的最优解时，力求得到一个近似解，以局部最优得到全局最优。启发式算法具体有5个，分别是：粒子群算法、禁忌搜索算法、蚁群算法、模拟退火算法、遗传算法，此外还有一些不常用的其他优化算法。

本文使用遗传算法对设计的无人机-电动汽车联合配送模型进行算例解析，同时基于同样的算例使用传统的汽车配送模式进行解析计算，通过两者配送效率的对比验证本文所设计模型的科学性。

3 无人机-电动汽车联合配送项目研究的意义

当今时代，随着经济全球化趋势的发展，物流作为一种经济流动的方式，对社会生产和国家发展以及人民的生活改善都有着重要意义。因其能在有效的时间内将其他空间的供给物品递送至需求人手中，从而产生经济效益。而种种数据也表明了物流在当今时代扮演着不可替代的角色。

在这个知本时代，物流业若要不断地创新突破，就要不断地改良配送方式以提高配送效率，而修改配送路线、转变配送方式、增加配送劳动力等都是各大物流企业提出的优化作业模式的方法。考虑到如今的顾客们最关注的就是商品能否按时送达手中，而无人机的直线行驶必然比地面车辆的弯路行使快得多。且由于地面上的弯路过多，这就导致了汽车配送货物的效率并不是很高，而随着无人机行业的快速发展，汽车搭配无人机联合配送模式恰好能满足直线运输的条件。

因为二氧化碳等温室气体的大量产生，温室效应越发严重，这是在科学力量高速发展时学术界必须注意的一个问题。全球变暖带来的自然灾害无时无刻都在给地球环境带来危害，若采用汽车搭配无人机进行联合配送，汽车的尾气必定会产生大量的二氧化碳从而加剧温室效应，因此在运输货物选择车辆种类方面也应是新型配送模式应该考虑的问题。考虑到电动汽车不会产生碳排放，这一运输工具则恰好符合了保护环境和可持续发展的要求，因此在车辆选择方面电动汽车是一个不二选择。

自2019年12月，全国乃至全世界都在共同对抗新型冠状病毒，这就在一定程度上影响到了传统物流方式的配送效率。若能通过无人机送货，达到零接触的物流配送方式将非常适合当下的防疫抗疫形势。还需指出，目前仍有少部分街道和村道路况崎岖，不利于配送，故而智能投递应该得到普及。由此可知，电动汽车与无人机联合配送已然成为本次学术探讨的重点研究课题。

4 电动汽车-无人机联合配送建模设计

4.1 问题与模型假设

本文根据电动汽车与无人机联合配送路径规划研究，以完成物流配送任务总时间最小为实现目标，建立数学模型。主要考虑的问题如下：不同区域的配送总站在各自区域通过需求随机为客户提供物流交付服务。配送中心使用电动汽车和无人机进行联合快递配送，一辆电动汽车上配备了2架无人机。在配送之前，给电动汽车装载货物，并在车顶配置2架可运输货物的无人机。配送过程中，电动汽车和无人机能同时为客户服务，通过汽车送上门或者是无人机上门的方式来达成配送。但无人机因为承重能力较差，无法实现搭载超过5磅的货物，所以每当有超过5磅的货物时，将该货物留在电动汽车仓库中，待电动汽车空闲时再配送该超重货物。电动汽车先给无人机挂载合适重量的货物，随后控制无人机飞行，无人机根据物流地址控制飞行至客户的所在地，最后完成交付服务。在无人机配送货物到顾客手中这一过程有序展开的同时，电动汽车送完超重货物后可以前往当前地区的服务区站点，待无人机送完货物后回到该服务区进行回收重复使用。

为了简化数学模型以便于更直观的研究，对模型设计做以下假设：

（1）电动汽车与无人机在配送过程中所有经过的路况视为理想型，即没有交通堵塞、突发交通事故等影响电动汽车和无人机行驶路线的因素。

（2）在进行配送服务时不考虑因为用户退货寄快递而产生的逆向运输情况。

（3）假设电动汽车在一次配送服务过程中蓄电池电量足够，不考虑配送过程中中途到达充电站充电的情况。

4.2 符号说明

4.3 模型建立

4.3.1 目标函数综上分析可知，目标函数的数学表达式可写为：

该目标函数以电动汽车与无人机联合配送完成当前服务范围内配送总时间最小为目标，最小化电动汽车从配送中心出发到完成本次服务范围内最后一个节点的所用的总时间。上文提到，电动汽车和无人机共同负责本次服务范围内的所有用户节点，无人机可以覆盖到的用户节点电动汽车不用负责，但是对无人机无法提供服务的用户节点电动汽车需要提供配送服务。每当无人机对当前某一节点完成配送服务后会返回在该节点或者下一节点等待的电动汽车，故目标函数中对于总时间的计算以电动汽车在最后一个节点完成配送服务为基准。

4.3.2 约束函数

研究中的一个约束函数可由下式来确定：

式（3）规定电动汽车在一次配送任务中只能从配送中心驶出一次，具体数学公式如下：

其中，表示的节点是无人机和电动汽车在服务范围内可以到达的节点∈，表示无人机节点中某一个元素∈。

式（4）规定电动汽车在一次配送任务中只能返回配送中心一次，式（3）和式（4）是对电动汽车在某一次配送任务中不重复进入和离开配送中的约束，避免计算中的冗余。研究推得的数学公式如下：

式（4）是对无人机在服务范围内某一节点起飞次数的限制，即在每一个节点最多只能起飞一次。

式（5）对无人机在服务范围内某一节点被回收次数做限制，无人机在每一个节点处最多只能被回收一次。进一步推得的数学公式可写为：

式（6）规定当无人机服务范围内从节点出发到达节点并在节点被回收，那么电动汽车必须要跟随无人机的飞行路径，沿到节点方向行驶。由此推得的数学公式为：

5 解决电动汽车-无人机联合配送模型的解析算法和算例分析

5.1 模型解析算法概述

本文中对设计的电动汽车-无人机联合配送模型的解析是基于遗传算法展开的。遗传算法是一种解决最优化问题的进化算法，通过借鉴了一些生物学中的现象，将大自然中优胜劣汰的生物进化规律应用到对数学问题的求解中。对于一个具体的优化问题来讲，将该问题一些可选解以完全随机的种群展开，设计一个实用度评估函数，用于对种群展开后每一代进化得到的新的种群做适应度评估，选择更优的一部分作为下一次算法迭代中的使用种群。关于本文选择遗传算法对模型进行解析的原因，对此优势详述如下。

（1）遗传算法不是单单从一个个体解开始搜索，而是通过从全局的整体，逐一查找个体进行搜索，且通过串集搜索，不会卡在局部寻找，而是从全局获取最优解。

（2）遗传算法会对当前生成的种群中每一个个体进行计算，利用评估算法对符合条件的个体做进一步筛选，这种计算方法不会使系统陷入到一个局部中去。

（3）遗传算法基本没有用到其他的搜索空间知识或者其它的辅助信息知识，单单通过适应度函数值来评估比对个体的差异，再通过差异结果进行相对应的遗传操作处理。普通的可微分数学函数不会影响适应度函数，还可以根据需求定义自身函数的定义域，从而影响值域。

（4）遗传算法的随机性更强，这也是由其搜索机制本身具有的较强不确定性决定的，故而该算法的解更能模拟现实中的复杂情况。

（5）遗传算法具有自我适应、自我学习、自我组织的功能，通过类似生物的遗传进化过程自我搜索个体信息，由此找出生存概率最高的个体，淘汰劣势的个体，再选择存活的个体还会继续进化，适者生存地改变自我基因结构，进而合理使用生存环境。

（6）算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。

5.2 算例分析

5.2.1 说明

在以一个仓库为起点和终点的服务范围内，共设10个节点，仓库为0节点，其它1～9个节点均为客户节点，节点的位置见表1。在表1中，节点位置相关信息以经度、纬度标注出，每2个节点之间的距离用曼哈顿距离表示。根据上文的调查结果，大部分快递重量不超过5磅，所以将无人机的最大载重量设为5磅，超过5磅的货物由电动汽车进行配送。电动汽车在单次配送服务过程中一次性携带本次配送需要的所有快递并搭载2架无人机从仓库出发，完成所有配送服务后返回仓库中。假设电动汽车的蓄电池电量能够支持其在服务范围内一次完成所有配送，中途无需充电。

表1 节点相关信息Tab.1 Node-related information

为了完成模块功能的实现，使用Python以及QT等编程语言进行代码程序编写，并结合遗传算法对其求解。电动汽车-无人机联合配送计算结果见表2。从表2的电动汽车-无人机联合配送计算结果中可以看出，电动汽车和无人机在整个服务过程中的配送路径，电动汽车的配送路径为［0，4，7，3，9，2］（［，，］表示配送工具从节点出发，经过节点到达节点，下文中同理），无人机1的配送路径为［4，5，7］，［4，6，7］，无人机2的配送路径为［9，1，2］，［9，8，2］。除此之外，还可以从表2中得到电动汽车和2架无人机在每个节点的开始时间和结束时间以及其它状态信息，如无人机的起飞、降落、配送等。通过计算，电动汽车联合无人机完成此次配送服务的时间为5 114.388 s。

表2 电动汽车-无人机联合配送计算结果Tab.2 Calculations for joint distribution of electric vehiclesdrones

5.2.2 电动汽车-无人机联合配送与电动汽车普通配送模式的对比分析

本文设计的电动汽车-无人机联合配送模型相比现实中普通的车辆配送多配备了2架无人机，用于减少配送服务的总时长，提高整体配送效率。作为对比，基于上文的算例设计了普通电动汽车模型，求解结果见表3。表3中，电动汽车的行驶路径为［0，4，5，6，7，3，9，8，1，2］。

表3 传统电动汽车配送计算结果Tab.3 Traditional electric vehicles distribution calculations

从本次可计算结果可以得出使用电动汽车进行配送货物的物流服务交付完成的总时长为6 774.409 s。相比之下，电动汽车-无人机联合配送模式用时5 114.388 s。时间效率直接提升了24.5%。由此看来在传统的电动汽车配送模式中加入2架无人机的确可以大幅提升配送效率，无人机可以有效改善汽车因路况拥挤、交通灯较多等情况引起的配送时间长的问题。

6 结束语

本文分析了近年来国内外学者在物流末端配送方面的研究现状，燃油汽车配送仍然是如今物流末端配送的主流方式。但是从能源清洁的角度来看，以纯电力驱动的运输工具是比燃油驱动汽车更好的选择。在如今国内外新能源（以纯电力驱动为主）汽车大力发展的前提下，本文选择了电动汽车搭配2架电力驱动的无人机完成以一个仓库为中心在一定范围内完成配送服务。无人机的广泛应用是近年来一个关注度持续走高的热点话题，无人机在物流配送方面的研究近些年在国内外都已经转入了试用阶段且初有成果。在较为复杂的末端配送过程中，无人机的应用可以很好地克服路况、地形等复杂因素，以提高配送效率。据此，本文以一辆电动汽车搭载2架无人机为原型，以完成一定范围内配送服务总时间最小为目标建立了电动汽车-无人机联合配送模型，模型中的目标函数在满足一系列约束条件的前提下，寻求最高效的配送策略。论文选择了遗传算法对无人机-电动汽车联合配送模型进行模拟数据的解析，通过与相同环境下传统汽车不搭载无人机的配送模式对比，表明了无人机的加入有效地提升了配送效率，验证了此模型的科学性。

本项研究还有以下待改进的地方：

（1）电动汽车-无人机联合配送模型设计过程中没有考虑到配送过程中较为复杂的交通问题，比如交通堵塞、还有突发的交通事件等。

（2）模型中没有考虑到用户退货产生的逆向配送情况。

（3）模型中没有考虑电动汽车在服务范围内蓄电池是否够用，这就需要将充电站的距离以及充电时间等因素增加到约束函数中。

（4）可以进一步分析无人机-电动汽车联合配送模型中电动汽车携带无人机的数量对整体配送效率的影响程度。

（5）可以尝试使用深度学习检验本模型在更大范围内、更复杂场景下的配送情况，确定出电动汽车搭载无人机的最优个数。