|
|||||
|
|
| 有向黑白旅行商问题 | |
| 引用本文： | 江贺,张宪超,陈国良.有向黑白旅行商问题[J].计算机学报,2007,30(3):431-439. |
| 作者姓名： | 江贺 张宪超 陈国良 |
| 作者单位： | 1. 大连理工大学软件学院,大连,116621;中国科学技术大学计算机科学与技术系,合肥,230027 2. 大连理工大学软件学院,大连,116621 3. 中国科学技术大学计算机科学与技术系,合肥,230027 |
| 基金项目： | 国家自然科学基金 , 国家自然科学基金 , 辽宁省自然科学基金 , 大连理工大学校科研和教改项目 |
| 摘 要： | 黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式--有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效. |
| 关 键 词： | 有向黑白旅行商问题 NP-难解 混合整数线性规划 启发式算法 旅行商问题 Traveling Salesman Problem 求解 实验 启发式算法 多项式 整数线性规划 约束 指数 公式 混合 更一般形式 无向 工作集 研究 应用 调度 航线 网络设计 光纤 |
| 修稿时间： | 2005-03-182006-06-05 |
Directed Black and White Traveling Salesman Problem |
|
| JIANG He,ZHANG Xian-Chao,CHEN Guo-Liang.Directed Black and White Traveling Salesman Problem[J].Chinese Journal of Computers,2007,30(3):431-439. | |
| Authors: | JIANG He ZHANG Xian-Chao CHEN Guo-Liang |
| Affiliation: | 1.School of Software, Dalian University of Technology, Dalian 116621; 2.Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027 |
| Abstract: | 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. |
| Keywords: | directed black and white traveling salesman problem NP-hard mixed integer linear programming heuristics |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |