Vehicle routing optimization with relay:an arc-based column generation approach
Alexandre Jacquillata,b , Alexandria Schmidb,∗ , Kai Wangca Sloan School of Management, MIT, Cambridge, MA, USA
b Operations Research Center, MIT, Cambridge, MA, USA
c Heinz College, Carnegie Mellon University, Pittsburgh, PA, USA∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 10, 2022
Keywords: relay logistics, physical internet, time-space network, column generation

1INTRODUCTION

The logistics sector is a key enabler to growth and development. Decades of improvements inthe design and operations of logistics systems have played an important role to support today’s
unprecedented growth of e-commerce as well as increasing delivery speeds. Yet, logistics providers
face critical challenges to meet customer demand in increasingly interconnected networks, withlimited capacity. In particular, spatial-temporal patterns routinely result in unnecessary vehicle
miles traveled and empty backhauls. These inefficiencies have an important socio-economic toll,
as exemplified by the low profit margins and high driver turnover faced by trucking operators.
Moreover, the logistics sector contributes to nearly 20% of greenhouse gas emissions, creating
intensive pressure to mitigate its environmental footprint (International Energy Agency, 2020).
On the bright side, freight transportation is witnessing several concomitant transformations.
One area—at the core of this paper—lies in connected vehicles. By leveraging sensors andactuators, telematics provide near-real-time visibility into vehicle locations. Thanks to these datasources, digital platforms can provide decision-support systems to enhance freight operations.
These advances have fueled new practices throughout supply chains based on collaboration,consolidation and cooperation which, collectively, can considerably improve the efficiency andsustainability of logistics operations (Savelsbergh & Van Woensel, 2016, Cleophas et al., 2019).
One of these innovations is known as relay-based logistics. As opposed to point-to-point trucking
operations, relay operations decompose each origin-destination trip into short segments traveledby separate drivers, using a network of “pit-stops”. That is, a driver can move one order throughone segment along one direction, drop the vehicle to another driver, and immediately travel along
the opposite direction to serve another order. These operations rely heavily on connected vehicles
and digitization to coordinate operations across the network of pit-stops. In the short term, relay
logistics can improve drivers’ lifestyles by allowing them to return home on a frequent basis. In
the long term, they can play a catalyst role toward the “Physical Internet”, by enabling modular
logistics operations based on standardized and connected components (Montreuil, 2011).
To be successful, however, relay logistics require dedicated capabilities to coordinate operations
TRISTAN XI Symposium

Vehicle routing optimization with relay

A. Jacquillat, A. Schmid, K. Wang

2across pit-stop networks. At the downstream level, relay operations raise the immediate questionof which driver should cover which segment to move trucks and shipments across the network. But
relay operations also require service providers to comprehensively re-optimize routing operations
at the upstream level, in order to create relay opportunities and take full advantage of thecoordination capabilities. In response, the goal of this paper is to develop new models andalgorithms to optimize routing operations in relay-based logistics networks.
Specifically, we develop a new approach to optimize truck routes and driver assignments in order
to best serve incoming orders in relay-based logistics. From a technical standpoint, we formulate
a model that brings together several layers of time-space networks, with coupling constraints
coordinating all entities. This approach, however, comes at the price of a large number of decisionvariables and constraints. We therefore develop a novel solution algorithm based on arc-based
column generation, which starts from small time-space networks and expands them iteratively,until convergence. From a practical standpoint, we partner with Rivigo, a pioneer of relay-based
operations in India. Using real-world data, we demonstrate the benefits of our modeling andalgorithmic approach to maximize order throughput and minimize vehicle miles traveled in theIndian network. We also leverage the proposed modeling and algorithmic approach to evaluate
the potential of relay-based operations in logistics. We detail the paper’s contributions below.

2MODEL FORMULATION

