The Service Network Scheduling Problem
M. Hewitta,∗ , F. Lehuédéba Loyola University Chicago,Chicago,United States of America,mhewitt3@luc.edu
b IMT Atlantique, Nantes, France,fabien.lehuede@imt-atlantique.fr

We consider the optimization problem of determining schedules for shipments on known paths
within a terminal network in order to minimize vehicle transportation costs. We refer to thisproblem as the Service Network Scheduling Problem and present two mixed integer programming
formulations of that problem. The first is based on the classical idea of a time-expanded
network. The second formulation is new and is based on sets of shipment consolidations. We
show both analytically and computationally that the consolidation-based formulation can be thesuperior of the two, but that its enumerative nature renders it ineffective for instances withlarge numbers of shipments. Thus, we present a column generation-based algorithm for solving
the consolidation-based formulation that relies on solving relaxations that are integer programs.
We demonstrate the superior performance of this algorithm with a computational study.

December 18, 2021
Keywords: Service Network Design Problem, Scheduling, Column Generation, Integer Programming

1

INTRODUCTION

Consolidation carriers are transportation companies that transport shipments that are small
relative to vehicle capacity. Consolidation carrier is an umbrella term that covers companies
participating in one (or both) of the less-than-truckload freight and small parcel industries. As
transportation exhibits economies of scale, profitability for such companies is driven by consolidation. Specifically, dispatching vehicles that transport multiple shipments, each potentiallyassociated with a different customer. Such consolidation is typically enabled by routing shipments on paths through a network of terminals as opposed to directly from customer origin todestination, as is often done in full truckload transportation.
More precisely, a path for a shipment refers to the sequence of terminals it visits, with thesequence beginning at the origin terminal for the shipment and ending at its destination terminal.
We also refer to these paths as consisting of one or more transportation moves, where a transportation move refers to physical transportation, either by a shipment or a capacitated vehicle,
between terminals in the network. Transportation moves executed by a vehicle incur a cost thatis independent of the shipments it transports. Lastly, the schedule for a path prescribes dispatch
times for each of its transportation moves. These schedules in turn imply vehicle dispatch times
on those same moves. Achieving high levels of consolidation, and low transportation costs, requires determining paths for shipments through such networks, and schedules for those paths,
that enable multiple shipments to dispatch on the same transportation move at the same time.
Jointly determining these paths and schedules is typically seen as a tactical planning problem
and is modeled as a variant of the Scheduled Service Network Design Problem (SSNDP) (Crainic
et al. , 2021).
A carrier may seek to keep shipment paths constant over some planning horizon (e.g. amonth), in order to maintain consistency with the operations that support the execution of
those paths. However, for some types of carriers (e.g. road-based Less-than-truckload freighttransportation carriers) there is often flexibility, operationally-speaking, with respect to thescheduling of paths. In the near-term when more accurate forecasts of shipment volumes are
TRISTAN XI Symposium

Original abstract submittal

M. Hewitt, F. Lehuédé

2known, it may be willing to adjust the schedules for those paths if doing so leads to greater
consolidation. Thus, we consider the problem of optimally determining shipment path schedules
in order to minimize total vehicle transportation costs. We refer to this problem as the Service
Network Scheduling Problem (SNSP).
We propose two mixed integer programming formulations of this problem. The first is basedon the classical idea of a time-expanded network (Ford & Fulkerson, 1958, 1962). The second
is based on enumerations of consolidations of shipments. We prove the equivalence of the formulations. We also show both analytically and computationally that the consolidation-based
formulation can be the stronger of the two, but that its enumerative nature renders it computationally ineffective for instances based on large numbers of shipments.
Thus, we present an algorithm for solving the consolidation-based formulation that does notenumerate sets of consolidations a priori, but instead dynamically in the course of its execution.
Clearly, one framework for such an algorithm is Branch-and-Price (Barnhart et al. , 1998, Desaulniers et al. , 2006). As such an algorithm involves solving linear relaxations of a formulation,
many of the technical advancements of today’s solvers at solving integer programs is lost. We
present an algorithm that operates in a fashion that is similar to Branch-and-Price, in that at
each iteration it solves an optimization problem and then uses information from the solution tothat optimization problem to determine variables to add. It differs from Branch-and-Price in thatthe optimization problem solved is an integer program that is formulated so as to be a relaxationof the original problem. We refer to this algorithm as IP − ColGen, or, Integer Programmingbased Column Generation. We prove the correctness of this algorithm and demonstrate with acomputational study its superiority to solving the static formulation. We believe this algorithm
and formulation technique can be employed in formulations of and solution methods for the moregeneral SSNDP, something we will discuss during the presentation.

2

Methodology

In this section, we present the consolidation-based methodology for this problem. We omit the
time-expanded network formulation for brevity and because it is classical. We model the terminal
network and moves within that network with the directed network D = (N , A), where N is a setof nodes that model terminals in the network and A is a set of arcs that model transportation
moves within that network. Formally, the set A consists of pairs (i, j), i, j ∈ N that model
physical travel from terminal i to terminal j. Associated with each arc (i, j) ∈ A is a travel timedenoted by τij , a per-vehicle capacity denoted by uij , and a per-vehicle cost denoted by fij .
We model shipments that must be routed through the network with the set K of commodities.
Associated with each commodity k ∈ K is an origin terminal, ok , and destination terminal, dk .
We let ek denote the earliest time at which commodity k is available at its origin terminal,
ok , and lk denote the latest time at which k can be delivered to its destination terminal, dk .
Lastly, associated with commodity k is a size qk quoted in the same unit as the capacity factors
uij , (i, j) ∈ A associated with arcs.
Recalling that our problem presumes that paths for shipments are known, we let pk =v1k , ..., vrkk represent the sequence of nodes from N in the path of commodity k ∈ K, with v1k = okand vrkk = dk . We let P = ∪k∈K pk denote the set of all such shipment paths. Relatedly, forcommodity k we let the node set N k ⊆ N contain the nodes vik in that path and the arc setk ) in that path. We also let K = {k ∈ K : (i, j) ∈ Ak } denote
Ak ⊆ A contain the arcs (vik , vi+1
ij
the set of commodities with a path that contains arc (i, j) ∈ A. Lastly, we note that given thepath pk and earliest available and latest due times ek , lk for commodity k, one can derive a time
window [αvk , βvk ] during which k can be at each node v in its path.
The proposed formulation of the SNSP that is based on sets of possible consolidations on eacharc, (i, j) ∈ A. To define the formulation we let Cij = {C 1 , . . . , C nij }, C g ⊆ Kij ∀g = 1, . . . , nij ,denote all sets of commodities that can dispatch on arc (i, j) at the same time. Recalling that
TRISTAN XI Symposium

Original abstract submittal

M. Hewitt, F. Lehuédé

3[αik , βik ] denotes the time window during which commodity k must depart from node i, we have
kq
kq
mg
g
that C g = {k1g , . . . , kmg } ∈ Cij ∀g = 1, . . . , nij if and only if ∩q=1 [αi , βi ] 6= ∅. In words,
a consolidation is feasible on an arc if and only if the time windows for all commodities inthat consolidation overlap in at least one time point. That said, Cij also contains all singletonsets. Namely, if k ∈ Kij , then there exists g ∈ [1, nij ] such that C g = {k}. In addition, we
let C = ∪(i,j)∈A Cij . Throughout this paper we will refer to “consolidation C g ” as shorthand forg
the set of commodities {k1g , . . . , kmg } contained in that consolidation. Regarding data elements
associated with these consolidationPsets, we let the attribute φkC ∈ {0, 1}, k ∈ K, C ∈ C represent
whether k ∈ C. We also let sC = dconsolidation C.

k∈C qkuije represent the number of vehicles needed to transport

To model the SNSP, we let the binary variable wC indicate whether the consolidation consisting of commodities in set C ∈ Cij traveling together on arc (i, j) ∈ A is chosen. Note thischoice implies that the commodities must dispatch at the same time. We let the integer variable
yij represent the number of vehicles that dispatch on arc (i, j) ∈ A. We let the decision variables γvkk vk , i = 1, . . . , nk − 1 prescribe the time at which commodity k dispatches on the arcii+1k ), i = 1, . . . , n − 1 on its path. With these sets and decision variables, we define the(vik , vi+1k
optimization problem Cons-SNSP(C), as

zCons (C) = minimizeX

fij yij(1)∀k ∈ K, (i, j) ∈ Ak ,(2)∀(i, j) ∈ A,

(3)∀(i, j) ∈ A, k, k 0 ∈ Kij ,(4)∀k ∈ K, i = 1, . . . , nk − 2,(5)∀k ∈ K, i = 1, . . . , nk − 1,(6)k∀(vik , vi+1
) ∈ pk , k ∈ K,

(7)

wC ∈ {0, 1}∀C ∈ C,(8)yij ∈ N∀(i, j) ∈ A.

(9)(i,j)∈A

subject toX
φkC wC = 1
C∈Cij

X

sC wC ≤ yij

C∈Cij
0

0

X

k
k
γij
− γij
≤ Mikk (1 −0

φkC φkC wC )C∈Cijγvkk vk
ii+1+ τvk vki

αvk ≤ γvkk vkiiγvkk vk
i

i+1

i+1

i+1

≤ γv kki+1 vi+2≤ βv k∈Ni

The objective seeks to minimize the total costs associated with vehicle moves that transportconsolidations of shipments. Constraints (2) ensure that a consolidation is chosen for eachcommodity on each arc in its path. Constraints (3) ensure that sufficient capacity is paid foron each arc to support the consolidations chosen for that arc. Constraints (4) ensure that allcommodities in the consolidation chosen for an arc dispatch at the same time. Constraints (5)ensure that the dispatch times for arcs on the path of a commodity agree with their travel times.
Constraints (6) ensure the dispatch time decision variables occur within the corresponding time
windows. Constraints (7), (8), and (9) define the decision variables and their domains. While thebig-M value in constraints (4) may lead to a weak formulation, the formulation can be tightened00
without rendering any solutions infeasible by setting Mikk = βik − αik .
TRISTAN XI Symposium

Service Network Scheduling Problem

M. Hewitt, F. Lehuédé

3

4

Results

To compare the two formulations computationally, we generated a set of instances based on a
portion of the network of a United States-based LTL carrier. Specifically, we considered a portionof the network that consists of 25 terminals (e.g. |N | = 25) and 530 physical moves between
terminals (e.g. |A| = 530). Cost, capacity, and travel time data were provided by the carrier. In
addition, the carrier provided a load plan that prescribed paths through the terminal network forpairs of terminals (o, d) ∈ N based on their customer base at the time. We randomly generated
instances that vary in the number of commodities (100,150,200,250,300,350,400,450, and 500)
and other instance parameters.
We compare solving the consolidation-based formulation Cons-SNSP(C) with solving threevariants of the time-expanded network formulation. The first, labeled “T-E Network” consistsof solving the time-expanded network formulation over a complete time-expanded network. The
second, labeled “Reduced T-E Network” consists of solving the formulation over a reduced timeexpanded network. The third, labeled “Reduced T-E Network + Valid inequalities” consistsof solving the formulation over a reduced time-expanded network but strengthened with valid
inequalities.
Table 1 – % solved, time to termination, averaged over all instances
MethodT-E Network
Reduced T-E network
Reduced T-E Network + Valid inequalities
Consolidation% Solved
44.44%
58.33%
66.67%
77.78%

Time (sec.)
4,094.54
3,080.16
2,531.47
1,770.94

However, a downside of the consolidation-based formulation is its enumerative nature. Thus,
we have also developed a column generation-based algorithm to solve this formulation wherein
consolidations are generated dynamically during the course of its execution. We will present
this algorithm in detail during the talk. However, in Table 2 we report results from executing
this algorithm on the same instances discussed above. We see that the algorithm dramatially
Table 2 – Comparison of IP − ColGen with Cons-SNSP(C) by number of commodities# Commodities
IP-ColGen% Solved
Time (sec.)
Cons-SNSP(C)% Solved
Time (sec.)

100

150

200

250

300

350

400

450

500

Average

100%
0.52

100%
1.10

100%
1.58

100%
2.79

100%
6.52

100%
8.16

100%
28.56

100%
75.16

100%
131.18100%
28.40

100.00%0.52

100.00%1.41

100.00%3.00

100.00%5.43

75.00%
1,807.23

75.00%
1,857.88

100.00%606.8025.00%
5,462.01

25.00%
6,194.21

77.78%
1,770.94

outperforms solving the static, a priori formulation.

References
Barnhart, Cynthia, Johnson, Ellis L, Nemhauser, George L, Savelsbergh, Martin WP, & Vance, Pamela H.
1998. Branch-and-price: Column generation for solving huge integer programs. Operations research,46(3), 316–329.
Crainic, Teodor Gabriel, Gendreau, Michel, & Gendron, Bernard. 2021. Network Design with Applications
to Transportation and Logistics.
Desaulniers, Guy, Desrosiers, Jacques, & Solomon, Marius M. 2006. Column generation. Vol. 5. Springer
Science & Business Media.
Ford, Lester Randolph, & Fulkerson, Delbert Ray. 1958. Constructing maximal dynamic flows from static
flows. Operations research, 6(3), 419–433.
Ford, Lester Randolph, & Fulkerson, Delbert Ray. 1962. Flows in networks. Princeton University Press.

TRISTAN XI Symposium

Original abstract submittal