求解需求可拆分车辆路径问题的改进的金字塔演化策略

Improved pyramid evolution strategy for solving split delivery vehicle routing problem

为了更加合理地求解需求可拆分的车辆路径问题(SDVRP),克服传统先路径后优化两阶段的求解方法容易陷入局部最优的缺点,以及解决智能优化算法在优化阶段未能将竞争与协作有机地融合为一体的问题,以配送路径最短和配送车辆最少为优化目标,提出了一种改进的金字塔演化策略(IPES)。首先,以金字塔为基础,提出了求解SDVRP的编码、解码方式以及层级间的协作策略;其次,根据遗传算法的随机、“适者生存”的高度并行、自适应等特点,以及金字塔结构各层分工不同,设计了一种适合SDVRP的自适应邻域算子,使得算法能够快速收敛到最优;最后,得到最优解。相较于分段求解算法、聚类算法、粒子群算法、人工蜂群算法、禁忌搜索算法,四个仿真实验的结果表明,在求解各案例的最优路径时,所提IPES的求解精度分别至少提升了0.92%、0.35%、3.07%、9.40%,验证了在求解SDVRP时,IPES具有良好的性能。

To solve the Split Delivery Vehicle Routing Problem(SDVRP)more reasonably,overcome the shortcoming that the traditional two-stage solution method of first route and then optimization is easy to fall into local optimization,and handle the problem that the intelligent optimization algorithm fails to integrate competition and cooperation organically in the optimization stage,an Improved Pyramid Evolution Strategy(IPES)was proposed with the shortest delivery path and the least delivery vehicles as the optimization objectives.Firstly,based on the pyramid,the encoding and decoding methods and hierarchical cooperation strategy were proposed to solve SDVRP.Secondly,according to the characteristics such as the random of genetic algorithm,high parallelism of“survival of the fittest”and self-adaption,as well as the different labor division of different layers of pyramid structure,an adaptive neighborhood operator suitable for SDVRP was designed to make the algorithm converge fast to the optimum.Finally,the optimal solution was obtained.Compared with the piecewise solving algorithm,clustering algorithm,particle swarm algorithm,artificial bee colony algorithm,taboo search algorithm,the results of four simulation experiments show that,when solving the optimal path of each case,the proposed IPES has the solution accuracy improved by at least 0.92%,0.35%,3.07%,9.40%respectively,which verifies the good performance of IPES in solving SDVRP.