基于混合履约与异构编码的车机协同配送方法及系统

本发明属于无人配送路径规划与智能优化算法，特别涉及基于混合履约与异构编码的车机协同配送方法及系统。

背景技术：

1、近年来，无人车与无人机协同配送模式因其兼具无人车大载重、长续航与无人机高机动性、低空直达的双重优势，已成为解决城市末端物流配送“最后一公里”成本高企、时效性差等问题的重要技术路径。该模式通过空地载具的协同配合，可有效兼顾大载重长距离运输与灵活快速直达客户的双重要求，具有显著的经济效益和应用前景。

2、在空地协同配送系统中，汇合点决策是连接无人车与无人机作业的核心环节。现有汇合点决策方式主要分为两大类。第一类为连续空间动态会合模式，即允许无人机与无人车在二维平面内的任意位置完成物资交接。然而，该类方法的决策变量维度随客户规模呈指数级增长，导致计算复杂度过高，难以支撑中等及以上规模配送网络的实时求解需求。连续空间动态会合在城市末端配送这类对实时性有要求的场景中难以实际应用。第二类为固定停靠点模式，即将汇合点预设为有限个固定候选位置，通过离散化压缩决策空间以降低计算负担。然而，该类方法的汇合点位置一旦确定便无法随客户空间分布变化而动态调整，容易导致无人机末端飞行距离过长，汇合布局缺乏对客户分布的自适应性。

3、此外，在客户履约模式方面，现有研究普遍默认所有客户均需经过“无人车转运至汇合点、无人机从汇合点起飞完成末端配送”的完整协同流程。现有方法对所有客户统一采用车机协同模式进行配送。然而，对于距离配送中心较近、配送物资重量较轻的客户而言，由无人机直接从配送中心直送往往更为经济高效，无需经过无人车转运环节。若对近距离轻载客户仍强制采用车机协同流程，将导致无人车运输资源的浪费，增加了系统整体运营成本。

4、综上，现有技术中尚缺乏一种能够同时兼顾汇合点布局对客户空间分布的自适应能力、配送模式根据客户特征的内生差异化选择、以及异构决策变量在统一框架下协同优化的配送技术方案。特别是在汇合点激活状态发生变化时，现有方法通常需要分阶段重新计算客户归属与车辆路径，或将上述调整作为独立的修复步骤事后处理，缺少一种以激活状态变化为触发事件、同步联动更新汇合点激活层、客户归属层与无人车路径层的一体化编码层联动机制。

5、需要说明的是，在上述背景技术部分公开的信息仅用于加强对本发明的背景的理解，因此可以包括不构成对本领域普通技术人员已知的现有技术的信息。

技术实现思路

1、为了解决或至少缓解以上问题中的一个或多个，提供了一种基于混合履约与异构编码的车机协同配送方法及系统，不仅能通过离散候选汇合点的动态激活实现汇合布局对客户分布的自适应调整，更能通过混合履约预划分机制将纯无人机直送与车机协同配送两类模式内生于同一优化框架，同时借助三层异构编码实现汇合点激活、客户指派与车辆路径三类变量的协同进化，并通过建立汇合点激活状态变化触发的三层编码联动更新机制，实现激活层、归属层与路径层的同步联动更新与一致性保持，最终输出兼顾经济性与时效性的最优配送方案。

2、为实现上述目的，按照本发明的第一方面，提供基于混合履约与异构编码的车机协同配送方法，包括以下步骤：

3、s1、获取配送网络数据，对所有客户执行混合履约预划分，将客户标记为纯无人机直送模式或车机协同配送模式；

4、s2、对车机协同配送模式客户的坐标进行聚类，生成有限个离散候选汇合点，并建立各车机协同配送客户与候选汇合点之间的初始归属关系；

5、s3、构建三层异构编码染色体，统一表征汇合点激活状态、客户至汇合点的无人机指派关系以及无人车访问汇合点的顺序；

6、s4、采用遗传算法对由所述三层异构编码染色体构成的种群进行迭代进化，在迭代过程中分别对汇合点激活编码层、客户归属编码层和无人车路径编码层执行适配各自编码特点的交叉操作和变异操作；

