一种面向时间窗与容量约束的智慧物流车辆路径优化方法

本发明涉及智慧物流与运输路径优化，尤其涉及车辆路径规划、配送调度优化、二次无约束二值优化建模以及量子启发式组合优化求解技术，特别涉及一种面向时间窗与容量约束的智慧物流车辆路径优化方法。

背景技术：

1、随着电子商务、即时配送和智慧供应链的快速发展，物流配送系统的运行规模不断扩大，客户订单呈现出数量多、分布广、需求异构和时效要求高等特点；在实际配送过程中，物流企业不仅需要规划车辆从配送中心出发、访问多个客户节点并返回配送中心的行驶路线，还需要同时考虑客户需求量、车辆容量、客户服务时间、配送时间窗以及车辆协同调度等多种业务约束；因此，车辆路径规划与调度优化已成为提高物流配送效率、降低运输成本和提升服务质量的重要技术手段。

2、在实际智慧物流配送场景中，客户节点数量往往较多，且常伴随严格或软性的服务时间窗限制、多车辆容量约束以及客户访问唯一性约束等条件。特别是在无空闲等待规则下，车辆到达客户节点后必须立即开始服务，不能通过等待方式消除早到时间偏差，导致客户实际开始服务时刻完全由前序访问顺序、节点间运输时间和服务时间递推决定。此时，一旦客户访问顺序发生变化，后续客户的开始服务时刻、早到程度、晚到程度以及时间窗惩罚均会发生联动变化，使路径优化问题呈现出强耦合、高维度和离散组合爆炸等特点。

3、针对此类问题，现有技术中常采用启发式算法或元启发式算法进行求解，例如遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法及其混合改进方法等。上述方法在一定程度上能够降低求解复杂度，并获得可行路径方案，但在大规模客户节点、复杂时间窗惩罚和多车辆容量约束共同作用下，仍可能存在搜索过程依赖初始解、容易陷入局部最优、参数调节复杂、结果稳定性不足以及难以与新型量子优化求解框架直接适配等问题。

4、近年来，二次无约束二值优化模型，即 qubo 模型，为车辆路径规划等组合优化问题提供了新的建模方式。qubo 模型能够将原问题中的目标函数和约束条件通过罚函数机制统一转化为二值变量空间中的能量函数，从而适配量子退火、相干伊辛机以及量子启发式模拟退火等新型求解器。通过将客户访问顺序、路径代价和约束条件转化为 qubo 形式，可为复杂车辆路径优化问题提供一种面向量子计算或量子启发式计算的求解途径。现有研究和工程应用中已有将 qubo 建模与量子启发式求解用于车辆路径等组合优化问题的尝试，但相关方法多集中于基础路径排序或小规模约束场景，难以同时兼顾时间窗惩罚、大规模客户节点和多车辆容量约束等因素。

5、但是，若直接将大规模车辆路径问题完整转化为全局 qubo 模型，随着客户节点数量、车辆数量和访问位置数量的增加，二值变量规模和二次耦合项数量会迅速膨胀，导致求解器难以稳定求解。尤其在同时考虑服务时间窗、无空闲等待、客户唯一服务、车辆容量限制和多车辆协同调度时，若采用传统弧变量建模方式，还需引入复杂的子回路消除约束和大量辅助变量，不利于控制模型规模，也不利于 qubo 模型的紧凑表达。

6、此外，现有基于 qubo 的车辆路径优化方法多侧重于基础路径排序或简单旅行商问题，对时间窗惩罚、无空闲等待规则和多车辆容量约束的协同刻画仍不充分。一方面，若在 qubo 模型中直接引入真实开始服务时刻及其递推约束，将显著增加辅助变量和约束项，造成模型规模过大；另一方面，若仅以距离或运输时间作为优化目标，又难以反映客户时间窗违反带来的实际服务代价，导致求得的路径方案虽运输距离较短，但在真实配送评价中可能产生较大的早到或晚到惩罚。

