A New Evolutionary Multiobjective Model for Traveling Salesman Problem

Authors:

Abstract
The traveling salesman problem (TSP) is one of the most classical NP-hard problems in the combinatorial optimization, as which many practical problems, such as scheduling problems and vehicle-routing cost allocation problems, can be abstracted. The introduction of multiobjective in traveling salesman problem is a very important research topic which brings serious challenges to TSP. Currently, genetic algorithms (GA) are one of the most effective methods to solve multiobjective traveling salesman problem. However, GA-based algorithms suffer the premature convergence, the insufficient diversity and nonuniform distribution of solutions when solving MOTSP, which further restrict the wide application of GA-based algorithms. In order to overcome these problems, this paper proposes an improved method for genetic algorithms based on a novel evolutionary computational model, named as Physarum-inspired computational model (PCM). Based on the prior knowledge of PCM, the initialization of population in the proposed method is first optimized to enhance the distribution of solutions. Then the hill climbing method (HC) is used to improve the diversity of individuals and avert running into the local optimum. Compared to other MOTSP solving algorithms, a series of experiments results demonstrate that our proposed method achieve a better performance.
Funding Information
  • National Natural Science Foundation of China (U1803263, 61762020)
  • Natural Science Foundation of Chongqing Municipality (cstc2018jcyjAX0274)

This publication has 36 references indexed in Scilit: