IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v36y2002i1p63-78.html
   My bibliography  Save this article

Analysis and Algorithms for the Transtainer Routing Problem in Container Port Operations

Author

Listed:
  • Ananthapadmanabhan Narasimhan

    (Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801)

  • Udatta S. Palekar

    (Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801)

Abstract

The problem of minimizing the time taken to load the containers from the container stack yard onto the ship is called the transtainer routing problem. We first do a theoretical investigation of the problem to understand the structural properties of the problem. We then use these results to prove that the problem is NP -Complete. The problem is then formulated as an integer program. A branch-and-bound based enumerative method is developed to obtain an exact solution to the problem. An algorithm to solve the matching problem on a line at the root node of the branch-and-bound tree is developed. Several lower bounds to prune the size of the tree are also developed. A result which states that there cannot exist a polynomial time heuristic with a bounded worst case unless P = NP is proved. Based on this result, an enumerative heuristic with a worst-case performance ratio of 1.5 is designed. Computational tests on randomly generated problems are conducted to evaluate the exact and heuristic algorithms.

Suggested Citation

  • Ananthapadmanabhan Narasimhan & Udatta S. Palekar, 2002. "Analysis and Algorithms for the Transtainer Routing Problem in Container Port Operations," Transportation Science, INFORMS, vol. 36(1), pages 63-78, February.
    • Handle: RePEc:inm:ortrsc:v:36:y:2002:i:1:p:63-78
    DOI: 10.1287/trsc.36.1.63.576
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.36.1.63.576
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.36.1.63.576?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Mordecai Avriel & Michal Penn & Naomi Shpirer & Smadar Witteboon, 1998. "Stowage planning for container ships to reduce the number of shifts," Annals of Operations Research, Springer, vol. 76(0), pages 55-71, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gharehgozli, Amir Hossein & Yu, Yugang & de Koster, René & Udding, Jan Tijmen, 2014. "An exact method for scheduling a yard crane," European Journal of Operational Research, Elsevier, vol. 235(2), pages 431-447.
    2. Iris F. A. Vis & Hector J. Carlo, 2010. "Sequencing Two Cooperating Automated Stacking Cranes in a Container Terminal," Transportation Science, INFORMS, vol. 44(2), pages 169-182, May.
    3. Kang, Seungmo & Medina, Juan C. & Ouyang, Yanfeng, 2008. "Optimal operations of transportation fleet for unloading activities at container ports," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 970-984, December.
    4. Anne Ehleiter & Florian Jaehn, 2018. "Scheduling crossover cranes at container terminals during seaside peak times," Journal of Heuristics, Springer, vol. 24(6), pages 899-932, December.
    5. Woo, Youn Ju & Kim, Kap Hwan, 2011. "Estimating the space requirement for outbound container inventories in port container terminals," International Journal of Production Economics, Elsevier, vol. 133(1), pages 293-301, September.
    6. Zapfel, Gunther & Wasner, Michael, 2006. "Warehouse sequencing in the steel supply chain as a generalized job shop model," International Journal of Production Economics, Elsevier, vol. 104(2), pages 482-501, December.
    7. Xiao-Ming Yang & Xin-Jia Jiang, 2020. "Yard Crane Scheduling in the Ground Trolley-Based Automated Container Terminal," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(02), pages 1-28, March.
    8. Gharehgozli, Amir & Yu, Yugang & de Koster, René & Du, Shaofu, 2019. "Sequencing storage and retrieval requests in a container block with multiple open locations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 261-284.
    9. Gharehgozli, A.H. & Roy, D. & de Koster, M.B.M., 2014. "Sea Container Terminals," ERIM Report Series Research in Management ERS-2014-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    10. Xi Guo & Shell Ying Huang, 2012. "Dynamic Space and Time Partitioning for Yard Crane Workload Management in Container Terminals," Transportation Science, INFORMS, vol. 46(1), pages 134-148, February.
    11. Dirk Briskorn & Florian Jaehn & Andreas Wiehl, 2019. "A generator for test instances of scheduling problems concerning cranes in transshipment terminals," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 45-69, March.
    12. Ehleiter, Anne & Jaehn, Florian, 2016. "Housekeeping: Foresightful container repositioning," International Journal of Production Economics, Elsevier, vol. 179(C), pages 203-211.
    13. Jiang, Xin Jia & Jin, Jian Gang, 2017. "A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 62-75.
    14. Galle, Virgile & Barnhart, Cynthia & Jaillet, Patrick, 2018. "Yard Crane Scheduling for container storage, retrieval, and relocation," European Journal of Operational Research, Elsevier, vol. 271(1), pages 288-316.
    15. Vallada, Eva & Belenguer, Jose Manuel & Villa, Fulgencia & Alvarez-Valdes, Ramon, 2023. "Models and algorithms for a yard crane scheduling problem in container ports," European Journal of Operational Research, Elsevier, vol. 309(2), pages 910-924.
    16. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    17. Jin, Bo & Yu, Zhishan & Yu, Mingzhu, 2022. "Inbound container remarshaling problem in an automated container terminal," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    18. Amir Hossein Gharehgozli & Gilbert Laporte & Yugang Yu & René de Koster, 2015. "Scheduling Twin Yard Cranes in a Container Block," Transportation Science, INFORMS, vol. 49(3), pages 686-705, August.
    19. Kim, Kap Hwan & Park, Young-Man, 2004. "A crane scheduling method for port container terminals," European Journal of Operational Research, Elsevier, vol. 156(3), pages 752-768, August.
    20. Shell Ying Huang & Ya Li, 2017. "Yard crane scheduling to minimize total weighted vessel loading time in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 689-720, December.
    21. Li, Wenkai & Wu, Yong & Petering, M.E.H. & Goh, Mark & Souza, Robert de, 2009. "Discrete time model and algorithms for container yard crane scheduling," European Journal of Operational Research, Elsevier, vol. 198(1), pages 165-172, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    2. Ji, Mingjun & Guo, Wenwen & Zhu, Huiling & Yang, Yongzhi, 2015. "Optimization of loading sequence and rehandling strategy for multi-quay crane operations in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 1-19.
    3. Shih-Liang Chao & Pi-Hung Lin, 2021. "Minimizing overstowage in master bay plans of large container ships," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 71-93, March.
    4. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    5. Monaco, Maria Flavia & Sammarra, Marcello & Sorrentino, Gregorio, 2014. "The Terminal-Oriented Ship Stowage Planning Problem," European Journal of Operational Research, Elsevier, vol. 239(1), pages 256-265.
    6. Chien-Chang Chou & Pao-Yi Fang, 2021. "Applying expert knowledge to containership stowage planning: an empirical study," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 4-27, March.
    7. Dusan Ku & Tiru S. Arthanari, 2016. "On double cycling for container port productivity improvement," Annals of Operations Research, Springer, vol. 243(1), pages 55-70, August.
    8. Fazi, Stefano, 2019. "A decision-support framework for the stowage of maritime containers in inland shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 1-23.
    9. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    10. Rui Rei & João Pedroso, 2013. "Tree search for the stacking problem," Annals of Operations Research, Springer, vol. 203(1), pages 371-388, March.
    11. Imai, Akio & Sasaki, Kazuya & Nishimura, Etsuko & Papadimitriou, Stratos, 2006. "Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks," European Journal of Operational Research, Elsevier, vol. 171(2), pages 373-389, June.
    12. Parreño, Francisco & Pacino, Dario & Alvarez-Valdes, Ramon, 2016. "A GRASP algorithm for the container stowage slot planning problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 141-157.
    13. Lixin Tang & Jiyin Liu & Fei Yang & Feng Li & Kun Li, 2015. "Modeling and solution for the ship stowage planning problem of coils in the steel industry," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(7), pages 564-581, October.
    14. Ding, Ding & Chou, Mabel C., 2015. "Stowage planning for container ships: A heuristic algorithm to reduce the number of shifts," European Journal of Operational Research, Elsevier, vol. 246(1), pages 242-249.
    15. Rune Larsen & Dario Pacino, 2021. "A heuristic and a benchmark for the stowage planning problem," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 94-122, March.
    16. Franzkeit, Janna & Schwientek, Anne Kathrina & Jahn, Carlos, 2020. "Stowage planning for inland container vessels: A literature review," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Jahn, Carlos & Kersten, Wolfgang & Ringle, Christian M. (ed.), Data Science in Maritime and City Logistics: Data-driven Solutions for Logistics and Sustainability. Proceedings of the Hamburg International Conferen, volume 30, pages 247-280, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    17. R. Roberti & D. Pacino, 2018. "A Decomposition Method for Finding Optimal Container Stowage Plans," Service Science, INFORMS, vol. 52(6), pages 1444-1462, December.
    18. Hyunwoo Park & Christian C. Blanco & Elliot Bendoly, 2022. "Vessel sharing and its impact on maritime operations and carbon emissions," Production and Operations Management, Production and Operations Management Society, vol. 31(7), pages 2925-2942, July.
    19. Byung Kwon Lee & Joyce M. W. Low, 2022. "A constraint programming approach to capacity planning in container vessels," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 24(2), pages 415-438, June.
    20. Delgado, Alberto & Jensen, Rune Møller & Janstrup, Kira & Rose, Trine Høyer & Andersen, Kent Høj, 2012. "A Constraint Programming model for fast optimal stowage of container vessel bays," European Journal of Operational Research, Elsevier, vol. 220(1), pages 251-261.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:36:y:2002:i:1:p:63-78. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.