We develop an integer programming model that optimizes vehicle routes, driver assignments andorder deliveries in relay-based logistics operations. It is formulated as a multi-commodity flow
problem across four layers of time-space networks: (i) one for each customer order (ii) one foreach driver (iii) one for empty trucks, and (iv) one for driver rebalancing. Accordingly, the model
optimizes four sets of decisions: the flow of each order from an origin to a destination, the flow ofeach driver across the pit-stop network (while coming back home periodically), the flow of empty
trucks, and the flow of rebalancing trips for drivers. As compared to traditional vehicle routing
models (based on order-vehicle assignment), this problem is complicated by the coordination
between driver operations and vehicle operations (based on order-truck-driver assignment).
The model balances two objectives, by minimizing miles traveled (a proxy for operating costs) andorder delay (a proxy for level of service). Order-level constraints ensure that each order travels
from origin to destination, maintain flow balance, and compute delays. Truck-level constraints
maintain flow balance and apply initial truck availability. Driver-level constraints maintain flowbalance and apply staffing rules. Finally, linking constraints ensure consistency between order
movements, truck movements, and driver movements—namely, ensuring driver availability tocover truck-order assignments and empty trucks’ trips.
By leveraging a multi-commodity flow structure, this model admits a tight linear programming
relaxation. Its main complexity lies in its dimensionality. For drivers, staffing rules—in particular, each driver returning home regularly—lead to sparse time-space networks. For orders,
however, time-space networks cannot be easily reduced because optimal solutions may involve
detours to enable consolidation across the whole pit-stop network. One approach would be toproceed via heuristic arc reduction (e.g., a Boston–Miami order may not travel between Los
Angeles and Seattle), but such heuristics can lead to sub-optimality or even infeasibility.

3ARC-BASED COLUMN GENERATION

Instead, we propose a novel approach termed arc-based column generation. This approach starts
with very sparse order-level time-space networks, and expands them by generating arcs iteratively
TRISTAN XI Symposium

Vehicle routing optimization with relay

A. Jacquillat, A. Schmid, K. Wang

3

until convergence. Note that the approach does not rely on a set partitioning formulation togenerate paths, but instead uses the original formulation to generate arcs to build a small timespace network for each order. Specifically, the algorithm iterates between two modules:– Sparse time-space problem: This problem generates a globally feasible solution by solving avariant of the model that restricts the set of arcs for each order. In the full problem, binary
variables xia track whether order i travels through arc a ∈ Ai in its time-space network.
The sparse time-space problem restricts these variables to a subset of arcs Abi ⊆ Ai .
– Subproblem: Using dual information from the sparse time-space problem, we compute thereduced cost associated with each order-arc pair (i, a). The subproblem seeks, for eachorder, a set of arcs that create a new path from origin to destination with minimal reduced
cost. This is formulated as a shortest path problem on the full time-space network. We
then add all corresponding arcs to the sparse time-space problem and proceed to Step 1.
As compared to “traditional” column generation methods, the subproblem does not seek a variable(or a column) with negative reduced cost, but rather a set of variables that create a path withnegative total reduced cost. The algorithm terminates when there exists no such path for any
order—although there may exist arc-based variables with negative reduced cost. We prove that
this termination criterion guarantees optimality of the incumbent sparse time-space problem
solution. As a result, the algorithm converges finitely to the optimal solution of the model’slinear programming relaxation. We can embed it into a branch-and-price scheme to guarantee
convergence to the solution of the full integer programming model.
Ultimately, this arc-based column generation algorithm provides a generalizable solution approach for time-space network optimization. As compared to heuristic arc reduction techniques,
it yields an exact procedure to construct a reduced time-space network, without leading to potentially sub-optimal solutions or infeasible instances.

4RESULTS

