IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v105y2017icp123-147.html
   My bibliography  Save this article

Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem

Author

Listed:
  • Iris, Çağatay
  • Pacino, Dario
  • Ropke, Stefan

Abstract

This paper focuses on the integrated berth allocation and quay crane assignment problem in container terminals. We consider the decrease in the marginal productivity of quay cranes and the increase in handling time due to deviation from the desired position. We consider a continuous berth, discretized in small equal-sized sections. A number of enhancements over the state-of-the-art formulation and an Adaptive Large Neighborhood Search (ALNS) heuristic are presented. Computational results reveal that the enhancements improve many of the best-known bounds, and the ALNS outperforms the state-of-the-art heuristics for many instances. We also conduct further analysis on a new larger benchmark.

Suggested Citation

  • Iris, Çağatay & Pacino, Dario & Ropke, Stefan, 2017. "Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 123-147.
    • Handle: RePEc:eee:transe:v:105:y:2017:i:c:p:123-147
    DOI: 10.1016/j.tre.2017.06.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554516308535
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2017.06.013?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Cordeau, Jean-François & Laporte, Gilbert & Moccia, Luigi & Sorrentino, Gregorio, 2011. "Optimizing yard assignment in an automotive transshipment terminal," European Journal of Operational Research, Elsevier, vol. 215(1), pages 149-160, November.
    2. Feng Li & Jiuh-Biing Sheu & Zi-You Gao, 2015. "Solving the Continuous Berth Allocation and Specific Quay Crane Assignment Problems with Quay Crane Coverage Range," Transportation Science, INFORMS, vol. 49(4), pages 968-989, November.
    3. Lee, Der-Horng & Chen, Jiang Hang & Cao, Jin Xin, 2010. "The continuous Berth Allocation Problem: A Greedy Randomized Adaptive Search Solution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1017-1029, November.
    4. Hansen, Pierre & Mladenovic, Nenad & Moreno Pérez, Jos´e A., 2008. "Variable neighborhood search," European Journal of Operational Research, Elsevier, vol. 191(3), pages 593-595, December.
    5. Imai, Akio & Chen, Hsieh Chia & Nishimura, Etsuko & Papadimitriou, Stratos, 2008. "The simultaneous berth and quay crane allocation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(5), pages 900-920, September.
    6. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2016. "Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals," European Journal of Operational Research, Elsevier, vol. 254(3), pages 985-1001.
    7. Jin, Jian Gang & Lee, Der-Horng & Hu, Hao, 2015. "Tactical berth and yard template design at container transshipment terminals: A column generation based approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 168-184.
    8. Frank Meisel & Christian Bierwirth, 2013. "A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals," Transportation Science, INFORMS, vol. 47(2), pages 131-147, May.
    9. Imai, Akio & Nishimura, Etsuko & Papadimitriou, Stratos, 2001. "The dynamic berth allocation problem for a container port," Transportation Research Part B: Methodological, Elsevier, vol. 35(4), pages 401-417, May.
    10. Hansen, Pierre & Oguz, Ceyda & Mladenovic, Nenad, 2008. "Variable neighborhood search for minimum cost berth allocation," European Journal of Operational Research, Elsevier, vol. 191(3), pages 636-649, December.
    11. Iris, Çağatay & Pacino, Dario & Ropke, Stefan & Larsen, Allan, 2015. "Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 75-97.
    12. Buhrkal, Katja & Zuglian, Sara & Ropke, Stefan & Larsen, Jesper & Lusby, Richard, 2011. "Models for the discrete berth allocation problem: A computational comparison," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(4), pages 461-473, July.
    13. Lu Zhen & Ek Peng Chew & Loo Hay Lee, 2011. "An Integrated Model for Berth Template and Yard Template Planning in Transshipment Hubs," Transportation Science, INFORMS, vol. 45(4), pages 483-504, November.
    14. Giallombardo, Giovanni & Moccia, Luigi & Salani, Matteo & Vacca, Ilaria, 2010. "Modeling and solving the Tactical Berth Allocation Problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 232-245, February.
    15. Jiyin Liu & Yat‐wah Wan & Lei Wang, 2006. "Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 60-74, February.
    16. Türkoğulları, Yavuz B. & Taşkın, Z. Caner & Aras, Necati & Altınel, İ. Kuban, 2014. "Optimal berth allocation and time-invariant quay crane assignment in container terminals," European Journal of Operational Research, Elsevier, vol. 235(1), pages 88-101.
    17. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    18. Jean-François Cordeau & Gilbert Laporte & Pasquale Legato & Luigi Moccia, 2005. "Models and Tabu Search Heuristics for the Berth-Allocation Problem," Transportation Science, INFORMS, vol. 39(4), pages 526-538, November.
    19. Meisel, Frank & Bierwirth, Christian, 2009. "Heuristics for the integration of crane productivity in the berth allocation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 196-209, January.
    20. Muller, Laurent Flindt & Spoorendonk, Simon & Pisinger, David, 2012. "A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times," European Journal of Operational Research, Elsevier, vol. 218(3), pages 614-623.
    21. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    22. Shang, Xiao Ting & Cao, Jin Xin & Ren, Jie, 2016. "A robust optimization approach to the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 44-65.
    23. Lalla-Ruiz, Eduardo & Expósito-Izquierdo, Christopher & Melián-Batista, Belén & Moreno-Vega, J. Marcos, 2016. "A Set-Partitioning-based model for the Berth Allocation Problem under Time-Dependent Limitations," European Journal of Operational Research, Elsevier, vol. 250(3), pages 1001-1012.
    24. Imai, Akio & Sun, Xin & Nishimura, Etsuko & Papadimitriou, Stratos, 2005. "Berth allocation in a container port: using a continuous location space approach," Transportation Research Part B: Methodological, Elsevier, vol. 39(3), pages 199-221, March.
    25. Imai, Akio & Yamakawa, Yukiko & Huang, Kuancheng, 2014. "The strategic berth template problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 77-100.
    26. Ilaria Vacca & Matteo Salani & Michel Bierlaire, 2013. "An Exact Algorithm for the Integrated Planning of Berth Allocation and Quay Crane Assignment," Transportation Science, INFORMS, vol. 47(2), pages 148-161, May.
    Full references (including those not matched with items on IDEAS)

    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. Liu, Changchun, 2020. "Iterative heuristic for simultaneous allocations of berths, quay cranes, and yards under practical situations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    2. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    3. Zhen, Lu & Liang, Zhe & Zhuge, Dan & Lee, Loo Hay & Chew, Ek Peng, 2017. "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 193-217.
    4. Fanrui Xie & Tao Wu & Canrong Zhang, 2019. "A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem," Transportation Science, INFORMS, vol. 53(5), pages 1427-1454, September.
    5. Kai Wang & Lu Zhen & Shuaian Wang, 2018. "Column Generation for the Integrated Berth Allocation, Quay Crane Assignment, and Yard Assignment Problem," Transportation Science, INFORMS, vol. 52(4), pages 812-834, August.
    6. Guo, Liming & Zheng, Jianfeng & Liang, Jinpeng & Wang, Shuaian, 2023. "Column generation for the multi-port berth allocation problem with port cooperation stability," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 3-28.
    7. Sung Won Cho & Hyun Ji Park & Chulung Lee, 2021. "An integrated method for berth allocation and quay crane assignment to allow for reassignment of vessels to other terminals," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 123-153, March.
    8. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    9. Iris, Çağatay & Pacino, Dario & Ropke, Stefan & Larsen, Allan, 2015. "Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 75-97.
    10. Feng Li & Jiuh-Biing Sheu & Zi-You Gao, 2015. "Solving the Continuous Berth Allocation and Specific Quay Crane Assignment Problems with Quay Crane Coverage Range," Transportation Science, INFORMS, vol. 49(4), pages 968-989, November.
    11. T. R. Lalita & G. S. R. Murthy, 2022. "Compact ILP formulations for a class of solutions to berth allocation and quay crane scheduling problems," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 413-439, March.
    12. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    13. Imai, Akio & Yamakawa, Yukiko & Huang, Kuancheng, 2014. "The strategic berth template problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 77-100.
    14. Wawrzyniak, Jakub & Drozdowski, Maciej & Sanlaville, Éric, 2020. "Selecting algorithms for large berth allocation problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 844-862.
    15. Agra, Agostinho & Oliveira, Maryse, 2018. "MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem," European Journal of Operational Research, Elsevier, vol. 264(1), pages 138-148.
    16. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    17. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    18. Shang, Xiao Ting & Cao, Jin Xin & Ren, Jie, 2016. "A robust optimization approach to the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 44-65.
    19. Liu, Baoli & Li, Zhi-Chun & Sheng, Dian & Wang, Yadong, 2021. "Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 23-47.
    20. Lu Zhen & Shuaian Wang & Kai Wang, 2016. "Terminal allocation problem in a transshipment hub considering bunker consumption," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(7), pages 529-548, October.

    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:eee:transe:v:105:y:2017:i:c:p:123-147. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.