Strategic planning under uncertainty in transportation networks
I. Fragkosa,∗ , J. Wagenaarb , M. Farob
a Rotterdam School of Management, Erasmus University, Rotterdam, The Netherlands

ifragkos@rsm.nl

b Tilburg School of Economics and Management, Tilburg University, Tilburg, The Netherlands

j.c.wagenaar_1@uvt.nl, w.l.c.faro@uvt.nl∗ Corresponding author

Logistics service providers (LSPs) utilize transportation assets such as car wagons and containers
to satisfy customer demand. Servicing such demand requires that assets of appropriate capacity
should be utilized for the transportation operation. The amount of time required for transportation
operations can be affected by network disruptions and is therefore stochastic. This gives rise to ageneralized newsvendor problem, where the LSP decides how many assets to acquire and how toschedule them so that stochastic demand requests that require specific capacity but uncertain time
are fulfilled. Excess demand can be satisfied by utilizing spot assets, which, however, come at ahigher cost. We apply this framework to an LSP who leases train wagons on an annual basis andresponds to demand fluctuations via ad-hoc spot train rentals and formulate this problem as a twostage stochastic program. Structural properties of the formulation and a column generation-based
procedure greatly reduce the search space of optimal solutions. Computational results illustrate
the efficiency of our approach.

April 11, 2022
Keywords: Strategic Planning; News-vendor; Column Generation; Cutting Stock Problem.

1INTRODUCTION

Logistic service providers (LSPs) offer door-to-door transportation services to companies spanning across multiple industries. In order to carry out such services with high operational efficiency, their capability to respond to fluctuating customer demand is of paramount importance.
Timely access to transportation infrastructure, such as train wagons and containers, requires
the deployment of assets provisioned well in advance, so that resorting to reactive, last-minutealternatives is kept to a minimum.
Consider, for instance, a provider of rail transportation services, who may commit to theacquisition of a certain number of train wagons on an annual basis, either by entering in longterm leasing agreements or by purchasing the wagons herself. If her customers’ demand exhibit
strong seasonal fluctuations and she needs additional wagons to cover it, she will have to use
spot wagons, which are often priced at a premium. Therefore, committing to a small numberof wagons for long-term usage exposes her to demand variability, leading to last-minute orders
and recurrent, one-off costs. Committing upfront, however, to an unnecessarily large number ofwagons can lead to significant fixed costs, affect liquidity, and ultimately the prosperity of heroperations. Such a position can lead to financial distress, especially if anticipated demand is notrealized.
Although such decisions have additional complexities, in the case of transportation assets
there is one aspect that makes them particularly challenging: customer demand is in the formof transportation services, while supply for those services is in the form of asset acquisitions.
Moreover, requests for transportation services have two dimensions of uncertainty: the numberof requests per customer, and the time spent for each request, which is the round-trip duration
to the customer and the time spend in her premises to carry out the service. Translating such
TRISTAN XI SymposiumOriginal abstract submittal

I. Fragkos, J. Wagenaar, and M. Faro

2service requests to strategic asset acquisition decisions is challenging, and depends critically on
the efficiency of the underlying operations. The literature has considered this problem in several
specific settings (Yamada et al., 2009, Nourinejad & Roorda, 2017, Noori-daryan et al., 2017,Meng et al., 2014), but, to the best of our knowledge, our work is the first one to provide aunifying, stylized framework that captures this trade-off.
In this work, we formulate this problem as a two-stage, multi-period stochastic mixed-integer
program and solve it using column generation and a customized algorithm. We provide computational results that demonstrate the efficiency of our approach.

2METHODOLOGY

