Joint service capacity planning and dynamic container routing in shipping network with uncertain demands

• Model joint service capacity planning and shipment routing with uncertainty.
• Apply SAA and PHA to solve small-scale problems.
• Develop a new APHA to solve the problem for large shipping network in reality.
• Compare SAA, PHA, and APHA on both hypothetic and realistic networks.

Service capacity planning is a key tactic decision in container shipping, which has a significant impact on daily operations of shipping company. On the other hand, operational decisions such as demand fulfilment and shipment routing will impact on service capacity requirements and utilisation, particularly in the presence of demand uncertainty. This article proposes a two stage stochastic programming model with recourse to deal with the problem of joint service capacity planning and dynamic container routing in liner shipping. The first stage of the model concerns how to determine the optimal service capacity, and the second focuses on the optimal routing of shipments in stochastic and dynamic environments under a given service capacity plan. Initially, SAA (Sample Average Approximation) is employed to solve the model. Noting the computational complexity of the problem, Progressive Hedging Algorithm (PHA) is employed to decompose the SAA model into a number of scenario-based models so that reasonably large scale problems can be solved. To handle larger scale problems, we develop a new solution procedure termed as APHA (Adapted Progressive Hedging Algorithm) that further decomposes the scenario-based model into job (customer order) based models with measurable error bounds. Numerical experiments are conducted to illustrate the effectiveness of the proposed APHA in solving the problems under consideration.