7、在大规模客户配送场景下，客户节点数量增加还会进一步放大上述问题。单纯依靠全局 qubo 建模容易出现变量数量过多、求解时间过长和可行解筛选困难等问题；而单纯依靠传统启发式分解方法，又可能造成局部路径优化与全局路径评价口径不一致，难以兼顾运输时间、时间窗惩罚和车辆容量约束。对于多车辆配送场景，还需要同时确定车辆使用数量、客户分配关系以及各车辆内部访问顺序，其中车辆数量优化与路径代价优化之间具有明显的层次关系，若缺少合理的分层建模和迭代修正机制，则难以实现车辆数量最少与综合配送代价较优之间的统一。

8、鉴于此，申请人提出了一种面向时间窗与容量约束的智慧物流车辆路径优化方法。

技术实现思路

1、本发明的目的是为了解决现有二次无约束二值优化qubo等量化求解技术在处理车辆路径规划时，存在的必须显式引入大量连续的时间辅助变量以描述无空闲等待规则，且现有弧变量建模极易引入复杂的消除子回路约束的问题，从而导致智慧物流车辆路径优化主题存在模型求解空间呈指数级爆炸即变量膨胀，物流调度服务器在面对实际大规模客户订单时，面临极大的算力开销和内存占用，导致调度系统响应延迟高、甚至因硬件资源受限而无法求得满足物理装载容量与严苛配送时效的有效车辆调度方案的技术问题，而提出本发明的一种面向时间窗与容量约束的智慧物流车辆路径优化方法。

2、为了解决上述技术问题，本发明采用的技术方案为：

3、一种面向时间窗与容量约束的智慧物流车辆路径优化方法，包括以下步骤：

4、步骤1：获取智慧物流配送网络的基础数据，并设置决策变量，得到用于车辆路径优化的基础信息和二值决策变量；

5、步骤2：利用步骤1得到的基础信息和二值决策变量，构建包含约束惩罚和运输目标的数学表达式，得到基础目标函数；

6、步骤3：在步骤2得到的基础目标函数基础上，结合时间窗约束机制引入时间窗代理惩罚项，并基于历史优良路径构造引导项，得到嵌入时间窗违规风险的引导型代理目标函数；

7、步骤4：利用求解器对步骤3得到的引导型代理目标函数进行求解，并通过无空闲等待规则进行回代计算，筛选获得单车辆基础路径；其中，所述单车辆基础路径为经时间窗代理引导和真实回代评价后得到、用于后续多车辆客户分配和局部路径排序的单车辆候选路径；

8、步骤5：在大规模或多车辆配送场景下，基于客户时间窗差异、节点间运输时间和客户节点间空间距离数据构建综合距离矩阵，执行客户聚类、容量约束分配、各车辆局部路径排序和跨车辆迭代修正，最终获得多车辆路径优化结果。

9、步骤1具体包括以下子步骤：

10、步骤1-1）获取智慧物流配送网络的基础数据，基础数据包括配送中心节点、客户节点集合、客户需求量、客户服务时间、客户允许开始服务的时间窗上下界、节点间运输时间矩阵、客户节点间空间距离数据以及车辆容量上限，获得基础信息；

11、步骤1-2）基于客户访问顺序构建单车辆路径顺序编码模型，设置描述客户与访问位置对应关系的二值决策变量，结合基础信息，最终得到用于车辆路径优化的基础信息和二值决策变量。

12、在步骤1-1）中，配送网络节点集合表示为：

13、；

14、其中，节点 0 表示配送中心，客户节点集合表示为：

15、；

16、节点至节点的运输时间为，客户的需求量为，客户的服务时间为，客户的允许开始服务时间窗为：

17、；

18、其中，为客户允许开始服务的时间窗下界，为客户允许开始服务的时间窗上界，为客户节点总数；车辆最大载货容量为；客户与客户之间的空间距离为，需要特别说明的是，和均表示客户节点索引，且，表示当前访问位置对应的客户，表示与客户相邻或待比较的另一客户。