We use the following notation for our model.
Sets.
C = {1, . . . , |C|}, Customers, indexed by c.
T = {1, . . . , |T |}, Time periods, indexed by t.
N = {1, . . . , |N |}, Assets, indexed by n.
S = {1, . . . , |S|}, Scenarios, indexed by s.
Parameters.
ρ,Maximum duration an asset can be in service per time period.
θcts , Service request demand of customer c in time period tunder scenario s (number of trips required)τcts , Duration an asset is deployed to perform one service request of customer cin time period t under scenario s
kt ,Number of spot assets available during time period t at the spot market.
pts ,Probability that in time period t scenario s realizes.
Λ,Regular asset acquisition cost.
Γ,Spot asset acquisition cost.
Decision variables.
ω,
Number of assets acquired at the beginning of the planning horizon (regular assets).
ζts ,Number of additional assets rented from the spot market,
during time period t under scenario s (spot assets).
ynts ,= 1, if asset n is utilized in time period t under scenario s, 0 otherwise
Acnts ,
Number of service requests of customer c satisfied by asset n,during time period t under scenario s.
Using the sets, parameters and variables, the Strategic Model (SM) is defined as follows.
XXmin Λω + Γpts ζts(1)t∈T s∈SXs.t. ω + ζts ≥∀t ∈ T, ∀s ∈ S(2)Acnts = θcts ,∀c ∈ C, ∀t ∈ T, ∀s ∈ S(3)τcts Acnts ≤ ρynts ,∀n ∈ N, ∀t ∈ T, ∀s ∈ S(4)∀t ∈ T, ∀s ∈ S(5)∀n ∈ N, ∀t ∈ T, ∀s ∈ S(6)∀c ∈ C, ∀n ∈ N, ∀t ∈ T, ∀s ∈ S(7)ynts ,n∈N

Xn∈NX
c∈C

ζts integer0 ≤ ζts ≤ kt ;ynts ∈ {0, 1},
Acnts ≥ 0;
ω ≥ 0;

Acnts integerω integer(8)

The objective function minimizes the total expected cost, which consists of the cost of the regularassets and the expected cost of spot assets. Constraints (2) state that the assets required should
TRISTAN XI Symposium

Original abstract submittal

I. Fragkos, J. Wagenaar, and M. Faro

3

be lower than or equal to the total number of available assets, spot and regular, for every time
period and scenario. Constraints (3) show that service requests from customer c, θcts , must be
satisfied by asset deployments in a scenario/ time period combination. Constraints (4) pose thatthe total time an asset is in use during a time period under a scenario should be no higher thanits available operating time in every scenario/ time period combination. Finally, Constraints(5)-(8) show the bounding and integrality restrictions of the decision variables.
A key property of (1)-(8) is that theP variables that are in the objective function appear onlyin constraints (2), lower bounded by n∈N ynts , the number of required assets in each period
and scenario. Therefore, a simpler version of the SM model (1)-(8) can be formulated assumingthat the number of required assets in each time period and scenario, δts , is given exogenously.
We use δ to denote the vector of δts . Then, model (9)-(12) describes this reformulation.
XXz(δ) = min Λω + Γpts ζts(9)t∈T s∈Ss.t. ω + ζts ≥ δts ,∀t ∈ T, ∀s ∈ S(10)

ω integer(11)∀t ∈ T, ∀s ∈ S(12)

ω ≥ 0,
ζts ∈ {0, 1, . . . , kt },Here, the objective, (9), is identical to the original objective, and constraints (10) state that
there need to be at least as many assets available in each time period/scenario combination as
there is demand for. For model (9)-(12), we can formally prove the following result, which westate hereby as a remark.
Remark 2.1 Define(∗δts:= min)X(13)ynts : (3) − (4); (6) − (7)n∈N∗ for all t ∈ T, s ∈ S, (9)-(12) and (1)-(8) have the same optimal objective value.
• If δts = δts∗ for all t ∈ T, s ∈ S, then the optimal objective value of (9)-(12) is an upper• If δts ≥ δts
bound to the optimal objective of (1)-(8).
∗ for all t ∈ T, s ∈ S with at least one inequality strict, then the optimal objective• If δts ≤ δtsvalue of (9)-(12) is a lower bound to the objective solution of (1)-(8).
∗ by solving (13)Remark 2.1 can be used to devise an algorithm to solve (1)-(8): calculate δts
for each t, s, and then use them to solve (9)-(12). The former step can be done efficiently with acolumn generation algorithm, because (13) has a cutting-stock problem structure. In the original
cutting-stock problem, the goal is to cut paper rolls in a number of pieces of a certain length (notnecessary identical lengths) while minimizing the total number of paper rolls that are needed. In
our setting, the problem is to select schedules defining the number of service requests an asset
will satisfy of different customers during time period t ∈ T under scenario s ∈ S, i.e. a cutting
pattern represents the allocation of an asset to customers. The set of all possible asset schedules
is denoted by Q. Then, the service requests satiated by an asset to customer c ∈ C in asset
schedule q ∈ Q is signified by vqc . We drop the indexes t and s for brevity and define the integer
variable λq , which represents the number of assets following schedule q. Then, subproblem (13)can be formulated as follows.
X
min
λq
(14)
q∈Qs.t.

