Middle Mile Consolidation Network Design with Robust Lead
Time Constraints
Lacy Greening∗ , Mathieu Dahan, and Alan Erera
Georgia Institute of Technology, Atlanta, GA, USA∗ Corresponding author, lacy.greening@gatech.edu

April 4, 2022
Keywords: e-commerce logistics; service network design; middle mile;

1

INTRODUCTION

New e-commerce retailing models such as ship-to-home and ship-to-store require that retailers
implement new approaches for distributing directly to consumers on demand. Some high-demand
stock-keeping units (SKUs) may be held at fulfillment centers (FCs), while others may be shipped
directly from vendors. Middle-mile consolidation network design problems arise when large
retailers jointly coordinate shipments from vendors and FCs into last-mile distribution (LMD)
facilities, seeking consolidated truckloads when possible to reduce high less-than-truckload (LTL)and parcel freight charges. Competition among e-commerce retailers to serve consumers rapidly
leads to tight lead time requirements for shipments in the middle mile. Traditional flat-network
service network design (SND) models for trucking (Powell & Sheffi, 1983) can incorporate transittime constraints, but do not account for delays created by low shipment frequencies. Timeexpanded network models (Jarrah et al., 2009, Erera et al., 2013) can address this shortcoming,but often result in very large model instances that are intractable for the problems faced bylarger shippers. In this work, we adopt an idea from public transit, i.e., model waiting delays
as the inverse of outbound departure frequencies (Spiess & Florian, 1989, Cancela et al., 2015),
to fully capture constraints on shipment lead times in flat network models that can be solved
effectively and demonstrate the impact of more conservative lead time constraints.

2OPTIMIZATION MODELING

We consider a large shipper that needs to move shipments to fill orders from known origins toknown destinations within specified lead times. Let (N , L) define the shipper’s service network,where the node set N denotes the set of facilities in the network; these include vendor locations,FCs, LMD facilities, and potentially other sorting and transfer locations. The directed arc set L
consists of the set of potential freight transportation lanes connecting pairs of locations, where alane is defined as the physical arc with a transportation mode (e.g., LTL or truckload) assigned.
Each load of size q dispatched on lane l incurs a fixed-plus-linear cost given by the expression
Al + Bl q. Furthermore, each lane specifies an associated upper bound Qmax
and lower boundlQminon
thesizeofeachdispatchedload.
Shipment
demandismodeledusing
a set K of comlmodities. Let Rk represent the set of potential consolidation routes for commodity k, where
each route is an ordering of adjacent freight transportation lanes connecting its origin ok to its
destination dk , and potentially uses one or more transfer facilities. A unique freight route r ∈ Rk
must be selected to specify a consolidation plan for commodity k and has a total handling costof Cr . We denote R := ∪k∈K Rk as the set of potential freight routes.
We use a flat network representation of capacity allocation to lanes and an associated representation of shipment consolidation into load dispatches. Thus, freight transportation capacity
decisions are modeled as frequencies of load dispatches on lanes per time. The demand inputs
TRISTAN XI Symposium

Original abstract submittal

Greening, Dahan, and Erera

2are also expressed as constant rates per time; let Vk be the demand rate for commodity k, representing the aggregated average shipment size (volume) flowing from ok to dk per time. The
goal is to select a joint set of freight routes for all commodities along with load dispatch frequencies on selected lanes such that all commodity volume is transported feasibly and total cost isminimized. Thus, let binary variables xr indicate whether route r ∈ R is selected, continuous
variables vl indicate the total shipment volume assigned to each lane l, and integer variables flcount the number of loads dispatched per time on lane l. We can formulate the middle mileconsolidation (MMC) model as follows:minx,f,v

s.t.

XX



(1a)

∀ k ∈ K,(1b)

∀ l ∈ L,(1c)vl ≤ Qmax
fl ,l∀ l ∈ L,(1d)vl ≥ Qmin
fl ,l∀ l ∈ L.

(1e)

Cr x r +r∈RX

Al fl + Bl vll∈Lxr = 1,r∈Rkvl =XXVr xr ,k∈K {r∈Rk |r∋l}

The objective is to determine a transportation consolidation plan that minimizes the total transportation and handling costs. Constraints (1b) ensure that one route is selected for each commodity. Constraints (1c) determine the total volume flowing on each lane l aggregated acrosscommodities. Constraints (1d) and (1e) set the required load dispatch frequencies for each laneusing upper and lower bounds on load size.

2.1

Using Waiting Delays to Constrain Lead Times

The frequency of load dispatches on a lane impacts lead times since lower frequencies lead tolonger waiting delays at dispatch locations. Given the load dispatch frequency fl on lane l, weassume trucks are scheduled to deterministically dispatch every f1l time units and are uncoordinated across facilities. If the shipments for each commodity k are then assumed to arrive
ready for shipment at ok according to a uniform distribution, it is reasonable to assume that allarriving shipments to be dispatched from a facility will have similarly distributed arrival times.
Thus, the waiting delay experienced by any individual shipment on each lane l can be modeled
as a uniform random variable Wl ∼ Uniform(0, f1l ). Given this model, the expected waiting time
experienced by all shipments before being dispatched on lane l is E[Wl ] = 12 f1l . We define theexpected lead time of a route as the sum of lane transit times and expected waiting delays forload dispatches. The allowable waiting delay Ŵr of route r is its lead time requirement less thesum of its lane transit times. A load plan satisfies the lead time requirement (in expectation) ofrouteP 1r 1if and only if the total expected waiting delay along that route does not exceed Ŵr (i.e.,l∈r 2 fl ≤ Ŵr ).
To formulate this middle mile consolidation with waiting times (MMCW) model, we use a linearization approach similar to that proposed in Cancela et al. (2015) for transit network design
problems. Define for each lane l a set of binary variables zlf over a finite set Fl of possible load
dispatch frequency values. We then substitute the frequency variables as follows:

fl =X

f zlf ,∀ l ∈ L.

(2)

f ∈Fl

TRISTAN XI Symposium

Original abstract submittalGreening, Dahan, and Erera

3We now formulate the MMCW model as follows:XXXf zlf + Bl vlAlmin
Cr x r +x,z,vs.t.

r∈R(3a)f ∈Fll∈L(1b) − (1e) using (2) where applicable,
Xzlf ≤ 1,∀ l ∈ L,(3b)f ∈Fl

1XX 1|r|zlf ≤ Ŵr xr + (1 − xr ),2f2∀ r ∈ R.

(3c)l∈r f ∈FlConstraints (3b) select at most one frequency for each lane. Constraints (3c) ensure the total
expected waiting time along each selected route is no more than the total allowable waiting delay.
Note that the main drawback of the MMCW model is the potentially large number of binary
variables zlf needed when lanes have many possible frequency values. To avoid this, we now
develop a simpler alternative for finding a reasonable solution to the MMCW problem denotedas the middle mile consolidation with allocated waiting delay (MMCW-A) model. This approach
restricts the space of feasible solutions by allocating fixed fractions of a route’s total allowablewaiting delay a priori to each of its lanes. Under this assumption, the following linear constraints
can be directly added to (1) to yield the MMCW-A model:
fl ≥

1 |r|
xr ,2 Ŵr

∀ r ∈ R, ∀ l ∈ r.

(4)

The right-hand side of constraints (4) represents the minimum number of load dispatches needed
to ensure the expected waiting delay for each load dispatched does not exceed the evenlydistributed allowable waiting delay. The simpler MMCW-A model can be used to find a strong
starting solution for the MMCW model as the commodity and/or route sets grow much larger.

2.2

Protecting Against Variability in Waiting Delays

Constructing the lead time constraints (3c) or (4) using the expected waiting delays E[Wl ] = 12 f1l
does not account for the potential variance in the random load dispatch waiting delays and can
only guarantee that the lead time requirements are met with probability 0.5. However, for everyroute r and desired commodity on-time arrival probability
pr , the shipper may want to select loadP
dispatch frequencies fl for each lane l ∈ r so that P( l∈r Wl ≤ Ŵr ) ≥ pr , that is, the probabilityof the total waiting delay on route r not exceeding Ŵr is at least pr . Since the waiting delay
experienced by arriving shipments for lane l is assumed to be given by Wl ∼ Uniform(0, f1l ), theprobability that the commodity traveling along r arrives on time to its destination is given by
the following expression (Kang et al., 2010):!
X
X 1 |r|X
1|J|PWl ≤ Ŵr =(−1)
max
0,Ŵ
−.
(5)
Qr
fl|r|! l∈r f1l∈rl