19、在步骤1-2）中，二值决策变量为，当时表示客户被安排在第

p个访问位置，当时表示客户不位于该访问位置，

p为代表车辆行车访问顺序位置的正整数索引。

20、步骤2具体包括以下子步骤：

21、步骤2-1）针对二值决策变量构建位置唯一性约束惩罚项；

22、步骤2-2）针对二值决策变量构建客户唯一性约束惩罚项；

23、步骤2-3）结合节点间运输时间矩阵和二值决策变量，构建描述车辆从配送中心出发并返回的单车辆闭环路径的运输时间目标函数；

24、步骤2-4）将位置唯一性约束惩罚项、客户唯一性约束惩罚项与运输时间目标函数进行组合计算，最终得到基础目标函数。

25、在步骤2-1）中，构建位置唯一性约束惩罚项采用的公式为：；

26、其中，为位置唯一性约束罚函数；

27、在步骤2-2）中，构建客户唯一性约束惩罚项采用的公式为；

28、其中，为客户唯一性约束罚函数；

29、在步骤2-3）中，构建运输时间目标函数采用的公式为：；

30、其中，为运输时间目标函数，表示配送中心至首个客户的运输时间，表示客户至客户的运输时间，表示客户返回配送中心的运输时间；

31、在步骤2-4）中，得到基础目标函数采用的公式为：，其中为单车辆基础目标函数，为用于提高违反约束能量代价的约束罚系数。

32、步骤3具体包括以下子步骤：

33、步骤3-1）按照无空闲等待规则，基于初始路径或历史优良路径构造锚点路径，并推演参考开始服务时刻序列；

34、步骤3-2）利用参考开始服务时刻序列与时间窗上下界，计算客户节点被安排在不同访问位置时的位置型时间窗代理代价；

35、步骤3-3）利用参考开始服务时刻序列与节点间运输时间矩阵，计算相邻转移型时间窗代理代价；

36、步骤3-4）将位置型时间窗代理代价和相邻转移型时间窗代理代价合并，并嵌入至基础目标函数中，获得代理目标函数；

37、步骤3-5）基于历史优良路径构造引导项加入代理目标函数中，最终得到用于求解的引导型代理目标函数。

38、在步骤3-1）中，参考开始服务时刻满足：

39、设锚点路径为，其中表示锚点路径中第个访问位置对应的客户节点，且任一客户节点在锚点路径中仅出现一次；

40、；

41、；

42、表示第p个访问位置对应的参考开始服务时刻，表示首个访问位置的参考开始服务时刻，为配送中心到首个锚点节点的运输时间，为锚点节点的服务时间，为锚点节点之间的运输时间，其中表示锚点路径中第个访问位置对应的客户节点，表示锚点路径中的首个客户节点；

43、在步骤3-2）中，计算位置型时间窗代理代价公式为：

44、；

45、其中，，为位置型时间窗代理项，为客户在

p个位置的代理时间窗惩罚，为早到惩罚系数，为晚到惩罚系数，与为最大值函数；

46、在步骤3-3）中，计算相邻转移型时间窗代理代价公式为：

47、；

48、其中，，，为相邻转移型时间窗代理项，表示该相邻转移关系下客户的时间窗代理惩罚，表示当客户位于第个访问位置，客户位于第个访问位置时，估算得到的客户的代理开始服务时刻；

49、在步骤3-4）中，获得代理目标函数公式为：

50、；

51、其中，为带时间窗代理代价的目标函数，为时间窗代理代价整体缩放系数，为位置型代理项权重系数，为相邻转移型代理项权重系数；

52、在步骤3-5）中，得到引导型代理目标函数公式为：

53、；

54、其中，，；

