基于双角色无人机和车辆协同的取送货路径规划方法、设备及介质

本发明涉及取派件路径规划领域，尤其是涉及一种基于双角色无人机和车辆协同的取送货路径规划方法、设备及介质。

背景技术：

1、取派件问题（pdp）要求在最小化成本的条件下完成三类任务：仅取件任务、仅派件任务，以及配对的取件-派件任务。对于配对任务，从取件点收取的货包必须被送达其对应的派件点，这一前序约束使pdp比纯派件问题更为复杂。随着电子商务和即时配送的快速发展，高效pdp解法的需求日益迫切。

2、无人机因速度快、不受路面交通拥堵影响而在物流配送中受到广泛关注。但无人机受载重和电池容量限制，飞行范围有限，每次飞行只能携带有限数量的货包，完成配送或电量耗尽后须返回补给点充电补货。与之互补的是，车辆运输范围长、载重大，但速度慢且易受交通拥堵影响。研究人员因此提出以车辆作为无人机移动仓库和充电站的协同模式，充分发挥两者的互补优势。

3、在末端配送运营中，最主要的成本驱动因素并非行驶距离，而是每个已部署车辆-司机单元的固定成本，包括车辆保险、司机薪资，以及因人员流失率高（早期员工流失率通常超过60%）而持续产生的招募、入职和培训成本。任何能够减少完成既定任务所需车辆-司机单元数量的策略，都将直接降低末端物流最主要的成本压力。

4、现有主流无人机-车辆协同策略存在以下局限：每辆车辆通常仅携带单架无人机，且每个车辆-无人机配对单元在整个配送过程中保持固定绑定。

5、随着车辆载机技术进步，单辆车辆已可携带5架以上无人机。但现有策略仍将无人机限制为隶属于其指定车辆的独立运营单元，严重制约了协同灵活性：无人机即使在其他更近的车辆处能服务更多任务，也必须返回指定车辆；一旦某个车辆-无人机单元完成取件，即使其他单元在成本上更适合完成对应的派件任务，该单元也必须独立完成派件，无法将包裹转移。

6、因此，亟需设计一种解决末端配送场景中固定绑定策略导致无人机利用率低且车辆-无人机部署成本高的复杂调度难题。

技术实现思路

1、本发明的目的就是为了克服上述现有技术存在的缺陷而提供了一种基于双角色无人机和车辆协同的取送货路径规划方法、设备及介质，旨在解决末端配送场景中任务类型多样（仅取件、仅派件、配对取派件）、配对任务存在严格前序约束、固定绑定策略导致无人机利用率低且车辆-无人机部署成本高的复杂调度难题。

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

3、根据本发明的第一方面，提供了一种基于双角色无人机和车辆协同的取送货路径规划方法，包括：

4、s1，在任务点对应的空间区域内配置至少一辆车辆和多架无人机，将车辆配置为包裹存储移动仓库及无人机起降平台，将无人机配置为执行任务和/或车辆间的包裹转移，无人机完成服务后降落于可用的车辆上，以仓库和任务点为节点，构建送货任务图；

5、s2，基于取送货任务图，生成贪婪初始解：首先，将所有纯取货点和纯送货点分配给车辆，构建车辆初始路径；其次，将成对取送货任务点插入车辆路径中；最后，将满足无人机能耗约束的任务点改由无人机服务，构造贪婪初始解；

6、s3，将贪婪初始可行解编码为每个任务点的四元组，分别对应于任务点编号、无人机标签、包裹转移索引和起飞点索引；

7、s4、基于总成本目标函数和约束条件，在编码后的贪婪初始可行解基础上，在禁忌搜索框架内循环调用邻域搜索算子进行寻优，所述邻域搜索算子包括交换算子、变异算子和插入算子，满足终止条件后解码输出最优车辆-无人机协同规划路径。

8、优选地，所述以仓库和任务点为节点，构建送货任务图，其中，节点集由仓库节点0与任务点节点集合构成，为任务点节点数，边集合。

9、优选地，所述将满足无人机能耗约束的任务点改由无人机服务，具体为：对于任务点，若从车辆路径上的起飞点到任务点再到降落点的无人机能耗不超过无人机最大电池容量，则将任务点改由无人机服务。

