The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra

被引：26

作者：

Corberan, A ^{[1
]}

Sanchis, JM

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, Fac Matemat Valencia, E-46100 Burjassot, Spain

[2] Univ Politecn Valencia, Dept Matemat Aplicada, ETSI Ind, E-46071 Valencia, Spain

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1998年 / 108卷 / 03期

关键词：

General Routing Problem; Rural Postman Problem; Graphical Traveling Salesman Problem; routing; facets of polyhedra;

D O I：

10.1016/S0377-2217(96)00337-2

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-inducing inequalities are presented. (C) 1998 Elsevier Science B.V.

引用

页码：538 / 550

页数：13

共 16 条

[1]

Assad A. A., 1995, HDB OPERATIONS RES M, V8, P375

[2]

BELENGUER JM, 1990, POLYHEDRAL RESULTS C

[3]

Christofides N., 1981, ALGORITHM RURAL POST

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