Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
EURO Journal on Transportation and Logistics
Published in: EURO Journal on Transportation and Logistics 4/2017

15-08-2016 | Research Paper

New models and algorithms for the container stack rearrangement problem by yard cranes in maritime ports

Authors: Niraj Ramesh Dayama, Andreas Ernst, Mohan Krishnamoorthy, Vishnu Narayanan, Narayan Rangaraj

Published in: EURO Journal on Transportation and Logistics | Issue 4/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Whenever sets of objects are piled up in heaps, columns or stacks, any rearrangement of these objects requires substantial amount of time, effort and cost. In this paper, we study the problem of optimizing such “stack-rearrangement operations” when multiple similar objects or blocks need to be rearranged. We discuss the problem in the context of yard crane operations in maritime ports, where cargo containers are stored and fetched by yard cranes. We intend to minimize the crane operations that are required during container stack rearrangement by yard cranes. This paper defines the underlying abstract mathematical problem and proves its computational complexity. Thereafter, we propose suitable mathematical models for the problem and devise several (exact) approaches to solve it. We provide several families of new problem data instances and the prove the efficacy of our algorithms by doing extensive computational analysis over the data instances.
previous article Minimizing the logistic ratio in the inventory routing problem
next article The stochastic vehicle routing problem, a literature review, Part II: solution methods

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
AAPA rankings (2010) Traffic of containers handled at major container ports. http://​en.​wikipedia.​org/​wiki/​List_​of_​world’s_busiest_container_ports. Last accessed 19 May 2013
Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. J ACM 55(5):23:1–23:27
Aslidis A (1989) Combinatorial algorithms for stacking problems. Ph.D. thesis, Massachusetts Institute of Technology
Bang-Jensen J, Thomassen C (1992) A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J Disc Math 5(3):366–376CrossRef
Bohrer P (2005) Crane scheduling in container terminals. Ph.D. thesis
Caserta M, Voß S, Sniedovich M (2011) Applying the corridor method to a blocks relocation problem. OR Spectr 33(4):915–929CrossRef
Caserta M, Schwarze S, Vo S (2012) A mathematical formulation and complexity considerations for the blocks relocation problem. Eur J Oper Res 219(1):96–104CrossRef
Castillo BD, Daganzo CF (1993) Handling strategies for import containers at marine terminals. Transp Res Part B 27(2):151–166CrossRef
Charbit P, Thomassé S, Yeo A (2007) The minimum feedback arc set problem is NP-hard for tournaments. Comb Probab Comput 16(1):1–4CrossRef
Chen T (1999) Yard operations in the container terminal—a study in the unproductive moves. Marit Policy Manag 26(1):27–38CrossRef
Chen L, Langevin A, Riopel D (2011) A tabu search algorithm for the relocation problem in a warehousing system. Int J Prod Econ 129(1):147–156CrossRef
Christofides N, Colloff I (1973) The rearrangement of items in a warehouse. Oper Res 21(2):577–589CrossRef
Claus A (1984) A new formulation for the travelling salesman problem. SIAM J Algebraic Discrete Methods 5(1):21–25CrossRef
Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper Res 2(4):393–410
Dekker R, Voogd P, Asperen E (2007) Advanced methods for container stacking. In: Kim KH, Gunther HO(eds) Container terminals and cargo systems. Springer, Berlin, pp 131–154
Forster F, Bortfeldt A (2012) A tree search procedure for the container relocation problem. Comput Oper Res 39(2):299–309CrossRef
Graham R, Lawler E, Lenstra J, Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326. (In: Discrete optimization II proc of the adv research inst. on disc. opt. and systems applications. Elsevier)
Hamdi SE, Mabrouk A, Bourdeaudhuy T (2012) A heuristic for the container stacking problem in automated maritime ports. In: Information control problems in manufacturing, volume 14 | part 1. 14th IFAC symp. on information control problems in manufacturing
Huynh N (2008) Analysis of container dwell time on marine terminal throughput and rehandling productivity. J Int Logist Trade 6(2):69–89CrossRef
Ileri Y, Bazaraa M, Gifford T, Nemhauser G, Sokol J, Wikum E (2006) An optimization approach for planning daily drayage operations. Central Eur J Oper Res 14:141–156CrossRef
Kahn AB (1962) Topological sorting of large networks. Commun ACM 5(11):558–562CrossRef
Karpinski M, Schudy W (2010) Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. In: Algorithms and computation, lecture notes in computer science, vol 6506. Springer, Berlin, pp 3–14
Kefi M, Korbaa O, Ghedira K, Yim P (2007) Heuristic-based model for container stacking problem. In: 19th intl. conf. on prod. research
Kim K (1997) Evaluation of the number of rehandles in container yards. Comput Ind Eng 32(4):701–711CrossRef
Kim KH, Park YM, Ryu KR (2000) Deriving decision rules to locate export containers in container yards. EJOR 124(1):89–101CrossRef
Kim KH, Bae JW (1998) Re-marshaling export containers in port container terminals. Comput Ind Eng 35:655–658 (Selected Papers from the 22nd ICC and IE Conf)CrossRef
Kim KH, Kim HB (2002) The optimal sizing of the storage space and handling facilities for import containers. Transp Res 36(9):821–835CrossRef
Kozan E, Preston P (1999) Genetic algorithms to schedule container transfers at multimodal terminals. Int Trans Oper Res 6(3):311–329CrossRef
Laporte G (1997) Modeling and solving several classes of arc routing problems as traveling salesman problems. Comput Oper Res 24(11):1057–1061CrossRef
Mittal AK (1975) Optimal rearrangement of objects. Ph.D. thesis, Case Western Reserve University
Ng W, Mak K (2005) Yard crane scheduling in port container terminals. Appl Math Model 29(3):263–276CrossRef
Padberg M, Sung TY (1991) An analytical comparison of different formulations of the travelling salesman problem. Math Program 52(1–3):315–357CrossRef
Park K, Park T, Ryu K (2013) Planning for selective remarshaling in an automated container terminal using coevolutionary algorithms. Int J Ind Eng Theory Appl Pract 20:1–2
Peterkofsky RI, Daganzo CF (1990) A branch and bound solution method for the crane scheduling problem. Transp Res Part B Methodol 24(3):159–172CrossRef
Phatchara S, Kanchana S, Banchar A (2013) A solution of the container stacking problem by genetic algorithm. Int J Eng Tech 5(1):45–49
Ramachandran V (1988) Finding a minimum feedback arc set in reducible flow graphs. J Algorithms 9(3):299–313CrossRef
Srour FJ, van de Velde S (2013) Are stacker crane problems easy? A statistical study. Comput Oper Res 40(3):674–690CrossRef
Steenken D, Voß S, Stahlbock R (2004) Container terminal operation and operations research—a classification and literature review. OR Spectr 26(1):3–49CrossRef
Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146–160CrossRef
Watanabe I (1991) Characteristics and analysis method of efficiencies of container terminal: an approach to the optimal loading/unloading method. Container Age 3:36–47
Zhu Y, Lim A (2004) Crane scheduling with spatial constraints: mathematical model and solving approaches. In: AIM 30-2004, 8th intl symp. on AI and math., vol 6, pp 1–10
Metadata
Title
New models and algorithms for the container stack rearrangement problem by yard cranes in maritime ports
Authors
Niraj Ramesh Dayama
Andreas Ernst
Mohan Krishnamoorthy
Vishnu Narayanan
Narayan Rangaraj
Publication date
15-08-2016
Publisher
Springer Berlin Heidelberg
Published in
EURO Journal on Transportation and Logistics / Issue 4/2017
Print ISSN: 2192-4376
Electronic ISSN: 2192-4384
DOI
https://doi.org/10.1007/s13676-016-0098-8

Premium Partner

    Image Credits