IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v316y2024i1p152-167.html
   My bibliography  Save this article

An adaptive large neighborhood search heuristic for the multi-port continuous berth allocation problem

Author

Listed:
  • Martin-Iradi, Bernardo
  • Pacino, Dario
  • Ropke, Stefan

Abstract

In this paper, we study a problem that integrates the vessel scheduling problem with the berth allocation into a collaborative problem denoted as the multi-port continuous berth allocation problem (MCBAP). This problem optimizes the berth allocation of a set of ships simultaneously in multiple ports while also considering the sailing speed of ships between ports. Due to the highly combinatorial character of the problem, exact methods struggle to scale to large-size instances, which points to exploring heuristic methods. We present a mixed-integer problem formulation for the MCBAP and introduce an adaptive large neighborhood search (ALNS) algorithm enhanced with a local search procedure to solve it. The computational results highlight the method’s suitability for larger instances by providing high-quality solutions in short computational times. Practical insights indicate that the carriers’ and terminal operators’ operational costs are impacted in different ways by fuel prices, external ships at port, and the modeling of a continuous quay.

Suggested Citation

  • Martin-Iradi, Bernardo & Pacino, Dario & Ropke, Stefan, 2024. "An adaptive large neighborhood search heuristic for the multi-port continuous berth allocation problem," European Journal of Operational Research, Elsevier, vol. 316(1), pages 152-167.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:1:p:152-167
    DOI: 10.1016/j.ejor.2024.02.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724000948
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.02.003?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. Vieira, Bruno S. & Ribeiro, Glaydston M. & Bahiense, Laura & Cruz, Roberto & Mendes, André B. & Laporte, Gilbert, 2021. "Exact and heuristic algorithms for the fleet composition and periodic routing problem of offshore supply vessels with berth allocation decisions," European Journal of Operational Research, Elsevier, vol. 295(3), pages 908-923.
    2. 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.
    3. Fagerholt, Kjetil, 2001. "Ship scheduling with soft time windows: An optimisation based approach," European Journal of Operational Research, Elsevier, vol. 131(3), pages 559-571, June.
    4. Carlo, Héctor J. & Vis, Iris F.A. & Roodbergen, Kees Jan, 2014. "Transport operations in container terminals: Literature overview, trends, research directions and classification scheme," European Journal of Operational Research, Elsevier, vol. 236(1), pages 1-13.
    5. Yu, Jingjing & Tang, Guolei & Song, Xiangqun, 2022. "Collaboration of vessel speed optimization with berth allocation and quay crane assignment considering vessel service differentiation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    6. 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.
    7. Kim, Kap Hwan & Moon, Kyung Chan, 2003. "Berth scheduling by simulated annealing," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 541-560, July.
    8. K Fagerholt & G Laporte & I Norstad, 2010. "Reducing fuel emissions by optimizing speed on shipping routes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(3), pages 523-529, March.
    9. Guo, Liming & Zheng, Jianfeng & Du, Haoming & Du, Jian & Zhu, Zhihong, 2022. "The berth assignment and allocation problem considering cooperative liner carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    10. 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.
    11. 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.
    12. François, Véronique & Arda, Yasemin & Crama, Yves & Laporte, Gilbert, 2016. "Large neighborhood search for multi-trip vehicle routing," European Journal of Operational Research, Elsevier, vol. 255(2), pages 422-441.
    13. Dulebenets, Maxim A., 2018. "A comprehensive multi-objective optimization model for the vessel scheduling problem in liner shipping," International Journal of Production Economics, Elsevier, vol. 196(C), pages 293-318.
    14. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    15. 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.
    16. Du, Yuquan & Chen, Qiushuang & Quan, Xiongwen & Long, Lei & Fung, Richard Y.K., 2011. "Berth allocation considering fuel consumption and vessel emissions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1021-1037.
    17. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    18. Yongpei Guan & Raymond K. Cheung, 2005. "The berth allocation problem: models and solution methods," Springer Books, in: Hans-Otto Günther & Kap Hwan Kim (ed.), Container Terminals and Automated Transport Systems, pages 141-158, Springer.
    19. 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.
    20. Hellsten, Erik Orm & Sacramento, David & Pisinger, David, 2020. "An adaptive large neighbourhood search heuristic for routing and scheduling feeder vessels in multi-terminal ports," European Journal of Operational Research, Elsevier, vol. 287(2), pages 682-698.
    21. 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.
    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. 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.
    2. 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.
    3. 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.
    4. Ya Xu & Kelei Xue & Yuquan Du, 2018. "Berth Scheduling Problem Considering Traffic Limitations in the Navigation Channel," Sustainability, MDPI, vol. 10(12), pages 1-22, December.
    5. Yuquan Du & Qiushuang Chen & Jasmine Siu Lee Lam & Ya Xu & Jin Xin Cao, 2015. "Modeling the Impacts of Tides and the Virtual Arrival Policy in Berth Allocation," Transportation Science, INFORMS, vol. 49(4), pages 939-956, November.
    6. 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).
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Yi Ding & Shuai Jia & Tianyi Gu & Chung-Lun Li, 2016. "SGICT Builds an Optimization-Based System for Daily Berth Planning," Interfaces, INFORMS, vol. 46(4), pages 281-296, August.
    13. Xiang, Xi & Liu, Changchun & Miao, Lixin, 2017. "A bi-objective robust model for berth allocation scheduling under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 294-319.
    14. 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.
    15. 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.
    16. 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.
    17. Guo, Liming & Zheng, Jianfeng & Du, Jian & Gao, Ziyou & Fagerholt, Kjetil, 2024. "Integrated planning of berth allocation, quay crane assignment and yard assignment in multiple cooperative terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    18. Abdellah Salhi & Ghazwan Alsoufi & Xinan Yang, 2019. "An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports," Annals of Operations Research, Springer, vol. 272(1), pages 69-98, January.
    19. Du, Yuquan & Chen, Qiushuang & Quan, Xiongwen & Long, Lei & Fung, Richard Y.K., 2011. "Berth allocation considering fuel consumption and vessel emissions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1021-1037.
    20. Shih-Wei Lin & Ching-Jung Ting & Kun-Chih Wu, 2018. "Simulated annealing with different vessel assignment strategies for the continuous berth allocation problem," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 740-763, December.

    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:ejores:v:316:y:2024:i:1:p:152-167. 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/locate/eor .

    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.