Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (1): 41-47.doi: 10.1007/s12204-019-2039-9

• • 上一篇    下一篇

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖)   

  1. (1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Jilin Vocational College of Industry and Technology, Jilin 132013, Jilin, China; 3. College of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China)
  • 出版日期:2019-02-28 发布日期:2019-01-28
  • 通讯作者: WANG Shengsheng *(王生生 E-mail:wss@jlu.edu.cn

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

DONG Ruyi (董如意), WANG Shengsheng *(王生生), WANG Guangyao (王光耀), WANG Xinying (王新颖)   

  1. (1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Jilin Vocational College of Industry and Technology, Jilin 132013, Jilin, China; 3. College of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China)
  • Online:2019-02-28 Published:2019-01-28
  • Contact: WANG Shengsheng *(王生生 E-mail:wss@jlu.edu.cn

摘要: Traveling salesman problem (TSP) is one of the typical NP-hard problems, and it has been used in many engineering applications. However, the previous swarm intelligence (SI) based algorithms for TSP cannot coordinate with the exploration and exploitation abilities and are easily trapped into local optimum. In order to deal with this situation, a new hybrid optimization algorithm based on wolf pack search and local search (WPS-LS) is proposed for TSP. The new method firstly simulates the predatory process of wolf pack from the broad field to a specific place so that it allows for a search through all possible solution spaces and prevents wolf individuals from getting trapped into local optimum. Then, local search operation is used in the algorithm to improve the speed of solving and the accuracy of solution. The test of benchmarks selected from TSPLIB shows that the results obtained by this algorithm are better and closer to the theoretical optimal values with better robustness than those obtained by other methods.

关键词: traveling salesman problem (TSP), swarm intelligence (SI), wolf pack search (WPS), combinatorial optimization

Abstract: Traveling salesman problem (TSP) is one of the typical NP-hard problems, and it has been used in many engineering applications. However, the previous swarm intelligence (SI) based algorithms for TSP cannot coordinate with the exploration and exploitation abilities and are easily trapped into local optimum. In order to deal with this situation, a new hybrid optimization algorithm based on wolf pack search and local search (WPS-LS) is proposed for TSP. The new method firstly simulates the predatory process of wolf pack from the broad field to a specific place so that it allows for a search through all possible solution spaces and prevents wolf individuals from getting trapped into local optimum. Then, local search operation is used in the algorithm to improve the speed of solving and the accuracy of solution. The test of benchmarks selected from TSPLIB shows that the results obtained by this algorithm are better and closer to the theoretical optimal values with better robustness than those obtained by other methods.

Key words: traveling salesman problem (TSP), swarm intelligence (SI), wolf pack search (WPS), combinatorial optimization

中图分类号: