(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111614801.3 (22)申请日 2021.12.27 (71)申请人 安徽大学 地址 230601 安徽省合肥市经开区九龙路 111号 (72)发明人 田野　孙脉海　项小书　张兴义　 (74)专利代理 机构 安徽省合肥新 安专利代理有 限责任公司 34101 代理人 陆丽莉　何梅生 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06N 3/00(2006.01) (54)发明名称 一种基于多种群进化算法的带时间窗的车 辆路径规划方法 (57)摘要 本发明公开了一种基于多种群进化算法的 带时间窗的车辆路径规划方法， 包括： 1为带时间 窗的车辆路径问题生成一个辅助问题； 2随机初 始化生成两个种群， 种群1用于优化原始问题， 种 群2用于优化辅助问题； 3基于协同进化算法框架 迭代优化两个种群并定期对两个种群执行局部 搜索操作， 直到满足停止条件， 输出最优种群中 非支配等级最高的个体作为车辆路径规划以及 时间安排的最优 方案。 本发明能解决带时间 窗的 车辆路径规划问题， 在找到最小使用车辆数目的 同时， 能得到更短的总行驶距离， 从而提高运输 效率， 并降低运输成本 。 权利要求书4页 说明书9页 附图2页 CN 114330870 A 2022.04.12 CN 114330870 A 1.一种基于多种群进化算法的带时间窗的车辆路径规划方法， 其特征是应用于由1个 仓库c0、 N个客户以及K辆运输车所组成的配送服务区域中， 在所述配送服务区域中， 将N个 客户记为c＝{c1,c2,…,ci,…,cN}， 1≤i≤N； ci表示第i个客户， 令第i个客户ci的时间窗记 为[ei,li]， 其中， ei和li分别表示对第i个 客户ci服务的最早开始时间和最晚结束时间； 令第 i个客户ci所需要的服务时长记为si， 车辆到达第i个客户ci的时间点记为ti， 车辆从第i个 客户ci到达第j个客户cj的时间记为Tij， wi表示车辆在第i个客户ci的等待时间； 在所述配送服务区域中将所述仓库c0和N个客户分别作为节点， 记为点集V＝{c0,c1, c2,…,ci,…,cN}； 将所述仓库c0与各个客户之间以及N个客户之间直线路径作为边集E＝{< i,j>|i,j∈V,i≠j}； 其中， <i,j>表示任意第i个节点和第j个节 点之间的直线路径； 记所述 直线路径<i,j>的距离矩阵为dij； 假设K辆运输车的最 大载重量均为Q； 假设所有的车辆均是 以仓库c0为起点和终点； 所述车辆路径规划方法是按如下步骤进行： 步骤1、 建立带时间窗的车辆路径规划模型forigin： 步骤1.1、 利用式(1)建立带时间窗的车辆路径规划的第一目标函数f1： f1＝K     (1) 步骤1.2、 利用式(2)建立带时间窗的车辆路径规划的第二目标函数f2： 式(2)表示所有车辆的总行驶路程， 其中， aijk表示第k辆运输车是否经过第i个节点和 第j个节点之间的直线路径； 若aijk＝1， 则表示第k辆运输车经过第i个节点和第j个节点之 间的直线路径， 若aijk＝0， 则表 示第k辆运输车不经过第i个节 点和第j个节点之间的直线路 径； 步骤1.3、 利用式(3)建立总目标函数f： min f＝(f1,f2)     (3) 步骤1.4、 利用式(4) ‑式(10)构建约束条件： tj＝ti+wi+si+Tij for i,j∈{1,. ..,N},i≠j     (9) ei≤ti+wi≤li for i∈{1,...,N}   (10) 式(4)表示所述运输车从仓库c0出发后， 完 成服务任务后必须全部返回仓库c0； 当ai0k＝ 1时， 表示第k辆运输车经过所述第i个节点和仓库c0之间的直线路径＜i,0＞； 当a0jk＝1时，权　利　要　求　书 1/4 页 2 CN 114330870 A 2表示第k辆运输车 经过所述仓库c0和第j个节点之间的直线路径＜0,j＞； 式(5)表示在每个客户处的第k辆运输车的出度 等于入度； 当ajik＝1时， 表示第k辆运输 车经过所述第j个节点与第i个节点之间的直线路径＜j,i＞； 当ajik＝0时， 表示第k辆运输 车不经过所述第j个节点与第i个节点之间的直线路径＜j,i＞； 式(6)和式(7)表示每 个客户都能被访问到并且仅被访问一次； 式(8)表示在所述第k辆运输车行驶路径上的容积约束； 在第k辆运输车的服务路线上 的所有客户需求之和不能多于运输车的最大 载重量Q； 式(9)和式(10)表示时间窗约束， 运输车要保证在要求的时间窗口内完成对客户的服 务， tj表示车辆 到达第j个客户cj的时间点； 且ti‑ei表示违反程度； 步骤2、 从车辆路径规划模型forigin中去除时间窗约束后构成辅助车辆路径规划模型 fhelp； 步骤3、 基于辅助车辆路径规划 模型fhelp， 利用双种 群协同进化算法求解车辆路径规划 模型forigin； 步骤3.1： 初始化大小均为N的两个种群Population1与Population2； 其中， 两个种群中 的每个个体均由所有客户的下标序列组成， 并根据运输车的最大载重量在客户的需求达到 最大载重量时在下 标序列中插 入0作为不同路线的分隔符； 步骤3.2、 根据式(1)和式(2)计算第一种群Population1中每个个体在车辆路径规划模 型forigin下的目标函数值， 并根据式(9)和式(10)计算每辆车到达指定客户的时间点以及时 间窗约束的违反程度； 步骤3.3、 根据式(1)和式(2)计算第二种群Population2中每个个体在辅助车辆路径规 划模型fhelp下的目标函数值； 步骤3.4、 定义当前迭代次数t， 并初始化t＝1； 设置最大迭代次数为tmax； 以第一种群 Population1作为第t代种群 以第二种群Population2作为第t代辅助种群 步骤3.5、 交配池选择： 步骤3.5.1、 采用NSGA ‑Ⅱ算法中的交配池选择方案， 对第t代种群 中的个体 根据其目标函数值和时间窗约束进行非支配排序， 并对不满足时间窗约束的个体在其每一 维的目标值上加上其违反程度后再进 行非支配排序； 再计算排序后的个体的拥挤距离后进 行二元锦标赛选择， 直至 选出N/2个 个体作为第t 代父代并记作 步骤3.5.2、 采用NSGA ‑Ⅱ算法中的交配池选择方案， 对第t代辅助种群 中的 个体根据目标函数值进行非支配排序并计算拥挤距离后， 再进行二元锦标赛选择， 直至选 出N/2个个体作为第t 代辅助父代并记作 步骤3.6、 产生子代； 步骤3.6.1、 对第t代父代 中的个体执行基于序列的遗传算子以产生大小为N/2 的第t代子代种群 步骤3.6.2、 对第t代辅助父代 中的个体执行基于序列的遗传 算子以产生大小为 N/2的第t 代辅助子代种群 权　利　要　求　书 2/4 页 3 CN 114330870 A 3