ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (8): 1751-1762.doi: 10.7544/issn1000-1239.2017.20170347

Special Issue: 2017人工智能前沿进展专题

Previous Articles     Next Articles

Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem

Dong Xueshi, Dong Wenyong, Wang Yufeng   

  1. (Computer School, Wuhan University, Wuhan 430072)
  • Online:2017-08-01

Abstract: Balanced traveling salesman problem (BTSP), a variant of traveling salesman problem (TSP), is another combination optimization problem, which can be applied in many fields such as the optimization problem for gas turbine engines (GTE). BTSP can only model optimization problems with the single traveling salesman and task, but can’t model and optimize the problem with multiple salesmen and tasks at the same time. Therefore, this paper firstly provides a multi-objective balanced traveling salesman problem (MBTSP) model, which can model the optimization problems with multiple salesmen and tasks. Specifically it can be applied to the real-world problems with multiple objectives or individuals, for example, the optimization for multiple GTE. Some literatures have proved that ITO algorithm and genetic algorithms can show better performance in solving combination optimization problems, therefore, the paper utilizes the hybrid ITO algorithm (HITO) and hybrid genetic algorithm (GA) to solve MBTSP. For HITO, it utilizes ant colony optimization (ACO) to produce a probabilistic generative model based on graph, and then uses the drift and volatility operators to update the model, and obtains optimum solution. For the hybrid GA, the first is improved by greedy method called GAG, the second GA is optimized by incorporating hill-climbing named GAHC, and the final one is GASA. In order to effectively test the algorithms, the paper makes extensive experiments using small scale to large scale MBTSP data. The experiments show that the algorithms are effective and reveal the different characteristics in solving MBTSP problem.

Key words: hybrid ITO (HITO) algorithm, hybrid genetic algorithms, balanced traveling salesman problem (BTSP), multi-objective balanced traveling salesman problem (MBTSP), ant colony optimization (ACO)

CLC Number: