(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110688494.7 (22)申请日 2021.06.21 (65)同一申请的已公布的文献号 申请公布号 CN 113343575 A (43)申请公布日 2021.09.0 3 (73)专利权人 太原科技大 学 地址 030024 山西省太原市万柏林区窊流 路66号 (72)发明人 陈高华　郗传松　周子涵　陈康　 裴育　丁庆伟　 (74)专利代理 机构 太原中正和专利代理事务所 (普通合伙) 14116 专利代理师 焦进宇 (51)Int.Cl. G06F 30/27(2020.01)G06Q 10/04(2012.01) G06N 3/00(2006.01) G06F 111/06(2020.01) (56)对比文件 CN 112633555 A,2021.04.09 CN 109978471 A,2019.07.0 5 审查员 严荣 (54)发明名称 基于改进蚁群算法的多目标车辆路径优化 方法 (57)摘要 本发明属于物流配送、 电子商务、 智能优化、 网络分析等应用领域， 具体技术方案为： 基于改 进蚁群算法的多目标车辆 路径优化方法， 具体步 骤如下： 一、 在初始时刻， 将信息素总量与各个需 求点和配送中心的距离作为信息素分布矩阵， 设 计初始信息素的具体表达式； 二、 考虑客户与客 户之间的时间窗宽度及碳排放量， 设计转移规则 的具体表达式； 三、 更新信息素表达式； 四、 引入 混沌扰乱机制， 对信息素进行混沌初始化； 本发 明提出了一种以配送总成本最低、 碳排放量最少 的多目标车辆路径优化模型， 多目标模型能更好 地兼顾物 流配送中的配送总成本和碳排放量， 与 经典蚁群算法相比， 改进蚁群算法在配送总成本 上平均节省了6.5％、 碳排放量上平均节省了 3.5％。 权利要求书4页 说明书12页 附图3页 CN 113343575 B 2022.05.10 CN 113343575 B 1.基于改进蚁群算法的多目标 车辆路径优化方法， 其特 征在于， 一、 在初始时刻， 将信 息素总量与各个客户和配送中心的距离作为信 息素分布矩阵， 初 始信息素的具体表达式为： Q为每一次搜索蚂蚁释放的信息 素总量， d1i为客户i和配送中心的实际距 离， d1j为客户j 和配送中心的实际距离； 二、 考虑客户i与客户j的时间窗宽度及碳 排放量， 转移规则的具体表达式为： q为假定的固定阈值， 用来控制状态转移规则参数， q0为一个在区间[0， 1]上的随机数， 当q<q0， 采用确定性搜索模型， 当q≥q0， 采用改进的概 率模型； 改进的概 率模型 具体表达式为： α为信息素浓度重要因子， β、 ω和γ为启发函数重要程度因子， dij为配送车辆从客户i 点到客户j点的距离， 为启发函数， Widthij＝l(i)‑e(i)为客户的时间窗宽度， Zij为 路径上客户i到客户j配送车辆产生的碳排放量， 其值越小， 说明点i到点j的所积累的信息 素浓度越高， 则蚂蚁选择 该条路径的可能性越高； 三、 更新后的信息素表达式为： Δ τij、 和 的具体表达如下：权　利　要　求　书 1/4 页 2 CN 113343575 B 2τij(t)表示在第 t次迭代时， 客户i和客户j之间路径 上的信息素浓度； p表示为每一次迭 代后， 路径上信息素的挥发因子； Δτij表示每一次迭代的i点与j点信息素改变总量； 表示在该次迭代中， 第kk个蚂蚁对于点i与点j信息素改变 的贡献值； 表示额外对 目前 获得的最优路径的奖励； lkk表示第kk个蚂蚁选择的路径的总长； lbest表示目前获得的最优 路径的总长； sizepop为蚂蚁总数； e(i)为客户接受服务的最早时间,l(i)为客户接受服务 最晚时间； 四、 引入混沌扰乱机制， 对信息素进行混沌初始化， 根据混沌迭代方程生成一组混沌变 量,混沌变量是通过L ogistic映射产生的， 具体方式如下： Fij(t+1)＝ μFij(t)*[1‑Fij(t)]                (6) 混沌扰动 后的信息素 更新表达式为: ξ为可调节系数， 是一个常数， Fij(t)是混沌变量， μ为控制变量， μ的取值范围为[3.5 ‑ 4.0]； 模型求解的具体流 程如下： 1)、 初始化参数， 设定最大迭代次数maxiter， 按照公式(1)对每个客户点之间产 生初始 信息素， 初始化迭代次数＝0， 确定每 个参数的函数值； 2)、 创建禁忌表， 让所有的配送车辆从配送中心出发， 在满足约束 的前提下， 按照公式 (2)来选择 下一个客户， 并将此客户添加至禁忌表； 3)、 若配送车辆不满足下一个客户点的需求， 则配送车辆返回配送中心， 更新禁忌表， 重复该过程， 直到所有的客户点全部加入到禁忌表中， 禁忌表更新满足时间窗和载重限制； 4)、 采用2 ‑opt对每次路径内的配送路径进行局部优化； 5)、 所有蚂蚁完成循环后， 按照公式(4)更新信息素， 计算当前迭代得到的可行解， 并与 前代所得到的可行解进行对比， 记录最优解， 若算法5次得出的可行解不变， 则引入混沌扰 动机制， 按照公式(6)、 (7)来更新信息素； 6)、 当nc＝nc+1且nc<maxiter， nc为迭代次数， 则执行步骤2、 3、 4、 5， 否则算法迭代结 束， 输出最优解。 2.根据权利要求1所述的基于改进蚁群算法的多目标车辆路径优化方法， 其特征在于，权　利　要　求　书 2/4 页 3 CN 113343575 B 3