Xλq vqc = θc ,∀c ∈ C(15)∀q ∈ Q(16)q∈Q

λq ≥ 0;
TRISTAN XI Symposium

λq ∈ Z

Original abstract submittal

I. Fragkos, J. Wagenaar, and M. Faro

4We then state a proposition that shows how using the knowledge of δts we can calculate ωand ζts .
Proposition 2.1 Model (9)-(12) is convex and piecewise linear in ω. Further, let ωmin =maxt∈T {maxs∈S {δts } − kt } and P = {(t, s) : δts ≥ ωmin }. Then, the optimal number of regular assets ω ∗ is in the set Ω∗ := {ωmin } ∪ {δts , ∀(t, s) ∈ P } and the optimal number of spot
∗ = max(0, δ − ω ∗ ).
assets follows from ζtsts3RESULTS

In our algorithm, we use column generation to solve (13) and then a simple line search across∗ to find the optimal ω, as implied by Proposition 2.1. To test our approach, we
all feasible δtshave generated instances with varying periods (|T | ∈ P{26, 62}), customers (|C| ∈ {2, 4, 8, 16}),
θcts
scenarios |S| ∈ {5, 10, 20, 50} and capacity tightness ( c∈C∈ {0.6, 1}). The combination ofktparameters leads to 192 instances, which were classified to small, medium and large according toProblem size
SmallMedium
Large

Instances
549048Gap (%)CPLEX CG
00
1.26
0.03
7.110.01

CPU (s)CPLEXCG
1.23
15.86
3,978
255
7,200 (TL) 1,728

No solution
CPLEX CG0070350

Table 1 – Average values over the Small, Medium, and Large instances for CPLEX and our custom
algorithm (CG). TL denotes time limit.

4DISCUSSION

We study the strategic planning of transportation assets, a problem faced by LSPs, emphasizingthat demand for services is expressed in the form of service requests and time during which theservicing asset is occupied. Our formulation captures the core elements of this problem, and assuch it can be extended to more specific situations. We utilize a decomposition scheme where
each subproblem, formulated as a cutting-stock problem, is solved by column generation andtheir solutions are utilized in a reduced reformulation of the original problem, which we cansolve in polynomial time by exploiting its structure.

References
Meng, Qiang, Wang, Shuaian, Andersson, Henrik, & Thun, Kristian. 2014. Containership routing andscheduling in liner shipping: overview and future research directions. Transportation Science, 48(2),265–280.
Noori-daryan, Mahsa, Taleizadeh, Ata Allah, & Govindan, Kannan. 2017. Joint replenishment and pricing
decisions with different freight modes considerations for a supply chain under a composite incentivecontract. Journal of the operational research society, 1–20.
Nourinejad, Mehdi, & Roorda, Matthew J. 2017. A continuous approximation model for the fleet composition problem on the rectangular grid. OR spectrum, 39(2), 373–401.
Yamada, Tadashi, Russ, Bona Frazila, Castro, Jun, & Taniguchi, Eiichi. 2009. Designing multimodal
freight transport networks: A heuristic approach and applications. Transportation science, 43(2),129–143.

TRISTAN XI Symposium

Original abstract submittal