{'fraction_non_alphanumeric': 0.03505723244305089, 'fraction_numerical': 0.016244191757017114, 'mean_word_length': 4.591888466413181, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimization Models for Autonomous Transfer Hub Networks

Autonomous trucks are expected to fundamentally transform the freight transportation industry. In particular, Autonomous Transfer Hub Networks (ATHN), which combine autonomous trucks on middle miles with human-driven on the first and last miles, are seen as the most likely deployment pathway of this technology. This paper presents three methods to optimize ATHN operations and compares them: a constraint-programming model, a column-generation approach, and a bespoke network flow method. Results on a real case study indicate that the network flow model is highly scalable and outperforms the other two approaches by significant margins.


Introduction
Autonomous trucks are expected to fundamentally transform the freight transportation industry. Morgan Stanley estimates the potential savings from automation at $168 billion annually for the US alone [Greene, 2013]. Additionally, autonomous transportation may improve on-road safety, and reduce emissions and traffic congestion [Short and Murray, 2016;Slowik and Sharpe, 2018]. SAE International [2018] defines different levels of driving automation, ranging from L0 to L5, corresponding to no-driving automation to full-driving automation. The current focus is on L4 technology (high automation), which aims at delivering automated trucks that can drive without any need for human intervention in specific domains, e.g., on highways. The trucking industry is actively involved in making L4 vehicles a reality. Daimler Trucks, one of the leading heavyduty truck manufacturers in North America, is working with both Torc Robotics and Waymo to develop autonomous trucks [Heavy Duty Trucking, 2021]. In 2020, truck and engine maker Navistar announced a strategic partnership with technology company TuSimple to go into production by 2024 [Transport Topics, 2020]. Truck manufacturers Volvo and Paccar have both announced partnerships with Aurora [TechCrunch, 2021]. Other companies developing self-driving vehicles include Embark, Gatik, Kodiak, and Plus [FleetOwner, 2021;Forbes, 2021;FreightWaves, 2021].
A study by Viscelli [2018] describes different scenarios for the adoption of autonomous trucks by the industry. The most likely scenario, according to some of the major players, is the transfer hub business model [Viscelli, 2018;Roland Berger, 2018;Shahandasht et al., 2019]. An Autonomous Transfer Hub Network (ATHN) makes use of autonomous truck ports, or transfer hubs, to hand off trailers between human-driven trucks and driverless autonomous trucks. Autonomous trucks then carry out the transportation between the hubs, while conventional trucks serve the first and last miles (see Figure 1). Orders are split into a first-mile leg, an autonomous leg, and a last-mile leg, each of which served by a different vehicle. A human-driven truck picks up the cargo at the customer location, and drops it off at the nearest transfer hub. A driverless autonomous truck moves the trailer to the transfer hub closest to the destination, and another human-driven truck performs the last leg.
ATHNs apply automation where it counts: Monotonous highway driving is automated, while more complex local driving and customer contact is left to humans. Global consultancy firm Roland Berger [2018] estimates operational cost savings between 22% and 40% in the transfer hub model, based on cost estimates for three example trips. A recent white paper published by Ryder System, Inc.
[2021] studies whether these savings can be attained for actual operations and realistic orders. It models ATHN operations as a scheduling problem and uses a Constraint Programming (CP) model [Dalmeijer and Van Hentenryck, 2021] to minimize empty miles and produce savings from 27% to 40% on a case study in the Southeast of the US. This paper reconsiders the optimization of ATHNs through both a solution quality and a solver performance lens. In addition to the CP model, it considers a model based on the Vehicle Routing Problem with Full Truckloads (VRPFL) [Arunapuram et al., 2003]. This model is tackled by two different approaches: a Column Generation (CG) approach and a Network Flow (NF) approach. The main technical contributions can be summarized as follows: (1) the NF model provides lower bounds as strong as those of CG on the Ryder case study; (2) solutions to the NF model can be transformed into upper bounds that are within 1% of optimality; and (3) the resulting NF-based approach is highly scalable and provides orders of magnitudes of improvement over CP and CG. From a case study standpoint, the main contribution of the paper is to provide the first lower bounds for the ATHN optimization and to demonstrate that real instances can be solved to near-optimality.
The remainder of this paper is organized as follows. Section 2 formally defines the problem of optimizing ATHN operations, and Section 3 introduces the three solution methods. Section 4 compares the methods on the case study, and Section 5 provides the conclusions.

Problem Statement
The ATHN problem aims to find a plan for a set of vehicles to fulfill a list of customer tasks at minimum cost. Let L be a set of locations, including hub locations L H ⊂ L, with driving time τ ij ≥ 0 and driving distance c ij ≥ 0 between locations i, j ∈ L (τ ij , c ij > 0 if i = j). Customers request freight to be picked up at a given location at a given time, to be transported to a dropoff location. This information is used to generate a set of tasks T , where each order generates a first-mile task (regular truck from pickup to hub), an autonomous task (transportation between the hubs), and a last-mile task (regular truck from hub to dropoff). Every task t ∈ T corresponds to a single leg, and is defined by an origin o(t) ∈ L, a destination d(t) ∈ L, and a pickup time p(t). The duration of a task equals τ o(t)d(t) + 2S, where S ≥ 0 is the fixed time for loading or unloading a trailer. The pickup time of the first-mile task is equal to the customer requested pickup time, and pickup times for subsequent tasks are set to the time that the freight is planned to arrive at o(t). The set of available trucks is partitioned into autonomous trucks K, and regular trucks K h at every hub h ∈ L H .
A feasible plan is created by assigning all tasks to the vehicles. It is assumed that an appointment flexibility of ∆ ≥ 0 minutes is permitted, which means that task t ∈ T may start anywhere in the interval [p(t) − ∆, p(t) + ∆]. Trucks are assumed to provide dedicated service, i.e., they transport one order at a time, and may be scheduled with any start-and end-point over the planning horizon. Every task must be assigned to the right kind of truck, and tasks performed by the same vehicle must not overlap in time. If the dropoff location i of the previous task does not match the pickup location j of the next task, then an empty relocation is necessary with time τ ij and cost c ij . An optimal plan performs all the tasks at minimum total driving distance, or equivalently, at minimum total relocation distance.
The problem described above can be decomposed and solved independently for the autonomous network and for the operations at each of the hubs. The main challenge is in optimizing the autonomous network since, in practice, the first-and last-mile problems are not very constrained. That is the focus of the paper.

Models and Methodology
The problem of optimizing ATHN operations is modeled as a scheduling problem and as a VRPFL. Three different solution methods are proposed: The scheduling problem is solved with CP, and the VRPFL is addressed with a CG-based heuristic and with an NF model. For simplicity the methods are presented for the autonomous part of the network only. This is without loss of generality, because the ATHN problem is decomposable.

Scheduling Modeling
The ATHN optimization can be modeled as a scheduling problem and solved using CP as in the Ryder [2021] case study. Figure 2 reproduces the CP model for this problem using OPL syntax [Van Hentenryck, 1999].
The main decision variables are the interval variables task[t] that specify the start and end times of task t when processed by the autonomous network, and the optional interval variables ttask[k,t] that are present if task t is transported by truck k. These optional variables consist of three subtasks that are captured by the interval variables load[k,t] for loading, ship[k,t] for transportation, and unload[k,t] for unloading. The other key decision variables are the sequence variables truckSeq[k] for every truck: these variables represent the sequence of tasks performed by every truck. They contain the loading, shipping, and unloading interval variables associated with the trucks, and their types. The type of a loading interval variable is the origin of the task, the type of an unloading interval variable is the destination of the task, and the type of the shipping interval variable is the specific type shipType that is used to represent the fact that there is no transition cost and transition time between the load and shipping subtasks, and the shipping and destination subtasks. The model also contains two auxiliary decision variables to capture the empty mile cost between a task and its successor, and the empty mile cost of the truck sequence.
The objective function (line 28) minimizes the total empty mile cost. The constraints in lines 31-33 specify the potential start times of the tasks, and are defined in terms of the pickup times and the flexibility parameter. The span constraints (line 35) link the task variables and their subtasks, while the constraints in lines 36-37 link the subtasks together. The alternative constraints on  line 39 specify that each task is processed by a single truck. The empty mile costs between a task and its subsequent task (if it exists) is computed by the constraints in line 41 that use the typeOfNext expression on the sequence variables. The total empty mile cost for a truck is computed in line 43. The noOverlap constraints in line 51 impose the disjunctive constraints between the tasks and the transition times. The CP model is solved with the CPLEX CP Optimizer version 12.8.

Vehicle Routing Modeling
The ATHN optimization can be modeled as a variant of the Vehicle Routing Problem with Full Truckloads [Arunapuram et al., 2003]. The VRPFL is formulated on the directed task graph G = (V, A). The set V = T ∪ {src, snk} contains a vertex for every task, together with a source and a sink node. Operations of a single truck are modeled by a route from src to snk, where arcs model the transition from one task to the next. Arcs are defined between the tasks, going out of the source, and going into the sink. If arc a ∈ A connects task t to task t , it is associated with time i.e., performing task t and relocating to the start location of task t . Arcs connecting to src take no time and have no cost, and arcs into snk do not require relocation. Every vertex t ∈ V \{src, snk} has a time window [p(t) − ∆, p(t) + ∆]. The ATHN problem amounts to finding a minimum-cost set of at most |K| feasible routes on G that cover all vertices. A route is feasible if it starts at the source, ends at the sink, and satisfies the time constraints.
Preprocessing A computational challenge in solving Vehicle Routing Problems (VRPs) is dealing with cycles in the underlying graph: either cycles are not addressed, which results in a weak lower bound, or cycles are avoided, which takes computational effort [Costa et al., 2019]. For long-distance trucking, it turns out that almost all cycles can be removed in preprocessing by only keeping arcs between task t and t if it is possible to perform the tasks in that order, i.e., p(t) − ∆ + τ tt ≤ p(t ) + ∆. The arcs imply an ordering on p(t) if all tasks take sufficiently long. In particular, for ∆ ≤ S it is guaranteed that τ tt > 2S ≥ 2∆ such that every arc follows the ordering p(t) < p(t ), and the graph is acyclic.
Column Generation VRP variants are often formulated with a set-partitioning formulation and solved with column generation (e.g., see [Costa et al., 2019]). Let R be the set of all feasible routes, and let binary variable x r be one if and only if route r ∈ R is selected. The cost of a route c r is the sum over the arc costs. Figure 3 states the set-partitioning formulation. Objective (1) minimizes the total distance and Constraints (2) ensure that all tasks are performed. Equations (4) define the variables. A CG-based restricted master heuristic [Joncour et al., 2010] is used to solve the problem. First, CG is used to solve the Linear Programming (LP) relaxation and to obtain a lower bound on the objective value. CG is a technique to solve LPs by only generating the variables min a∈A c a y a (subtour elimination constraints) (9) (time constraints) (10) y a ∈ {0, 1} ∀a ∈ A (11) (columns) as they are needed, which makes it suited to deal with the large number of x-variables [Desaulniers et al., 2005]. The problem is split into a master problem and a subproblem that are solved iteratively until convergence. The master problem is an LP that is solved with Gurobi 9.1.2, and the subproblem is typically solved with a labeling algorithm. This paper uses the labeling algorithm provided by the cspy Python package [Sanchez, 2020]. Motivated by the (almost) acyclic nature of the task graphs, this paper does not address cycles. The CG procedure results in a valid lower bound and a setR of routes that are relevant to the LP relaxation. An upper bound is generated by solving the set-partitioning formulation with integer variables for route setR. To make it easier to construct solutions, tasks are allowed to be performed multiple times, and duplicates are removed afterwards. The result is a feasible solution to the ATHN problem. The CG method is a heuristic, but may be extended to an exact method by embedding CG in a branch-and-bound framework [Barnhart et al., 1998].

Network Flow
The VRPFL can also be modeled with the vehicle-flow formulation that is presented by Figure 4 (similar to VRP1 in Toth and Vigo [2014]). Rather than using route variables, the vehicle-flow formulation uses binary flow variables y a that indicate whether arc a ∈ A is part of any route. For brevity, let δ + (t) and δ − (t) denote the set of arcs going out and coming into t ∈ V , respectively. Objective (5) minimizes the total distance. Constraints (6) and (7) require that each task has an inflow and outflow of one, which ensures the task is performed, and Constraint (8) limits the maximum number of vehicles. The subtour elimination constraints prevent cyclic flows and the time constraints ensure that the time windows are satisfied. Together the constraints ensure a disjoint set of feasible routes, just like the setpartitioning model in Figure 3. Toth and Vigo [2014] present different implementations for Constraints (9)-(10) but the details are not important to this paper.
Given the near-acyclicity of task graphs in ATHNs, Constraints (9)-(10) are relaxed. The remaining Prob-lem (5)-(8), (11) will be referred to as the NF model. Relaxing these constraints is motivated by the structure of the task graph: Only few cycles are expected after preprocessing the arcs, which makes the subtour elimination constraints almost redundant. Furthermore, the remaining arcs only connect tasks that can be performed sequentially in time, making the time constraints less important. Another important observation is that the NF model has the integrality property and can therefore be solved in polynomial time with LP [Ahuja et al., 1993]. Solving the NF model (5)-(8), (11) with linear programming immediately provides a lower bound. This follows from the fact that the NF model is a relaxation of the vehicle-flow formulation (5)-(11). It is important to remark that the lower bound still depends on the time flexibility parameter ∆, even if the time constraints are relaxed. This stems from the arc preprocessing step, which removes more arcs when the flexibility shrinks. The NF model for a flexibility δ is denoted by NF δ .
Upper bounds are generated according to the following procedure. Solve NF δ for a selection of different time flexibilities δ ≤ ∆, including δ = 0. For each δ take the vehicle routes that are produced by NF δ and try to apply them to NF ∆ . First, check if the subtour elimination constraints are satisfied. Next, if this is the case, try to satisfy the time constraints of NF ∆ by following each of the routes and setting the earliest possible starting time for every vertex. If this is also successful, the resulting solution is a feasible solution to the ATHN problem with flexibility ∆.
The above procedure is opportunistic, but surprisingly it is guaranteed to produce a feasible solution for δ = 0 if one exists, and this solution is trivially feasible for larger flexibilities. Proof. Arc preprocessing for ∆ = 0 ensures that all arcs (t, t ) satisfy p(t)+τ tt ≤ p(t ). This immediately implies that the graph is acyclic and thus that the subtour elimination constraints are automatically satisfied. Following any route, the condition above ensures that starting task t at time p(t) satisfies the time constraints. As the minimum-cost solution to NF 0 also satisfies the relaxed constraints, the solution is optimal.
The fact that the upper bound procedure is guaranteed to work is specifically due to autonomous vehicles. The main technical difference is that autonomous trucks are completely interchangable, while human-driven trucks need to be distinguished to ensure that drivers return to their specific starting point [Arunapuram et al., 2003] or that they do not exceed the maximum driving time [Gronalt et al., 2003]. Gronalt et al. [2003] consider a network flow relaxation with aggregated drivers which results in a lower bound, but the outcomes cannot be transformed into upper bounds. Human factors do not apply to autonomous trucks, which enables the simple upper bound strategy in this paper.

Case Study
The three models are applied to the realistic order data introduced in the Ryder [2021] white paper. Ryder prepared this representative dataset for its dedicated transportation business in the Southeast of the US, reducing the scope to orders that were strong candidates for automation.

Data Description
The dataset consists of long-haul trips (431 miles average) that start in the first week of October 2019, and stay completely within the following states: AL, FL, GA, MS, NC, SC, and TN. The case study focuses on scheduling the 494 most challenging orders that currently consist of a single delivery followed by an empty return trip. These orders make up 24% of the dataset, and account for 53% of the empty mileage. Two sets of hubs are considered: a small network with 17 transfer hubs in the areas where Ryder trucks most frequently access the highway system, and a large network that includes 13 additional hubs in locations with fewer highway access points. Figure 5 visualizes the networks. The exact hub locations are masked, but the figures are accurate within a 50 mile range. Orders that are better served with a conventional truck are filtered out, and the remaining orders are split into separate tasks. See the Ryder [2021] white paper for additional details.
Base Cases Two base cases are considered in the case study: The N-17 base case on the small network and the N-30 base case on the large network. Both cases assume a time flexibility of ∆ = 60 minutes, loading or unloading of S = 30 minutes, |K| = 50 autonomous trucks are available, and operating autonomous trucks will be 25% cheaper per mile than conventional trucks. After filtering, the N-17 and N-30 base cases respectively serve 437 and 468 orders on the ATHN. This paper focuses on optimizing the autonomous part of the system. When comparing costs to the current system, it is assumed that the first/last-mile tasks can be served with at most 25% empty miles. The associated models are significant in size: The CP model (Figure 2) has about 100,000 variables and 100,000 constraints. The NF model (5)-(8), (11) is similar in size but only contains continuous variables. The set-partitioning formulation (Figure 3) has around 500 constraints and generates about 3,000 variables as part of the CG procedure.  The bounds are not guaranteed to always be the same: If autonomous trucks are 40% cheaper than regular trucks and time flexibility is increased to ∆ = 120 minutes, then CG generates a lower bound that is 0.07% better than the bound produced by NF. Hence the NF model presents an excellent trade-off in terms of quality and time. The Ryder [2021] white paper only considers the CP method, which inherently does not produce bounds. Now that lower bounds are available they will be used to assess solution quality and complement earlier work. Table 2 compares the three methods on their ability to produce high-quality solutions. For consistency with earlier work, each method is given one additional hour after computing the lower bound to generate a feasible solution. The CG method makes use of the route set R that was obtained while calculating the lower bound. The NF method uses the procedure described in Section 3.2 to opportunistically generate solutions from NF δ for δ ∈ {0, 30, 60}. Additionally, the table includes optimality gaps that compare the upper bounds to the lower bounds presented earlier.
The NF method again outperforms the other methods. The solutions found by the CP method already correspond to significant savings of more than 27% for ATHN compared to the current system. However, the optimality gaps of over 11% show that more savings may be possible. Surprisingly, the CG method fails to find a feasible solution within one hour. Intermediate solutions are found with 55 and 56 vehicles for N-17 and N-30 respectively, but these plans are already more expensive than those found with CP. It seems that the route set R is not necessarily a good starting point to find a feasible solution. The NF method is the clear winner: Not only are the solutions significantly better than those ob-  tained from the CP method, they are provably within only 1% from optimality. Figure 6 visualizes the NF solution for the N-17 base case: The tasks are spread out over the week, which explains why the time constraints are not very restrictive and relaxing them still leads to good results.

Impact of Time Flexibility
Deviating from an agreed time window flexibility must be negotiated with the customer, but if there are significant benefits in terms of efficiency, this may be worth the effort. To determine the impact of appointment flexibility, the two models that produced feasible solutions (CP and NF) are compared on the N-17 base case for different values of ∆ ranging from 30 to 120 minutes. The time limit is set to four hours per setting to account for the fact that instances with more flexibility are more difficult to solve. Figure 7 summarizes the upper bounds (UB-CP, UB-NF) and the lower bounds (LB-NF) that are generated for different flexibility parameters. If UB-CP deteriorates when ∆ increases, the previous better solution is reported. The upper bounds for the NF method are calculated with the opportunistic procedure for δ ∈ {0, 30, 60, 90, 120}. Similar to the base case, Figure 7 shows that the NF method maintains strong performance when time flexibility is increased. The largest optimality gap of 1.2% is obtained for ∆ = 90. The NF method was unable to improve from ∆ = 60 to ∆ = 90, but is able to benefit from additional flexibility provided by ∆ = 120. The CP method is able to benefit significantly from the extension of ∆ = 60 to ∆ = 90, but does not improve after that. A possible explanation is that additional flexibility increases the search space, which makes it more difficult for the CP method to find a good solution.
The performance of the NF method is consistent when the experiment is repeated for different values of cost reduction per mile compared to conventional trucks. Additional instances are generated for 30%, 35%, and 40% cost reduction and for different time flexibilities. On all instances the optimality gap found by the NF method is less than 1.6%. These results further support that the NF method is able to find high-quality solutions.

Impact on ATHN Cost Savings
The Ryder [2021] white paper reported cost saving in the range of 27%-40% for the challenging orders when ATHN is compared to current operations. The lower value stems from applying the CP model to the N-17 base case. The solution found by the NF model improves this number to 32.2%. The higher value follows from the scenario that considers the N-30 base case with autonomous trucks that are 40% cheaper per mile. Applying the NF model to this instance results in a solution with 44.0% cost savings compared to current operations. It follows that better optimization methods improve the range of potential cost savings from 27%-40% to 32%-44%, which strengthens the business case for ATHNs and autonomous trucking.

Conclusion
Autonomous trucks are expected to fundamentally transform the freight transportation industry. Recent studies have shown that Autonomous Transfer Hub Networks (ATHN), which combine autonomous trucks on middle miles with human-driven on the first and last miles, can produce significant savings. This paper presented three different methods to optimize ATHN operations: a Constraint-Programming (CP) method, a Column-Generation (CG) method, and a Network Flow (NF) method. The methods were compared on a realistic case study with data provided by Ryder System, Inc. The paper complemented earlier work by calculating lower bounds on performance. This showed that the ATHN CP solution, which already corresponds to large savings compared to the current system, could potentially be improved. It was demonstrated on the case study that the NF model effectively exploits the problem structure and outperforms the other methods: It produces both lower bounds that are comparable to the CG method and upper bounds that improve upon the CP method in a matter of seconds. Further analysis showed that NF is able to benefit from additional pickup flexible, and consistently outperforms the other methods. The NF method improved the range of potential savings of ATHN from 27%-40% to 32%-44%, further strengthening the business case for autonomous trucking.