• 算法设计与分析 •

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

1. (华北计算技术研究所,北京100080)
• 出版日期:2023-01-04 发布日期:2023-01-04
• 作者简介:王阔(1996—),男,河北石家庄人,硕士研究生,研究方向:计算机系统结构,E-mail: 1213498519@qq.com; 通信作者:郝福珍(1970—),男,研究员级高级工程师,硕士,研究方向:计算机技术,嵌入式技术,E-mail: haofz216@163.com。

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

1. (North China Institute of Computing Technology, Beijing 100080, China)
• Online:2023-01-04 Published:2023-01-04

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