We introduce the problem of Capacitated Relay Network Design under Stochastic Demand and Consolidation-Based Routing (CRND-SDCR), which focuses on improving the efficiency and resiliency of large-scale relay logistics hub networks against demand variability by integrating tactical planning decisions. We model the commodity demand uncertainty through a finite set of stochastic scenarios and formulate CRND-SDCR as a two-stage stochastic program with mixed-integer recourse. The first stage comprises long-term decisions where we locate relay hubs and decide their respective sizes whereas the second stage involves tactical decisions, where we design a minimum-cost consolidation plan on a multi-commodity flow network for a given stochastic commodity demand realization.

We develop a decomposition-based branch-and-cut algorithm that uses nested Benders decomposition and Integer L-shaped method coupled with sample average approximation. We employ Benders decomposition at two stages: Akin to classical stochastic programs, we solve for each stochastic scenario, the dual of the linear programming relaxation of our second-stage subproblem to add Benders feedback cuts to the first-stage master problem. However, as the LP relaxation of the second-stage problem entails solving a capacitated multi-commodity minimum-cost network flow problem, solving it and its dual by directly feeding it to an off-the-shelf optimization solver is not computationally efficient. Hence, we use Benders decomposition (again) to solve the relaxed second-stage subproblem by decomposing it on the basis of each O-D pair. Here, we leverage the underlying network-flow structure to generate Benders cuts in polynomial time using shortest-path routines. In order to enhance the computational efficiency of our solution approach even further, we add valid inequalities and strengthen the formulations by adding specific dummy variables. Finally, to guarantee the exactness of our solution approach, we add integer L-shaped cuts by solving the second-stage subproblem exactly through Benders decomposition as well.

We conduct an extensive case study pertaining to the design of large-scale relay networks to be used for finished vehicle deliveries of a US-based car manufacturer company that partnered with our research team. We show that our solution approach can obtain provably (near) optimal solutions for practically relevant instances and that our tailored implementation of decomposition-based branch-and-cut scales better in comparison to its classical counterpart with an increase in demand scenarios and network size. We assess the performance of the generated networks by determining minimum-cost consolidation plans for all available stochastic demand scenarios, and compare it with that of relay networks designed for an average parcel demand scenario. Our designed networks showcase significantly higher robustness against demand variability, as they can fulfill more demand by short-haul transportation and at a lower cost. Finally, we benchmark the performance of our generated relay networks against literature-proposed relay networks designed by approximating the tactical planning decisions and depict the importance of considering such tactical planning decisions at the network design stage.

Practical network design applications are often complicated by temporal considerations such as transit times and time-varying network parameters. While these problems can be modeled with time-indexed formulations, this often results in huge time-expanded graphs. The recently-developed dynamic discretization discovery (DDD) method allows many time-dependent problems to become more tractable by iteratively solving instances of the problem on smaller networks where each node has its own discrete set of departure times.

However, in the current implementation of DDD, all arcs departing a common node share the same set of departure times. This causes DDD to be ineffective for solving problems where all near-optimal solutions require many distinct departure times at the majority of the nodes in the network. To address this shortcoming, we develop a DDD framework where the set of departure times is determined on the arc level rather than the node level. This approach is particularly effective for region-based networks.

Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that, in the general model, it is NP-hard to determine whether a feasible sortation plan exists. We discuss several special settings, where (near-)feasibility of a given sortation instance can be determined efficiently. The algorithms we propose are fast and build on combinatorial witness set type lower bounds that are reminiscent and extend those used in earlier work on degree-bounded spanning trees and arborescences.

The scalability of optimization models is a common concern in academic literature, but in industry, scalability to multiple use cases is equally critical. Often overlooked, this aspect results in a proliferation of optimization models, each with similar mathematical structures, but specialized software for solving distinct problems. This presentation delves into the design of software solutions that enable resolution of diverse business challenges at scale.