Volume 65, Issue 1 pp. 43-55

Research Article

The stacker crane problem and the directed general routing problem

Thais Ávila,

Thais Ávila

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Search for more papers by this author

Ángel Corberán,

Corresponding Author

Ángel Corberán

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Correspondence to: Á. Corberán, e-mail: [email protected]Search for more papers by this author

Isaac Plana,

Isaac Plana

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Search for more papers by this author

José M. Sanchis,

José M. Sanchis

Dept. de Matemática Aplicada, Universidad Politécnica de Valencia, Valencia, Spain

Search for more papers by this author

Thais Ávila,

Thais Ávila

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Search for more papers by this author

Ángel Corberán,

Corresponding Author

Ángel Corberán

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Correspondence to: Á. Corberán, e-mail: [email protected]Search for more papers by this author

Isaac Plana,

Isaac Plana

Dept. d'Estadística i Investigació Operativa, Universitat de València, Valencia, Spain

Search for more papers by this author

José M. Sanchis,

José M. Sanchis

Dept. de Matemática Aplicada, Universidad Politécnica de Valencia, Valencia, Spain

Search for more papers by this author

First published: 09 January 2015

https://doi.org/10.1002/net.21591

Citations: 12

Share a link

Email
Wechat
Bluesky

Abstract

In this article, we deal with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP, in which the service activity occurs both at some of the nodes and at some of the arcs of a directed graph, contains a large number of important arc and node routing problems as special cases, including the SCP. We describe large families of facet-defining inequalities for the DGRP. Furthermore, a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included. These results show that our algorithm is among the best solution procedures proposed for both problems. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 43–55. 2015

REFERENCES

1 G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, and G. Laporte, Static pickup and delivery problems: A classification scheme and survey, TOP 15 (2007), 1–31.
10.1007/s11750-007-0009-0
Web of Science® Google Scholar
2 M. Blais and G. Laporte, Exact solution of the generalized routing problem through graph transformations, J Oper Res Soc 54 (2003), 906–910.
10.1057/palgrave.jors.2601590
Web of Science® Google Scholar
3 V. Campos and J.V. Savall, A computational study of several heuristics for the DRPP, Comput Optim Appl 4 (1995), 67–77.
10.1007/BF01299159
Google Scholar
4 G. Carpaneto, M. Dell'Amico, and P. Toth, Exact solution of large scale, asymmetric traveling salesman problems, ACM Trans Math Softw 21 (1995), 395–409.
Google Scholar
5 N. Christofides, V. Campos, A. Corberán, and E. Mota, An algorithm for the rural postman problem on a directed graph, Math Program Study 26 (1986), 155–166.
10.1007/BFb0121091
Web of Science® Google Scholar
6 J. Cirasella, D.S. Johnson, L.A. McGeoch, and W. Zhang, Traveling salesman problem: Algorithms, instance generators, and tests, ALENEX 2001 Proceedings, Lecture Notes in Computer Science 2153, A.L. Buchsbaum and J. Snoeyink (Editors), Springer, Berlin, 2001, pp. 32–59.
Google Scholar
7 Á. Corberán, G. Mejía, and J.M. Sanchis, New results on the mixed general routing problem, Oper Res 53 (2005), 363–376.
10.1287/opre.1040.0168
Web of Science® Google Scholar
8 Á. Corberán, I. Plana, and J.M. Sanchis, A branch & cut algorithm for the windy general routing problem and special cases, Networks 49 (2007), 245–257.
10.1002/net.20176
Web of Science® Google Scholar
9 Á. Corberán, A. Romero, and J.M. Sanchis, The mixed general routing polyhedron, Math Program 96 (2003), 103–137.
10.1007/s10107-003-0391-9
Web of Science® Google Scholar
10 H.A. Eiselt, M. Gendreau, and G. Laporte, Arc routing problems, part 2: The rural postman problem, Oper Res 43 (1995), 399–414.
10.1287/opre.43.3.399
Web of Science® Google Scholar
11 G.N. Frederickson, M.S. Hecht, and C.E. Kim, Approximation algorithms for some routing problems, 17th Annual Symposium on Foundations of Computer Science, Houston, TX, 1976, pp. 216–227.
Google Scholar
12 G.N. Frederickson, M.S. Hecht, and C.E. Kim, Approximation algorithms for some routing problems, SIAM J Comput 7 (1978), 178–193.
10.1137/0207017
Web of Science® Google Scholar
13 R. Hassin and S. Khuller, z-approximations, J Algorithms 41 (2001), 429–442.
10.1006/jagm.2001.1187
Web of Science® Google Scholar
14 D.S. Johnson, G. Gutin, L.A. McGeoch, A. Yeo, W. Zhang, and A. Zverovitch, “Experimental analysis of heuristics for the atsp,” The travelling salesman problem and its variations, combinatorial optimization vol. 12, G. Gutin and A.P. Punnen (Editors), Kluwer Academic Publishers, Dordrecht, 2002, pp. 445–487.
Google Scholar
15 G. Laporte, Modeling and solving several classes of arc routing problems as traveling salesman problems, Comput Oper Res 24 (1997), 1057–1061.
10.1016/S0305-0548(97)00013-0
Web of Science® Google Scholar
16 D. Naddef and G. Rinaldi, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, Math Program 51 (1991), 359–400.
10.1007/BF01586945
Web of Science® Google Scholar
17 J.V. Savall, Polyhedral results and approximate algorithms for the directed rural postman problem, Ph.D. Thesis, University of Valencia, 1990.
Google Scholar
18 J. Srour, Dissecting drayage: an examination of structure, information, and control in drayage operations, Phd thesis, Erasmus Universiteit Rotterdam, 2010.
Google Scholar
19 J. Srour and S. van de Velde, Are stacker crane problems easy? A statistical study, Comput Oper Res 40 (2013), 674–690.
10.1016/j.cor.2011.06.017
Web of Science® Google Scholar
20 L. Zhang, Polynomial algorithms for the k-Chinese postman problem, Proceedings of the IFIP 12th World Computer Congress. Volume 1: Algorithms, Software, Architecture, J. Van Leeuwen (Editor), Elsevier, Amsterdam, 1992, pp. 430–435.
Web of Science® Google Scholar
21 L. Zhang and W. Zheng, Genetic coding for solving both the stacker crane problem and its k-variant, IEEE International Conference on Systems, Man and Cybernetics, IEEE, Piscataway, NJ, 1995, pp. 1061–1066.
Google Scholar

Citing Literature

Volume65, Issue1

January 2015

Pages 43-55

The stacker crane problem and the directed general routing problem

Abstract

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

The stacker crane problem and the directed general routing problem

Abstract

REFERENCES

Citing Literature

References

Related

Information