不确定旅行商问题的鲁棒模型及其算法研究  

Robust Model and Algorithms for the Uncertain Traveling Salesman Problem

作　　者：柯良军[1] 尚可[1] 冯祖仁[1] 

机构地区：[1]西安交通大学机械制造与系统工程国家重点实验室,西安710049

出　　处：《计算机科学》2012年第B06期238-241,共4页Computer Science

基　　金：国家自然科学基金项目(60905044);教育部博士点基金项目(20090201120042)资助

摘　　要：旅行商问题是一类重要的组合优化问题。针对不确定旅行商问题,采用区间数来描述其城市间的旅行时间。在鲁棒优化理论框架下,建立其模型。该模型的突出特点是其鲁棒性可调。提出了一类求解该模型的精确算法和蚁群算法。与精确算法相比较,结果表明了所提出的蚁群算法能在较短时间内求得最优或近优的解。最后,分析了模型的性能,结论表明,在不确定环境下,鲁棒解是有效的。Traveling salesman problem is an important combinatorial optimization problem.The uncertain traveling salesman problem was considered.For each edge,an interval data was used to describe the uncertain travel time.In the framework of robust optimization,a model was developed.The prominent feature of this model is that the degree of conservativeness is adjustable.An exact algorithm and an ant colony optimization approach were proposed to deal with this model.Compared with the exact algorithm,the experimental results show that the proposed ant colony optimization approach can obtain optimal or near optimal solutions within very shorter time.Finally,the property of the model was stu-died.The results support that the robust solution is useful in the uncertain environment.

关 键 词：旅行商问题 鲁棒优化 精确算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]