求解带时间窗车辆路径问题的改进型烟花算法

Improved Fireworks Algorithm for Solving Vehicle Routing Problem with Time Window

针对带时间窗车辆路径问题,为寻求组合优化问题最优解,构建总运输成本最小数学模型。由于烟花算法搜索半径不能自适应调整,算法后期易陷入局部最优,故对爆炸算子进行改进,使最优烟花搜索半径自适应调整,增强后期局部搜索能力;同时利用分布式信息共享机制避免算法早熟并引入变异火花增强种群多样性。利用标准测试集进行验证后,结果表明该算法在求解带时间窗车辆路径问题时不仅具有可行性和有效性,并且收敛速度快、搜索质量高。

Aiming at the vehicle routing problem with time window,in order to find the optimal solution for the combinatorial optimization problem,the minimum mathematical model of total transportation cost is constructed.Since the search radius of the fireworks algorithm cannot be adaptively adjusted,the algorithm is more likely to fall into local optimum later.Therefore,the explosion operator is improved and the search radius of the optimal fireworks is adjusted adaptively,the ability of the search at the local late is enhanced and the distributed information sharing mechanism is used to avoid premature algorithm and introduce variation sparks,thus enhancing population diversity.And then,the standard test set is used to verify it.The results show that the algorithm is not only feasible and effective in solving the vehicle path problem with time window,but also have fast convergence speed and high search quality.