使用遗传算法解决MTSP问题的一种新的染色体设计

A New Approach to Solving the Multiple Traveling Salesperson Problem Using Genetic Algorithms

多旅行商问题(Multiple Traveling Salesperson Problem,简称MTSP)讨论的是如何安排m(>1)位旅行商访问n(>m)座城市,要求每个城市只允许被访问一次时,求解所有旅行商花费的费用和是最小(或最大)的问题。MTSP问题其实与单旅行商问题(Traveling Salesperson Problem,简称TSP)相似,但是由于添加了任何城市只要被某一旅行商访问到即可这个附加条件,因而增加了问题复杂度。在以前使用遗传算法(GA)研究解决MTSP问题时,通常采用标准的TSP染色体和处理方法。现为解决MTSP问题给出了一种新的染色体设计和相关的处理方法,并与以往的理论设计和计算性能进行比较。计算测试显示,新的方法能够获得较小的查找空间,在许多方面,新的方法产生的解空间更好。

The Multiple Traveling Salesperson Problem（MTSP） involves scheduling m 〉 1 salespersons to visit a set ofn 〉 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 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/WfSP 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.