基于自组织优化算法的一类多旅行商问题

Constrained multiple traveling salesman problem based on self-organizing optimization algorithm

多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。

The Multiple Traveling Salesman Problem （MTSP） is an extension of the traveling salesman problem （ TSP）. MTSP is a classical combinatorial optimization problem with more complexity and applicability. The MTSP with the up-limit of the cities to be visited for each salesman was studied and the self-organizing algorithm （SOA） was introduced to solve the problem. The MTSP was transformed into a TSP by introducing virtual cities and the local fitness of virtual city was defined to deal with the relevant constraints. The computational results with a number of benchmark problems show that SOA can be effectively applied in solving the proposed MTSP with superior performance.