55、为加入锚点引导后的目标函数，为位置锚定奖励项的引导权重系数，为边连接奖励的引导权重系数，为锚点路径对应的客户-位置矩阵中取值为0或1的元素，当锚点路径中第个访问位置对应客户时，，否则，，为位置锚定奖励项，为边连接奖励项。

56、步骤4具体包括以下子步骤：

57、步骤4-1）利用量子启发式求解器求解引导型代理目标函数得到候选二值矩阵，将候选二值矩阵解码为候选客户访问序列；

58、步骤4-2）对候选客户访问序列进行合法校验，剔除不满足位置唯一性约束或客户唯一性约束的序列，保留可行候选路径；

59、步骤4-3）针对可行候选路径，按照无空闲等待规则逐点推演每个客户的真实开始服务时刻、早到时间偏差以及晚到时间偏差；

60、步骤4-4）结合早到时间偏差、晚到时间偏差与总运输时间，计算可行候选路径的真实综合目标值，最终筛选出真实综合目标值最小的路径作为单车辆基础路径，所述单车辆基础路径用于后续大规模客户分层处理或多车辆路径优化中的客户分配与局部排序；

61、在步骤4-1）中，候选客户访问序列表示为：；其中，表示单车辆闭环配送路径，表示第

p个访问位置对应的客户节点序号，；

62、在步骤4-2）中，合法校验需满足：

63、；

64、即要求只有当每个客户恰好出现一次且每个访问位置恰好对应一个客户时判定为合法；

65、在步骤4-3）中，推演真实开始服务时刻公式为：

66、，；

67、其中，为首个客户的真实开始服务时刻，为客户的真实开始服务时刻，为前序客户的服务时间，为前序客户至当前客户的运输时间；

68、早到时间偏差为；

69、其中，为客户的早到偏差，为客户的实际开始服务时刻；

70、晚到时间偏差为；

71、其中，为客户的晚到偏差；

72、在步骤4-4）中，计算真实综合目标值采用的公式为：

73、；其中，为真实综合目标值，为路径对应的真实路径总运输时间。

74、步骤5具体包括以下子步骤：

75、步骤5-1）基于节点间运输时间、客户时间窗差异和客户节点间空间距离数据构建综合距离矩阵，并根据综合距离矩阵将客户节点划分为若干客户簇，所述客户簇用于作为客户-车辆初始分配的候选结构，或用于限制后续客户移位与客户交换操作的搜索范围；

76、步骤5-2）基于客户总需求量和车辆最大载货容量，确定理论最小车辆数下界；

77、步骤5-3）构建客户-车辆分配规则，设置客户-车辆分配变量，在保证车辆装载量不超限的前提下，将客户节点划分至不同车辆服务集合；

78、步骤5-4）针对第辆车对应的客户服务集合，令，并在该客户子集上设置局部顺序编码变量，其中，将步骤2至步骤4中的客户集合、客户数量和二值变量分别替换为、和，计算第车辆的真实路径代价；

79、步骤5-5）在多车辆路径方案间执行客户移位与客户交换操作，计算各操作带来的目标增量，最终在满足车辆容量约束、客户唯一服务约束和车辆闭环约束的候选方案中，按照车辆使用数量优先、同等车辆数量下系统综合路径代价最小的字典序目标，选择多车辆路径优化结果；

80、在步骤5-1）中，综合距离矩阵采用公式：；其中，为客户与客户之间的综合距离，、、、分别为归一化后的节点间运输时间、时间窗中心差异、时间窗宽度差异和空间距离，，，，为满足和为1的权重系数；

81、在步骤5-2）中，确定理论最小车辆数下界公式为：，其中，；为理论最小车辆数下界，为全部客户总需求量，表示向上取整运算，为客户z的需求量；

82、在步骤5-3）中，客户-车辆分配变量为，，，其中为当前迭代考察的车辆数量，初始取；当表示客户分配给车辆

v，否则为0，

v为车辆标识索引；车辆装载量为：，容量约束为；

