基于蚁群算法与Q-Learning融合的城市末端配送路径动态规划方法与流程

本发明涉及智能物流路径规划，具体为基于蚁群算法与q-learning融合的城市末端配送路径动态规划方法。

背景技术：

1、城市末端配送面临订单波动、交通拥堵和配送时间窗约束等多重动态因素，需要在短时间内生成满足多约束的高质量配送路径。现有的路径规划方法主要依赖蚁群算法、遗传算法等群体智能算法，或单独使用q-learning、深度q网络等强化学习算法进行单智能体路径决策。蚁群算法通过信息素的正反馈机制逐步逼近最优解，在静态环境中有较好表现，但在交通状态频繁变化的情况下，信息素更新滞后于环境变化，容易导致已收敛路径失去时效性，且传统蚁群算法仅依赖路径长度等因素更新信息素，无法刻画节点状态的长期价值差异。单独的q-learning方法通过试错学习状态-动作价值，可以自适应动态环境，但面对大规模节点和多配送任务时，状态空间和动作空间急剧膨胀，单智能体探索效率低下，难以在可接受时间内收敛到有效路径。

2、将群体智能与强化学习简单串行结合，如先用蚁群生成候选解再用q-learning微调或反过来，仍未能充分利用两种机制在搜索过程中的互补信息，蚁群的探索过程缺乏对节点长期价值的感知，而q-learning的价值更新也缺少群体经验的有效引导。如何在蚂蚁的逐步决策中实时引入学习得到的节点价值，以及如何利用已学到的状态价值差异反向修正蚁群的信息素积累，是实现两种算法深度融合并提升动态路径规划效率的两个关键问题。

技术实现思路

1、本发明提供一种基于蚁群算法与q-learning融合的城市末端配送路径动态规划方法，以解决现有技术在动态环境下路径规划寻优速度慢、信息素更新无法反映节点长期价值差异的问题，实现蚁群探索与强化学习价值评估的在线互馈，显著提升动态配送路径的生成质量和实时响应能力。

2、为了实现上述目的，本发明提供如下技术方案：本发明提供一种基于蚁群算法与q-learning融合的城市末端配送路径动态规划方法，该方法将蚁群算法的分布式搜索能力与q-learning的自适应决策能力相结合，在动态交通环境下实时生成兼顾配送效率与时间窗约束的最优路径。为实现该目的，本发明的技术方案包括：

3、步骤s1，采集实时配送任务集与路网动态交通数据，构建包含节点状态和边通行时间的动态环境模型。优选的，构建动态环境模型时，将配送区域划分为多个网格节点，每个节点关联实时交通拥堵系数和配送时间窗约束，并根据实时交通数据动态更新节点间的通行时间作为边权重，从而准确反映路网状态变化和对配送时效的要求。

4、步骤s2，初始化蚁群算法的蚂蚁数量、信息素初始浓度以及q-learning的状态-动作价值表。作为优选的初始化方式，为每个网格节点定义状态空间，该状态空间由当前时间窗剩余时长和节点拥堵等级组成；为每个状态分配可行动作集合，所述可行动作集合包含通往相邻节点的各条边；将q表中所有状态动作对的初始值设为0，为后续学习和搜索提供统一起点。

5、步骤s3，每只蚂蚁依据结合当前q值与启发式信息的概率转移规则选择下一节点，并在移动过程中利用时序差分误差更新q值。其中，概率转移规则设计为：对于当前蚂蚁所在节点i，计算每个候选下一节点j的转移概率，该转移概率正比于节点i到节点j边上的信息素浓度、q表中状态i下动作j的q值的指数函数，以及启发式信息的β次方三者的乘积；所述启发式信息为边通行时间的倒数。由此，蚂蚁在选择路径时既受群体信息素引导，又综合了q学习对长期价值的评估，有效兼顾局部通行成本和全局配送效率。

6、当蚂蚁从节点i移动到节点j后，立即获得即时奖励，该即时奖励为负的边通行时间与时间窗违反惩罚之和；计算时序差分误差，该误差等于即时奖励加上折扣因子乘以节点j的最大q值，再减去节点i下动作j的当前q值；使用该误差乘以学习率对节点i下动作j的q值进行更新，使个体经验能够在线积累并自适应调整转移倾向。

