一类多旅行商问题的计算及仿真分析  

Computation and Simulation Analysis of a Kind of Multiple Traveling Salesman problem

作　　者：王大志[1] 汪定伟[1] 闫杨[1] 

机构地区：[1]东北大学系统工程研究所,沈阳110004

出　　处：《系统仿真学报》2009年第20期6378-6381,共4页Journal of System Simulation

基　　金：国家自然科学基金重点项目(7043100);国家自然科学基金创新群体项目(60521003);国家科技支撑计划项目(2006BAH02A09)

摘　　要：旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展。多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs)。针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的。Traveling salesman problem is one of the classical problems in Combinatorial Optimization, and the multiple traveling salesman problem （MTSP） is a generalization of the well-known traveling salesman problem （TSP）, where more than one salesman is allowed to be used in the solution. Moreover, the characteristics of the MTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems （VRPs） by incorporating some additional side constraints. Although there exists a wide body of the literature for the TSP and the VRP, the MTSP has not received the same amount of attention. A special case of multiple traveling salesman problem was calculated by adopting Lin-Kernighan algorithm, then a two stage procedure was applied in order to make sure that the number of cities each traveling salesman visited are the same and the total tour length is minimized. The calculation and simulation results are satisfactory.

关 键 词：旅行商问题 多旅行商问题 Lin-Kemighan算法 两阶段方法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]