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

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

作　　者：李天龙[1] 吕勇哉[1] 

机构地区：[1]浙江大学智能系统与控制研究所,杭州310027

出　　处：《计算机应用》2010年第2期458-460,共3页journal of Computer Applications

基　　金：国家创新研究群体科学基金资助项目(NCRGSFC:60721062);国家自然科学基金资助项目(60774081)

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

关 键 词：多旅行商问题 虚拟城市 自组织优化算法 局部适值 

分 类 号：TP30[自动化与计算机技术—计算机系统结构] TP182[自动化与计算机技术—计算机科学与技术]