7、作为更优选的实施方式，每只蚂蚁在移动过程中还执行局部信息素更新：蚂蚁每经过一条边，立即在该边上减少一定比例的信息素，以减少后续蚂蚁盲目跟随同一路径的概率，且所述局部信息素减少比例由当前边上的q值偏差动态调节。这一联动机制在保持种群多样性的同时，利用q值偏差灵敏反映路径质量的相对变化，显著降低了算法陷入局部最优的风险。

8、步骤s4，完成一轮迭代后，根据蚂蚁路径的累计配送时间与q值偏差修正信息素增量，进而更新全局信息素。具体的修正方式为：对于蚂蚁k走过的每条边，计算该边的基准信息素增量，该基准信息素增量等于蚂蚁k完成配送的总时间倒数；计算该边两端节点状态的q值偏差，所述q值偏差为节点j的最大q值减去节点i的最大q值；将基准信息素增量乘以偏差因子，该偏差因子为1加上q值偏差与预设幅度的乘积，得到修正信息素增量。更新全局信息素时，对所有边上的信息素进行挥发，挥发后的信息素等于当前信息素乘以挥发残留系数；对每只蚂蚁走过的边，将修正信息素增量累加到挥发后的信息素上；并对超出信息素上限的边进行截断处理。通过q值偏差修正信息素，使高价值路径获得更强正反馈，低价值路径的信息素被抑制，从而加快收敛速度并提升解的质量。

9、步骤s5，重复步骤s3和步骤s4直至收敛，输出当前最优配送路径。判断收敛的条件为：连续多轮迭代中最佳路径总时间的变化幅度低于预设阈值，或者达到最大迭代次数。在输出最优配送路径的同时，还输出该路径对应的q值序列，为后续路径微调和快速重规划提供量化依据。

10、本发明提供的方法具备突出的动态适应能力，步骤s1中还实时接收配送任务变更和交通事件信息。在步骤s5收敛后，若存在未完成的配送任务或路网状态发生显著变化，则重新触发步骤s2至步骤s5，对剩余未完成的配送任务进行动态重规划。尤其在重新初始化q表时，保留原有q表中未受影响区域的状态-动作价值作为先验知识，使新规划过程能够复用已学经验，在动态环境中快速收敛至新的最优配送路径，显著提升末端配送的实时响应性和鲁棒性。

11、在上述技术方案中，本发明提供的技术效果和优点：

12、在蚂蚁的节点转移决策中，概率转移规则由节点间信息素浓度、q表中状态-动作价值的指数函数以及边通行时间倒数的幂次方共同决定。q值以指数形式参与转移概率计算，使得单只蚂蚁在选择下一节点时，不仅考虑由群体积累的信息素所指示的历史较优路径，还直接利用自身经过在线学习获得的状态-动作价值判断。当某条边在q表中具有较高价值时，即使当前信息素浓度尚未充分累积，该边仍可获得较高的被选择概率，从而将强化学习的个体前瞻性经验实时注入蚁群的随机搜索过程。这一机制在交通状态突然变化时，可快速引导蚂蚁避开拥塞区域或时间窗紧张的节点，避免单纯依赖信息素滞后的反馈，大幅缩短了动态环境下重新发现有效路径所需的迭代次数。

13、在全局信息素更新环节，利用节点状态的q值偏差修正信息素增量。对蚂蚁途经的每条边，先以配送总时间的倒数作为基准信息素增量，再计算边两端节点各自最大q值的偏差，将该偏差与预设幅度相乘后叠加到基准增量上，形成修正信息素增量。q值偏差反映了相邻节点在长期价值上的落差：当从节点i移动到节点j能带来明显的价值提升时，这条边会获得比仅凭行程时间所表征的更大的信息素增强。这种以价值偏差驱动的信息素调节方式，使信息素分布不仅记录路径的长短经验，还嵌入了对节点状态的长期价值评估，促使蚁群在后续迭代中更倾向于选择那些能导向高价值状态的边，在动态时间窗和拥堵变化的场景下可维持路径的全局最优倾向，并抑制由于局部交通波动引发的路径碎片化。