Hyperconnected Logistics Hub Network Design Under Reliability
and Adversarial Disruptions
Onkar Kulkarnia,∗ , Mathieu Dahana , and Benoit Montreuila,ba Physical Internet Center, Supply Chain & Logistics Institute, School of Industrial andSystems Engineering, Georgia Institute of Technology, Atlanta, Georgia, USAb Coca-Cola Chair in Material Handling and Distribution
onkar.kulkarni@gatech.edu, mathieu.dahan@isye.gatech.edu, benoit.montreuil@isye.gatech.edu∗ Corresponding author
Keywords: Hyperconnected Network Design, Multi-Stage Optimization, Resilience, PhysicalInternet

1

INTRODUCTION

The recent surge in e-commerce and world trade has led the parcel delivery industry to be oneof the fastest growing industries. Due to efforts for quicker parcel delivery, the industry requires
meticulous planning and proper execution. The planning phase involves strategic decision making such as logistics hub network design. Although the Hub-and-spoke configuration for logistics
hub networks has been widely studied (Ben-Ayed, 2013), this topology does not perform well inhigh demand scenarios as it may cause congestion of parcels at hubs during peak delivery times(Tu & Montreuil, 2019). To improve the overall parcel delivery process and to overcome thecurrent limitations, hyperconnected logistics networks have been proposed in the Physical Internet (PI). Hyperconnected logistics networks are multi-plane interconnected meshed networks
that link open-access hubs present on multiple planes. Together they shape an open network of
networks, termed a logistics web (Montreuil et al., 2018).
Nevertheless, all logistics networks, including those shaping the PI’s logistics web, face disruptions
caused by frequent events such as power outages or major traffic jams, as well as low-probability
high-impact events such as natural disasters, pandemics, and deliberate attacks. Such disruptions lead to delayed parcel deliveries, increased delivery costs, and excess pressure on functional
network components. Some investigations consider disruptions at hubs and transportation edges
to design a small-scale network (Zhalechian et al., 2018). However, such a small network reveals
little to an industry that aims to persistently deliver parcels across a wide geographical region.
In (Kulkarni et al., 2021), the authors propose solution approaches based on integer programs
to design large-scale hyperconnected networks that can sustain random disruptions.
In this work, we formulate a tri-level stochastic optimization model to design a large-scale hyperconnected meshed logistics hub network that can sustain random and worst-case disruptions. To
solve this problem, we first study an integer-programming-based heuristic algorithm that selects
hubs so as to connect every origin-destination pair with multiple shortest edge-disjoint paths.
We conduct non-adversarial and adversarial disruption experiments to compare the efficiency
and resilience of the proposed solution against that of traditional lean logistics networks. Next,
we aim to scale an exact solution approach based on the L-shaped method that leverages the
structure of the problem to design optimally resilient hyperconnected logistics networks.

2

METHODOLOGY

We consider a logistics company or a group of such companies that seeks to design a resilient
hyperconnected intercity logistics hub network to transport commodities between a set of OriginDestination (O-D) pairs P by opening H logistics hubs among a predefined finite set of candidate
locations. Each O-D pair p ∈ P is associated with a commodity demand of Dp units. Let E denotethe set of directed edges (i, j) representing the available transportation links connecting locations
TRISTAN XI Symposium

Original abstract submittal

Onkar Kulkarni, Mathieu Dahan, and Benoit Montreuil

