论文部分内容阅读
黑白旅行商问题是经典旅行商问题的推广，在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用．已有研究工作集中在无向黑白旅行商问题上．文章研究该问题的更一般形式——有向黑白旅行商问题．首先，给出了有向黑白旅行商问题的混合整数线性规划公式．与目前无向黑白旅行商问题包含指数多个约束的规划公式相比，它仅包含多项式个约束．其次，给出了一种启发式算法．实验表明，该启发式算法能够有效地求解黑白旅行商问题的实例．由于无向黑白旅行商问题是有向黑白旅行商问题的特例，故文中的结论对于求解无向黑白旅行商问题同样有效．