A metaheuristic for stochastic service network design

Arild Hoff 1, Arnt-Gunnar Lium 2, Arne Løkketangen 1, and Theodor Crainic 3

1 Molde University College,P.O.Box 2110 NO-6402 Molde, Norway,
Arild.Hoff@himolde.no, arne.lokketangen@himolde.no,

2 SINTEF Technology and Society, Trondheim, Norway,
ArntGunnar.Lium@sintef.no,

3 ESG UQAM and CIRRELT, Montreal, Canada,
theo@crt.umontreal.ca

Abstract. This paper considers the time-dependent service network design
problem with stochastic demand. Service Network Design consists
of two stages: in the first stage we decide routes for vehicles, in the
second we route the freight. In the stochastic version of the problem,
the first stage is done prior to observing the random supply and demand,
while in the second stage we can react to the observed values. In
a stochastic-programming context, the freight routing would be referred
to as a recourse action. We use an implementation with a network where
all the nodes (terminals) are repeated for all time periods. The arcs in
the network are directed and represent a link from one node to another
between two consecutive periods. Each link is associated by a capacity
and may represent vehicles driving from one terminal to another. If no
vehicles are driving along the link the capacity is zero and if one or more
vehicles are driving along the link the capacity is equal to the sum of the
vehicles’ capacities. In addition, the freight can be stored at a terminal.
A number of commodities are given, each having a random volume to
be transported between two given nodes by a given time period. The
total cost of a solution consists of sum of the following components: The
expected cost of operating the vehicles, the expected cost of handling
the freight and the expected cost of outsourcing the part of the demand
which can not be delivered. The uncertainty in the demand is represented
by scenarios. The model integrates the balancing of empty vehicles, the
cost of handling freight in intermediate terminals, the costs associated
with moving freight using the selected services, and the penalty costs of
not being able to deliver freight. A metaheuristic search method is presented
for solving