2i and j. These edges induce hyperconnectivity by connecting any two locations that are withina specified travel time. For each edge (i, j), we denote τij its traveling time in nominal situations.
However, traveling along these edges is prone to delays caused by disruptions. The logistics
company has access to historical data regarding the travel times on each edge in E. We suppose that these disruption events can be modeled using a representative finite set of scenariosΩ. Each scenario ω ∈ Ω occurs with a probability πω and associates each edge (i, j) with atravel time τijω . In addition, the network also experiences extreme disruption events, caused bynatural disasters or adversarial attacks, for which the company has less data and cannot include
in the set of scenarios Ω. Thus, the company also wants to ensure that the designed network isresilient against worst-case disruptions, which are assumed to occur with probability πwc . Then,the goal is to select a subset of hub locations so that the network connects every O-D pair, is efficient in terms of transportation, and is resilient against random and worst-case edge disruptions.
To this end, we develop a tri-level optimization model. In the first stage, the logistics company
selects which hubs to open. For each potential logistics hub candidate h, we define the binary
variable yh that is equal to 1 if hub h is open. The disruption scenario occurs during the second
stage: With probability πω , scenario ω of random disruptions occurs, while with probability πwc ,a fictitious adversary with a disruption budget B allocates continuous delays xij to the networkedges as to maximize the company’s cost of operations. In the third stage, the company transports the commodities based on the realized disruption scenario. We model this stage using aflow formulation: For every O-D pair p and every edge (i, j), we define flow variables fijp,ω andfijp,wc for each random disruption scenario ω and the worst-case disruption, respectively. Theseflow variables represent the amount of each commodity traveling along each edge under eachdisruption scenario. Commodities can only flow on transportation edges that connect logistics
hubs opened in the first stage, and satisfy the flow conservation constraints.
The objective of the logistics company is to minimize the total cost of fulfilling the demand,
assumed in this model to be proportional to the total distance traveled by commodities. Thus,
the third-stage flow decision variables f are selected so as to minimize the route length for eachcommodity in each scenario. The fictitious adversary aims to maximize the length of the shortest
route between each O-D pair. Finally, the logistics company selects the hubs to open in the firststage so as to minimize the total shortest path lengths, averaged across all disruption scenarios,
including the worst-case scenario. The objective of the problem can be formulated as follows:
(
min
y

X
ω∈Ω

πω · minωfnX X
p∈P (i,j)∈E

τijω fijp,ω

on+ πwc · max min
wc
x

f

nX X

(τij + xij )fijp,wc

)
oo
. (1)

p∈P (i,j)∈E

The problem defined above is challenging to solve for real-world instances due to the large numberof random scenarios and potential combinations of opened hubs. In order to tackle this problem,
we first propose a heuristic algorithm, which selects hubs to open using an integer program
so as to connect every O-D pair with multiple shortest edge-disjoint paths. To evaluate theresilience of the network, the worst-case disruption scenario is determined by solving a linear
program obtained by dualizing the third-stage flow problem, similarly to the single shortest pathinterdiction problem (Israeli & Wood, 2002). Secondly, we leverage the structure of the problem
to propose an exact solution algorithm. In particular, we find that by sequentially dualizing thethird and second stages, we obtain a large-scale mixed-integer program. Thus, we employ theL-shaped method (Slyke & Wets, 1969) to solve (1), where we split the decisions into two stages.
We fix the first-stage decisions, then obtain a lower bound on the second stage value function
and successively add cuts to better approximate the shape of the second-stage value function.
Our ongoing efforts consist in scaling this algorithm to real-world instances.
TRISTAN XI Symposium

Original abstract submittal

Onkar Kulkarni, Mathieu Dahan, and Benoit Montreuil

3

3

CASE STUDY AND PRELIMINARY RESULTS

We apply the developed solution approaches to design a resilient hyperconnected intercity parcel
logistics hub network to be the backbone infrastructure of China for ground transportation andconsolidation of parcels. This network will form one tier in a PI-oriented multi-plane meshednetwork and could be leveraged by multiple parcel delivery companies to move numerous millionsof parcels every day between Chinese cities. The network is to serve 184 O-D pairs in regions thathouse 91.88% of the Chinese population and are spread across 93.81% of the Chinese inhabitableland with 92.17% of total Chinese GDP (Li et al., 2018).
To design the network, we consider 807 candidate locations for intercity hubs that are either
major highway intersections and/or existing city-based hubs (inbound/outbound). In addition,
due to regulations imposed by the Chinese government, a truck driver can drive for 11 hours
per day and hence, we limit the transportation edges (i, j) ∈ E to up to 5.5 hours’ drive time
between locations to enable truck drivers to return home daily while the parcels keep moving
toward their destinations. The resulting graph contains 44,330 directed edges.
In this preliminary work, we design a resilient logistics hub network by using the above-mentioned
integer-programming-based heuristic. Specifically, we opened 80 hubs to connect each O-D pair –with identical demand – by four edge-disjoint paths. To compare the proposed resilient networkwith a lean meshed network, we also designed a lean network by selecting 80 hubs to open withthe goal of minimizing the (single) shortest path length between each O-D pair. Similarly, thetransportation edges were limited to 5.5 hours’ drive. Figure 1 illustrates the resulting networks.

