面向带时间窗车辆路径问题的PGSA算法优化  

Optimization of Plant Growth Simulation Algorithm for Vehicle Routing Problem with Time Windows

作　　者：王阔 郝福珍[1] WANG Kuo;HAO Fu-zhen(North China Institute of Computing Technology,Beijing 100080,China)

机构地区：[1]华北计算技术研究所,北京100080

出　　处：《计算机与现代化》2022年第12期26-32,共7页Computer and Modernization

摘　　要：VRPTW问题是带时间窗约束的车辆路径问题,该问题的求解通常被应用到物流的路径规划环节,现实意义突出,属于NP难题,计算量随问题规模增大呈指数增长。PGSA算法是模拟植物生长信息和分支模式的启发式算法,被用于求解组合优化问题。本文以配送总路程最短为目标构建VRPTW问题的约束模型,在原始PGSA算法的基础上,使用双阶段的搜索方案,提高初始解的质量,设计有向生长机制和局部解跳出机制更改原算法生长点的生长策略,提高了PGSA算法的搜索效率。通过在标准数据集上的实验分析,改进后的PGSA算法相比原始PGSA算法,能达到更好的收敛结果,求解效率更高,是一种有效的求解方法。VRPTW problem is a vehicle routing problem with time window constraints. The solution of this problem is usually applied to the logistics path planning. It is of great practical significance and belongs to the NP problem. The amount of computation of VRPTW problem increases exponentially with the increase of data scale. Plant growth simulation algorithm(PGSA) is a heuristic algorithm that simulates plant growth information and branching patterns, and is used to solve combinatorial optimization problems. In this paper, a constraint model of VRPTW problem is constructed with the goal of minimizing the total distance of distribution. On the basis of the original PGSA, a two-stage search scheme is used to improve the quality of the initial solution. The directed growth mechanism and local solution jump-out mechanism are designed to change the growth strategy of the original algorithm, and the search efficiency of the PGSA algorithm is improved. Through the experimental analysis on the standard data set, the improved plant growth simulation algorithm can achieve better convergence results and higher efficiency than the original plant growth simulation algorithm, so it is an effective solution method.

关 键 词：VRPTW问题 路径规划 PGSA算法 有向生长机制 局部解跳出机制 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP305[自动化与计算机技术—计算机科学与技术]