A heterogeneous fleet liner ship scheduling problem with port time uncertainty

We deal with a schedule design problem for a heterogeneous fleet liner shipping service under uncertain waiting and handling times at ports. In a liner shipping service, longer than expected waiting and handling times at a port may cause a delay from scheduled departure time. We consider the problem to find the departure times at ports and sailing times of ships between ports so that the total fuel burn is minimized while targeted overall service level (a performance measure based on on-time departure probabilities) is achieved. We consider two new aspects of the problem. The first one is the heterogeneous fleet where each ship type may have different fuel efficiency, i.e. a different fuel burn function. The second one is considering critical ports on the route, i.e. considering the fact that on-time performance at some critical ports might be more important for the shipping company. We propose a model which finds different service levels for different ship type-port pairs by considering importance of ports and fuel efficiencies of ships. We also give a new overall service level measure for the entire route by combining service levels for different ship type-ports pairs. We propose a chance constrained nonlinear mixed integer programming formulation for the problem. Finally, we give computational results that show the effects of several experimental factors on fuel consumption, speed and service level.