计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 300-306.DOI: 10.11772/j.issn.1001-9081.2020050615

所属专题: 前沿与综合应用

• 前沿与综合应用 • 上一篇    

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

李华峰, 黄樟灿, 张蔷, 湛航, 谈庆   

  1. 武汉理工大学 理学院, 武汉 430073
  • 收稿日期:2020-05-11 修回日期:2020-06-30 出版日期:2021-01-10 发布日期:2020-08-14
  • 通讯作者: 黄樟灿
  • 作者简介:李华峰(1995-),男,山西临汾人,硕士研究生,主要研究方向:智能计算;黄樟灿(1960-),男,湖北武汉人,教授,博士,主要研究方向:智能计算、图像处理;张蔷(1996-),女,河南信阳人,硕士研究生,主要研究方向:智能计算;湛航(1996-),男,湖北孝感人,硕士研究生,主要研究方向:智能计算;谈庆(1991-),男,湖南长沙人,硕士研究生,主要研究方向:智能计算、图像处理。
  • 基金资助:
    国家自然科学基金资助项目(61672391)。

Improved pyramid evolution strategy for solving split delivery vehicle routing problem

LI Huafeng, HUANG Zhangcan, ZHANG Qiang, ZHAN Hang, TAN Qing   

  1. School of Science, Wuhan University of Technology, Wuhan Hubei 430073, China
  • Received:2020-05-11 Revised:2020-06-30 Online:2021-01-10 Published:2020-08-14
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61672391).

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

关键词: 需求可拆分, 车辆路径问题, 金字塔演化策略, 遗传算法, 自适应邻域算子

Abstract: 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.

Key words: split delivery, vehicle routing problem, pyramid evolution strategy, genetic algorithm, adaptive neighborhood operator

中图分类号: