\titlesizeMulti-Period Stochastic Logistic Hub Capacity Planning
for Relay Transportation

Multi-Period Stochastic Capacity Planning, Relay Transportation, Hub Capacity-Routing Problem, Physical Internet

As reported in [1], truck driver shortage reached a historic high of over 80,000 in 2021, and predictions indicate it may exceed 160,000 by 2030. The traditional end-to-end transportation heavily depends on long-haul freight movement. Covering extensive distances in a single trip requires drivers to endure prolonged periods away from home, which negatively impacts the physical and mental health of drivers, constituting a major factor in truck driver shortage [2, 3]. To address these problems, many researchers are exploring a shift from conventional end-to-end transportation to relay transportation [4, 5]. The key idea behind relay transportation is to position logistic hubs along transport routes. Then the tasks of long-haul freight shipments can be distributed among multiple short-haul drivers commuting between fixed-base hubs. This approach enables truckers to operate near their residences and return home everyday.

However, one of the main challenges in adopting relay transportation is the need for a large number of physical facilities - logistic hubs, which is especially unfriendly to small and medium-sized carriers. The introduction of the Physical Internet (PI) offers a promising avenue for addressing this challenge. Proposed by [4], PI presents an innovative approach to shaping supply chains, guiding them towards sustainability, economic efficiency, and social responsibility. One of the core concepts of PI is to promote an open and cooperative sharing economy. Distinguishing from the ordinary sharing economy, the PI infrastructure is open to multiple parties rather than exclusively dedicated to a single company or group of companies. Building on this concept, [6] utilize a multi-agent simulation to demonstrate that resource-sharing transportation within the framework of PI enhances the performance of transport operations across financial, operational, social, and environmental dimensions.

Motivated by the innovative concept of PI, we examine a setting where an RTC aims to contract with hub providers to secure space for relay transportation under demand variations and uncertain travel time caused by network disruptions. Within this context, we define a multi-period stochastic hub capacity planning with routing problem (referred to as MSHCRP) to determine dynamic hub throughput capacities as well as shipment routing at each planning period. We then formulate a two-stage stochastic optimization model for the MSHCRP, aiming to minimize overall expenses while addressing both demand and travel time uncertainty. However, the resulting mixed-integer programming (MIP) poses computational challenges for real-world problems. To tackle this issue, we adopt a scenario reduction algorithm proposed by [7] to approximate underlying continuous distributions for demand and travel time.

The rest of this paper is organized as follows. Section 2 briefly summarizes literature reviews of the relevant works. In Section 3, we describe the problem setting and state research assumptions. Section 4 formulates a two-stage stochastic program model and presents the scenario generation and reduction method to alleviate the computational challenge. Section 5 delineates the dataset and experiments, extracting insights from the obtained results. Finally, Section 6 concludes this paper and discusses future research avenues.

The hub location-routing problem (HLRP) has received considerable attention in academic research for decades. Introduced by [9], HLRP comprises two levels of decisions: a strategic level focused on determining hub locations and an operational level dealing with route planning. However, a notable critique of classical (single-period) HLRP is the disparity between the long-term nature of strategic decisions and the short-term nature of operational decisions [10]. To bridge this temporal gap, the multi-period HLRP emerges as a viable solution, offering more frequent planning intervals for routing decisions. Although this multi-period approach is not novel, relevant research within the HLRP literature remains limited. Previous work by [11] explored scenarios involving progressive hub openings or closures, and studies by [12] considered dynamic modular hub capacity that can gradually expand over the planning horizon. These considerations reflect real-world constraints, where budgetary limitations and resource availability may prohibit the simultaneous setup of an entire hub network. Another issue identified in the existing literature on HLRP is the heavy reliance on long-haul deliveries due to the significant costs associated with constructing hubs. This results in poor working conditions for drivers and further exacerbates the ongoing truck driver shortage. To alleviate this problem, we suggest an innovative solution where carriers can dynamically lease hub capacity through short-term contracts and use these hubs as simple relay facilities, which are not only cost-effective but also easily adjustable. This variant of multi-period HLRP allows carriers to manage long-haul shipments efficiently using short-haul drivers, promoting a driver-friendly approach. Additionally, it provides greater flexibility for carriers to adapt to dynamic environments.