10、优选地，所述将贪婪初始可行解编码为每个任务点的四元组，分别对应于任务点编号、无人机标签、包裹转移索引和起飞点索引，具体包括：

11、基于车辆路径的分配机制编码，将贪婪初始可行解编码为关于每个任务点的四元组（）；

12、其中，

13、为任务点编号，其中，时对应于仓库；

14、为无人机标签，通过数值编码表示为：当前任务点由无人机在执行飞行中服务，车辆执行当前任务点并从此处发射无人机，车辆执行当前任务点并在此处接收无人机降落，以及车辆执行当前任务点并在此处接收无人机降落；

15、为包裹转移索引，其中表示无转移，非零时，表示无人机飞行承担包裹转移任务，其值为所转移包裹对应的取货任务点编号或送货任务点编号；

16、为起飞点索引，表示无人机起飞的任务点编号。

17、优选地，所述无人机标签，具体编码设置为：

18、，表示当前任务点由无人机在执行一次飞行中连续服务，多个连续的对应同一架无人机在一次起飞后依次服务的多个任务点；

19、，表示车辆服务当前任务点，并在当前任务点处发射一架无人机，后续任务点由所述发射的无人机执行，直至遇到的降落点；

20、，表示车辆服务当前任务点，并在当前任务点处接收一架无人机降落，并通过起飞点索引记录当前任务点为接收的无人机起飞的任务点编号；

21、，表示当前任务点仅由车辆服务，不涉及任何无人机操作；

22、其中，、、和为设置的四个不同的编码整数值。

23、优选地，所述邻域搜索算子包括交换算子、变异算子和插入算子，具体为：

24、（1）交换算子，包括：

25、任务点交换算子，随机选择两个由车辆执行的任务点，交换其在车辆路径中的位置；

26、无人机标签交换算子，随机选择一个由无人机执行的任务点和一个由车辆执行的任务点，将无人机飞行的降落点改为该车辆任务点，同时更新相关和值；以及，

27、无人机包裹转移交换算子，随机选择一个转移包裹和一个同一起飞点路径内的车辆任务点，将该转移飞行的起飞点移至该车辆任务点，并更新值；

28、（2）变异算子，包括：

29、无人机任务变异算子，随机选择一个由无人机执行的任务点，将其转换为由车辆服务，并相应调整起飞点和降落点的值；若该无人机飞行仅有一个任务点，则删除整个飞行；以及，

30、车辆任务变异算子，随机选择一个由车辆执行的任务点，将其转换为由无人机服务，并寻找相邻的任务点作为起飞点和降落点，更新和值；以及，

31、（3）插入算子，包括：

32、插入仓库算子，随机选择一个由车辆执行的任务点，在其前面插入仓库节点0，将原车辆路径分割为两条；

33、插入车辆路径算子，随机选择一个由无人机执行的任务点，将其插入到某车辆路径中由车辆执行的任务点之后，并标记为车辆服务；

34、插入无人机飞行算子，随机选择一个由车辆执行的任务点，将其插入到某无人机飞行的任务点序列中，并标记为无人机服务。

35、优选地，所述约束条件包括：

36、（1）先取后派前序约束，即配对任务的取件任务点须在派件任务点之前完成服务：

37、，

38、式中：为任务点节点集合，为任务节点数；为无人机在取件任务点处的离开时刻，为车辆在取件任务点处的离开时刻；为无人机在派件任务点处的到达时刻；为车辆在派件任务点处的到达时刻；表示无人机是否服务任务点,1表示执行任务点，0表示非无人机执行该任务点；每个任务点由车辆或无人机执行一次；

39、（2）无人机单次飞行能耗约束：

40、，

41、式中：为无人机从任务点到任务点的飞行能耗；为取送货任务图中的边集合；为无人机集合；为无人机最大电池容量；为表征无人机是否从任务点飞到任务点的二进制变量，表示无人机从任务点飞到任务点；

42、（3）三节点飞行路径综合能量约束，保证无人机在动态跨卡车协同过程中，从起飞节点经任务节点到回收节点的完整航迹满足电量约束，使生成的空地协同方案具有实际可执行性：

43、，

44、式中：为无人机从任务点到任务点的飞行能耗；为无人机在任务点的执行任务能耗；为无人机在任务点的悬停等待时间能耗；为无人机在任务点降落的等待车辆能耗；表示无人机服务任务点；

45、（4）到达时间与行驶时间一致性约束：

46、，

47、式中：为从任务点到任务点的距离；为无人机飞行速度；为取送货任务图中的节点集合；为任意大的正数；

48、（5）无人机载重跟踪约束：

49、，

50、式中：、分别为无人机在任务点、任务点的负载；为任务点的需求量；为无人机最大载重；

51、（6）车辆载重跟踪约束：

52、，

53、式中：为车辆最大载重；为车辆集合。

54、优选地，所述总成本目标函数包括车辆行驶成本、无人机能耗成本及固定部署成本，数学表达式为：

55、，

56、，

57、，

58、，

59、，

60、式中：为总成本目标函数；为无人机从任务点到任务点的飞行能耗；为无人机在任务点的执行任务能耗；为无人机在任务点的悬停等待时间能耗；为无人机在任务点降落的等待车辆能耗；为单位能耗系数；为无人机自重；、、分别表示无人机在任务点、任务点、任务点的载重，为本次飞行中无人机最后执行的任务点；为从任务点到任务点的距离；为无人机飞行速度；为任务点的需求量；为任务点的服务时长，为任务点的悬停时长；表示车辆是否从任务点行驶到任务点的判断变量；成本系数表示车辆单位距离成本，成本系数表示无人机单位能耗成本、成本系数表示每部署一个无人机-车辆对的固定成本；

61、当无人机执行车辆间的纯包裹传递时，仅计入飞行能耗和等待车辆能耗；当无人机在同一次飞行中同时执行任务并传递货包时，其载重包含有待传递货包重量。

62、根据本发明的第二方面，提供了一种电子设备，包括存储器和处理器，所述存储器上存储有计算机程序，所述处理器执行所述程序时实现任一项所述的方法。

63、根据本发明的第三方面，提供了一种计算机可读存储介质，其上存储有计算机程序，所述程序被处理器执行时实现任一项所述的方法。

64、与现有技术相比，本发明具有以下优点：

65、（1）针对现有无人机-车辆协同策略中无人机与车辆固定绑定、无法在不同车辆间动态降落以及无法在车辆之间转移包裹的核心局限，本发明通过赋予无人机双重角色能力：一方面作为末端执行器高效完成各类任务点的服务，另一方面作为包裹流转中继在车辆之间动态传递已取件包裹。从根本上打破传统固定绑定策略中同一车辆-无人机单元必须独立完成配对任务取件与派件的刚性约束，实现跨单元、跨车辆的柔性协同。

66、（2）本发明设计了基于车辆路径的分配机制，将解表示为每个任务点的四值编码（任务点编码、无人机标签、无人机载荷、无人机索引），将任务点访问序列、无人机起降标记、包裹传递标识以及飞行追溯信息进行紧密耦合，从而能够精确刻画无人机在不同车辆间动态起降、跨单元传递包裹、以及在单次飞行中同时执行任务与转移包裹的复杂时空动态关系。

67、（3）采取三阶段贪婪初始化策略以及禁忌搜索深度寻优的双层逻辑：首先依据车辆载重、任务点时间窗口、配对任务前序约束及无人机最大电池容量等硬性约束，通过最近邻插入、配对任务嵌入和任务主体再分配三个阶段快速构建一个满足基本可行性的初始解；随后，引入禁忌搜索算法框架，通过设计三类多层级的邻域搜索算子，涵盖任务点交换、无人机标签交换、包裹传递交换的交换算子，无人机任务与车辆任务互转的变异算子，以及插入仓库节点、插入车辆执行、插入无人机执行的插入算子；在解空间内进行高效邻域搜索。特别地，插入仓库节点算子可将一条车辆路线动态分裂为两条，使算法能够自适应调整所部署的车辆-无人机单元总数，在解质量与部署成本之间实现最优平衡。

68、（4）本发明寻优过程中受控于一个综合目标函数，该函数动态权衡了车辆行驶成本、无人机全程能耗以及车辆-无人机固定部署成本，从而确保输出的路径方案既满足所有时间窗口约束、先取后派前序约束和能量可行性约束，又能在末端配送场景下以最少的单元部署实现最低总成本。