[3J4-J-1] Fundamental AI, theory: search and application

[3J4-J-1-03] Algorithm of Traveling Salesman Problem using Particle Swarm Optimization

〇Yuki Yamada¹, Hajime Anada¹ (1. Tokyo City University)

Keywords:Traveling Salesman Problem, Particle Swarm Optimization

Many economic and industrial problems lead to combinatorial optimization problems. Of these combinatorial optimization problems, the traveling salesman problem (TSP) is one of the most important problem in the field of technology and science. And particle swarm optimization (PSO) is a population based stochastic optimization technique inspired by social behavior of bird flocking or fish schooling. PSO has been applied to various combinatorial optimization problems belonging to nondeterministic polynomial-time hard (NP-hard) combinational problems. But applying PSO to TSP is difficult. Therefore, we construct a new algorithm which is based on PSO. We confirmed the effectiveness of our algorithm using several benchmark problems taken from the TSPLIB, which is a library of traveling salesman problem.