Optimization for Multiple Traveling Salesman Problem Based on Genetic Algorithm
J. Chen†*, Y. Jia†, & G. Houghton‡
†Management school, Hangzhou Dianzi University, Hangzhou, 310018, China
‡Exercise and Health, The University of Western Australia, Perth, Australia
ABSTRACT: As a classical NP-hard problem, traveling salesman problem is of great significance, at the same time, solving multiple traveling salesman problem has much more practical significance. In the past, research on multiple traveling salesman problem is usually limited to set the optimization criterion to the minimal sum of all the traveling salesman path, comparatively, the literature about multiple traveling salesman problem of minimizing the maximum of all the traveling salesman path is rare. To solve the multiple traveling salesman problem of minimizing maximum value of all the traveling salesman path, this paper firstly introduces the mathematical model for the multiple traveling salesman problem, then by using genetic algorithm to optimize this problem, and proposes a matrix decoding method. Matrix decoding method is suitable for solving multiple traveling salesman problem of asymmetric and symmetric distance. In this paper, multiple traveling salesman problem of asymmetric distance is as sample to have tests and the performances of different crossovers are compared.
Keywords: Genetic algorithm; Multiple traveling salesman problem; Optimization; Decoding method.