无人机和车辆联合配送路径优化方法、装置及介质

本发明涉及物流配送领域，尤其是涉及一种无人机和车辆联合配送路径优化方法、装置及介质。

背景技术：

1、近年来，无人机技术的发展已经成为了国内外高科技领域的热门话题。作为一种颠覆性的技术，无人机在军事、民用、商业等领域都得到了广泛的应用。中国政府高度重视无人机技术的发展，为无人机产业提供了政策支持和市场保障。2018年，印发了《新一代人工智能发展规划》，其中提到无人机技术在智慧城市、农业、物流配送等领域的应用前景非常广阔。同时，国家航空航天局发布的《无人驾驶航空器系统发展规划》明确了未来五年无人机技术的发展方向和目标，包括提高无人机自主飞行、加强应用场景研究和建设、加强无人机人才培养等方面。此外，国家还出台了一系列政策，如允许民用无人机飞行高度提升、对无人机相关企业给予税收优惠等，进一步推动了无人机产业的发展。

2、无人机已被广泛应用于多个领域，如农业、环保、安防、航空、物流、配送等。无人机的运用已经改善了许多传统工作的效率，特别是在一些需要高效运作、迅速响应的应急救援任务中。例如，无人机可以在火灾、洪水等自然灾害中提供空中监测和救援，减少人员伤亡和财产损失。

3、随着互联网和电商的发展，物流配送成为一个重要的领域。在市场竞争的加剧和消费者需求的不断增加下，物流配送的瓶颈逐渐凸显。而无人机在物流配送中的应用，可以解决传统物流配送的瓶颈问题，实现快速配送和精准投递，其运营成本也相对较低，同时还能减少交通拥堵和环境污染。

4、无人机在物流配送中的主要优势在于速度和灵活性。无人机可以在短时间内完成货物的配送，避免人力资源浪费和交通拥堵等问题。此外，无人机还可以在一些特殊环境中完成物资运输和交付，例如山区、海岛等地区，以及一些恶劣的天气条件下。

5、目前，无人机在物流配送中的应用还处于初级阶段。然而，各大物流企业和电商平台纷纷开始了相关试点和尝试。无人机作为物流配送中的新型运输工具，具有成本低、操控方便、环境要求低、生存能力较强等优点，在物流运输应用中具有很大潜力，可承担更多的配送任务。但由于其体积较小，也有载重量小、飞行距离较短、受天气影响较大等不足，而传统配送车辆具有容量大、可长距离配送、安全稳定性高、相关配送技术成熟等优点，无人机和车辆的联合配送能充分发挥各自的优势，亚马逊、ups、京东等大型物流企业都在大力研发新的无人机配送模式。

6、在地震、山洪等突发事件发生后，被破坏的路段和小区，限制了车辆的配送，而无人机具有无视地形飞行、作业效率高、相对成本低等优势，可以快速地到达灾区或紧急救援现场，缩短物资运输时间，提高应急响应速度，为应急物资运输提供高效便捷的手段。此外，无人机可以提高物资的配送速度和准确性，避免人员进入危险区域的风险，同时还可以提高运输的安全性。随着无人机技术的不断发展和普及，如何保证大量物资及时高效、无接触送达，无人机和车辆联合配送模式的研究将具有重大意义。

7、为构建合理的模型，研究者尝试从经典的路径问题出发，如：旅行商问题（tsp）和车辆路径问题（vrp），假设车辆和无人机相互合作，共同完成所有客户的配送任务。

8、（1）旅行商问题

9、murray和chu在2015年提出了飞行助手旅行商问题（fstsp）和并行无人机调度旅行商问题（pdstsp）两种模型，这是该方向上发表较早且影响较大的文章，为后续大量研究提供了参考。

10、fstsp中车辆和无人机需要协调控制，两者联合协作。boccia等为避免建模时使用大m法进行约束的缺点，对fstsp提出了一种新的整数线性规划模型（ilp），并基于列生成法对20个客户节点问题进行求解。murray和raj针对单车辆多无人机的mfstsp问题，通过一种三阶段的启发式算法，分析了无人机的不同电池大小、有效载荷、飞行距离和飞行阶段对联合配送总完工时间的影响，并得出额外的无人机可能会带来边际收益递减。

11、pdstsp中车辆和无人机没有合作，两者独立完成各自的配送任务。saleu等在murray构建的pdstsp模型基础上，提出了一种两步迭代启发式算法，使用229个客户点的大规模案例进行了测试。dellamico等结合局部搜索算法来求解pdstsp问题，目的是尽量减少服务全部客户的总时间，并采用murray和saleu的案例数据验证了模型在中小规模案例中有效性。ham等将pdstsp扩展到多车辆多无人机多仓库的场景，考虑了无人机能同时在仓库或客户点进行取货或送货，以最小化所有任务的完工时间为目标，无人机从车辆上发射后，可以在不同车辆上完成回收。

12、agatz等将此路径问题称为无人机旅行商问题(tsp-d)，以最小化配送成本为目标构造混合整数模型，基于局部搜索和动态规划，采用先路由后聚类的两阶段启发式算法解决该问题。bouman等则改进了传统tsp问题的动态规划算法，并结合*算法进行优化，使其适宜解决大规模的tsp-d问题。ha等针对单卡车和单无人机的tsp-d问题，以最小化总配送成本和卡车等待无人机的惩罚成本为目标，通过分割tsp最优路径为tsp-d路径，提出了一种先聚类再路由的贪婪随机自适应搜索算法。kitjacharoenchai等将tsp-d扩展为多卡车与无人机联合配送问题，允许无人机在不同车辆完成降落，设计了一种基于插入的启发式算法以解决大规模案例，并与单卡车配送和单无人机单车辆的结果进行比较。mario等为更大限度利用无人机进行包裹配送，提出卡车不仅可以在固定节点收发无人机，而且可以沿配送路径进行无人机的发射和回收。一些技术人员提出了一个混合整数线性规划公式，将tsp-d模型分解成两个决策阶段，第一个阶段选择并排序车辆的服务节点，第二个阶段针对卡车路线和剩余节点进行无人机调度，设计了一种benders型分解算法来求解大规模实例。

13、（2）车辆路径问题

14、当考虑到更多无人机和车辆的配送限制时，tsp就拓展为vrp。为提高联合配送效率，savuran和karakaya提出了一个新的变种modvrp，假设车辆沿着一条直线前进，有大量的客户点分布在路线两侧，无人机出发后尽可能多配送客户点。dorling考虑了无人机的飞行距离和载重的关系，构建vrps整数线性模型，验证了无人机的能量消耗和载重呈线性关系，并应用模拟退火算法对模型进行求解，得出能量消耗和送货时间不能同时达到最优。

15、而在无人机的限制上，wang等考虑到续航能力限制下的无人机车辆路径问题（vrp-d），提出无人机可以从仓库或任意客户地点的卡车上进行发射和接收，并分析了几种最坏情况下的配送结果，结果表明最坏情况下的结果取决于每辆卡车上的无人机数量，以及无人机和车辆的相对速度。sacramento等针对联合配送中大型实例求解困难的问题，提出一种自适应大规模邻域搜索元启发式算法，同时对无人机相关参数进行敏感性分析。scherme等基于混合整数线性规划，引入了有效不等式集（vieq），对无人机分配和调度问题（dasp），在给定现有车辆路线的情况下，寻找无人机的最优分配和调度的，结果表明提出的模型能有效的求解vrp-d问题。wang和sheu在城市物流中应用了联合配送，将vrp-d中基于弧的问题模型转变为基于路径的模型，同时开发了一种分支定价法，来寻找高质量的精确解。kuo等拓展了sacramento等人的vrp-d数学公式，考虑到不同客户存在时间窗口限制，开发了一个客户时间窗（vrptwd）存在的无人机车辆路径问题模型来探索这种合作，并提出了一种简单有效的可变邻域搜索（vns）算法来求解vrptwd问题。

16、此外，部分研究者从另一个变种两级车辆路径问题出发，分两层路径规划，无人机以车辆路径上的节点为中心，进行一定范围内的货物配送。部分学者应用2e-clrp的模型给出了如何利用车载无人机进行情报收集、侦查、监视任务，该问题的第一层相当于求解一个部分环路巡游问题，车辆只需要选择部分的停靠点来发射回收无人机，而第二层相当于求解一个单环的车辆路由问题，无人机需要根据其续航能力的约束，用尽可能短的时间访问所有的目标点。一些学者提出了新的双层车载无人机合作路由问题2e-gucrp，假设车辆不能停留在原地。在2e-vrp的基础上，提出车辆不仅负责包裹配送，还充当无人机的移动仓库，无人机可以携带多个包裹从车辆上发射，在完成交付后返回车辆，并对无人机在运送多个包裹时的能量消耗过程进行了分析。引入了带时间窗和移动卫星的两级车辆路径问题2e-vrp-tm，以运营成本最小化为目标，在第一梯队中使用车辆从配送中心（dc）出发，向客户交付带时间窗口的包裹，当车辆停在客户位置进行无人机的发射和回收时，车辆被会被当作移动卫星。

17、特别的，中国专利cn 113139678a公开了无人机-车辆联合配送路径优化方法，器通过将部分配送点定义为停靠点，允许无人机车辆同时位于此点实现无人机的再次发射，从而增加了无人机的可达性，增加了可行解的空间范围，然而，该现有技术存在以下缺陷：

18、1、其将车辆的配送路径切分为子链，需要根据无人机的发射轮次进行逐次优化，从而导致优化效率较低。

19、2、其采用三阶段的模型，通过累加无人机和车辆的单次路径规划，然后整体调优，因此除了主目标外，还有两个子目标，以构造联合配送路径。如此，两个子目标的存在反而影响了最优解被搜索出来的概率。

20、3、无法实现约束条件的模块化拓展。

技术实现思路

1、本发明的目的就是为了解决上述现有技术存在的问题而提供一种无人机和车辆联合配送路径优化方法、装置及介质。

2、本发明的目的可以通过以下技术方案来实现：

3、一种无人机和车辆联合配送路径优化方法，包括：

4、步骤s1：获取所有配送点的位置和配送货物需求；

5、步骤s2：构建一个或多个约束条件组合；

6、步骤s3：将配送中心和所有配送点均作为节点，并随机生成节点序列，其中，所述节点序列中首个节点和末个节点均为配送中心，其余配送点随机排序于首个节点和末个节点之间；

7、步骤s4：基于当前的节点序列，结合所有约束条件，将各节点的配送属性定义为车辆配送节点、无人机配送节点或停靠点，并基于各节点的配送属性，结合节点的顺序生成车辆路径，以及一个或多个无人机路径；

8、步骤s5：基于得到的车辆路径和所有无人机路径生成总配送时间；

9、步骤s6：利用优化算法更新节点序列后，重复步骤s3至s5多次，并将总配送时间最短的车辆路径和所有无人机路径生成配送方案。

10、所述约束条件组合至少包括无人机最大载重约束、无人机最大航程约束和无人机协同约束；

11、所述步骤s4包括：

12、步骤s4-1：将节点序列中的第一个节点和最后一个节点的配送属性均定义为停靠点，并将节点序列中的第一个节点选取为第一节点；

13、步骤s4-2：自当前的第一节点往后遍历，基于无人机最大载重约束和无人机最大航程约束选择得到第二节点；

14、步骤s4-3：将当前的第二节点的配送属性定义为停靠点，第一节点和第二节点之间的所有未定义配送属性的节点的配送属性定义为无人机配送节点；

15、步骤s4-4：自当前的第二节点往后遍历，基于无人机协同约束选择得到第三节点；

16、步骤s4-5：将第二节点至第三节点之间的未定义配送属性的节点，以及第三节点的配送属性均定义为车辆配送节点；

17、步骤s4-6：判断是否还存在配送属性未定义的节点，若为是，则将第三节点作为新的第一节点，并返回步骤s4-2，反之，则执行步骤s4-7；

18、步骤s4-8：基于各节点的配送属性，结合节点的顺序生成车辆路径，以及一个或多个无人机路径。

19、所述步骤s4-2包括：

20、步骤s4-2-1：选择当前的第一节点的下一个未定义配送属性的节点作为目标节点；

21、步骤s4-2-2：判断以下条件是否均成立：

22、由第一节点依次经过各未定义配送属性的节点至目标节点的总距离小于无人机的最大续航，

23、由第一节点依次经过各未定义配送属性的节点至目标节点的货物配送总重量小于无人机的最大载重，

24、若为是，则执行步骤s4-2-3，反之，则执行步骤s4-2-4；

25、步骤s4-2-3：将当前的目标节点的下一个节点作为目标节点，并返回步骤s4-2-2；

26、步骤s4-2-4：判断当前的目标节点是否为第一节点的下一个未定义配送属性的节点，若为是，则将当前的目标节点作为第二节点，反之，则将当前的目标节点的前一节点作为第二节点。

27、所述步骤s4-2-3具体为：判断当前的目标节点是否为节点序列中的倒数第二个节点，若为是，则将当前的目标节点作为第二节点，并执行步骤s4-3，反之，则将当前的目标节点的下一个节点作为目标节点，并返回步骤s4-2-2。

28、所述步骤s4-4包括：

29、步骤s4-4-1：初始化候选节点集合为空集，选择当前的第二节点的下一个节点作为目标节点；

30、步骤s4-4-2：计算由第一节点依次经过各配送属性为无人机配送节点的节点至第二节点的无人机飞行时长作为第一时长，以及计算由第一节点依次经由第二节点后的各未定义配送属性的节点至目标节点，再至当前的目标节点的车辆行驶时长作为第二时长；

31、步骤s4-4-3：计算第二时长和第一时长的比值是否位于第一比例区间；

32、步骤s4-4-5：判断第二时长和第一时长的比值是否小于第一比例区间的左边界，若为是，则选择当前的目标节点的下一个节点作为目标节点，并返回步骤s4-4-2，反之，则执行步骤s4-4-6；

33、步骤s4-4-6：判断第二时长和第一时长的比值是否位于第一比例区间中，若为是，则将当前的目标节点加入至候选节点集合中，选择当前的目标节点的下一个节点作为目标节点，并返回步骤s4-4-2，反之，则执行步骤s4-4-7；

34、步骤s4-4-7：判断候选节点集合是否为空集，若为是，则执行步骤s4-6，反之，则在候选节点集合中选择一个最接近第一比例区间中点的节点作为第三节点。

35、所述步骤s4-4-6具体包括：

36、步骤s4-4-6-1：判断第二时长和第一时长的比值是否位于第一比例区间中，若为是，则执行步骤s4-4-6-2，反之，则执行步骤s4-4-7；

37、步骤s4-4-6-2：将当前的目标节点加入至候选节点集合中，并判断当前的目标节点是否为节点序列中的倒数第二个节点，若为是，则执行步骤s4-4-7，反之，则当前的目标节点的下一个节点作为目标节点，并返回步骤s4-4-2.

38、所述总配送时间为：

39、

40、其中：为车辆到达配送中心的时刻，为无人机第k次发射到达配送中心的时刻，为取大函数，n为节点的数量。

41、所述优化算法为模拟退火算法。

42、一种无人机和车辆联合配送路径优化装置，包括存储器、处理器，以及存储于所述存储器中的程序，所述处理器执行所述程序时实现如上述的方法。

43、一种存储介质，其上存储有程序，所述程序被执行时实现如上述的方法。

44、与现有技术相比，本发明具有以下有益效果：

45、1、直接对整个节点序列进行操作并一次性生成完整的车辆与无人机路径方案，避免了分段优化带来的计算复杂度和效率损失，此外，优化目标仅为最小化总配送时间这唯一的主目标，摒弃了现有技术中多个子目标并存的结构，这消除了子目标间的相互干扰，使得优化算法能更直接、高效地搜索全局最优解并且明确将约束条件组合与路径生成解耦。在优化过程中可灵活集成不同的约束条件，而无需改变核心优化流程，为后续添加新的约束提供了清晰的模块化接口。

46、2、明确了至少包括无人机最大载重约束、无人机最大航程约束和无人机协同约束这几类核心约束，并将其融入到一个自动化的节点属性划分流程中，这种设计使得各类约束可以独立计算和校验，实现了约束条件的模块化管理，通过一套确定的规则来将随机节点序列转化为符合多重约束的唯一的可行配送方案，从而实现了单层优化逻辑，极大地提到了优化速度，并且为后续的优化迭代提供了高质量的初始解或邻域解。

47、3、确保在规划无人机配送段时，严格遵循无人机的物理能力限制。通过逐步试探并校验累计距离与累计重量，能够精准地确定一次无人机飞行所能覆盖的最远节点，从而保证生成的每一条无人机子路径都是实际可执行的，提高了方案的有效性与安全性。

48、4、增加了对节点序列边界的特判处理，使得算法逻辑更加严谨和完整，能够正确处理当无人机潜力巨大，可能覆盖后续几乎所有节点直至序列末尾的特殊情况，增强了算法的鲁棒性和处理各类场景的能力

49、5、一方面，通过引入第一时长与第二时长的比值，并设定一个合理的第一比例区间，该机制旨在为无人机和车辆匹配节奏相当的作业段落，这有助于减少车辆或无人机因等待另一方而产生的闲置时间，从而提升联合配送的整体协同效率；另一方面，通过筛选比值落在合理区间内的候选节点，并选择最接近区间中点的节点作为第三节点，该策略倾向于为车辆分配一个与刚刚完成的无人机配送段在耗时上相匹配的配送段，促进了两种运力之间的负载均衡，有利于进一步缩短总完工时间。