Feeder Ship Routing Problem with Tidal Time Windows

In a shipping network, feeder ships need to fulfill the demand for cargo transportation between a hub port and its feeder ports. The objective of the Feeder Ship Routing Problem (FSRP) is to minimize the transportation cost, while the feasible time of entering and leaving a port is affected by tide and load due to the limitation of the waterway depth. Different from classic VRPTW(Vehicle Routing Problem with Time Windows), the tidal time windows in this study change by the route of the ship, bringing a challenge to solve the problem. This paper studies an FSRP with nonlinear time windows and solved by Column Generation after a model simplification by Dantzig-Wolfe Decomposition. Numerical experiments and sensitivity analyses proved that the algorithm is effective and that considering tidal influence can effectively reduce the operation cost of the fleet.