The general routing polyhedron: A unifying framework

被引：13

作者：

Letchford, AN ^{[1
]}

机构：

[1] Univ Lancaster, Sch Management, Dept Management Sci, Lancaster LA1 4YX, England

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1999年 / 112卷 / 01期

关键词：

polyhedra; valid inequalities; general routing problem;

D O I：

10.1016/S0377-2217(97)00377-9

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

It is shown how to transform the General Routing Problem (GRP) into a variant of the Graphical Travelling Salesman Problem (GTSP). This transformation yields a projective characterisation of the GRP polyhedron. Using this characterisation, it is shown how to convert facets of the GTSP polyhedron into valid inequalities for the GRP polyhedron. The resulting classes of inequalities subsume several previously published classes. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：122 / 133

页数：12

共 27 条

[1]

[Anonymous], ANNOTATED BIBLIOGRAP

[2]

APPLEGATE D, 1995, 9505 DIMACS BELL COM

[3] SMALL TRAVELING SALESMAN POLYTOPES [J].

BOYD, SC ;

CUNNINGHAM, WH .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (02) :259-271

[4]

CAPRARA A, 1997, OR978 DEIS U BOL

[5] A POLYHEDRAL APPROACH TO THE RURAL POSTMAN PROBLEM [J].

CORBERAN, A ;

SANCHIS, JM .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 79 (01) :95-114

[6]

CORBERAN A, 1997, COMMUNICATION

[7]

CORBERAN A, 1996, IN PRESS EUR J OPER

[8] THE TRAVELING SALESMAN PROBLEM ON A GRAPH AND SOME RELATED INTEGER POLYHEDRA [J].

CORNUEJOLS, G ;

FONLUPT, J ;

NADDEF, D .

MATHEMATICAL PROGRAMMING, 1985, 33 (01) :1-27

[9]

Edmonds J., 1973, Mathematical Programming, V5, P88, DOI 10.1007/BF01580113

[10] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

← 1 2 3 →