|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Director of Academic Committee at Kaifa District
其他任职：开发区校区学术分委员会主任（Director of Academic Committee at Kaifa Campus）
性别：男
毕业院校：多伦多大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：软件工程. 运筹学与控制论
办公地点：开发区（Kaifa District Campus）
联系方式：mingchul@dlut.edu.cn
电子邮箱：mingchul@dlut.edu.cn
Using Gavish-Grave LP to formulate the directed black and white traveling salesman problem
点击次数：
论文类型：会议论文
发表时间：2007-05-27
收录刊物：EI、CPCI-S
卷号：4489
期号：PART 3
页面范围：293-+
关键字：black and white traveling salesman problem; linear programming; Gavish-Grave LP
摘要：The black and white traveling salesman problem (BWTSP) is a new class of NP-hard problem arising from work on airline scheduling and telecommunication fiber networks. The existing Ghiani LP for the undirected BWTSP contains an exponential number of constraints. For a special case of the directed BWTSP whose L = +infinity, the LP with polynomial number of constraints could be obtained by transforming it to an asymmetric traveling salesman problem with replenishment arcs (RATSP), whereas there exists no LP for the directed BWTSP in its general form. This paper proposes a LP with 3n(2) +2n constraints only for the directed BWTSP in such a way that, by reducing the problem to an asymmetric traveling salesman problem (ATSP), we add n(2) cardinality constraints and n(2) length constraints to the existing Gavish-Grave LP for the ATSP. The new LP is also valid for the undirected BWTSP when viewed as a special case of the directed BWTSP.