Highlights The Tidal Berth Time Window concept is introduced for the first time in the routing problem. Tides can influence the feasibility of ship routes, leading to nonlinear multiple time windows associated with the shipload and the tidal pattern. A formulation of nonlinear mixed integer programming is developed, encompassing ship routing, pickup-and-delivery scheduling, speed optimization, and tidal berth time windows. To the author's knowledge, this is the first study to jointly consider routing and speed optimization while incorporating both pickup-and-delivery and multiple time windows. A Branch-and-Price(B&P) framework is proposed to solve the aforementioned model. The framework decomposed the model into a set partitioning master problem and a pricing subproblem. To generate possible routes, a spatial-tempo labeling algorithm and a heuristic acceleration are designed., These algorithms address pickup and delivery as well as speed optimization. Furthermore, tailored domination rules are implemented to handle multiple time windows. Realistic simulated instances are used to test the model and algorithm. The results compare the effectiveness of the two proposed algorithms and demonstrate the economic benefits of considering the tidal berth time windows in tramp ship schedules.

    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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Tramp ship routing and speed optimization with tidal berth time windows


    Contributors:
    Gao, Yuan (author) / Sun, Zhuo (author)


    Publication date :

    2023-08-27




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    Tramp ship routing and scheduling with speed optimization

    Norstad, Inge / Fagerholt, Kjetil / Laporte, Gilbert | Elsevier | 2010


    Tramp ship operation

    Engineering Index Backfile | 1930


    Tramp ship with machinery aft

    Engineering Index Backfile | 1953