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

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