首页 | 本学科首页   官方微博 | 高级检索  
     


A new class of cutting planes for the symmetric travelling salesman problem
Authors:Bernhard Fleischmann
Affiliation:(1) Lehrstuhl für Quantitative Methoden der Betriebswirtschaftslehre, Universität Hamburg, Von-Melle-Park 5, D-2000 Hamburg 13, FR Germany
Abstract:A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known ldquocomb inequalitiesrdquo, the ldquopath inequalitiesrdquo and the ldquo3-star constraintsrdquo as special cases. Its relation to the ldquoclique tree inequalitiesrdquo is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and—under certain conditions—to define facets of the polyhedron associated with this problem.
Keywords:Travelling salesman problem  cutting planes  polyhedron  facets
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号