The increasing complexities of real-world scenarios highlight the need to incorporate stochastic elements into problem modeling. In the literature on HLRP, two main types of uncertainties are usually considered separately: demand uncertainty, reflecting changes or fuzziness in demand, and travel time uncertainty, associated with factors such as traffic congestion or network failures. For instance, [12] utilized a polynomial function to capture time-dependent demand dynamics, addressing a multi-period HLRP through various meta-heuristic algorithms. [13] addressed seasonal fluctuations in the air freight market, formulating air hub location and flight routing as a two-stage stochastic program model. In a different context, [14] explored HLRP with congestion effects in cargo delivery, while [15] proposed an HLRP model based on two-stage stochastic optimization under the risk of hub disruptions. However, to the best of our knowledge, limited effort has been made to integrate both demand and travel time uncertainty within a multi-period framework, let alone adapting it to the context of relay-based transportation. Our study aims to bridge this gap in the HLRP literature by formulating a two-stage stochastic optimization model that simultaneously addresses two distinct uncertainties in a multi-period and relay-based setting. In the experimental phase, we conduct numerical experiments based on real automotive data, focusing on critical uncertainty parameters. These experiments yield valuable insights into the impact of demand and travel time uncertainty on network robustness, cost-effectiveness, delivery efficiency, and environmental impacts.

This work tackles a logistic hub capacity planning challenge within a relay-based transportation network under a multi-period and multi-uncertainty environment. The key objective is to efficiently serve logistical demands while minimizing hub costs and transportation costs under uncertain conditions. In our study, logistic hubs primarily serve as facilities offering parking spots for driver waiting and resting, along with switch zones and buffer spots for driver and trailer swaps to support relay transportation. This definition aligns with the design of PI transit centers [8]. The contracted capacity in this scenario denotes the throughput capacity of logistic hubs, involving modular factors such as the number of parking spots and trailer swap docks. Specifically, we assume that the RTC makes one-year contracts with hub providers, indicating a total planning horizon of one year. Within this time frame, we explore a case where carriers have the flexibility to modify their contracted throughput capacities across different planning seasons in response to evolving demand needs, albeit with associated capacity-changing penalties. In Section 5, we conduct experiments to delve into the advantages of this dynamic (i.e., multi-period) setting.

A primary challenge lies in accounting for different time spans for various decision types. To address this, we formulate the problem using a two-stage stochastic program that divides decisions into two stages: The first stage involves logistic hub capacity level decisions, while the second stage encompasses freight routing decisions and extra capacity decisions. As depicted in Figure 1, capacity level decisions are made at the beginning of each planning season $t_{k}$, whereas routing and extra capacity usage decisions are made for each operational period $\varphi_{i}$ after realizing demand and geographical disruptions. We assume all shipments are dispatched at the beginning of each operational period and are fully routed through the network, without occupying the transportation resources of the subsequent operational period.

Another major challenge is to determine logistic hub capacity in the face of uncertainty. When signing a capacity contract, the demand for future periods remains unknown. However, it is the demand that primarily influences capacity decisions. To model demand uncertainty, we assume that the carrier has historical data reflecting demand distribution from past service records, and model this uncertainty through probabilistic scenarios. Yet, even with sufficient data for scenario generation, incorporating too many scenarios can pose a computational burden. To balance this trade-off, we implement a scenario reduction to reduce computational effort while preserving the quality of the approximation.

We model this problem as a two-stage stochastic program to strategically determine logistic hub throughput capacities for each planning season, ensuring the fulfillment of logistic needs while minimizing both hub costs and transportation costs. The first stage decisions involve determining the throughput capacity levels of each logistic hub. In the second stage, following the realization of demand and geographical disruptions, decisions are made regarding freight shipment routing within the network and the utilization of extra throughput capacity at each logistic hub. The model notations are displayed in Table LABEL:tab:notations and its formulation are as follows:

The objective function (1) is designed to minimize the expected total costs over the scenario set during the entire planning horizon. Flow conservation constraints (2)-(4) ensure the proper routing of each freight shipment from its origin to its destination. Constraints (5) prevent capacity restriction violations for each logistic hub. Constraints (6) affirm that the initial throughput capacity at each logistic hub is empty. Constraints (7) and (8) assure the selection of exactly one hub capacity deployment strategy in each planning season, with consecutive changes in capacity levels for each hub. Lastly, constraints (9) specify the domains of the model variables.

In this study, we tackle two types of uncertainty: demand and travel time uncertainty. To address computational challenges in stochastic models with continuous distributions, we adopt a common approach of modeling uncertainty using discrete probabilistic scenarios. Specifically, we utilize a Poisson distribution to generate weekly demand from the Freight Analysis Framework (FAF) yearly demand dataset [16]. The Poisson arrival rate is determined by the historical monthly demand share, evenly distributed across four weeks within each month. This process is iterated 50 times to create 50 scenarios, all sharing the same arrival rate. For travel time uncertainty, we consider two key parameters: disruption rate and intensity. We assume that hubs operate independently and have a probability of being disrupted based on a given rate. For example, a disruption rate of 0.05 and intensity of 1.5 mean that each hub faces a 5% probability of disruption, and the travel time on the arc connecting to the interruption hub is 1.5 times the normal travel time. This simulates scenarios such as construction and maintenance within a hub, occurring independently.

