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

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.

Key words: VRPTW problem, path planning, PGSA algorithm, directed growth mechanism, local solution jump-out mechanism