有向黑白旅行商问题

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

旅行商问题的综述教学研究

旅行商问题是数学上的组合优化问题,是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视,对其的求解亦提出了各种不同算法;同时就该问题还提出了各种推广形式,但就该问题的教学研究却很少有人涉及。针对这些情况,本文就该问题的综述与教学做几方面的研究,以提高对该问题的教学质量、增强学生的学习积极性。

带多项式量级约束条件的多商品流BWTSP线性规划

黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n2+n+2|B|个权值约束条件.最终得到原始问题仅包含3n2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.