×

Tree based models and algorithms for the preemptive asymmetric stacker crane problem. (English) Zbl 1246.90018

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] S. Anily and R. Hassin, The swapping problem. Networks22 (1992) 419-433. · Zbl 0763.90080 · doi:10.1002/net.3230220408
[2] S. Anily, M. Gendreau and G. Laporte, The preemptive swapping problem on a tree. Submitted to Networks (2009). · Zbl 1233.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 · Zbl 0794.90039 · doi:10.1137/0803002
[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 · Zbl 1017.90095 · doi:10.1023/A:1008779125567
[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 · Zbl 0662.68043 · doi:10.1137/0217053
[6] E. Balas, M. Fischetti and W. Pulleyblank, The precedence constrained asymmetric traveling salesman problem. Math. Program.68 (1995) 241-265. Zbl0835.90109 · Zbl 0835.90109 · doi:10.1007/BF01585767
[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 · Zbl 1121.90001 · doi:10.1007/s11750-007-0009-0
[8] C. Bordenave, M. Gendreau and G. Laporte, A branch-and-cut algorithm for the preemptive swapping problem. Technical Report CIRRELT-2008-23 (2008). · Zbl 1247.90072
[9] C. Bordenave, M. Gendreau and G. Laporte, Heuristics for the mixed swapping problem. Comput.Oper.Res.37 (2010) 108-114. Zbl1171.90331 · Zbl 1171.90331 · doi:10.1016/j.cor.2009.03.032
[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 · Zbl 1206.90137 · doi:10.1002/net.20312
[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). · Zbl 1177.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 · Zbl 0760.68033 · doi:10.1137/0221066
[17] G.N. Frederickson and D.J. Guan, Nonpreemptive ensemble motion planning on a tree. J. Algorithms15 (1993) 29-60. Zbl0784.68040 · Zbl 0784.68040 · doi:10.1006/jagm.1993.1029
[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 · Zbl 1040.90570 · doi:10.1287/ijoc.12.3.237.12636
[20] L. Gouveia and P. Pesneau, On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks48 (2006) 77-89. Zbl1103.90084 · Zbl 1103.90084 · doi:10.1002/net.20122
[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 · Zbl 1176.90055 · doi:10.1016/j.ejor.2008.05.009
[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 · Zbl 0585.90084 · doi:10.1016/0377-2217(85)90257-7
[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 · Zbl 0136.14705
[25] J. Little, K. Murty, D. Sweeney and C. Karel, An algorithm for the traveling salesman problem. Oper. Res.11 (1963) 972-989. · Zbl 0161.39305 · doi:10.1287/opre.11.6.972
[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. · Zbl 1278.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. Zbl0505.90045 · Zbl 0505.90045 · doi:10.1016/0377-2217(83)90099-1
[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 · Zbl 0957.90030 · doi:10.1016/S0305-0548(99)00066-0
[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 · Zbl 0994.90110 · doi:10.1016/S0305-0548(00)00109-X
[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 · Zbl 0894.90128 · doi:10.1016/S0898-1221(97)00090-4
[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).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.