IDEAS home Printed from https://ideas.repec.org/a/spr/eurjtl/v8y2019i4d10.1007_s13676-018-0128-9.html
   My bibliography  Save this article

The stochastic discrete berth allocation problem

Author

Listed:
  • Xavier Schepler

    (Université d’Angers)

  • Nabil Absi

    (Ecole des Mines de Saint-Etienne and LIMOS, UMR CNRS 6158, CMP Georges Charpak)

  • Dominique Feillet

    (Ecole des Mines de Saint-Etienne and LIMOS, UMR CNRS 6158, CMP Georges Charpak)

  • Eric Sanlaville

    (Normandie Univ, UNIHAVRE, LITIS)

Abstract

This paper deals with the discrete berth allocation problem with stochastic arrival times of vessels. The problem is to assign incoming vessels to a finite set of berthing points (berths) and to schedule them. The major objective is to minimize the expected total turnaround time of the vessels. We develop several new proactive, reactive and proactive/reactive approaches to this problem. Numerical experiments enable to compare these approaches. They show the impact of using full stochastic information instead of using mean values in a deterministic setting. The proactive/reactive approach, based on iterated tabu search and stochastic dynamic programming, provides good results when uncertainties on arrival times remain limited, while requiring only a few minutes of computing time on average. For larger levels of uncertainty, the proposed pure reactive approach clearly outperforms the others.

Suggested Citation

  • Xavier Schepler & Nabil Absi & Dominique Feillet & Eric Sanlaville, 2019. "The stochastic discrete berth allocation problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 363-396, December.
    • Handle: RePEc:spr:eurjtl:v:8:y:2019:i:4:d:10.1007_s13676-018-0128-9
    DOI: 10.1007/s13676-018-0128-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13676-018-0128-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13676-018-0128-9?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. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    2. Ursavas, Evrim & Zhu, Stuart X., 2016. "Optimal policies for the berth allocation problem under stochastic nature," European Journal of Operational Research, Elsevier, vol. 255(2), pages 380-387.
    3. 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.
    4. 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.
    5. 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.
    6. Michael Pinedo, 1983. "Stochastic Scheduling with Release Dates and Due Dates," Operations Research, INFORMS, vol. 31(3), pages 559-572, June.
    7. Jam Dai & Wuqin Lin & Rajeeva Moorthy & Chung-Piaw Teo, 2008. "Berth Allocation Planning Optimization in Container Terminals," International Series in Operations Research & Management Science, in: Christopher S. Tang & Chung-Piaw Teo & Kwok-Kee Wei (ed.), Supply Chain Analysis, pages 69-104, Springer.
    8. 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.
    9. Ya Xu & Qiushuang Chen & Xiongwen Quan, 2012. "Robust berth scheduling with uncertain vessel delay and handling time," Annals of Operations Research, Springer, vol. 192(1), pages 123-140, January.
    10. 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.
    11. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    12. Theo E Notteboom, 2006. "The Time Factor in Liner Shipping Services," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 8(1), pages 19-39, March.
    13. Han, Xiao-le & Lu, Zhi-qiang & Xi, Li-feng, 2010. "A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1327-1340, December.
    14. Bert Vernimmen & Wout Dullaert & Steve Engelen, 2007. "Schedule Unreliability in Liner Shipping: Origins and Consequences for the Hinterland Supply Chain," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 9(3), pages 193-213, September.
    15. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    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. Agra, Agostinho & Rodrigues, Filipe, 2022. "Distributionally robust optimization for the berth allocation problem under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 164(C), pages 1-24.
    2. Rodrigues, Filipe & Agra, Agostinho, 2022. "Berth allocation and quay crane assignment/scheduling problem under uncertainty: A survey," European Journal of Operational Research, Elsevier, vol. 303(2), pages 501-524.
    3. Jaap-Jan Steeg & Menno Oudshoorn & Neil Yorke-Smith, 2023. "Berth planning and real-time disruption recovery: a simulation study for a tidal port," Flexible Services and Manufacturing Journal, Springer, vol. 35(1), pages 70-110, March.

    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. Changchun Liu & Xi Xiang & Li Zheng, 2020. "A two-stage robust optimization approach for the berth allocation problem under uncertainty," Flexible Services and Manufacturing Journal, Springer, vol. 32(2), pages 425-452, June.
    2. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    3. 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.
    4. Changchun Liu & Xi Xiang & Li Zheng, 2017. "Two decision models for berth allocation problem under uncertainty considering service level," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 312-344, December.
    5. 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.
    6. 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.
    7. Iris, Çağatay & Lam, Jasmine Siu Lee, 2019. "Recoverable robustness in weekly berth and quay crane planning," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 365-389.
    8. Shangyao Yan & Chung-Cheng Lu & Jun-Hsiao Hsieh & Han-Chun Lin, 2019. "A Dynamic and Flexible Berth Allocation Model with Stochastic Vessel Arrival Times," Networks and Spatial Economics, Springer, vol. 19(3), pages 903-927, September.
    9. 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.
    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. Robenek, Tomáš & Umang, Nitish & Bierlaire, Michel & Ropke, Stefan, 2014. "A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports," European Journal of Operational Research, Elsevier, vol. 235(2), pages 399-411.
    12. 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.
    13. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    14. Nitish Umang & Michel Bierlaire & Alan L. Erera, 2017. "Real-time management of berth allocation with stochastic arrival and handling times," Journal of Scheduling, Springer, vol. 20(1), pages 67-83, February.
    15. Rodrigues, Filipe & Agra, Agostinho, 2022. "Berth allocation and quay crane assignment/scheduling problem under uncertainty: A survey," European Journal of Operational Research, Elsevier, vol. 303(2), pages 501-524.
    16. Rodrigues, Filipe & Agra, Agostinho, 2021. "An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times," European Journal of Operational Research, Elsevier, vol. 295(2), pages 499-516.
    17. 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).
    18. Kramer, Arthur & Lalla-Ruiz, Eduardo & Iori, Manuel & Voß, Stefan, 2019. "Novel formulations and modeling enhancements for the dynamic berth allocation problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 170-185.
    19. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    20. Ursavas, Evrim & Zhu, Stuart X., 2016. "Optimal policies for the berth allocation problem under stochastic nature," European Journal of Operational Research, Elsevier, vol. 255(2), pages 380-387.

    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:spr:eurjtl:v:8:y:2019:i:4:d:10.1007_s13676-018-0128-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.