7、s5、在交叉操作或变异操作后，检测汇合点激活编码层中各候选汇合点的激活状态是否发生变化；当候选汇合点由激活状态变为未激活状态时，将当前归属于该汇合点的全部车机协同配送客户重新分配至其他已激活且满足载重和航程约束的汇合点，并从无人车路径编码层中删除该汇合点；当候选汇合点由未激活状态变为激活状态时，从当前归属于其他已激活汇合点的车机协同配送客户中选择距离该汇合点最近的客户，将其归属更新至该新激活汇合点，并将该汇合点按最近邻原则插入无人车路径编码层；对汇合点激活编码层、客户归属编码层和无人车路径编码层执行同步写回，形成更新后的完整染色体；

8、s6、对更新后的染色体依次执行汇合点-客户归属-无人车路径一致性校验、无人机载重与航程校验以及客户软时间窗校验，根据校验结果对染色体进行相应修复，并计算修复后染色体的适应度；

9、s7、以配送时间、运营成本及时间窗惩罚的加权和最小化为优化目标进行迭代，当满足预设收敛条件时，解码最优染色体并输出最终配送方案。

10、进一步地，所述配送网络数据包括配送中心位置、客户点位置及物资重量、客户软时间窗、候选汇合点位置、无人车与无人机的速度及单位运营成本、无人机最大载重及最大航程、无人车电池容量及安全预留电量。

11、进一步地，混合履约预划分包括：

12、计算各客户到配送中心的欧氏距离；当客户到配送中心的欧氏距离小于预设距离阈值，且该客户的需求重量小于预设重量阈值时，将该客户标记为纯无人机直送模式；否则标记为车机协同配送模式；

13、被标记为纯无人机直送模式的客户，由无人机直接从配送中心起飞完成配送并返航，不占用无人车和汇合点资源；被标记为车机协同配送模式的客户，由无人车将配送物资运送至对应汇合点后，再由无人机从汇合点起飞完成末端配送；

14、所述纯无人机直送模式和车机协同配送模式在整个优化过程中共存，且各客户的模式标记在预划分完成后保持不变。

15、进一步地，三层异构编码染色体具体包括：

16、采用二进制编码表示各候选汇合点激活状态的汇合点激活编码层，其长度等于候选汇合点总数，字符串中每一位对应一个候选汇合点，取值为1时表示该候选汇合点处于激活状态，取值为0时表示该候选汇合点处于未激活状态；

17、采用整数编码表示各车机协同配送客户所归属汇合点编号的客户归属编码层，其长度等于车机协同配送模式客户的总数，数组中每个元素的值表示对应客户被指派到的汇合点编号，且客户仅能被分配至汇合点激活编码层中处于激活状态的汇合点；

18、采用排列编码表示无人车访问已激活汇合点顺序的无人车路径编码层，其长度等于汇合点激活编码层中处于激活状态的汇合点的数量，序列中的元素表示无人车访问已激活汇合点的先后顺序，且仅包含汇合点激活编码层中取值为1的汇合点；

19、三层编码共同构成一条完整染色体，共享同一适应度函数进行评价，且客户归属编码层的长度和无人车路径编码层的长度均随汇合点激活编码层中激活状态的变化而动态调整。

20、进一步地，生成离散候选汇合点和初始归属关系，包括：

21、对全部车机协同配送模式客户的二维空间坐标执行k-means聚类，将各聚类中心作为初始离散候选汇合点，并将属于同一聚类簇的客户初始分配至对应的候选汇合点；

22、以配送中心为起点，将全部已激活汇合点组成未访问集合，每次从所述未访问集合中选择距离当前位置最近的汇合点，将其加入无人车路径并将该汇合点作为新的当前位置，重复执行直至全部已激活汇合点均被访问，最后返回配送中心，得到无人车初始闭环路径；

23、通过多次执行客户聚类、初始归属分配和最近邻路径生成操作，生成预设数量的初始个体，并由所述初始个体组成遗传算法的初始种群。

24、进一步地，当候选汇合点由激活状态变为未激活状态时，包括：

25、遍历客户归属编码层，查找当前归属于该待关闭汇合点的全部车机协同配送客户，形成待重新分配客户集合；

