[发明专利]基于改进粒子群优化的带时间窗约束的车辆路径优化方法

摘要

本发明涉及一种基于改进粒子群优化的带时间窗约束的车辆路径优化方法，包括步骤：步骤10：参数初始化设置；步骤20：构造粒子群；步骤30：粒子解码，依据解码规则对粒子进行解码；步骤40：适应度计算，对于解码得到的配送路线；步骤50：查找个体最优状态和群体最优状态，选出群体最优状态Pg，Pg即为当前迭代条件下车辆路径问题的最优路径；条件判断，粒子群搜索到的最优位置即为当前状态下的最优路径，若未达到终止条件，则转向步骤601，否则转向步骤603；步骤601：状态更新；步骤602：引入交叉算子操作，转入步骤30重复进行粒子解码；步骤603：迭代结束，输出车辆路径问题的最优路径结果。

主权项

一种基于改进粒子群优化的带时间窗约束的车辆路径优化方法，其特征在于包括如下步骤：步骤10：参数初始化设置，设定学习因子c1和c2，最大进化代数nmax，惯性因子初始值ω0，惯性因子终值ωe，交叉概率pc，种群中粒子总数n；步骤20：构造粒子群，在初始值范围内，根据粒子和速度的编码方式初始化粒子群X＝(X1，X2，…，Xn)，各粒子的位置xid及速度vid；步骤30：粒子解码，依据解码规则对粒子进行解码；步骤40：适应度计算，按照“先线路后分组”的方法进行解码，对于解码得到的配送路线，计算目标值z，染色体的适应度定义为Fitness＝1/z；步骤50：查找个体最优状态和群体最优状态，粒子的适应度计算完成后，每个粒子的当前适应度与自身己知的最优适应度比较，选出个体最优状态Pi，Pi即为当前迭代条件下第i个粒子的最优路径；将种群中本次迭代的最优粒子适应度与种群己知的最优适应度比较，选出群体最优状态Pg，Pg即为当前迭代条件下车辆路径问题的最优路径；步骤60：条件判断，结束条件选为达到最大迭代次数Tmax，或者粒子群搜索到的最优位置满足评价指标，粒子群搜索到的最优位置即为当前状态下的最优路径，若未达到终止条件，则转向步骤601，否则转向步骤603；步骤601：状态更新，根据当前状态更新公式，进行粒子的状态更新；步骤602：引入交叉算子操作，依据交叉概率pc，形成t+1时刻种群Xt+1；转入步骤30重复进行粒子解码；步骤603：迭代结束，输出车辆路径问题的最优路径结果。