A new approach to solving the multiple traveling salesperson problem using genetic algorithms

作者：Carter Arthur E; Ragsdale Cliff T^*

来源：European Journal of Operational Research, 2006, 175(1): 246-257.

DOI：10.1016/j.ejor.2005.04.027

• genetic algorithms
• scheduling
• traveling salesman

The multiple traveling salesperson problem (MTSP) involves scheduling m > 1 salespersons to visit a set of n > m locations so that each location is visited exactly once while minimizing the total (or maximum) distance traveled by the salespersons. The MTSP is similar to the notoriously difficult traveling salesperson problem (TSP) with the added complication that each location may be visited by any one of the salespersons. Previous studies investigated solving the MTSP with genetic algorithms (GAs) using standard TSP chromosomes and operators. This paper proposes a new GA chromosome and related operators for the MTSP and compares the theoretical properties and computational performance of the proposed technique to previous work. Computational testing shows the new approach results in a smaller search space and, in many cases, produces better solutions than previous techniques.

• 出版日期2006-11-16
• 单位美国弗吉尼亚理工大学(Virginia Tech)