26、对于所述待重新分配客户集合中的每个客户，计算该客户到其余各已激活汇合点的距离，优先选择距离最近的已激活汇合点作为候选目标汇合点，并检查将该客户转移至所述候选目标汇合点后，该候选目标汇合点对应的无人机配送任务是否满足最大载重和最大航程要求，若不满足则顺次选择距离次近的已激活汇合点；

27、完成全部待重新分配客户的归属更新后，将客户归属编码层中相应客户的汇合点编号更新为新的目标汇合点编号，并从无人车路径编码层中删除已关闭汇合点对应的元素。

28、进一步地，当候选汇合点由未激活状态变为激活状态时的具体处理方式为：

29、计算各车机协同配送客户到该新激活汇合点的距离，从当前归属于其他已激活汇合点的客户中，选择距离该新激活汇合点最近的客户，将其在客户归属编码层中的归属关系更新为该新激活汇合点；

30、将新激活汇合点加入已激活汇合点集合，以配送中心为起点，将更新后的全部已激活汇合点组成未访问集合，每次选择距离当前位置最近的未访问汇合点加入无人车路径并将其作为新的当前位置，重复执行直至全部已激活汇合点均被访问，最后返回配送中心，得到更新后的无人车路径编码层。

31、进一步地，适配各编码层特点的交叉操作和变异操作具体为：

32、对汇合点激活编码层采用两点交叉和位翻转变异，其中两点交叉随机选择两个交叉位置并交换两个父代个体在所述两个交叉位置之间的二进制段，位翻转变异随机选择一个基因位并将其二进制值取反；

33、对客户归属编码层采用单点交叉和单基因随机替换变异，其中单点交叉随机选择一个交叉位置并交换两个父代个体在所述交叉位置之后的整数段，单基因随机替换变异随机选择一个基因位并将其替换为其他已激活汇合点的编号；

34、对无人车路径编码层采用部分匹配交叉和交换变异，其中部分匹配交叉随机选择两个交叉位置，交换两个父代个体在所述两个交叉位置之间的排列段并通过部分映射修复重复元素，交换变异随机选择两个基因位并交换其位置。

35、进一步地，多级约束校验与修复包括：

36、首先执行汇合点-客户归属-无人车路径一致性校验：检查客户归属编码层中各客户是否被分配至汇合点激活编码层中处于激活状态的汇合点，检查无人车路径编码层中是否包含未激活汇合点，以及检查承担客户配送任务的已激活汇合点是否均包含在无人车路径编码层中；若存在不一致，则对客户进行重新指派或对无人车路径进行修正；

37、一致性校验通过后，执行无人机载重与航程校验：对各已激活汇合点对应的全部无人机配送任务的货物总重量和飞行总距离进行核算，判断是否超过无人机最大载重和最大航程限制；若出现超限，则将导致超限的客户转移至邻近且未超限的其他已激活汇合点，并重新进行载重与航程校验；

38、载重与航程校验通过后，执行客户软时间窗校验：检查各客户的实际配送完成时间是否晚于预设的最晚配送时间；对于迟到时间超过预设容忍范围的客户，将该客户重新分配至无人车能够较早到达的已激活汇合点，或者调整该客户对应汇合点在无人车路径编码层中的访问顺序，以减少时间窗违约程度。

39、为实现上述目的，按照本发明的第二方面，提供基于混合履约与异构编码的车机协同配送系统，包括：

40、混合履约预划分模块，用于获取配送网络数据，对所有客户执行混合履约预划分，将客户标记为纯无人机直送模式或车机协同配送模式；

41、离散汇合点管理模块，用于对车机协同配送模式客户的坐标进行聚类，生成有限个离散候选汇合点，并建立各车机协同配送客户与候选汇合点之间的初始归属关系；

42、三层协同进化模块，用于构建三层异构编码染色体，统一表征汇合点激活状态、客户至汇合点的无人机指派关系以及无人车访问汇合点的顺序；

43、采用遗传算法对由所述三层异构编码染色体构成的种群进行迭代进化，在迭代过程中分别对汇合点激活编码层、客户归属编码层和无人车路径编码层执行适配各自编码特点的交叉操作和变异操作；

