Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

被引：4

作者：

Corberan, Angel ^{[1
]}

Plana, Isaac

Sanchis, Jose M.

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, E-46003 Valencia, Spain

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

来源：

MATHEMATICAL PROGRAMMING | 2006年 / 108卷 / 01期

关键词：

polyhedral combinatorics; facets; Arc Routing; Windy Rural Postman Problem; Windy General Routing Problem; Mixed Rural Postman Problem;

D O I：

10.1007/s10107-005-0643-y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.

引用

页码：79 / 96

页数：18

共 21 条

[1]

BENAVENT E, 2005, IN PRESS COMPUT OPER

[2]

BENAVENT E, 2003, UNPUB EJOR

[3] The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities [J].