Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem

Hervé Kerivin; Mathieu Lacroix; Alain Quilliot; Hélène Toussaint

RAIRO - Operations Research (2011)

  • Volume: 45, Issue: 3, page 179-207
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Kerivin, Hervé, et al. "Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem." RAIRO - Operations Research 45.3 (2011): 179-207. <http://eudml.org/doc/276357>.

@article{Kerivin2011,
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. },
author = {Kerivin, Hervé, Lacroix, Mathieu, Quilliot, Alain, Toussaint, Hélène},
journal = {RAIRO - Operations Research},
keywords = {Preemptive stacker crane problem; routing; local search; heuristics; preemptive stacker crane problem; heuristics},
language = {eng},
month = {10},
number = {3},
pages = {179-207},
publisher = {EDP Sciences},
title = {Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem},
url = {http://eudml.org/doc/276357},
volume = {45},
year = {2011},
}

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
DA - 2011/10//
PB - EDP Sciences
VL - 45
IS - 3
SP - 179
EP - 207
AB - 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.
LA - eng
KW - Preemptive stacker crane problem; routing; local search; heuristics; preemptive stacker crane problem; heuristics
UR - http://eudml.org/doc/276357
ER -

References

top
  1. S. Anily and R. Hassin, The swapping problem. Networks22 (1992) 419–433.  Zbl0763.90080
  2. S. Anily, M. Gendreau and G. Laporte, The preemptive swapping problem on a tree. Submitted to Networks (2009).  Zbl1233.90075
  3. N. Ascheuer, L. Escudero, M. Grötschel and M. Stoer, A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing). SIAM J. Optim.3 (1993) 25–42.  Zbl0794.90039
  4. N. Ascheuer, M. Jünger and G. Reinelt, A Branch and Cut algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Comput. Optim. Appl.17 (2000) 61–84.  Zbl1017.90095
  5. 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.  Zbl0662.68043
  6. E. Balas, M. Fischetti and W. Pulleyblank, The precedence constrained asymmetric traveling salesman problem. Math. Program.68 (1995) 241–265.  Zbl0835.90109
  7. 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 OperationsResearch15 (2007) 1–31.  Zbl1121.90001
  8. C. Bordenave, M. Gendreau and G. Laporte, A branch-and-cut algorithm for the preemptive swapping problem. Technical Report CIRRELT-2008-23 (2008).  Zbl1247.90072
  9. C. Bordenave, M. Gendreau and G. Laporte, Heuristics for the mixed swapping problem. Comput.Oper.Res.37 (2010) 108–114.  Zbl1171.90331
  10. S. Chen and S. Smith, Commonality and genetic algorithms. Technical Report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (1996).  
  11. J.F. Cordeau, M. Iori, G. Laporte and J.J. Salazar-González, A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks55 (2010) 46–59.  Zbl1206.90137
  12. 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).  Zbl1177.90412
  13. I. Dumitrescu, Polyhedral results for the pickup and delivery travelling salesman problem. Technical Report, CRT-2005-27 (2005).  
  14. M.T. Fiala Timlin, Precedence constrained routing and helicopter scheduling. M. Sc. thesis, Department of Combinatorics and Optimization University of Waterloo (1989).  
  15. M.T. Fiala Timlin and W.R. Pulleyblank, Precedence constrained routing and helicopter scheduling: heuristic design. Interfaces22 (1992) 100–111.  
  16. G.N. Frederickson and D.J. Guan, Preemptive ensemble motion planning on a tree. SIAM J. Comput.21 (1992) 1130.  Zbl0760.68033
  17. G.N. Frederickson and D.J. Guan, Nonpreemptive ensemble motion planning on a tree. J. Algorithms15 (1993) 29–60.  Zbl0784.68040
  18. G.N. Frederickson, M.S. Hecht and C.E. Kim, Approximation algorithms for some routing problems. SIAM J. Comput.7 (1978) 178.  
  19. 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.  Zbl1040.90570
  20. L. Gouveia and P. Pesneau, On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks48 (2006) 77–89.  Zbl1103.90084
  21. H. Hernández-Pérez and J. Salazar-González, The multicommodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res.196 (2009) 987–995.  Zbl1176.90055
  22. B. Kalantari, A.V. Hill and S.R. Arora, An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res.22 (1985) 377–386.  Zbl0585.90084
  23. 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).  
  24. S. Lin, Computer solutions to the traveling salesman problem. Bell System Technical Journal44 (1965) 2245–2269.  Zbl0136.14705
  25. J. Little, K. Murty, D. Sweeney and C. Karel, An algorithm for the traveling salesman problem. Oper. Res.11 (1963) 972–989.  Zbl0161.39305
  26. S. Mitrovic-Minic and G. Laporte, The pickup and delivery problem with time windows and transshipment. INFOR44 (2006) 217–227.  
  27. 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.  Zbl1278.90168
  28. P. Oertel, Routing with Reloads. Doktorarbeit, Universität zu Köln (2000).  
  29. S.N. Parragh, K.F. Doerner and R.F. Hartl, A survey on pickup and delivery problems: Part II: Transportation between pickups and delivery locations. Journal für Betriebswirtschaft58 (2008) 21–51.  
  30. H.N. Psaraftis, A Dynamic Programming solution to the single-vehicle many to-many immediate request dial-a-ride problem. Transp. Sci.14 (1980) 130–154.  
  31. H.N. Psaraftis, k -interchange procedures for local search in a precedence constrained routing problem. Eur. J. Oper. Res.13 (1983) 391–402.  
  32. J. Renaud, F. Boctor and J. Ouenniche, A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper.Res.27 (2000) 905–916.  Zbl0957.90030
  33. J. Renaud, F. Boctor and G. Laporte, Perturbation heuristics for the pickup and delivery traveling salesman problem. Comput.Oper.Res.29 (2002) 1129–1141.  Zbl0994.90110
  34. K.M. Ruland and E.Y. Rodin, The pickup and delivery problem: Faces and branch-and-cut algorithm. Comput. Math. Appl.33 (1997) 1–13.  Zbl0894.90128
  35. H. Toussaint, Algorithmique rapide pour les problèmes de tournées et d'ordonnancement. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2010).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.