Path Planning Research For Robot And Vehicle With Time Windows Based On Swarm Intelligence Algorithm

At present the core of the swarm intelligence algorithm is the ant colony algorithm and the particle swarm optimization, since the swarm intelligence algorithm has obvious virtues of optimal performance, robustness, versatility and so on, it takes full advantage of getting the optimal solution while solving the path planning problem. And for this reason, more and more scholars devote into the study of how to use the swarm intelligence algorithm to solve the path planning problem.Aiming at the robot path planning problem and the vehicle routing problem with time windows, mathematical models are constructed first, then the swarm intelligence algorithm is adopted to solve models in this paper. The main contents are as follows:1. A method based on the improved MAKLINK graph is proposed to solve the robot path planning problem. Firstly the local path re-planning method is adopted to improve the MAKLINK graph and the bidirectional local search thought is combined to ensure the accuracy of the adaptive environmental model reconstruction. Secondly the Dijkstra algorithm is used to solve the initial optimal path and the enumeration method is introduced to ensure the diversity of the initial optimal path. Afterwards the dynamic double mutation particle swarm optimization is used to re-optimize the initial optimal path. At the same time the search operator is introduced to enlarge the search space of each particle which is on the edge of the dimension and the local search capability of the algorithm is improved for the reason. Finally, the simulation comparison result shows the feasibility and superiority of the proposed method.2. A two-phase optimization algorithm is proposed to solve the vehicle routing problem with time windows. At the first phase, the preliminary path is designed according to the ant colony algorithm. At the second phase, the preliminary path is separated into several sub-paths according to the distribution rule of the customer points. The customers of each sub-path can be served by only one car under the time and capacity constraints. The insert heuristic algorithm based on time windows classification is applied to optimize each sub-path. The optimization goal is to achieve the minimal total transportation cost. Compared with other algorithms, the simulation results in this paper show effectiveness and superiority.