44、在交叉操作或变异操作后，检测汇合点激活编码层中各候选汇合点的激活状态是否发生变化；当候选汇合点由激活状态变为未激活状态时，将当前归属于该汇合点的全部车机协同配送客户重新分配至其他已激活且满足载重和航程约束的汇合点，并从无人车路径编码层中删除该汇合点；当候选汇合点由未激活状态变为激活状态时，从当前归属于其他已激活汇合点的车机协同配送客户中选择距离该汇合点最近的客户，将其归属更新至该新激活汇合点，并将该汇合点按最近邻原则插入无人车路径编码层；对汇合点激活编码层、客户归属编码层和无人车路径编码层执行同步写回，形成更新后的完整染色体；

45、多约束校验模块，用于对更新后的染色体依次执行汇合点-客户归属-无人车路径一致性校验、无人机载重与航程校验以及客户软时间窗校验，根据校验结果对染色体进行相应修复，并计算修复后染色体的适应度；

46、配送方案输出模块、以配送时间、运营成本及时间窗惩罚的加权和最小化为优化目标进行迭代，当满足预设收敛条件时，解码最优染色体并输出最终配送方案。

47、采用上述技术方案后，本发明与现有技术相比具有以下有益效果：

48、本发明通过离散候选汇合点动态激活与混合履约预划分机制，将连续决策空间压缩为有限候选点集，并依据客户距离与物资重量预先分流纯无人机直送订单，从而降低计算复杂度并避免运力浪费；同时采用三层异构编码与联动更新机制，使汇合点激活、客户指派和路径顺序在同一染色体中协同进化，保证决策一致性；配合多级约束校验与加权单目标函数，在贴近实际时效成本权衡的同时提升求解质量与工程可行性，各模块通过标准化接口解耦，具备良好的可扩展性与维护性。

49、具体地，本发明通过离散候选汇合点动态激活机制，将汇合决策空间从无限连续域压缩为有限离散候选点集合，大幅降低了计算复杂度；同时通过编码中汇合点激活位随迭代动态优化，使汇合布局能够根据客户空间分布自适应调整，具有明确的工程实用性和场景适应性。

50、具体地，本发明通过混合履约预划分机制，根据客户距离配送中心的远近及物资重量，在编码生成前将客户划分为纯无人机直送与车机协同配送两类模式，纯无人机直送客户无需经无人车转运，可直接由无人机从配送中心完成配送，避免了所有客户一律采用车机协同流程所导致的近距离轻载客户运力浪费问题，有效降低了系统总运营成本。

51、具体地，本发明通过三层异构编码机制，将汇合点激活状态、客户至汇合点的无人机指派关系以及无人车访问汇合点的顺序三类异构决策变量统一编码至同一染色体中，三层编码在进化过程中共享同一适应度函数进行协同进化，避免了分阶段优化或独立编码导致的变量耦合关系割裂与局部最优问题，提高了求解质量。

52、具体地，本发明通过汇合点激活状态变化触发的三层编码联动更新机制，当汇合点由激活变为未激活时自动重新分配客户并从路径中删除该汇合点，当汇合点由未激活变为激活时自动将邻近客户归属至该汇合点并采用最近邻算法插入路径，使激活层、归属层和路径层的更新同步完成，从结构上避免了三层编码之间的不一致问题。

53、具体地，本发明通过依次执行一致性校验、载重与航程校验和软时间窗校验的多级约束处理机制，对三类决策变量之间的一致性和物理约束进行定向校验与修复，避免了传统罚函数法需反复调参且无法保证可行解的固有缺陷，提高了算法的工程实用性与收敛效率。

54、具体地，本发明将配送时间、运营成本与时间窗惩罚纳入统一的加权单目标函数，并在时间窗处理中仅对迟到客户施加线性惩罚，早到客户不产生惩罚成本，使目标函数更贴合实际运营场景中对时效性与经济性的综合权衡需求。

55、具体地，本发明通过将离散汇合点管理模块、三层协同进化模块与多约束校验模块划分为独立的可交互功能单元，各模块之间通过标准化的输入输出接口进行数据传递，使系统具备良好的可扩展性与维护性。

56、下面结合附图对本发明的具体实施方式作进一步详细的描述。