《计算机学报》文章摘要   全文下载
文章题目	有向黑白旅行商问题
作者	江贺1),2) 张宪超1) 陈国良2)
作者单位	1)(大连理工大学软件学院 大连 116621) 2)(中国科学技术大学计算机科学与技术系 合肥 230027)
发表年份	2007
发表月份	3期(431—439)
文章摘要	摘要 黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形式——有向黑白旅行商问题.首先,给出了有向黑白旅行商问题的混合整数线性规划公式.与目前无向黑白旅行商问题包含指数多个约束的规划公式相比,它仅包含多项式个约束.其次,给出了一种启发式算法.实验表明,该启发式算法能够有效地求解黑白旅行商问题的实例.由于无向黑白旅行商问题是有向黑白旅行商问题的特例,故文中的结论对于求解无向黑白旅行商问题同样有效. 关键词 有向黑白旅行商问题;NP-难解;混合整数线性规划;启发式算法 中图法分类号 TP301