(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211216756.0 (22)申请日 2022.09.30 (71)申请人 浙江工业大 学 地址 310014 浙江省杭州市下城区朝晖六 区潮王路18号 (72)发明人 鲁建厦　董嘉威　赵国利　翁微妮　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 刘静 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06Q 50/28(2012.01) G06F 111/04(2020.01)G06F 111/06(2020.01) G06F 111/08(2020.01) (54)发明名称 一种基于蚁群算法的带道路与时间窗车辆 路径优化方法 (57)摘要 本发明公开了一种基于蚁群算法的带道路 与时间窗车辆路径优化方法， 该方法包括： 以总 物流配送成本最低为目标建立目标函数， 构建带 时间窗约束车辆路径问题优化模 型， 并设定约束 条件； 根据已知的车间各工位需求点距离信息， 采用Floyd算法生成符合车间实际道路环境的最 短距离矩阵； 设计蚁群算法的状态 转移规则和信 息素更新相关参数， 采用改进的蚁群算法对求得 的距离矩 阵进行多次状态转移和信息素更新操 作， 通过多次迭代逐渐使可行解向最优解靠近， 从而得到最优路径。 本发明旨在 有效求得优良的 车辆行驶路线， 降低物流配送成本； 提高算法的 搜索效率与收敛速度， 跳出局部最优解， 增加最 优解的数量。 权利要求书4页 说明书10页 附图5页 CN 115470651 A 2022.12.13 CN 115470651 A 1.一种基于蚁群算法的带道路与时间窗车辆路径优化方法， 其特征在于， 包括以下步 骤： S1、 以包括车辆可变距离运输成本、 固定车辆运输成本和车辆等待时间成本在内的总 物流配送成本最小化 为目标， 建立带 软时间窗约束的车辆路径优化模型； S2、 根据车间实际布局的物流路线构 建了各工位需求点的距离关系， 调用Floyd算法求 解得到最短距离矩阵； S3、 在蚁群算法状态转移规则中增加了轮盘赌法选择下一目标点从而跳出局部最优 解； 在状态转移 概率中增加了工位配送时间窗宽度和车辆等待时间长度两个影响选择下一 目标点的因素； 在蚁群算法信息素更新中， 使用自适应挥发因子加快前期收敛速度， 将当前迭代过程 中走过最佳路线的总成本代替路径长度作为影响信息素更新的因素， 得到改进的蚁群算 法； 采用改进的蚁群算法对步骤S2求得的距离矩阵进行多次状态转移和信息素更新操作， 通过多次迭代逐渐使可 行解向最优解靠 近， 从而得到所有车辆的最优路径。 2.根据权利要求1所述的一种基于蚁群算法的带道路与时间窗车辆路径优化方法， 其 特征在于， 步骤(1)车辆路径优化模型如下 所示： 所述车辆路径优化模型包括总物流 运输成本最小化的目标函数和设定约束条件； 配送中心O拥有m辆载重为Q的物流配送车辆， 物流配送车辆集合为K＝{k1， k2，…， km}， 配送车辆负责对n个需求点进 行配送， 需求点集合为I， 其中每个需求点i的货物需求质量为 qi； Cij表示配送车辆从需求点i到需求点j的可变成本， 其中Cij＝c1dij， c1为车辆行驶距离单 位成本， dij为需求点i到需求点j的距离， tij为需求点i到需求点j点的时间， c2为车辆固定成 本； 满足需求点i的软时间窗为[Ei， Li]， Ei是需求点i最早服务时间窗， Li是需求点i最 晚服 务时间窗， 需求点i服务时间为Si， Tik为第k辆配送车辆在到达需求点i的时刻， Ti’k为配送车 辆在需求点i离开的时刻， WTik为在需求点i处等待的时间， π1为提前时间惩罚单位成本， S (Tik)为服务时间成本函数； 其中服 务时间成本函数如公式(1)所示； 在满足车辆最大装载量和时间窗约束的前提下使行驶距离成本 车辆数 量成本 和等待时间惩罚成本 在内的总物流运输成本最小化是该问 题的目标； xijk是第k辆车从需求点i到需求点j的数值， 取值为0或1； xOjk是第k辆车从配送中 心O到需求 点j的数值， 取值 为0或1； 建立如下目标函数： 所述车辆路径优化模型的约束条件如下：权　利　要　求　书 1/4 页 2 CN 115470651 A 2Ti'k＝Tik+WTik+Si,i∈I， k∈K                       (6) WTik＝max[0,(Ei‑Tik)],i∈I                        (7) Tik≤Li,i∈I                        (9) xijk∈{0,1},i,j∈I,i≠j,k∈K                           (10) 约束(3)表示每个需求点i必须被一辆配送汽车配送一次， xik是第k辆车经过需求点i的 数值， 取值为0或1； 约束(4)表示到达和 离开任意一个点的车辆数相等， 从而保证了路 由的 连续性， xijk是第k辆车从需求点i到需求点j的数值， 取值为0或1， xjik是第k辆车从需求点j 到需求点i的数值， 取值为0或1； 约束(5)表示配送车辆的装载质量不得超过车辆最大装载 量； 约束(6)表示离开需求点i处的时间为到达需求点i处的时间、 等待时间和服务时间之 和； 约束(7)表示在需求点i处的等待时间； 约束(8)表示到达 需求点j处 的时间Tjk是从需求 点i处出发时间与路径(i， j)的行驶时间之和； 约束(9)表示车辆在需求点i处的到达时间不 能超过需求 点i的最晚时间窗范围； 约束条件(10)表示决策变量 为二进制。 3.根据权利要求2所述的一种基于蚁群算法的带道路与时间窗车辆路径优化方法， 其 特征在于， 所述步骤(2)采用Floyd算法生成符合车间实际道路环境的最短距离矩阵， 车间 实际道路环境含义是结合车间实际布局的物流路线代替任意两需求点间直线相连的思想， 基于车间通道 节点约束求 解最短距离矩阵； 包括以下步骤： 步骤2.1， 初始化矩阵； 根据需求 点数量初始化距离矩阵； 步骤2.2， 记录已知节点之间最短距离信息， 更新距离矩阵； 步骤2.3， 判断并更新距离矩阵； 如果路径距离D(i,h)+D(h,j)<D(i,j)， 则更新最短距 离矩阵D(i,j)＝D(i,h)+D(h,j)； D(i,h)表示需求点i到需求点h的距离， D(h,j)表示需求点 h到需求点j的距离， D(i,j)表示需求 点i到需求点j的距离； 步骤2.4， 判断是否历经了所有节点； 步骤2.5， 输出 结果； 求解得到带道路的最短距离矩阵。 4.根据权利要求3所述的一种基于蚁群算法的带道路与时间窗车辆路径优化方法， 其 特征在于， 所述 步骤(3)具体步骤如下： 步骤3.1， 初始化 参数； 步骤3.2， 令迭代次数NC＝1， 将m辆车随机放在调度中心， 设置k ＝1； 步骤3.3， 重置第k辆 车的访问节点集合Ni； 根据状态转移概率选 择下一个要访问 的需求 点 判断需求点j的需求量和目前车辆装载量的和是否超过第k辆车的最大装载量， 超过第k辆车的最大装载量则转到步骤3.4， 若没有超过第k辆车的最大装载量， 则更新第k 辆车的访问节点 集合Ni和禁忌表；权　利　要　求　书 2/4 页 3 CN 115470651 A 3