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

Pilotage planning in seaports

Author

Listed:
  • Wu, Lingxiao
  • Jia, Shuai
  • Wang, Shuaian

Abstract

Vessel pilotage is compulsory in most seaports around the world. When traveling into or out of the terminal of a seaport, vessels should be navigated by sea pilots in order to follow correct and safe waterways. This paper studies a pilotage planning problem that involves decisions of scheduling the vessel traffic in a seaport, assigning work shifts to pilots, and scheduling the pilots in each work shift for vessel navigation. We formulate the problem as a linear mixed-integer programming (MIP) model that aims at minimizing the cost incurred by the pilotage operations, and show that the problem is strongly NP-hard. For solving the problem, we develop a branch-and-price (B&P) algorithm in which the pricing problem is solved by a novel dynamic programming algorithm. We further propose several acceleration techniques to improve the efficiency of the B&P algorithm. The computational performance of the B&P algorithm is evaluated in extensive numerical experiments. Computational results demonstrate that the B&P algorithm is able to solve problem instances of practical sizes, and that the algorithm outperforms a standard MIP solver and a solution method commonly used in practice.

Suggested Citation

  • Wu, Lingxiao & Jia, Shuai & Wang, Shuaian, 2020. "Pilotage planning in seaports," European Journal of Operational Research, Elsevier, vol. 287(1), pages 90-105.
    • Handle: RePEc:eee:ejores:v:287:y:2020:i:1:p:90-105
    DOI: 10.1016/j.ejor.2020.05.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720304203
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.05.009?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. Cruz, Roberto & Bergsten Mendes, André & Bahiense, Laura & Wu, Yue, 2019. "Integrating berth allocation decisions in a fleet composition and periodic routing problem of platform supply vessels," European Journal of Operational Research, Elsevier, vol. 275(1), pages 334-346.
    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. 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.
    6. 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.
    7. Dong, Jing-Xin & Song, Dong-Ping, 2009. "Container fleet sizing and empty repositioning in liner shipping systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(6), pages 860-877, November.
    8. 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.
    9. 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.
    10. Dong-Ping Song & Jonathan Carter, 2009. "Empty container repositioning in liner shipping1," Maritime Policy & Management, Taylor & Francis Journals, vol. 36(4), pages 291-307, August.
    11. Ng, ManWo, 2017. "Revisiting a class of liner fleet deployment models," European Journal of Operational Research, Elsevier, vol. 257(3), pages 773-776.
    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. Zhen, Lu & Xu, Zhou & Wang, Kai & Ding, Yi, 2016. "Multi-period yard template planning in container terminals," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 700-719.
    14. 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.
    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. Meng, Qiang & Wang, Tingsong & Wang, Shuaian, 2012. "Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand," European Journal of Operational Research, Elsevier, vol. 223(1), pages 96-105.
    17. 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.
    18. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    19. 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.
    20. Marek Wermus & James A. Pope, 1994. "Scheduling Harbor Pilots," Interfaces, INFORMS, vol. 24(2), pages 44-52, April.
    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. Sphiwe Eugene Mthembu & Mihalis Chasomeris, 2023. "An evaluation of the governance structure of marine services in South Africa’s ports system," Journal of Shipping and Trade, Springer, vol. 8(1), pages 1-22, December.
    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. Guo, Yunlong & Jin, Yongxing & Hu, Shenping & Yang, Zaili & Xi, Yongtao & Han, Bing, 2023. "Risk evolution analysis of ship pilotage operation by an integrated model of FRAM and DBN," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    5. Abou Kasm, Omar & Diabat, Ali & Bierlaire, Michel, 2021. "Vessel scheduling with pilotage and tugging considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    6. 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. 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.
    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 & 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.
    4. 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).
    5. 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.
    6. Abou Kasm, Omar & Diabat, Ali & Bierlaire, Michel, 2021. "Vessel scheduling with pilotage and tugging considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    7. 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.
    8. 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).
    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. 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.
    11. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    12. 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).
    13. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    14. 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.
    15. 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.
    16. Xufeng Tang & Chang Liu & Xinqi Li & Ying Ji, 2023. "Distributionally Robust Programming of Berth-Allocation-with-Crane-Allocation Problem with Uncertain Quay-Crane-Handling Efficiency," Sustainability, MDPI, vol. 15(18), pages 1-27, September.
    17. 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.
    18. 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.
    19. Chargui, Kaoutar & Zouadi, Tarik & El Fallahi, Abdellah & Reghioui, Mohamed & Aouam, Tarik, 2021. "Berth and quay crane allocation and scheduling with worker performance variability and yard truck deployment in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    20. Paul Corry & Christian Bierwirth, 2019. "The Berth Allocation Problem with Channel Restrictions," Transportation Science, INFORMS, vol. 53(3), pages 708-727, May.

    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:287:y:2020:i:1:p:90-105. 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.