We implement our model and algorithm using real-world data from Rivigo’s operations in 2019.
We embed our arc-based column generation algorithm into a rolling implementation to evaluate
its impact on relay-based logistics operations over a week of operations.
From a computational standpoint, we show that the proposed arc-based column generation algorithm converges effectively, in manageable computational times even for large-scale instances.
Table 1 reports results of our algorithm against three benchmarks: direct implementation of theinteger programming formulation, arc reduction heuristics, and “traditional” path-based columngeneration (based on an equivalent set partitioning formulation). The arc-based column generation algorithm yields near-optimal solutions by generating fewer arcs and terminating in shortercomputational times than all benchmarks.
From a practical standpoint, Table 2 compares the solution to (i) a greedy, myopic heuristic, (ii)a sequential benchmark that first optimizes truck-order assignments (without considering relay)
and then optimizes route-driver assignments (embedding relay dynamics ex post), and (iii) thehistorical routes implemented by Rivigo. Our solution reduces the costs by 10% as comparedto Rivigo’s historical operations, showing the benefits of optimization in complex relay-based
logistics networks. Second, the orders-then-drivers heuristic increases costs by 20%. This underscores that relay-based operations do not simply require adjustments at the “downstream” level;
instead, new relay capabilities require to re-optimize operations in order to create coordination
opportunities between trucks and drivers. Furthermore, our solution achieves a Pareto improvement against all benchmarks—fewer miles traveled and lower order delay—therefore yielding
win-win-win outcomes: better customer service, lower costs, and lower environmental footprint.
TRISTAN XI Symposium

Vehicle routing optimization with relay

A. Jacquillat, A. Schmid, K. Wang

4

Table 1 – Results of the arc-based column generation, against all computational benchmarks.
MethodCPU Time (s)Opt GapArcs

Direct IP (full network)
Arc reduction (aggressive)
Arc reduction (moderate)
Arc reduction (conservative)
Path-based column generation
Arc-based column generation

23,4705,665
6,706
18,697
5,982
2,975

0.00%
3.51%
0.81%
0.01%
0.62%
0.11%

169,266
45,374
93,583
119,301
8,165

Table 2 – Solution from modeling and computational approach, against all practical benchmarks.
MethodProposed method
Greedy heuristic
Orders-then-drivers
Actual routes

Cost

Total Miles

Empty Miles

Avg Delay

Orders Delivered

1,136,973
1,371,241(+20.6%)
1,386,701(+22.0%)1,255,678(+10.4%)

927,590
1,005,927(+8.4%)
1,043,762(+12.5%)
971,771(+4.8%)

80,503
155,561(+93.2%)
143,374(+78.1%)
98,200(+22.0%)0.50
0.94(+44.0%)0.89(+39.0%)0.75(+25.0%)544
462(-15.1%)449(-17.5%)469(-13.8%)

Finally, we compare relay operations to traditional point-to-point trucking in Table 3. For pointto-point, we introduce a parameter µ to incentivize drivers to come home: for small values of µ,
drivers may be on the road indefinitely, whereas, for large values of µ, drivers will systematically
return home even if this implies empty backhauling. First, note that the continuous movement ofgoods enabled by relay operations improves delay significantly when compared to point-to-point
operations. Next, by design, relay operations allow drivers to return home much more frequently
than point-to-point. Moreover, enabling drivers to come back home periodically in point-topoint operations (by increasing µ) has a significant cost in terms of empty miles. Ultimately,
our modeling and computational approach again results in a Pareto improvement as comparedto the no-relay benchmark: faster deliveries, better lifestyle for drivers, and fewer empty miles.
Table 3 – Comparison of relay and non-relay operations on a medium-sized instance.
OperationsµTotal Miles

Empty Miles

Avg Delay

Orders Delivered

Nights Away

Point-to-point
Point-to-point
Point-to-point
Point-to-point
Point-to-point
Relay

0.01
0.1
1
10
100
-

491,932
497,761545,860
629,380
648,140
516,715

58,77964,609112,707
196,164
214,469
91,143

1.77
1.77
1.77
1.79
1.79
0.55

536
536
536
536
533
613

3,248
3,230
2,018
1,691
1,915
963

References
Cleophas, Catherine, Cottrill, Caitlin, Ehmke, Jan Fabian, & Tierney, Kevin. 2019. Collaborative urban
transportation: Recent advances in theory and practice. European Journal of Operational Research,273(3), 801–816.
International Energy Agency. 2020. Energy Technology Perspectives 2020. Tech. rept.
Montreuil, Benoit. 2011. Toward a Physical Internet: meeting the global logistics sustainability grandchallenge. Logistics Research, 3(2), 71–87.
Savelsbergh, Martin, & Van Woensel, Tom. 2016. 50th anniversary invited article—city logistics: Challenges and opportunities. Transportation Science, 50(2), 579–590.

TRISTAN XI Symposium

Vehicle routing optimization with relay