(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210801023.7 (22)申请日 2022.07.08 (71)申请人 江苏师范大学 地址 221116 江苏省徐州市铜山 新区上海 路101号 (72)发明人 徐涛　张兆军　孙锐　 (74)专利代理 机构 南京纵横知识产权代理有限 公司 32224 专利代理师 雷向永 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06N 3/00(2006.01) G06N 3/12(2006.01) (54)发明名称 基于蚁群融合遗传算法的多目标快递揽件 路线优化方法 (57)摘要 本发明公开了基于蚁群融合遗传算法的多 目标快递揽件路线优化方法， 包括S1.读取路线 优化需要的信息； S2.构建快递收取路线的基本 信息， 建立数学模型， 使用整数编码方式来对解 进行表示； S3.使用蚁群算法生成初始解， 并对种 群进行锦标赛选择、 交叉、 变异得到下一代种群； S4.将父代种群与子代种群合并形成新种群， 选 取较优的个体放入外部档案， 使用当前最优解集 更新蚁群的信息素； S5.通过蚁群生成新的个体 合并外部档案中的个体作为新的种群， 再进行选 择、 交叉、 变异操作,重复步骤S4； S6.若 不满足种 群迭代终止条件， 返回步骤S4、 S5； S7.输出非支 配解集， 得到配送路线。 通过本发明能够合理降 低配送成本， 提高用户满意度。 权利要求书2页 说明书6页 附图2页 CN 115293407 A 2022.11.04 CN 115293407 A 1.基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其特征在于， 包括以下步 骤： S1： 读取路线优化需要的信息； S11： 读取下单信息， 下 单信息包括取件位置、 快件的重量和体积、 时间偏好信息； S12： 读取 快递员信息， 快递员信息包括快递 点位置和车辆信息； S2： 由获取的快递点位置和车辆信息、 顾客下单取件位置和时间偏好以及快件信息作 为构建快递收取路线的基本信息， 建立数 学模型， 使用整数编码方式来对解进行表示； S21： 货物载重和容积不能超过 快递车型最大限制； S22： 在实际快递揽件问题中， 快递员的揽件路线越短， 工作效率越高， 快递用车车型固 定， 完成路线上收取 快递产生的路径 距离Ci， 计算如下： cij表示节点i和节点j之间的距离， xijk表示车辆k是否从节点i出发前往节点j， 如果是， 则xijk＝1， 否则xijk＝0； S23： 在每条路线上， 考虑每个配送点所需的卸货时间以及车辆行驶时间， 与 时间相关 的目标为快件及时收取； S24： 通过最小化路径成本和最大化快件及时收取， 来评估解的优 越性； S25： 设计种群个体编码， 采用固定长度的不重复整数编码方式， 将每个顾客以整数表 示， 个体中整数位置对应访问顾 客点， 染色体长度为M+K ‑1， M为待访问顾 客总数， K为使用车 辆数目； S3： 使用蚁群算法生成初始解， 并对种群进行锦标赛选择、 交叉、 变异得到下一代种群； S31： 蚂蚁初始位置放置在快递 点， 即从快递员出发点 开始构建路径； S32： 根据蚂蚁k在当前节点i到下一节点j的概率转移公式， 按轮盘赌方式选择下一节 点； S33： 反复迭代蚁群算法到最大蚁群的数量Nants后， 得到整个的解集作为遗传操作的 初始解集； S34： 使用二元锦标赛选择优解作为交叉变异的父代种群， 对父代种群执行交叉变异操 作， 得到下一代种群； S4： 将父代种群与子代种群合并形成新种群， 选取较优的个体放入外部档案， 使用当前 最优解集更新蚁群的信息素； S41： 选取较优的方法为计算所有个体的非支配序数， 选择帕累托层级低且拥挤度小的 优良个体， 将其保存到规模固定的精英档案集； S42： 使用当前帕累托 最低层级(非支配解 集)更新蚁群信息素； S5： 通过蚁群生成新的个体合并外部档案中的个体作为新的种群， 再进行选择、 交叉、 变异操作,重复步骤S4； S6： 若不满足种群迭代终止条件， 返回步骤S4、 S5， 直到满足 终止条件； S7： 输出非支配解 集， 得到配送路线。 2.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S1的读取路线优化需要的信息具体为：权　利　要　求　书 1/2 页 2 CN 115293407 A 2在移动终端上设置取件位置、 快件的重量和体积、 偏好的揽件时间， 快递员的信 息有快 递员出发位置、 快递车辆信息 。 3.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S2中建立数 学模型具体为： 分析建立数 学模型。 4.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S2中编码具体为： 采用固定长度的不重复整数编码方式， 每个染色体基因代表访 问顾客点， 染色体长度 为M+K‑1， M为顾客数目， K为车辆总数目。 5.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S3中蚁群选择 下一节点方法具体为： 使用两点之间信息素浓度、 两点之间距离的倒数、 当前点的时间距离下一点偏好时间 的差值计算 转移概率， 使用轮 盘赌选择 下一节点。 6.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S3中二元锦标赛选择 方法具体为： 对蚁群生成的种群进行非支配排序， 使用二元锦标赛选择层级较低的个体； 如果选择 的两个个体层 级一样， 则选择拥挤度低的个体； 如果层 级和拥挤度都一样， 则随机选择一个 个体。 7.根据权利要求1所述的基于蚁群融合遗传算法的多目标快递揽件路线优化方法， 其 特征在于， 所述 步骤S7中生成配送路线方法具体为： 根据迭代计算结果， 产生的优化配送路线， 由非支配排序输出非支配解集， 解集中的每 个解代表一个顾客访问序列， 由访问序列解码得到配送路线。权　利　要　求　书 2/2 页 3 CN 115293407 A 3