The windy general routing polyhedron:: A global view of many known arc routing polyhedra

被引:17
作者
Corberan, Angel [1 ]
Plana, Isaac [1 ]
Sanchis, Jose M. [2 ]
机构
[1] Univ Valencia, Dept Estadist & Invest Operat, Valencia, Spain
[2] Univ Politecn Valencia, Dept Matemat Aplicada, E-46071 Valencia, Spain
关键词
arc routing problems; windy general routing problem; polyhedra; facets;
D O I
10.1137/050640886
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The windy postman problem consists of finding a minimum cost traversal of all of the edges of an undirected graph with two costs associated with each edge, representing the costs of traversing it in each direction. In this paper we deal with the windy general routing problem (WGRP), in which only a subset of edges must be traversed and a subset of vertices must be visited. This is also an NP-hard problem that generalizes many important arc routing problems (ARPs) and has some interesting real-life applications. Here we study the description of the WGRP polyhedron, for which some general properties and some large families of facet-inducing inequalities are presented. Moreover, since the WGRP contains many well-known routing problems as special cases, this paper also provides a global view of their associated polyhedra. Finally, for the first time, some polyhedral results for several ARPs defined on mixed graphs formulated by using two variables per edge are presented.
引用
收藏
页码:606 / 628
页数:23
相关论文
共 35 条
[1]  
Assad A. A., 1995, HDBK OPER R, P375, DOI 10.1016/S0927-0507(05)80109-4
[2]   Lower bounds and heuristics for the Windy Rural Postman Problem [J].
Benavent, Enrique ;
Carrotta, Alessandro ;
Corberan, Angel ;
Sanchis, Jose M. ;
Vigo, Daniele .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 176 (02) :855-869
[3]   The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities [J].
Chopra, S ;
Rinaldi, G .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (04) :602-624
[4]  
CHRISTOFIDES N, 1986, MATH PROGRAM STUD, V26, P155, DOI 10.1007/BFb0121091
[5]  
Christofides N, 1984, P 11 IFIP C COP SYST, P641
[6]   New results on the mixed general routing problem [J].
Corberán, A ;
Mejía, G ;
Sanchis, JM .
OPERATIONS RESEARCH, 2005, 53 (02) :363-376
[7]   The mixed general routing polyhedron [J].
Corberán, A ;
Romero, A ;
Sanchis, JM .
MATHEMATICAL PROGRAMMING, 2003, 96 (01) :103-137
[8]   A POLYHEDRAL APPROACH TO THE RURAL POSTMAN PROBLEM [J].
CORBERAN, A ;
SANCHIS, JM .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 79 (01) :95-114
[9]   The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra [J].
Corberan, A ;
Sanchis, JM .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 108 (03) :538-550
[10]  
CORBERAN A, 2007, TR052007 U VAL DEP S