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

Short-term berth planning and ship scheduling for a busy seaport with channel restrictions

Author

Listed:
  • Liu, Baoli
  • Li, Zhi-Chun
  • Wang, Yadong
  • Sheng, Dian

Abstract

This paper addresses the short-term berth planning and ship scheduling issues for a busy seaport with channel restrictions, in which the channel width of the port can accommodate one large-sized ship only or two small-sized ships in its two-way navigation (inbound and outbound). A mixed integer linear programming (MILP) model is presented, in which the inbound/outbound movements of ships between multiple anchorages and multiple basins, and the shifting movements of ships between or within the harbor basins are explicitly taken into account. In view that the MILP model is usually computationally low-efficient for practical large-sized problems, we reformulate the MILP into an equivalent set-partitioning model and develop a column generation (CG) algorithm to solve this model. Several efficient methods are also proposed to improve the performance of the CG algorithm. The computational experiments for a real Chinese port show that the proposed CG algorithm significantly outperforms some existing methods (e.g., branch-and-cut and truncated column generation) and the port scheduling schemes adopted in reality. It can solve the instances with up to 35 inbound ships, 35 outbound ships, 6 shifting ships, and 43 berths within ten minutes, with an average optimality gap of 0.32%. Managerial insights for the port operators are also provided to guide the operations and management of the ports with channel restrictions.

Suggested Citation

  • Liu, Baoli & Li, Zhi-Chun & Wang, Yadong & Sheng, Dian, 2021. "Short-term berth planning and ship scheduling for a busy seaport with channel restrictions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
  • Handle: RePEc:eee:transe:v:154:y:2021:i:c:s1366554521002301
    DOI: 10.1016/j.tre.2021.102467
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554521002301
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tre.2021.102467?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. Paul Corry & Christian Bierwirth, 2019. "The Berth Allocation Problem with Channel Restrictions," Transportation Science, INFORMS, vol. 53(3), pages 708-727, May.
    2. 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.
    3. Shuai Jia & Chung-Lun Li & Zhou Xu, 2019. "Managing Navigation Channel Traffic and Anchorage Area Utilization of a Container Port," Transportation Science, INFORMS, vol. 53(3), pages 728-745, May.
    4. 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.
    5. 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.
    6. 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.
    7. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    8. Amir Hossein Gharehgozli & Debjit Roy & René de Koster, 2016. "Sea container terminals: New technologies and OR models," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 18(2), pages 103-140, June.
    9. M. Flavia Monaco & Marcello Sammarra, 2007. "The Berth Allocation Problem: A Strong Formulation Solved by a Lagrangean Approach," Transportation Science, INFORMS, vol. 41(2), pages 265-280, May.
    10. Li, Shuqin & Jia, Shuai, 2019. "The seaport traffic scheduling problem: Formulations and a column-row generation algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 158-184.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Meng, Qiang & Wang, Shuaian & Lee, Chung-Yee, 2015. "A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 1-19.
    18. Xiaogang Jiao & Feifeng Zheng & Ming Liu & Yinfeng Xu, 2018. "Integrated Berth Allocation and Time-Variant Quay Crane Scheduling with Tidal Impact in Approach Channel," Discrete Dynamics in Nature and Society, Hindawi, vol. 2018, pages 1-19, October.
    19. 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.
    20. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.
    21. 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.
    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. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2022. "A two-stage stochastic programming model for seaport berth and channel planning with uncertainties in ship arrival and handling times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    2. 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).
    3. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2023. "A branch-and-price heuristic algorithm for the bunkering operation problem of a liquefied natural gas bunkering station in the inland waterways," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 145-170.
    4. Wang, Zehao & Zeng, Qingcheng & Li, Xingchun & Qu, Chenrui, 2024. "A branch-and-price heuristic algorithm for the ART and external truck scheduling problem in an automated container terminal with a parallel layout," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    5. 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.
    6. Zhao, Ke & Jin, Jian Gang & Zhang, Di & Ji, Sheng & Lee, Der-Horng, 2023. "A variable neighborhood search heuristic for real-time barge scheduling in a river-to-sea channel with tidal restrictions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    7. Gao, Zhendi & Ji, Mingjun & Kong, Lingrui & Hou, Xinhao, 2024. "Scheduling of automated ore terminal operations based on fixed inflow rhythm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 182(C).
    8. Hao, Luyao & Jin, Jian Gang & Zhao, Ke, 2023. "Joint scheduling of barges and tugboats for river–sea intermodal transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).

    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, 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.
    2. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2022. "A two-stage stochastic programming model for seaport berth and channel planning with uncertainties in ship arrival and handling times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    3. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2023. "A branch-and-price heuristic algorithm for the bunkering operation problem of a liquefied natural gas bunkering station in the inland waterways," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 145-170.
    4. 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.
    5. 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.
    6. 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.
    7. Fernández, Elena & Munoz-Marquez, Manuel, 2022. "New formulations and solutions for the strategic berth template problem," European Journal of Operational Research, Elsevier, vol. 298(1), pages 99-117.
    8. Li, Shuqin & Jia, Shuai, 2019. "The seaport traffic scheduling problem: Formulations and a column-row generation algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 158-184.
    9. 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.
    10. Wu, Lingxiao & Jia, Shuai & Wang, Shuaian, 2020. "Pilotage planning in seaports," European Journal of Operational Research, Elsevier, vol. 287(1), pages 90-105.
    11. Shuai Jia & Chung-Lun Li & Zhou Xu, 2019. "Managing Navigation Channel Traffic and Anchorage Area Utilization of a Container Port," Transportation Science, INFORMS, vol. 53(3), pages 728-745, May.
    12. Paul Corry & Christian Bierwirth, 2019. "The Berth Allocation Problem with Channel Restrictions," Transportation Science, INFORMS, vol. 53(3), pages 708-727, May.
    13. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    14. Eduardo Lalla-Ruiz & Stefan Voß & Christopher Expósito-Izquierdo & Belén Melián-Batista & J. Marcos Moreno-Vega, 2017. "A POPMUSIC-based approach for the berth allocation problem under time-dependent limitations," Annals of Operations Research, Springer, vol. 253(2), pages 871-897, June.
    15. 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.
    16. Qin, Tianbao & Du, Yuquan & Sha, Mei, 2016. "Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 167-185.
    17. 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.
    18. 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.
    19. Guo, Zijian & Cao, Zhen & Wang, Wenyuan & Jiang, Ying & Xu, Xinglu & Feng, Peng, 2021. "An integrated model for vessel traffic and deballasting scheduling in coal export terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    20. Petris, Matteo & Pellegrini, Paola & Pesenti, Raffaele, 2022. "Models and algorithms for an integrated vessel scheduling and tug assignment problem within a canal harbor," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1120-1135.

    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:154:y:2021:i:c:s1366554521002301. 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.