(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210964189.0 (22)申请日 2022.08.11 (71)申请人 姚陈潇 地址 201203 上海市浦东 新区中国(上海) 自由贸易试验区春晓路470号203-32 信箱 (72)发明人 姚陈潇　 (74)专利代理 机构 上海图灵知识产权代理事务 所(普通合伙) 31393 专利代理师 刘红梅 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06Q 30/02(2012.01) G06N 3/12(2006.01) (54)发明名称 基于混合遗传算法的车辆路径优化方法及 应用 (57)摘要 本发明提供了一种基于混合遗传算法的车 辆路径优化方法及应用， 涉及货物装 载和车辆 路 径的组合优化技术领域。 所述方法包括设置目标 适应度函数作为车辆路径方案的目标评价指标， 用来评价遗传算法中染色体的适应能力； 获取货 物信息和车辆信息， 执行建立序列信息步骤和生 成可行方案步骤， 以确定车辆路径方案； 在生成 可行方案步骤中， 计算初代染色体对应的目标适 应度函数值以选 择Pareto解， 并计算出每一迭代 过程中染色体的目标适应度函数值来比较 Pareto解， 去劣存优后确定最终的Pareto解及其 对应的车辆路径方案。 本发明针对实际运营情况 设置目标适应度函数来评价遗传操作后生成的 车辆路径方案， 以最终筛选出最优的车辆路径方 案。 权利要求书2页 说明书11页 附图3页 CN 115330051 A 2022.11.11 CN 115330051 A 1.一种基于混合遗传算法的车辆路径优化方法， 其特 征在于， 包括如下步骤： 设置目标适应度函数作为车辆路径方案的目标评价指标， 用来评价遗传算法中染色体 的适应能力； 获取货物信息和车辆信息， 执行建立序列信息步骤和生成可行方案步骤， 以确定车辆 路径方案； 在生成可行方案步骤中， 计算初代染色体对应的目标适应度函数值以选择 Pareto解， 并计算出每一迭代过程中染色体的目标适应度函数值来比较Pareto解， 去劣存 优后确定最 终的Paret o解及其对应的车辆路径方案； 所述车辆路径方案中包括所有路径以 及对应的装载 方案。 2.根据权利要求1所述的方法， 其特征在于， 所述目标适应度函数包括车辆路径方案的 运输总成本 costR和运输总时间timeR。 3.根据权利要求1所述的方法， 其特征在于， 所述染色体基于整数编码进行编制， 所述 染色体包括前半段的货物片段和后半段 的车型片段， 其中， 货物片段以零部件包装容器为 单位， 将一箱作为 一个基因， 当货物组合成托盘后， 将组合后一个托盘作为 一箱。 4.根据权利要求1所述的方法， 其特征在于， 在建立序列信息步骤中， 对应采集的货物 信息、 车型信息和供应商节 点信息， 建立货物序列I_list、 车型序列K_list和供应商节 点序 列S_list， 所述供应商节点序列S_list中供应商节 点顺序按照货物在货物序列I_list中的 位置信息对应排列。 5.根据权利要求1所述的方法， 其特 征在于， 生成可 行方案的步骤 包括： 步骤S201， 生成货物+车 型初始种群； 步骤S202， 基于初始种群 中的染色体信息， 对应得到车辆路径方案， 计算初始种群中各 条染色体的目标适应度函数值， 选择Pareto解及其对应的车辆路径方案， 将新Pareto解及 其对应的车辆路径方案， 写入Pareto 最优解集； 步骤S203， 对前述货物+车型初始种群中的每个染色体进行遗传操作， 生成货物子代种 群； 基于货物子代种群中的染色体信息， 对应得到车辆 路径方案， 计算货物子代种群中各条 染色体的目标适应度函数值， 比较Pareto解， 得到新Pareto解及其对应的车辆 路径方案， 并 写入Pareto 最优解集； 步骤S204， 判断是否满足终止条件， 若已达到终止条件， 则继续执行步骤S205， 否则， 返 回步骤S202； 步骤S205， 输出Pareto最优解集和对应的车辆路径方案， 输出的信息包含该路径上供 应商序列、 装载 方案、 运输时间ti、 运输总成本 costR和运输总时间timeR信息 。 6.根据权利要求5所述的方法， 其特 征在于， 对应得到车辆路径方案时， 包括 步骤： 步骤S2021， 建立货物与供应商节点的关系， 获取货物序列I_list、 车型序列K_list和 供应商节点序列S_list， 初始化iL＝1， iK＝1， 其中， iL代表第iL个货物， iK代表第iK个车 型， 设置待装货物序列L_l ist； 步骤S2022， 如果iK≤length(K_list)， 从车型序列K_list取出第iK个车型， 否则， 从车 型序列K_l ist取出第length(K_l ist)个车 型， 并获取 车厢体积CV； 步骤S2023， 从货物序列I_list中， 取出第iL个货物加入待装货物序列L_list， 当待装 货物序列中货物体积之和大于车厢体积CV， 执 行步骤S2024， 否则， 执 行步骤S2025； 步骤S2024， 将待装货物序列和车型对应的车厢信息作 为参数， 调用预设的模拟退火算权　利　要　求　书 1/2 页 2 CN 115330051 A 2法， 生成装载方案， 按照已装货物在货物序列I_list中的位置顺序， 排列出对应的供应商节 点S_list顺序， 去掉重复的供应商节点， 在供应商节点顺序S_list的开始节点和结束节点 处增加上配送中心， 生成路径， 将该路径存入车辆路径方案， 计算出该路径已装入货物的最 早交货时间窗和各货物是否迟到αi， 最后将已装货物从待装货物序列中删除， 设置iK＝iK+ 1； 步骤S2025， 当iL≤length(I_list)时， 设置iL＝iL+1， 执行步骤S2023； 如果待装货物 序列L_list为空， 进入步骤S2026， 否则， 返回步骤S2024； 步骤S2026， 输出车辆路径方案， 对前述车辆路径方案中任意i∈R， 每条Ri路径的信息， 包含该路径上 供应商序列、 装箱方案、 运输时间ti， 已装入的货物是否迟到αi。 7.根据权利要求6所述的方法， 其特征在于， 所述αi为0‑1变量， 针对货物i， i∈I， αi＝1 表示已装载在车 上， αi＝0表示未装载在车 上。 8.根据权利要求5所述的方法， 其特征在于， 所述遗传操作包括对货物+车型染色体的 选择、 交叉和变异操作； 所述遗传操作将染色体上货物片段和车型片段分别独立地进行选 择、 交叉和变异操作； 前述染色体各自的交叉概 率或前述变异概 率能够设置为相同的值。 9.根据权利 要求5所述的方法， 其特征在于， 对前述Pareto解进行解码以生成车辆路径 方案， 所述 解码包括 步骤： 步骤S301， 切分车型片段和货物片段： 针对切分车型片段， 顺序按照从头至尾方向， 每 次只切分一个车型， 获取该车型的车厢体积； 针对切分货物片段， 顺序按照从头至尾方向， 逐个切分， 直至本次已切分的货物体积之和超过车型 的车厢体积为止， 或者货物片段已切 分完毕； 步骤S302， 进行装载校验： 利用预设的车辆装载算法， 对已切分的车型和货物进行校验 并生成装载方案； 判断校验后是否有 未装入的货物， 判定为是时， 将未装入的货物放回货物 片段中， 循环处 理步骤S3 01和步骤S3 02， 直至将所有货物都装 入对应的车辆中； 步骤S303， 生成车辆路径方案： 根据每辆车已装入的货物， 生成车辆路径方案， 并计算 每条路径的最 早卸货的窗口时间、 运输总成本与运输总时间。 10.一种以实施权利要求1 ‑9中任一项所述的基于混合遗传算法的车辆路径优化系统, 其特征在于， 包括: 条件预置模块， 设置车辆装载约束条件和车辆路径约束条件， 以及车辆路径方案中对 应的目标评价指标； 信息输入模块， 用以输入货物信息、 车型信息和供应商节点信息； 方案生成模块， 用以 获取货物信息和车辆信息， 执行建立序列信息步骤和 生成可行方案步骤， 以确定车辆路径 方案； 在生 成可行方案步骤中， 计算初代染色体对应的目标适应度函数值以选择Paret o解， 并计算出每一迭代过程中染色体的目标适应度函数值来比较Paret o解， 去劣存优后确定最 终的Pareto解及其对应的车辆 路径方案； 所述车辆路径方案中包括所有路径以及 对应的装 载方案。权　利　要　求　书 2/2 页 3 CN 115330051 A 3