Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T09:16:33.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Tree based models and algorithmsfor the preemptive asymmetric Stacker Crane problem

Published online by Cambridge University Press:  21 October 2011

Hervé Kerivin ,
Mathieu Lacroix ,
Alain Quilliot  and
Hélène Toussaint
Hervé Kerivin
Affiliation:
Department of Mathematical Sciences, Clemson University, CLEMSON, O-326, Martin Hall, Clemson, 29634 SC, USA
Mathieu Lacroix
Affiliation:
LIMOS, CNRS UMR 6158, Université Blaise-Pascal, Clermont-Ferrand II, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France. [email protected]
Alain Quilliot
Affiliation:
LIMOS, CNRS UMR 6158, Université Blaise-Pascal, Clermont-Ferrand II, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France. [email protected]
Hélène Toussaint
Affiliation:
LIMOS, CNRS UMR 6158, Université Blaise-Pascal, Clermont-Ferrand II, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France. [email protected]
Get access

Abstract

In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the preemption hypothesis.

Keywords

Preemptive stacker crane problemroutinglocal searchheuristics
Type
Research Article
Information
RAIRO - Operations Research , Volume 45 , Issue 3 , July 2011 , pp. 179 - 207
Copyright
© EDP Sciences, ROADEF, SMAI, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anily, S. and Hassin, R., The swapping problem. Networks 22 (1992) 419–433. CrossRef
S. Anily, M. Gendreau and G. Laporte, The preemptive swapping problem on a tree. Submitted to Networks (2009).
Ascheuer, N., Escudero, L., Grötschel, M. and Stoer, M., A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing). SIAM J. Optim. 3 (1993) 25–42. CrossRef
Ascheuer, N., Jünger, M. and Reinelt, G., Branch, A and Cut algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Comput. Optim. Appl. 17 (2000) 61–84. CrossRef
M.J. Atallah and S.R. Kosaraju, Efficient solutions to some transportation problems with applications to minimizing robot arm travel. SIAM J. Comput. 17 (1988) 849.
Balas, E., Fischetti, M. and Pulleyblank, W., The precedence constrained asymmetric traveling salesman problem. Math. Program. 68 (1995) 241–265.
G. Berbeglia, J.F. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems: a classification scheme and survey. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research 15 (2007) 1–31.
C. Bordenave, M. Gendreau and G. Laporte, A branch-and-cut algorithm for the preemptive swapping problem. Technical Report CIRRELT-2008-23 (2008).
C. Bordenave, M. Gendreau and G. Laporte, Heuristics for the mixed swapping problem. Comput. Oper. Res. 37 (2010) 108–114.
S. Chen and S. Smith, Commonality and genetic algorithms. Technical Report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (1996).
Cordeau, J.F., Iori, M., Laporte, G. and Salazar-González, J.J., A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55 (2010) 46–59. CrossRef
C.E. Cortés, M Matamala and C. Contardo, The Pickup and Delivery Problem with Transfers: Formulation and Solution Approaches, in VII French – Latin American Congress on Applied Mathematics. Springer (2005).
I. Dumitrescu, Polyhedral results for the pickup and delivery travelling salesman problem. Technical Report, CRT-2005-27 (2005).
M.T. Fiala Timlin, Precedence constrained routing and helicopter scheduling. M. Sc. thesis, Department of Combinatorics and Optimization University of Waterloo (1989).
Fiala Timlin, M.T. and Pulleyblank, W.R., Precedence constrained routing and helicopter scheduling: heuristic design. Interfaces 22 (1992) 100–111. CrossRef
Frederickson, G.N. and Guan, D.J., Preemptive ensemble motion planning on a tree. SIAM J. Comput. 21 (1992) 1130. CrossRef
Frederickson, G.N. and Guan, D.J., Nonpreemptive ensemble motion planning on a tree. J. Algorithms 15 (1993) 29–60. CrossRef
Frederickson, G.N., Hecht, M.S. and Kim, C.E., Approximation algorithms for some routing problems. SIAM J. Comput. 7 (1978) 178. CrossRef
L.M. Gambardella and M. Dorigo, An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS J. Comput. 12 (2000) 237–255.
Gouveia, L. and Pesneau, P., On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48 (2006) 77–89. CrossRef
Hernández-Pérez, H. and Salazar-González, J., The multicommodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 196 (2009) 987–995. CrossRef
Kalantari, B., Hill, A.V. and Arora, S.R., An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res. 22 (1985) 377–386. CrossRef
M. Lacroix, Le problème de ramassage et livraison préemptif : complexité, modèles et polyèdres. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2009).
Lin, S., Computer solutions to the traveling salesman problem. Bell System Technical Journal 44 (1965) 2245–2269. CrossRef
Little, J., Murty, K., Sweeney, D. and Karel, C., An algorithm for the traveling salesman problem. Oper. Res. 11 (1963) 972–989. CrossRef
Mitrovic-Minic, S. and Laporte, G., The pickup and delivery problem with time windows and transshipment. INFOR 44 (2006) 217–227.
R. Montemanni, D.H. Smith and L.M. Gambardella, A heuristic manipulation technique for the sequential ordering problem. Comput. Oper. Res. 35 (2008) 3931–3944.
P. Oertel, Routing with Reloads. Doktorarbeit, Universität zu Köln (2000).
Parragh, S.N., Doerner, K.F. and Hartl, R.F., A survey on pickup and delivery problems: Part II: Transportation between pickups and delivery locations. Journal für Betriebswirtschaft 58 (2008) 21–51. CrossRef
Psaraftis, H.N., Dynamic Programming, A solution to the single-vehicle many to-many immediate request dial-a-ride problem. Transp. Sci. 14 (1980) 130–154. CrossRef
Psaraftis, H.N., $k$-interchange procedures for local search in a precedence constrained routing problem. Eur. J. Oper. Res. 13 (1983) 391–402. CrossRef
J. Renaud, F. Boctor and J. Ouenniche, A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 27 (2000) 905–916.
J. Renaud, F. Boctor and G. Laporte, Perturbation heuristics for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 29 (2002) 1129–1141.
Ruland, K.M. and Rodin, E.Y., The pickup and delivery problem: Faces and branch-and-cut algorithm. Comput. Math. Appl. 33 (1997) 1–13. CrossRef
H. Toussaint, Algorithmique rapide pour les problèmes de tournées et d'ordonnancement. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2010).