Highlights • An optimal liner ship routing and scheduling model in the mixed integer linear programming form is proposed, particularly taking into account schedule-sensitive demand and late-arrival penalty. • Two robust optimization counterparts of the deterministic ship routing and scheduling model are constructed for finding solutions in the uncertain weather and ocean conditions along the Northern Sea Route (NSR). • The value of robust optimization techniques in worst cases, the impact of revenue rate and demand sensitivity on solutions, the relationship between the order of a visited port and the weight of its uncertainty budget, and the relationship between the solution robustness and the variation tendency of uncertainty budgets, are exhibited.

Abstract Since sailing along the Northern Sea Route (NSR) through the Arctic Ocean comes into reality, commercial shipping developments including opening new liner services along this route have been put on the agenda. However, uncertainties within weather and ocean conditions in this region, especially during temperature-varying seasons, may cause failure to on-time arrivals, resulting unignorable or even unaffordable monetary losses. As a result, these uncertainties will inevitably affect cargo shippers’ willingness of choosing this being-explored route, even if on average its shipping time is much shorter than that of the traditional Asia-Europe shipping lines. In this context, the present paper describes a liner ship routing and scheduling problem considering schedule-sensitive demand and late-arrival penalty for operating incoming NSR shipping lines in the future. By using two types of uncertainty sets, bounded and budget-bounded uncertainty sets, we construct and solve two robust counterparts of this problem. The deterministic model and bounded robust model can be seen as special cases of the budget-bounded robust model when the uncertainty budget is set to null and full, respectively. A multifaceted case study of planning liner shipping routes and schedules along the NSR is conducted to validate the efficacy and efficiency of the proposed models and identify the effects of uncertainty bounds and budgets on the solution performance. The following facts and conclusions are revealed from the optimization results of the case study: The budget-bounded robust model functions the best in the worst condition; low revenue rate and high demand sensitivity are the major factors for excluding a candidate port from the route; the order of a visited port in the route decides the weight of its uncertainty budget on the entire shipping line; setting the uncertainty budget in a decelerative way will enhance the scheduling robustness of solutions.