- -

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

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

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

Show full item record

Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2006). Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems. Mathematical Programming. 108(1):79-96. https://doi.org/10.1007/s10107-005-0643-y

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/150683

Files in this item

Item Metadata

Title: Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems
Author: Corberán, A. Plana, I. Sanchís Llopis, José María
UPV Unit: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Issued date:
Abstract:
[EN] 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 ...[+]
Subjects: Polyhedral Combinatorics , Facets , Arc Routing , Windy Rural Postman Problem , Windy General Routing Problem , Mixed Rural Postman Problem
Copyrigths: Reserva de todos los derechos
Source:
Mathematical Programming. (issn: 0025-5610 )
DOI: 10.1007/s10107-005-0643-y
Publisher:
Springer-Verlag
Publisher version: https://doi.org/10.1007/s10107-005-0643-y
Project ID:
MCYT/TIC2003-05982-C05-01
GV/GRUPOS03/189
Thanks:
The authors wish to thank the Ministerio de Ciencia y Tecnología of Spain (project TIC2003-05982-C05-01) and the Generalitat Valenciana (Ref: GRUPOS03/189) their support.
Type: Artículo

References

Benavent, E., Carrotta, A., Corberán, A., Sanchis, J.M., Vigo, D.: Lower Bounds and Heuristics for the Windy Rural Postman Problem. Technical Report TR03-2003. Department of Statistics and OR, University of Valencia (Spain). Submitted to EJOR 2003

Benavent, E., Corberán, A., Piñana, E., Plana, I., Sanchis, J.M.: New Heuristics for the Windy Rural Postman Problem. To appear in Comput. Oper. Res. 2005

Chopra, S., Rinaldi, G.: The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities. SIAM J. Discrete Math. 9 (4), 602–624 (1996) [+]
Benavent, E., Carrotta, A., Corberán, A., Sanchis, J.M., Vigo, D.: Lower Bounds and Heuristics for the Windy Rural Postman Problem. Technical Report TR03-2003. Department of Statistics and OR, University of Valencia (Spain). Submitted to EJOR 2003

Benavent, E., Corberán, A., Piñana, E., Plana, I., Sanchis, J.M.: New Heuristics for the Windy Rural Postman Problem. To appear in Comput. Oper. Res. 2005

Chopra, S., Rinaldi, G.: The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities. SIAM J. Discrete Math. 9 (4), 602–624 (1996)

Christofides, N., Benavent, E., Campos, V., Corberán, A., Mota, E.: An Optimal Method for the Mixed Postman Problem. In: P. Thoft-Christensen (ed.) System Modelling and Optimization. Lecture Notes in Control and Information Sciences, 59. Berlin: Springer-Verlag 1984

Christofides, N., Campos, V., Corberán, A., Mota, E.: An Algorithm for the Rural Postman Problem. Report IC.OR. 81.5. Imperial College, London 1981

Corberán, A., Mejía, G., Sanchis, J.M.: New Results on the Mixed General Routing Problem. To appear in Oper. Res. 2005

Corberán, A., Mota, E., Sanchis, J.M.: A Comparison of Two Different Formulations for Arc Routing Problems on Mixed Graphs. To appear in Comput. Oper. Res. 2005

Corberán, A., Plana, I., Sanchis, J.M.: On the Windy General Routing Polyhedron. In preparation 2005

Corberán, A., Romero, A., Sanchis, J.M.: The Mixed General Routing Problem Polyhedron. Math. Programming 96, 103–137 (2003)

Cornuèjols, G., Fonlupt, J., Naddef, D.: The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming 33, 1–27 (1985)

Eiselt, H.A., Gendreau, M., Laporte, G.: Arc-Routing Problems, Part 2: the Rural Postman Problem. Oper. Res. 43, 399–414 (1995)

Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton, NJ 1962

Grötschel, M., Win, Z.: On the Windy Postman Polyhedron. Report No. 75, Schwerpunktprogram der Deutschen Forschungsgemeinschaft, Universität Augsburg, Germany 1988

Grötschel, M., Win, Z.: A Cutting Plane Algorithm for the Windy Postman Problem. Math. Programming 55, 339–358 (1992)

Guan, M.: On the Windy Postman Problem. Discrete Applied Mathematics 9, 41–46 (1984)

Letchford, A.: New inequalities for the General Routing Problem. Eur. J. Oper. Res. 96, 317–322 (1997)

Minieka, E.: The Chinese Postman Problem for Mixed Networks. Management Sci. 25, 643–648 (1979)

Naddef, D., Rinaldi, G.: The Symmetric Traveling Salesman Polytope and its Graphical Relaxation: Composition of Valid Inequalities. Math. Programming 51, 359–400 (1991)

Nobert, Y., Picard, J.C.: An Optimal Algorithm for the Mixed Chinese Postman Problem. Networks 27, 95–108 (1996)

Ralphs, T.K.: On the Mixed Chinese Postman Problem. Oper. Res. Lett. 14, 123–127 (1993)

Win, Z.: Contributions to Routing Problems. PhD Dissertation, University of Augsburg, Germany 1987

[-]

recommendations

 

This item appears in the following Collection(s)

Show full item record