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 problem, routing, local search, heuristics

@article{RO_2011__45_3_179_0, author = {Kerivin, Herv\'e and Lacroix, Mathieu and Quilliot, Alain and Toussaint, H\'el\`ene}, title = {Tree based models and algorithms for the preemptive asymmetric {Stacker} {Crane} problem}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {179--207}, publisher = {EDP-Sciences}, volume = {45}, number = {3}, year = {2011}, doi = {10.1051/ro/2011110}, mrnumber = {2865232}, zbl = {1246.90018}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2011110/} }

TY - JOUR AU - Kerivin, Hervé AU - Lacroix, Mathieu AU - Quilliot, Alain AU - Toussaint, Hélène TI - Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2011 SP - 179 EP - 207 VL - 45 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2011110/ DO - 10.1051/ro/2011110 LA - en ID - RO_2011__45_3_179_0 ER -

%0 Journal Article %A Kerivin, Hervé %A Lacroix, Mathieu %A Quilliot, Alain %A Toussaint, Hélène %T Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2011 %P 179-207 %V 45 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2011110/ %R 10.1051/ro/2011110 %G en %F RO_2011__45_3_179_0

Kerivin, Hervé; Lacroix, Mathieu; Quilliot, Alain; Toussaint, Hélène. Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem. RAIRO - Operations Research - Recherche Opérationnelle, Volume 45 (2011) no. 3, pp. 179-207. doi : 10.1051/ro/2011110. http://archive.numdam.org/articles/10.1051/ro/2011110/

[1] The swapping problem. Networks 22 (1992) 419-433. | MR | Zbl

and ,[2] The preemptive swapping problem on a tree. Submitted to Networks (2009). | MR | Zbl

, and ,[3] A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing). SIAM J. Optim. 3 (1993) 25-42. | MR | Zbl

, , and ,[4] A Branch and Cut algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Comput. Optim. Appl. 17 (2000) 61-84. | MR | Zbl

, and ,[5] Efficient solutions to some transportation problems with applications to minimizing robot arm travel. SIAM J. Comput. 17 (1988) 849. | MR | Zbl

and ,[6] The precedence constrained asymmetric traveling salesman problem. Math. Program. 68 (1995) 241-265. | MR | Zbl

, and ,[7] 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. | MR | Zbl

, , and ,[8] A branch-and-cut algorithm for the preemptive swapping problem. Technical Report CIRRELT-2008-23 (2008). | MR | Zbl

, and ,[9] Heuristics for the mixed swapping problem. Comput. Oper. Res. 37 (2010) 108-114. | MR | Zbl

, and ,[10] Commonality and genetic algorithms. Technical Report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (1996).

and ,[11] A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55 (2010) 46-59. | MR | Zbl

, , and ,[12] 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). | Zbl

,[13] Polyhedral results for the pickup and delivery travelling salesman problem. Technical Report, CRT-2005-27 (2005).

,[14] Precedence constrained routing and helicopter scheduling. M. Sc. thesis, Department of Combinatorics and Optimization University of Waterloo (1989).

,[15] Precedence constrained routing and helicopter scheduling: heuristic design. Interfaces 22 (1992) 100-111.

and ,[16] Preemptive ensemble motion planning on a tree. SIAM J. Comput. 21 (1992) 1130. | MR | Zbl

and ,[17] Nonpreemptive ensemble motion planning on a tree. J. Algorithms 15 (1993) 29-60. | MR | Zbl

and ,[18] Approximation algorithms for some routing problems. SIAM J. Comput. 7 (1978) 178. | MR

, and ,[19] An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS J. Comput. 12 (2000) 237-255. | MR | Zbl

and ,[20] On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48 (2006) 77-89. | MR | Zbl

and ,[21] The multicommodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 196 (2009) 987-995. | Zbl

and ,[22] An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res. 22 (1985) 377-386. | MR | Zbl

, and ,[23] 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).

,[24] Computer solutions to the traveling salesman problem. Bell System Technical Journal 44 (1965) 2245-2269. | MR | Zbl

,[25] An algorithm for the traveling salesman problem. Oper. Res. 11 (1963) 972-989. | Zbl

, , and ,[26] The pickup and delivery problem with time windows and transshipment. INFOR 44 (2006) 217-227. | MR

and ,[27] A heuristic manipulation technique for the sequential ordering problem. Comput. Oper. Res. 35 (2008) 3931-3944. | Zbl

, and ,[28] Routing with Reloads. Doktorarbeit, Universität zu Köln (2000).

,[29] A survey on pickup and delivery problems: Part II: Transportation between pickups and delivery locations. Journal für Betriebswirtschaft 58 (2008) 21-51.

, and ,[30] A Dynamic Programming solution to the single-vehicle many to-many immediate request dial-a-ride problem. Transp. Sci. 14 (1980) 130-154.

,[31] $k$-interchange procedures for local search in a precedence constrained routing problem. Eur. J. Oper. Res. 13 (1983) 391-402. | Zbl

,[32] A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 27 (2000) 905-916. | MR | Zbl

, and ,[33] Perturbation heuristics for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 29 (2002) 1129-1141. | Zbl

, and ,[34] The pickup and delivery problem: Faces and branch-and-cut algorithm. Comput. Math. Appl. 33 (1997) 1-13. | MR | Zbl

and ,[35] Algorithmique rapide pour les problèmes de tournées et d'ordonnancement. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2010).

,*Cited by Sources: *