Highlights • The heterogeneity of container vessels is considered. • The vessel schedule reliability problem with uncertainties is introduced. • A novel two-step approach with two programming sub-models is developed. • Conditional value-at-risk is adopted to measure uncertainty risk. • Total costs and delay times significantly decrease with risk aversion.

Abstract Schedule reliability is a crucial metric for measuring liner container shipping service. Due to the inherent uncertainties at sea and ports, schedule delays and unreliable on-time performance have long plagued shipping companies. In practice, the heterogeneity of container vessels also creates challenges for deployment and schedule optimization. To address the problem, we develop a two-step approach with two programming sub-models. In the first step, we tackle the challenges of ship deployment and scheduling by considering heterogeneous vessels and capturing the interarrival time between adjacent ports of call. In the second step, we use the conditional value-at-risk (CVaR) to address the uncertainty risk avoidance in schedule design. To solve the stochastic programming models, we employ a solution framework based on the outer linear approximation method and the risk measure method, where CVaR is specified as the risk measure. We illustrate the application of our model on a case study concerning a real route operated by COSCO Shipping Lines. The results show that the total cost of liner shipping service with heterogeneous fleet on the route can be reduce by 4.77% compared with homogeneous fleet. And the cost of risk with the reliable schedule can be decreased by 8.04% compared with the ideal schedule. The research conclusions can provide some useful decision-making references for shipping companies to deploy heterogeneous vessels and design reliable schedules.