The problem size, in terms of variables and constraints, significantly expands with an increasing number of scenarios. Given our focus on a large-scale relay network, the computational load becomes substantial with a large number of scenarios. To mitigate this issue, a common approach involves approximating the original set of scenarios with a smaller representative subset. In this work, we employ the fast forward selection (FFS) method, which is a widely used scenario reduction approach introduced by [7]. This FFS method selects the 10 scenarios out of the original scenario set with the shortest Kantorovich distance from the unselected set, making it the most representative of the unselected group, thus reducing computational burden while preserving solution quality.

In this section, we employ a yearly demand dataset for finished automotive vehicles sourced from the FAF database, with a specific focus on the southeast US. We conduct experiments focusing on critical uncertainty parameters, aiming to gain a comprehensive understanding of their influence on the economic and social performance of the system. The network nodes, as depicted in Figure 2(a), comprise 22 logistic hubs and 22 region centers. Figure 2(b) provides an overview of the relay network structure, with edges configured to ensure travel time along each route is limited to 5.5 hours. This design allows short-haul drivers to complete a round trip within 11 hours, in compliance with the daily driving hour limit set by US regulations. Lastly, Figure 2(c) illustrates the yearly demand flow across the southeast US, reflecting the distribution of freight volume.

To assess the impact of demand and travel time uncertainty on logistic hub capacity planning, we run the MSHCRP model across three uncertainty levels: low, intermediate, and high. Each level corresponds to a specific scenario set, generated using the method outlined in Section 4. Specifically, at the low uncertainty level, there is no disruption in the network, focusing exclusively on demand uncertainty. Moving to the intermediate uncertainty level, we introduce disruption uncertainty, where disruption scenarios are generated with a disruption rate of 0.05 and a disruption intensity of 1.5. Lastly, at the high uncertainty level, we examine a scenario with a disruption rate of 0.05 and a disruption intensity of 15, representing a significant delay penalty cost. To gain deeper insights into the benefits of dynamic modeling, we further compare the MSHCRP model with its static counterpart, where contracted capacities, once determined by the model, remain fixed throughout the entire planning horizon. All results are summarized in Table 2.

Firstly, we focus on the dynamic model (specifically the MSHCRP model) under the changes in uncertainty levels. As shown in Table 2, the total costs exhibit an increase from $44,383,187 to $47,023,527 with the escalation of uncertainty levels. Simultaneously, we can observe a decline in the average hub throughput capacity and a rise in the number of hubs. This suggests a trend within the model towards opening more hubs with a smaller design in the face of larger uncertainty, strategically mitigating hub disruption risks. In the transportation dimension, the fuel consumption increases from 108,129 tons to 112,859 tons, indicating the model is inclined to prioritize alternative longer routes to avoid disrupted arcs, thereby minimizing their impacts on operations.

Subsequently, we shift the focus to the comparison between the static model and dynamic model, as outlined in Table 2. The findings reveal that, through dynamic capacity planning, the carrier can realize savings exceeding $1,000,000 in hub costs by adjusting their logistic hub capacities across various planning seasons in response to evolving operational needs. Despite the reduced contracted capacity, the dynamic model uses approximately one-half to one-third of extra capacity compared to the static model, showcasing robustness in dynamic environments. On the other hand, the reduction in total hub capacity within the dynamic model has a negligible impact on hub network connectivity, transportation metrics, and environmental metrics, all of which remain relatively consistent with the static model. Overall, the results demonstrate that adopting the dynamic setting enables RTCs to proactively respond to dynamic circumstances, curtail avoidable expenditures, and enhance comprehensive logistical efficiency.

This study introduces a two-stage stochastic optimization model to tackle the multi-period stochastic hub capacity planning with routing problem (MSHCRP) in the context of relay transportation, which few researchers have paid attention to. Additionally, we leverage a scenario reduction algorithm based on FFS to approximate continuous distributions for demand and travel time. In the experimental section, we analyze the impact of uncertainties across four dimensions (network structure, hub contract, transportation, and environment) and compare the model with the static capacity planning model. The results demonstrate that dynamic capacity planning outperforms static capacity planning in terms of network robustness and cost-effectiveness, while maintaining strong performance in delivery efficiency and environmental impact.

Several promising avenues for future research can be identified. Firstly, investigating advanced computational methods like accelerated Benders decomposition and branch-and-price could enhance the solution approach, making it more efficient for large-scale instances. Secondly, the integration of relay-based transportation with emerging technologies, such as automatic and connected trucks, offers an exciting prospect for exploration. Thirdly, a more detailed categorization of hub capacity into distinct segments, such as loading zone capacity, parking zone capacity, and driver-switching zone capacity, could be beneficial. By implementing this approach, one can gain deeper insights, optimize resource allocation, and develop more effective strategies tailored to specific operational requirements.