有向黑白旅行商问题  

Directed Black and White Traveling Salesman Problem

作　　者：江贺[1] 张宪超[1] 陈国良[2] 

机构地区：[1]大连理工大学软件学院,大连116621 [2]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《计算机学报》2007年第3期431-439,共9页Chinese Journal of Computers

基　　金：国家自然科学基金重大项目(90412007);国家自然科学基金(60503003);辽宁省自然科学基金(20051082);大连理工大学青年教师培养基金资助

摘　　要：黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式——有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效.The black and white salesman problem （BWTSP） is a generalization of classic traveling salesman problem （TSP） arising from work on the design of telecommunication fiber networks using the SONET technology, the scheduling of airline operation, etc. The existing research work focused on the undirected BWTSP. This paper investigates the more general form of this problem, i.e. the directed BWTSP. First, this paper proposes a mixed integer linear programming （MILP） formulation for the directed BWTSP. Compared to the formulation with exponential number of constraints for the undirected BWTSP, the new one contains polynomial number of constraints only. Furthermore, a heuristics for the directed BWTSP is presented. Experiments indicated that the heuristics could effectively solve instances of the BWTSP. Results of this paper could be also useful for the undirected BWTSP when viewed as a special case of the directed BWTSP.

关 键 词：有向黑白旅行商问题 NP-难解 混合整数线性规划 启发式算法 

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