Research On TSP Based On Intelligent Optimization Algorithms And Its Application

In the traveling salesman problem (TSP) we are given n cities together with the pairwise distances between each two cities. The goal is to find the shortest tour visits every city exactly once and in the end returns to its starting city. The TSP is one of the most famous problems in combinatorial optimization. The cost to resolve TSP is exponential and it is proven to be NP-hard.It is a new hot subject rised in recent years to solve TSP with intelligent optimization algorithms. In this paper we mainly expand research on particle swarm optimization (PSO) and genetic algorithm (GA) for TSP.1. A novel improved PSO is advanced in this paper. We analyze the mechanism of basic particle swarm optimization and then introduce the average of individuals' extreme value to basic PSO to update the velocity of particles together with individual extreme and global extreme. Test result indicates that the improved PSO advanced distinctly in performance like convergence speed and convergence rate.2. An improvement to PSO algorithm for TSP is proposed by introducing crossover and mutation operators. We test the algorithm with 14-node TSP and 30-node TSP and the improved algorithm is proven valid.3. Resolve TSP with GA algorithm and experiments are conducted to analyze the influences on GA algorithm for TSP by fitness function, crossover probability and mutation probability.4. We design the optimization and decision making system for Shan Xi touring itineracies, construct the multi-object optimization model for Shan Xi tour itineracies. Satisfying Pareto optimal solutions of touring itineracies optimization for some sights are obtained in condition of multi-object of shortest distance, least time and lowest expense.