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.
Tramp ship routing and speed optimization with tidal berth time windows
2023-08-27
Article (Journal)
Electronic Resource
English
Tramp ship routing and scheduling with speed optimization
Online Contents | 2011
|Tramp ship routing and scheduling with speed optimization
Elsevier | 2010
|Engineering Index Backfile | 1930
Engineering Index Backfile | 1953
Combined ship allocation, routing and freight assignment in tramp shipping
Online Contents | 2011
|