A Consensus Fixing Based Heuristic for Liner Shipping Network Design with Stochastic Demands

To reach the sustainability goals in maritime shipping, it is important to design a route network that ensures a good utilization of the resources while ensuring sufficient capacity to satisfy the demand. The network design is complicated by fluctuating demand due to seasonal variation in production and demand. In addition, several events in the recent years have highlighted the importance of building robust supply chains where the liner shipping business is a crucial backbone to many of these. Due the significance of liner shipping with naturally fluctuating demand and disruptive events, we consider the Liner Shipping Network Design Problem with Uncertain Demand (LSNDP-UD). As stated in (Johansen et al., 2024), the LSNDP-UD has not been subject to extensive studies and thus motivates further solutions methods. In our work, we exploit the two-folded nature of LSNDP, since this is consisting of 1) designing a network with the objective of minimizing cost and 2) flowing containers through the network in order to maximize revenue. In this structure, we can consider the LSNDP-UN as a two-stage Stochastic Optimization Problem (SOP). Here, the first-stage decisions are to design the network, while the second-stage decisions are to flow the containers in the most efficient way depending on the given demand scenario. When solving SOPs, (Pisinger, 2024) states that there remains a great deal of unexplored methods involving metaheuristics. For this reason, we present a highly parallel metaheuristic based on consensus fixing: The first-stage decisions are solved using an Adaptive Large Neighborhood Search (ALNS) framework while the flow problems are solved using an fast column generation algorithm. We run the method in parallel for varying demand scenarios and in intermediate steps, the scenarios try to reach consensus about fixing first-stage decisions. The process of alternating between heuristic solution (first-stage), column generation (second-stage) and consensus fixing is repeated until we reach our termination criteria. We apply this methodology and report computational results using the real-life instances from LINER-LIB (Brouer et al., 2014). The main idea in the consensus fixing heuristic is to solve each scenario as an independent problem, and then use some heuristic criteria to reach consensus on the first-stage decision variables across the scenarios. Solving independent scenarios is known from Scenario Analysis (SCA) where structures from deterministic solutions can help guide decision-making for stochastic problems (King & Wallace, 2012). Consensus fixing thus falls within the SCA category, however, the novelty of the methodology comes from applying this during the search process. This general methodology was first introduced and successfully implemented in (Pisinger, 2024) on a stochastic price collection TSP. The results were quite promising and the consensus framework was proposed to be a general application tool for solving SOPs. In (Pisinger, 2024), the first-stage decisions were binary variables; should a customer be visited or not. This is not directly applicable for the more complex first-stage decision of LSNDP-UN; designing a network. In this work, we thus aims towards extending the consensus framework for SOPs in order to solve more complex solution structures. The main contribution of our final work can be summarized as follows: (i) We present a twostage stochastic formulation of the well-known liner shipping network design problem. (ii) We use consensus fixing to solve the stochastic problem. Several setups for the consensus-fixing heuristic are investigated. (iii) We apply ALNS to design routes and a fast column generation algorithm to flow containers through a network. (iv) Detailed computational results are presented for all LINER-LIB instances.