J⊆rl∈JExpression (5) is nonlinear in the load dispatch frequencies and again cannot be included directlyin the optimization model (1). To circumvent this limitation, we define for each route r ∈ R
a conservatism hyperparameter cr ∈ [0, 1] that the shipper can vary to adjust the probabilistic
guarantee of meeting the commodity lead time requirement. Then, for every route r ∈ R, werespectively replace constraints (3c) and (4) byXX 1crzlf ≤ Ŵr xr + cr |r|(1 − xr ),(6)
fl∈r f ∈Fland fl ≥ cr

TRISTAN XI Symposium|r|Ŵrxr ,∀ l ∈ r.

(7)

Original abstract submittalGreening, Dahan, and Erera

4Thus, we determine the lowest hyperparameter for which the lead time constraints (6) or (7)remove any load plan that does not meet the desired probability pr . Interestingly, we observethat deriving the conservatism level cr for the MMCW-A approach simply requires the on-time
probability pr and number of legs |r|, and is independent of the allowed waiting delay Ŵr .

3RESULTS

The instances used are synthetic but have been derived from historical weekly demand data
provided by a large U.S.-based e-commerce retailer. The instances have 160 vendors, 8 FCs, and90 LMD facilities with over 10,000 commodities; each commodity can have up to 5 route options.
Given the computational difficulty of solving a problem of this size, we run an IP-based local
search (IPBLS) for 12 hours to find good solutions. To measure service level,
wePcalculate thePPW ≤Ŵr )Vk(
volume-weighted expected on-time probability (vOTP) of a solution as k∈K P l∈r Vkl,k∈K
where the on-time probability of an individual commodity using route r is calculated using (5),the assigned load dispatch frequencies fl ∀ l ∈ r, and the allowable waiting delay Ŵr . Table 1
shows the results of using four different values of on-time probability guarantees.
Minpr0
0.5
0.6
0.7
0.8

Model
MMC
MMCW
MMCW-A
MMCW
MMCW-A
MMCW
MMCW-A
MMCW
MMCW-A

12-hr
IPBLS
Obj
$2,956,000$3,730,000$4,159,000$4,125,000$4,429,000$4,460,000$4,632,000$4,688,000$4,930,000

vOTP
0.47
0.80
0.95
0.92
0.98
0.95
0.99
0.98
0.99

Vol-Wtd
RouteLength
1.8
2.02.2
2.1
2.3
2.1
2.4
2.2
2.4

Avg Load
Disp Freq(#/week)
LTL TL
1.0
1.7
1.9
3.2
2.5
5.5
2.4
4.3
2.6
6.4
2.6
4.9
3.0
7.4
2.8
5.9
3.1
8.5

Loads/Week
LTL
60
790
1,030
980
1,250
1,490
1,270
1,560
1,330

TL
1,300
2,110
2,390
2,300
2,540
2,430
2,730
2,630
2,970

Vol-WtdUtilization
TL
92%
85%
86%
78%
82%
75%
80%
73%
75%

Table 1 – Comparing different service levels for MMCW and MMCW-A solved using 12-hr IPBLS.
We first observe that a design solution resulting from minimizing cost only would result in avOTP service level of 47%. We then see a significant improvement in vOTP when adding leadtime constraints, even for the case where all commodities are only guaranteed to be on timeat least 50% of the time. We also note that the number of loads dispatched increases as princreases, which results in less utilization of the trucks sent. A retailer can use this type ofanalysis to decide which design solution best balances cost and customer service. Finally, using
the restricted MMCW-A models to find network designs is a reasonable approach in some cases.

References
Cancela, H., Mauttone, A., & Urquhart, M.E. 2015. Mathematical programming formulations for transit
network design. Transportation research. Part B: methodological, 77, 17–37.
Erera, A.L., Hewitt, M., Savelsbergh, M.W.P., & Zhang, Y. 2013. Improved Load Plan Design ThroughInteger Programming Based Local Search. Transportation science, 47(3), 412–427.
Jarrah, A., Johnson, E.L., & Neubert, L.C. 2009. Large-Scale, Less-than-Truckload Service Network
Design. Operations research, 57(3), 609–625.
Kang, J., Kim, S., Kim, Y., & Jang, Y.S. 2010. Generalized convolution of uniform distributions. Journalof Applied Mathematics & Informatics, 28(01).
Powell, W.B., & Sheffi, Y. 1983. The load planning problem of motor carriers: Problem description anda proposed solution approach. Transportation research. Part A: general, 17(6), 471–480.
Spiess, H., & Florian, M. 1989. Optimal strategies: A new assignment model for transit networks.
Transportation research. Part B: methodological, 23(2), 83–102.

TRISTAN XI Symposium

Original abstract submittal