(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111293459.1 (22)申请日 2021.11.03 (71)申请人 河南科技大 学 地址 471000 河南省洛阳市洛龙区开元 大 道263号 (72)发明人 吴延峰　田凯　韩鹏飞　李丽红　 (74)专利代理 机构 北京盛凡佳华专利代理事务 所(普通合伙) 11947 代理人 李芳 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/00(2006.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06F 111/04(2020.01)G06F 111/08(2020.01) G06F 119/12(2020.01) (54)发明名称 一种基于改进蚁群算法的并行时间窗车辆 路径规划方法 (57)摘要 本发明公开了一种基于改进蚁群算法的并 行时间窗车辆路径规划方法， 包括以下步骤： 首 先根据订单要求确定硬时间窗， 并按时间窗顺序 对物流数据进行排序， 然后筛选出初始时间 窗相 同的个数， 以此来确定改进蚁群算法中的起始蚂 蚁数m； 迭代搜索并反馈， 判断当前状态是否满足 算法终止条件， 如果是则终止并返回最终结果， 如果不是则返回继续运行迭代搜索并反馈。 本发 明涉及车辆路径规划技术领域， 具体是提供了一 种基于改进蚁群算法的并行时间窗车辆路径规 划方法， 本方案旨在解决并行时间窗下的车辆行 驶路径规划问题， 提供了一种改进蚁群算法， 克 服传统蚁群算法在求解并行时间窗约束下的配 送路径问题的局限性。 权利要求书1页 说明书6页 附图2页 CN 114154394 A 2022.03.08 CN 114154394 A 1.一种基于改进蚁群算法的并行时间窗车辆路径规划方法， 其特征在于， 包括如下步 骤： 步骤1： 针对物流数据， 基于P ython编写数据处理程序， 借助百度 地图API批量获取两地 的实地距离， 得到距离矩阵； 步骤2： 根据订单要求确定硬时间窗， 接着按时间窗顺序对物流数据进行排序， 然后筛 选出初始时间窗相同的个数， 以此来确定改进蚁群算法中的起始蚂蚁数m； 导入由步骤1所 得到的距离矩阵以及订单信息、 时间窗矩阵和蚁群算法所需初始化变量， 对计算模型参数 进行初始化； 步骤3： 迭代搜索并反馈； 本步骤反复执行， 直至算法满足设定的终止条件为止； 在每一轮迭代过程中都将进行 如下操作： 首先生成m只蚂蚁第一次所访问的订单并记录， 并将对应蚂蚁的已访问订单从列 表中删除， 更新对应蚂蚁的容量， 迭代 次数+1， 然后判断是否达到终止条件， 若达到则输出 最优方案并结束， 否则执 行步骤4； 步骤4： 根据时间窗约束筛选可执行下个订单的蚂蚁， 若筛选完后为空集， 则初始化一 只新的蚂蚁执行此订单， 并更新对应蚂蚁的质量、 时间； 若筛选完后不为空集， 继续筛选出 根据质量约束可执行下个订单 的蚂蚁； 若存在依据质量筛选可执行下个订单 的蚂蚁， 则执 行步骤5， 否则， 选择距离最近的蚂蚁返回后能执行此订单或者次于距离最近的蚂蚁返回后 能执行此订单， 若不存在可 执行此订单的蚂蚁， 执 行步骤3； 步骤5： 计算可 执行下个订单的蚂蚁概 率， 根据轮 盘赌法选择 下个订单并记录 。 2.根据权利要求1所述的一种基于改进蚁群算法的并行时间窗车辆路径规划方法， 其 特征在于， 所述蚁群算法所需初始化变量包括最大迭代次数、 蚁群数量、 信息素浓度与权 重、 能见度及权 重、 等待区间权 重。 3.根据权利要求2所述的一种基于改进蚁群算法的并行时间窗车辆路径规划方法， 其 特征在于， 所述 终止条件为完成所有订单， 迭代次数达到 设置最大迭代数iter_Max， 且总距 离在规定的最后F次迭代中不再 下降。 4.根据权利要求3所述的一种基于改进蚁群算法的并行时间窗车辆路径规划方法， 其 特征在于， 所述总距离为同一起点发出的所有车辆完成全部订单并返回起点所历经的路径 之和。权　利　要　求　书 1/1 页 2 CN 114154394 A 2一种基于改进蚁群算法的并行时间窗车辆路径规划方 法 技术领域 [0001]本发明涉及车辆路径规划技术领域， 具体是指一种基于改进蚁群算法的并行时间 窗车辆路径规划方法。 背景技术 [0002]带有时间窗的车辆路径问题(Vehicle  Routing Problem with Time Windows, VRPTW)作为传统车辆路径问题(Vehicle  Routing Problem,VRP)的一个扩展， 除了考虑车 辆容量约束， 还要考虑车辆发车时间以及客户服务顺序， 并要在客户指定的时间窗内将货 物送达。 并行时间 窗下的车辆路径问题(Vehicle  Routing Problem under Parallel  Time  Windows， VRPPTW)是VRPTW问题的一种情况， 该 问题要求在相同时间窗内， 同时满足多个客 户的需求， 这类VRPTW问题在实际物 流配送中是广泛存在的。 例如， 对于生鲜品类的配送， 就 存在着多个客户要求将货物在同一时间送达的情况。 [0003]蚁群算法是一种用来寻找优化路径的概率型算法， 其灵感来源于蚂蚁在寻找食物 过程中发现路径的行为。 该算法利用蚂蚁行走 的路径表示待优化问题的可行解， 整个蚂蚁 群体的所有路径构成待优化问题的解空间。 路程较短的蚂蚁释放的信息素量较多， 随着时 间的推移， 较短路径上的信息素浓度会逐渐增加， 选择该路径的蚂蚁个数也越来越多。 最 终， 整个蚁群都会在正反馈的作用下选择到最佳路径， 此时便得到待优化问题的最优解。 这 种算法具有分布计算、 信息正反馈和启发式搜索的特征， 本质上是进化算法中的一种启发 式全局优化算法。 近年来， 蚁群算法凭借着其极强的鲁棒性、 协同性及隐含的并行性， 已然 成为众多启发式算法中的佼 佼者。 [0004]传统的蚁群算法是由一只蚂蚁遍历完所有节点再对方案进行分割， 若订单数据中 最早的时间窗出现并行时， 传统蚁群算法便显现出局限性。 如某公司三个客户订单 的预约 提货时间相同， 当蚂蚁选择第一站时， 只会从这三个客户中选择一个客户进行服务， 从而导 致另外两个客户服务超时， 算法失效。 为此， 当多个初始时间窗相同时， 就产生了并行需求， 需要利用多只蚂蚁同时并行从起始 点出发进 行遍历。 目前应用蚁群算法求解该问题的研究 大多是通过改变信息素更新方式或改变节点选择方式， 提高优化效果， 较少考虑利用多个 蚂蚁并行访问节点的方式； 加之该问题是强NP难题， 导致目前该问题的有效的解决方案极 少。 发明内容 [0005]针对上述情况， 为克服现有技术的缺陷， 本方案提供一种基于改进蚁群算法的并 行时间窗车辆路径规划方法， 本方案旨在解决并行时间窗下 的车辆行驶路径规划问题， 提 供了一种改进蚁群算法， 克服传统蚁群算法在求解并行时间窗约束下的配送路径问题的局 限性。 [0006]本发明采取的技术方案如下： 本方案基于改进蚁群算法的并行时间窗车辆路径规 划方法， 包括以下步骤：说　明　书 1/6 页 3 CN 114154394 A 3