(a) Lean network(b) Resilient network

Figure 1 – Hyperconnected logistics meshed networks with 80 hubs. Blue asterisks represent opened
hubs, and red lines represent transportation edges connecting hubs within 5.5 hours’ drive.
We validate the performance and resilience of the proposed network by analyzing the impact of
non-adversarial and adversarial disruptions. We conduct two sets of experiments: (i) random
disruptions, where each disruption scenario increases the travel time on a single edge by a certain
percentage; and (ii) worst-case disruptions, where a fictitious adversary has a delay budget toallocate across edges so as to maximize the total shortest path lengths across all commodities.
In the random edge disruption experiment, it can be observed that the increase in disruption
strength has little impact on the average shortest path length between O-D pairs in the proposed
network whereas the effect is quite significant in the lean logistics network. Table 1 bolsters thisclaim and shows that the the average increase in shortest path length in the proposed network
is 10 times lower than that of the lean logistics network.
TRISTAN XI Symposium

Original abstract submittal

Onkar Kulkarni, Mathieu Dahan, and Benoit Montreuil

4

Table 1 – Average increase in shortest path length (hours) during the random edge disruption
experiment for networks of size H = 80.
Increase in
Edge Length
50%
100%
150%
200%

Lean Logistics
Meshed Network
1.97
3.08
4.05
4.95

Resilient Hyperconnected
Logistics Meshed Network
0.202
0.256
0.296
0.481

In case of adversarial disruptions, it can be seen in Figure 2 that the lean logistics network
worsens at a higher rate compared to the proposed network as the disruptive impact increases.
Interestingly, the performance in nominal situations (when the total delay available to the adversary is 0) of the lean network is better than that of the resilient network but comparable. With
this marginal compromise in performance in the absence of disruptions, the proposed network
achieves a significantly higher capability to sustain adversarial disruptions in comparison to thelean network. Thus, our study illustrates the value of optimization and the Physical Internet indesigning hyperconnected meshed logistics network that are efficient and resilient.

Figure 2 – Worst-case disruption experiment for networks of size H = 80.
In the presentation, we intend to depict network designs obtained through the scaled L-shaped
algorithm to optimally solve the tri-level optimization problem (1) exactly for real-world instances, and compare its performance with heuristically generated network designs. We plan toillustrate the trade-off between efficiency and resilience capabilities among these networks in anuanced manner through simulations under real-world disruption scenarios. We will also show
the effect of hub capacity constraints on network designs and chalk out future research avenues.

References
Ben-Ayed, Omar. 2013. Parcel distribution network design problem. Operational Research, 13, 211–232.
Israeli, Eitan, & Wood, R. Kevin. 2002. Shortest-path network interdiction. Networks, 40(2), 97–111.
Kulkarni, Onkar, Cohen, Yaarit M., Dahan, Mathieu, & Montreuil, Benoit. 2021. Resilient Hyperconnected Logistics Hub Network Design. In: 8th International Physical Internet Conference.
Li, Minmin, He, Biao, Guo, Renzhong, Li, You, Chen, Yu, & Fan, Yong. 2018. Study on population
distribution pattern at the county level of China. Sustainability (Switzerland), 10(10).
Montreuil, B., Buckley, Shannon M., Faugère, Louis, Khir, Reem, & Derhami, Shahab. 2018. Urban
Parcel Logistics Hub and Network Design: The Impact of Modularity and Hyperconnectivity.
Slyke, R. M. Van, & Wets, Roger. 1969. L-Shaped Linear Programs with Applications to Optimal Control
and Stochastic Programming. SIAM Journal on Applied Mathematics, 17(4), 638–663.
Tu, Dan, & Montreuil, Benoit. 2019. MultiHyperconnected Megacity Logistics: Multi-Tier Territory
Clustering and Multi-plane Meshed Hub Network Design.
Zhalechian, M., Torabi, S. Ali, & Mohammadi, M. 2018. Hub-and-spoke network design under operationaland disruption risks. Transportation Research Part E: Logistics and Transportation Review, 109, 20–43.

TRISTAN XI Symposium

Original abstract submittal