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

Tramp ship routing and speed optimization with tidal berth time windows

Author

Listed:
  • Gao, Yuan
  • Sun, Zhuo

Abstract

Tramp shipping companies need to schedule shipping routes and decide on appropriate speeds based on short-term demand. This task differs from traditional vehicle routing problems (VRPs) in that the ship may wait for the tide, which changes with time. The wait time is a nonlinear function of the load, and in this paper, we describe this kind of wait as the ship following a tidal berth time windows. Additionally, the speed of the ship affects both the wait time and the sailing cost. This paper proposes a mixed-integer nonlinear programming model to tackle this problem. A branch-and-price framework is applied to solve the model efficiently, decomposing the model into a set partitioning master problem and an elementary shortest path subproblem. A labeling algorithm incorporating ship speed is developed to handle the subproblem, and further enhancements are made by optimizing the speed separately. Computational experiments show the effectiveness and accuracy of the proposed solution approach for large-scale instances. Moreover, considering the tidal time windows allows for exploiting the practical benefits of raising tides, which benefits the tramp shipping industry.

Suggested Citation

  • Gao, Yuan & Sun, Zhuo, 2023. "Tramp ship routing and speed optimization with tidal berth time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 178(C).
    • Handle: RePEc:eee:transe:v:178:y:2023:i:c:s1366554523002569
    DOI: 10.1016/j.tre.2023.103268
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523002569
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2023.103268?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. Hennig, F. & Nygreen, B. & Furman, K.C. & Song, J., 2015. "Alternative approaches to the crude oil tanker routing and scheduling problem with split pickup and split delivery," European Journal of Operational Research, Elsevier, vol. 243(1), pages 41-51.
    2. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    3. Homsi, Gabriel & Martinelli, Rafael & Vidal, Thibaut & Fagerholt, Kjetil, 2020. "Industrial and tramp ship routing problems: Closing the gap for real-scale instances," European Journal of Operational Research, Elsevier, vol. 283(3), pages 972-990.
    4. 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.
    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. Rigot-Müller, Patrick & Cheaitou, Ali & Etienne, Laurent & Faury, Olivier & Fedi, Laurent, 2022. "The role of polarseaworthiness in shipping planning for infrastructure projects in the Arctic: The case of Yamal LNG plant," Transportation Research Part A: Policy and Practice, Elsevier, vol. 155(C), pages 330-353.
    2. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    3. Wang, Shuaian, 2015. "Optimal sequence of container ships in a string," European Journal of Operational Research, Elsevier, vol. 246(3), pages 850-857.
    4. 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.
    5. Paredes-Belmar, Germán & Montero, Elizabeth & Lüer-Villagra, Armin & Marianov, Vladimir & Araya-Sassi, Claudio, 2022. "Vehicle routing for milk collection with gradual blending: A case arising in Chile," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1403-1416.
    6. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    7. Unsal, Ozgur & Oguz, Ceyda, 2019. "An exact algorithm for integrated planning of operations in dry bulk terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 103-121.
    8. Andreas T. Ernst & Ceyda Oğuz & Gaurav Singh & Gita Taherkhani, 2017. "Mathematical models for the berth allocation problem in dry bulk terminals," Journal of Scheduling, Springer, vol. 20(5), pages 459-473, October.
    9. 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.
    10. Frank, Markus & Ostermeier, Manuel & Holzapfel, Andreas & Hübner, Alexander & Kuhn, Heinrich, 2021. "Optimizing routing and delivery patterns with multi-compartment vehicles," European Journal of Operational Research, Elsevier, vol. 293(2), pages 495-510.
    11. Issam Krimi & Raca Todosijević & Rachid Benmansour & Mustapha Ratli & Abdessamad Ait Cadi & Afaf Aloullal, 2020. "Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints," Journal of Global Optimization, Springer, vol. 78(2), pages 349-373, October.
    12. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    13. Alessandro Hill & Eduardo Lalla-Ruiz & Stefan Voß & Marcos Goycoolea, 2019. "A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 173-182, April.
    14. Wang, Shuang & Jia, Haiying & Lu, Jing & Yang, Dong, 2023. "Crude oil transportation route choices: A connectivity reliability-based approach," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    15. 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.
    16. Duan, Gang & Aghalari, Amin & Chen, Li & Marufuzzaman, Mohammad & Ma, Junfeng, 2021. "Vessel routing optimization for floating macro-marine debris collection in the ocean considering dynamic velocity and direction," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    17. 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.
    18. Jingjing Tong & Heather Nachtmann, 2017. "Cargo prioritization and terminal allocation problem for inland waterway disruptions," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 19(3), pages 403-427, August.
    19. 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.
    20. 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.

    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:178:y:2023:i:c:s1366554523002569. 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.