Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks

Chungjae Lee, Wirattawut Boonbandansook, Vahid Eghbal Akhlaghi, Kevin Dalmeijer, Pascal Van Hentenryck

Abstract

The Autonomous Transfer Hub Network (ATHN) is one of the most promising ways to adapt self-driving trucks for the freight industry. These networks use autonomous trucks for the middle mile, while human drivers perform the first and last miles. This paper extends previous work on optimizing ATHN operations by including transfer hub capacities, which are crucial for labor planning and policy design. It presents a Constraint Programming (CP) model that shifts an initial schedule produced by a Mixed Integer Program to minimize the hub capacities. The scalability of the CP model is demonstrated on a case study at the scale of the United States, based on data provided by Ryder System, Inc. The CP model efficiently finds optimal solutions and lowers the necessary total hub capacity by 42%, saving $15.2M in annual labor costs. The results also show that the reduced capacity is close to a theoretical (optimistic) lower bound.

Introduction

The freight industry is increasingly looking toward Autonomous Transfer Hub Networks (ATHNs) to integrate self-driving technology. In this operational model, autonomous trucks manage the "middle mile"—the long, repetitive stretches of highway between hubs. Human drivers then take over for the "first and last miles," navigating complex urban environments and managing customer interactions.

While previous research has primarily focused on minimizing "empty miles" or total travel costs, it has largely overlooked the critical factor of hub capacity. A schedule that causes a surge of trucks to arrive at a single hub simultaneously necessitates massive infrastructure and a large, expensive workforce to handle peak demand. This paper addresses the challenge of smoothing these arrivals to minimize peak capacity requirements while maintaining cost-optimal routing.

Methodology

The researchers propose a decoupled, two-stage optimization framework:

  1. MIP for Routing: A flow-based Mixed Integer Programming (MIP) model determines the most cost-effective routes and an initial schedule, focusing on the spatial movement of loads.
  2. CP for Scheduling: These routes are then processed by a Constraint Programming (CP) model. CP is ideal for scheduling due to its ability to handle "cumulative constraints"—rules that track resource usage over time. The model shifts task start times within allowed flexibility windows (e.g., a 1-hour pickup window) to minimize the maximum number of trucks loading or unloading at any hub at any given time.

The study utilized a nationwide case study based on data from Ryder System, Inc., involving 6,842 loads over four weeks in October 2019 across 100 designated U.S. transfer hubs.

Key Results and Scalability

The CP model demonstrated significant performance gains and robustness. It reduced the necessary total hub capacity by 42% compared to the initial MIP-generated schedule. This reduction translates to an estimated $15.2M in annual labor savings based on the personnel required to staff these facilities.

Total hub capacity reduction and improvement percentage across different fleet sizes.

As shown in the results, the CP model is remarkably effective at "absorbing" increased workloads. While "Before CP" capacity requirements grow sharply with the number of trucks, the optimized "After CP" capacity remains relatively stable, staying close to the theoretical lower bound.

Network-Wide Impact

One of the most significant insights is that these substantial savings do not require radical rescheduling. In a 100-truck scenario, only 13% of loadings required adjustment, with most shifts being 30 minutes or less. This "power of small shifts" allows for significant operational efficiency without disrupting the core logistics plan.

Comparison of hub utilization across the U.S. network before and after CP optimization.

The visualization of the U.S. network highlights how the CP optimization effectively redistributes the load, reducing the peak pressure on major logistics hubs (represented by the size of the blue dots in the side-by-side comparison).

Conclusion and Future Directions

This research proves that a sequential MIP-then-CP approach is both highly effective and computationally efficient, solving national-scale problems in under 30 seconds. This makes it a viable tool for daily operational planning in the burgeoning autonomous trucking industry.

Future work may explore joint optimization—considering hub capacity simultaneously with routing—to potentially unlock even greater savings. Additionally, incorporating stochastic elements to account for real-world delays (e.g., weather or traffic) would enhance the robustness of the generated schedules.

Summary updated

Abstract

The Autonomous Transfer Hub Network (ATHN) is one of the most promising ways to adapt self-driving trucks for the freight industry. These networks use autonomous trucks for the middle mile, while human drivers perform the first and last miles. This paper extends previous work on optimizing ATHN operations by including transfer hub capacities, which are crucial for labor planning and policy design. It presents a Constraint Programming (CP) model that shifts an initial schedule produced by a Mixed Integer Program to minimize the hub capacities. The scalability of the CP model is demonstrated on a case study at the scale of the United States, based on data provided by Ryder System, Inc. The CP model efficiently finds optimal solutions and lowers the necessary total hub capacity by 42%, saving $15.2M in annual labor costs. The results also show that the reduced capacity is close to a theoretical (optimistic) lower bound.
BibTeX
@inproceedings{lee2023constraint,
  author = {Chungjae Lee and Wirattawut Boonbandansook and Vahid Eghbal Akhlaghi and Kevin Dalmeijer and Pascal Van Hentenryck},
  title = {{Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks}},
  booktitle = {CP},
  year = {2023},
  doi = {10.4230/lipics.cp.2023.46},
}
Figure