83、在步骤5-4）中，各车辆的真实路径代价公式为：，；其中，为第

v辆车的真实路径代价，为第v辆车的运输时间，为第

v辆车服务的客户数量，与分别为第

v辆车的第

k个访问客户的早到偏差和晚到偏差，若第辆车第个访问客户为,则，；为第

v辆车的时间窗惩罚；

84、在步骤5-5）中，跨车辆移位操作的目标增量公式为：，其中，为移位目标增量，、为原路径代价，、为新路径代价；

85、跨车辆交换操作的目标增量为：，其中，为交换目标增量，、为交换后的新路径代价，其中，和为参与客户移位或客户交换操作的两辆不同车辆的车辆索引，且；系统总综合目标值采用字典序目标公式：；其中，表示字典序最小化运算，即优先最小化车辆使用数量

k，当车辆使用数量相同时，再最小化系统综合路径代价；

86、最终输出结果包括车辆使用数量，各车辆服务客户集合，各车辆闭环访问路径，各客户实际开始服务时刻，各客户早到偏差和晚到偏差，各车辆运输时间，各车辆时间窗惩罚。

87、与现有技术相比，本发明具有如下技术效果：

88、1）本发明采用客户访问顺序编码方式建立客户—访问位置二值矩阵；该技术手段仅通过位置唯一性和客户唯一性两类约束即可刻画合法的物理行车路线结构，从根本上避免了传统弧变量建模中为了消除物理子回路而引入的复杂数学约束；此举缩减了qubo模型的维度，有效降低了底层计算硬件在路径搜索过程中的内存占用和算力消耗，提升了物流系统的调度响应速度；

89、2）针对时间窗约束导致模型庞大的技术难题，本发明创新性地提出了位置型时间窗代理代价与相邻转移型时间窗代理代价相结合的建模方式；该手段无需在模型中显式引入海量的连续服务时刻变量，而是将时间窗违约风险巧妙嵌入为qubo目标函数中的惩罚项，在保持模型紧凑性的同时，使得量子启发式等求解器能够顺利处理具有严格时效要求的实体物流网调度问题，避免了因模型超载导致的求解失败；

90、3）本发明采用代理qubo搜索—真实回代评价机制，在搜索阶段利用代理目标函数进行能量引导，而在结果输出前，统一按照实体物流场景中真实的“无空闲等待规则”逐点推演车辆真实的到达时刻、运输时间和时间窗惩罚；这一机制既兼顾了算法模型的求解效率，又确保了最终输出的车辆调度方案符合交通路况和客户业务规则，降低了因“早到”导致的车辆停车位占用或因“晚到”引发的时间窗违反带来的服务代价；

91、4）针对海量客户节点的实际物流场景，本发明构造了融合路网运输时间、时间窗中心差异、时间窗宽度差异以及客户节点间空间距离的综合距离矩阵，并采用了均衡聚类、簇间排序、簇内优化与全局修正的分层降维策略；该手段减小了直接构建超大规模全局qubo模型导致的系统崩溃风险，有效提高大规模客户路径规划的可计算性和方案生成效率；

92、5）针对多车辆固定容量的物理限制，本发明构建了外层客户分配 、内层单路线qubo 排序、跨车辆迭代修正协同配合的分解式协同优化框架；在满足客户唯一服务、单车物理装载量不超限以及实体路线闭环等硬性约束的前提下，优先压缩所需出车的物理数量上限，再优化综合行驶里程，从而在宏观上帮助物流企业最小化车辆采购及维护成本，在微观上降低车队的整体燃油或电力消耗；

93、6）本发明构建的紧凑型优化模型能够适配 kaiwu sdk 平台，并兼容模拟退火求解器、量子退火器、相干伊辛机等多种异构算力硬件；这使得该方法具备良好的技术迁移能力，企业可以低成本地将其集成至现有的智慧供应链 it 架构中，为未来全面接入量子计算算力奠定工程基础。