<< стр. 5(всего 15)СОДЕРЖАНИЕ >>

tij xij + fi yi , (3.29)
iв€€V1 j в€€V2 iв€€V1

where
tij = cij + gi dj , i в€€ V1 , j в€€ V2 . (3.30)

This transformation is based on the following observations. If the site i в€€ V1
is opened, the п¬Ѓrst term of the objective function (3.29) includes not only the
transportation cost cij xij , j в€€ V2 , but also the contribution gi dj xij of the variable
cost of the facility i в€€ V1 ; if, instead, the site i в€€ V1 is not opened, the variables
xij , j в€€ V2 , take the value 0 and that does not generate any cost.
Case B. A potential facility cannot be run economically if its activity level is lower
than a value qiв€’ or higher than a threshold qi+ . For intermediate values, the operating
cost grows linearly (see Figure 3.6). This case can be modelled as the previous case,
provided that in (3.29), (3.10)вЂ“(3.14), capacity constraints (3.11) are replaced with
the following relations:

qiв€’ yi qi+ yi , i в€€ V1 .
dj xij
j в€€V2

TLFeBOOK
92 DESIGNING THE LOGISTICS NETWORK
Fi (ui)

fi

ui

Figure 3.5 Operating cost Fi (ui ) of potential facility i в€€ V1 versus
activity level ui (case A).

Fi (ui)

fi

q+
qiв€’ ui
i

Figure 3.6 Operating cost Fi (ui ) of potential facility i в€€ V1 versus
activity level ui (case B).

Case C. The operating cost Fi (ui ) of a potential facility i в€€ V1 is a general concave
piecewise linear function of its activity level because of economies of scale. In the
simplest case, there only are two piecewise lines (see Figure 3.7). Then
пЈ±
пЈґfi + gi ui , if ui > ui ,
пЈІ
Fi (ui ) = fi + gi ui , if 0 < ui ui , i в€€ V1 , (3.31)
пЈґ
пЈі
if ui = 0,
0,

where fi < fi and gi > gi . In order to model this problem as before, each potential
facility is replaced by as many artiп¬Ѓcial facilities as the piecewise lines of its cost
function. For instance, if Equation (3.31) holds, facility i в€€ V1 is replaced by two

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 93
Fi (ui)

fi''

fi'

ui
ui'

Figure 3.7 Operating cost Fi (ui ) of potential facility i в€€ V1 versus
activity level ui (case C).

artiп¬Ѓcial facilities i and i whose operating costs are characterized, respectively,
by п¬Ѓxed costs equal to fi and fi , and by marginal costs equal to gi and gi . In this
way the problem belongs to case A described above since it is easy to demonstrate
that in every optimal solution at most one of the artiп¬Ѓcial facilities is selected.

Logconsult is an American consulting company commissioned to propose changes
to the logistics system of Gelido, a Mexican п¬Ѓrm distributing deep-frozen food. A key
aspect of the analysis is the relocation of the Gelido DCs. A preliminary examina-
tion of the problem led to the identiп¬Ѓcation of about |V1 | = 30 potential sites where
warehouses can be open or already exist. In each site several different types of ware-
houses can usually be installed. Here we show how the cost function of a potential
facility i в€€ V1 can be estimated. Facility п¬Ѓxed costs include rent, amortization of the
machinery, insurance of premises and machinery, and staff wages. They add up to
\$80 000 per year. The variable costs are related to the storage and handling of goods.
Logconsult has estimated the Gelido variable costs on the basis of historical data (see
Table 3.9).
Facility variable costs (see Figure 3.8) are inп¬‚uenced by inventory costs which
generally increase with the square root of the demand (see Chapter 4 for further
details). This relation suggests approximating the cost function of potential facility
i в€€ V1 through Equation (3.31), where ui = 3500 hundred kilograms per year.
The values of fi , fi , gi and gi can be obtained by applying linear regression (see
Chapter 2) to each of the two sets of available data. This way the following relations
are obtained:
fi = 80 000 + 2252 = 82 252 dollars per year;
gi = 18.5 dollars per hundred kilograms;

TLFeBOOK
94 DESIGNING THE LOGISTICS NETWORK

fi = 80 000 + 54 400 = 134 400 dollars per year;
gi = 4.1 dollars per hundred kilograms.

The problem can therefore be modelled as in (3.29), (3.10)вЂ“(3.14), provided that
each potential facility i в€€ V1 is replaced by two dummy facilities i and i with п¬Ѓxed
costs equal to fi and fi , and marginal costs equal to gi and gi , respectively.
By way of example, this approach is applied to a simpliп¬Ѓed version of the problem
where the potential facilities are in Linares, Monclova and Monterrey, each of them
having a capacity of 20 000 hundred kilograms per year, and the sales districts are
concentrated in four areas, around Bustamante, Saltillo, Santa Catarina and Monte-
morelos, respectively. The annual demands add up to 6200 hundred kilograms for
Bustamante, 6600 hundred kilograms for Saltillo, 5800 hundred kilograms for Santa
Catarina and 4400 hundred kilograms for Montemorelos. Transportation is carried
out by trucks whose capacity is 10 hundred kilograms and whose cost is equal to
\$0.98 per mile.
The Gelido location problem can be modelled as a CPL formulation:
Minimize
tij xij + fi y i
iв€€V1 j в€€V2 iв€€V1

subject to

xij = 1, j в€€ V2 ,
iв€€V1

i в€€ V1 ,
dj xij qi yi ,
j в€€V2
i в€€ V1 , j в€€ V2 ,
xij 1,
0
yi в€€ {0, 1}, i в€€ V1 ,

where V1 = {Linares , Linares , Monclova , Monclova , Monterrey , Monterrey },
V2 = {Bustamante, Saltillo, Santa Catarina, Montemorelos}. Linares and Linares
represent two dummy facilities which can be opened up in Linares, with a capacity
equal to

qi = 3500 hundred kilograms per year,
qi = 20 000 hundred kilograms per year,

respectively (the same goes for Monclova , Monclova , Monterrey and Monterrey );
xij , i в€€ V1 , j в€€ V2 , is a decision variable representing the fraction of the annual
demand of sales district j satisп¬Ѓed by facility i; yi , i в€€ V1 , is a binary decision
variable, whose value is equal to 1 if the potential facility i is open, 0 otherwise.
Costs tij , i в€€ V1 , j в€€ V2 , reported in Table 3.11, were obtained by means of

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 95

Table 3.9 Demand entries (in hundreds of kilograms per year) versus facility variable costs
(in dollars) as reported in the past in the Logconsult problem.

Demand Variable cost

1 000 17 579
2 500 56 350
3 500 62 208
6 000 76 403
8 000 85 491
9 000 90 237
9 500 96 251
12 000 109 429
13 500 107 355
15 000 122 432
16 000 116 816
18 000 124 736

Table 3.10 Distances (in miles) between potential facilities and
sales districts in the Logconsult problem.

Bustamante Saltillo Santa Catarina Montemorelos

Linares 165.0 132.5 92.7 32.4
Monclova 90.8 118.5 139.0 176.7
Monterrey 84.2 51.6 11.9 49.5

Equations (3.30), where the quantities cij , i в€€ V1 , j в€€ V2 , are in turn obtained
through Equation (3.15). In other words, cij = cij dj , with cij = (0.98 Г— 2 Г— lij )/10,
ВЇ ВЇ
where lij , i в€€ V1 , j в€€ V2 , represents the distance (in miles) between facility i and
market j (see Table 3.10).
The optimal demand allocation (see Table 3.12) leads to an optimal cost equal to
\$569 383.52 per year. Two facilities are located in Linares and Monterrey, with an
activity level equal to 3000 hundred kilograms per year and 20 000 hundred kilograms
per year, respectively (this means that the Linares and Monterrey dummy facilities
are opened).

3.4 Two-Echelon Multicommodity Location Models
In two-echelon multicommodity (TEMC) location problems, homogeneous facilities
have to be located as in SESC problems. However, both incoming and outgoing

TLFeBOOK
96 DESIGNING THE LOGISTICS NETWORK
Variable cost
140 000

120 000

100 000

80 000

60 000

40 000

20 000

0
Demand
0 2000 4000 6000 8000 10 000 12 000 14 000 16 000 18 000

Figure 3.8 Variable cost of a facility versus demand in the Logconsult problem.

Table 3.11 Annual costs (in dollars) tij , i в€€ V1 , j в€€ V2 , in the Logconsult problem.

Bustamante Saltillo Santa Catarina Montemorelos

Linares 315 208 293 502 212 681 109 342
Linares 225 928 198 462 129 161 45 982
Monclova 225 040 275 392 265 315 233 786
Monclova 135 760 180 352 181 795 170 426
Monterrey 217 020 188 850 120 828 124 089
Monterrey 127 740 93 810 37 308 60 729

Fraction of the annual demand of sales district j в€€ V2 satisп¬Ѓed by
Table 3.12
facility i в€€ V1 , in the Logconsult problem.

Bustamante Saltillo Santa Catarina Montemorelos

Linares 0.00 0.00 0.00 0.68
Linares 0.00 0.00 0.00 0.00
Monclova 0.00 0.00 0.00 0.00
Monclova 0.00 0.00 0.00 0.00
Monterrey 0.00 0.00 0.00 0.00
Monterrey 1.00 1.00 1.00 0.32

commodities are relevant and material п¬‚ows are not homogeneous. In what follows,
transportation costs are assumed to be linear, and each facility is assumed to be
characterized by a п¬Ѓxed and a marginal cost. If cost functions are piecewise linear
and concave, transformations similar to the ones depicted in Section 3.3 can be used

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 97

as a solution methodology. In the following, for the sake of clarity, it is assumed that
the facilities to be located are DCs supplied directly from production plants.
TEMC problems can be modelled as MIP problems. Let V1 be the set of production
plants; V2 the set of potential DCs, p of which are to be opened; V3 the set of the
demand points; K the set of homogeneous commodities; cij r , i в€€ V1 , j в€€ V2 , r в€€ V3 ,
k

k в€€ K, the unit transportation cost of commodity k from plant i to the demand
point r across the DC j ; dr , r в€€ V3 , k в€€ K, the quantity of product k required
k

by demand point r in a time unit (for example, one year); pi , i в€€ V1 , k в€€ K, the
k
в€’
maximum quantity of product k that plant i can manufacture in a time unit; qj and
+
qj , j в€€ V2 , the minimum and maximum activity level of potential DC j in a time
unit, respectively. Moreover, it is assumed that the operating cost of each DC j в€€ V2
depends on the amount of commodities through a п¬Ѓxed cost fj and a marginal cost
gj . Finally, it is assumed that demand is not divisible (see Section 3.2). Let zj , j в€€ V2 ,
be a binary variable equal to 1 if DC j is opened, 0 otherwise; yj r , j в€€ V2 , r в€€ V3 ,
k
a binary variable equal to 1 if demand point r is assigned to DC j , 0 otherwise; sij r ,
i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K, a continuous variable representing the quantity of
item k transported from plant i to demand point r through DC j . The TEMC model
is:
Minimize

kk k
cij r sij r + fj zj + gj dr yj r
iв€€V1 j в€€V2 rв€€V3 kв€€K j в€€V2 rв€€V3 kв€€K

subject to
k k
i в€€ V1 , k в€€ K,
sij r pi , (3.32)
j в€€V2 rв€€V3
k k
sij r = dr yj r , j в€€ V2 , r в€€ V3 , k в€€ K, (3.33)
iв€€V1

yj r = 1, r в€€ V3 , (3.34)
j в€€V2
в€’ +
k
j в€€ V2 ,
qj zj dr yj r qj zj , (3.35)
rв€€V3 kв€€K

zj = p, (3.36)
j в€€V2
zj в€€ {0, 1}, j в€€ V2 , (3.37)
yj r в€€ {0, 1}, j в€€ V2 , r в€€ V3 , (3.38)
k
i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K.
sij r 0, (3.39)

Inequalities (3.32) impose a capacity constraint for each production plant and for
each product. Equations (3.33) require the satisfaction of customer demand. Equa-

TLFeBOOK
98 DESIGNING THE LOGISTICS NETWORK

tions (3.34) establish that each client must be served by a single DC. Inequalities (3.35)
are DC capacity constraints. Equation (3.36) sets the number of DCs to be opened.
By removing some constraints (e.g. Equation (3.36)) or adding some new con-
straints (e.g. forcing the opening of a certain DC, or the assignment of some demand
points to a given DC) several meaningful variants of the above model can be obtained.
вЂў A plant i в€€ V1 is not able to produce a certain commodity k в€€ K (in this case
we remove the decision variables sij r for each r в€€ V3 and j в€€ V2 ).
k

вЂў A DC j в€€ V2 cannot be serviced efп¬Ѓciently by a plant i в€€ V1 because it is too
far from it (in this case we remove variables sij r for each r в€€ V3 and k в€€ K).
k

вЂў The time required to serve a demand point r в€€ V3 from potential DC j в€€ V2
k
is too long (in this case we remove variables yj r and variables sij r for each
i в€€ V1 and k в€€ K).

Demand allocation
When a set zj , j в€€ V2 and yj r , j в€€ V2 , r в€€ V3 , of feasible values for the binary vari-
ВЇ
ВЇ
ables is available, determining the corresponding optimal demand allocation amounts
to solving an LP problem:
Minimize
kk
cij r sij r (3.40)
iв€€V1 j в€€V2 rв€€V3 kв€€K

subject to
k k
i в€€ V1 , k в€€ K,
sij r pi , (3.41)
j в€€V2 rв€€V3
k k
sij r = dr yj r ,
ВЇ j в€€ V2 , r в€€ V3 , k в€€ K, (3.42)
iв€€V1
k
i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K.
xij r 0, (3.43)

A Lagrangian heuristic
The Lagrangian methodology illustrated for the CPL problem can be adapted to the
TEMC problem as follows. A lower bound is obtained by relaxing constraints (3.33)
with multipliers Оёj r , j в€€ V2 , r в€€ V3 , k в€€ K. The relaxed problem:
k

Minimize

k k k k k
(cij r + Оёj r )sij r + fj zj + (gj в€’ Оёj r ) dr yj r
iв€€V1 j в€€V2 rв€€V3 kв€€K j в€€V2 rв€€V3 kв€€K

subject to (3.32), (3.34)вЂ“(3.39), decomposes into two separate subproblems P1 and
P2 . P1 is the LP problem:

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 99

Minimize
k k k
(cij r + Оёj r )sij r
iв€€V1 j в€€V2 rв€€V3 kв€€K
subject to (3.32) and (3.39), which can be strengthened by adding constraints:
k k
sij r = dr , r в€€ V3 , k в€€ K,
iв€€V1 j в€€V2
+
k
qj , j в€€ V2 .
sij r
iв€€V1 rв€€V3 kв€€K

Subproblem P2 , deп¬Ѓned as
Minimize
k k
fj z j + (gj в€’ Оёj r ) dr yj r
j в€€V2 j в€€V2 rв€€V3 kв€€K
subject to (3.34)вЂ“(3.38), is an SESC problem (with indivisible demand) where DCs
have to be located and each customer r в€€ V3 has a single-commodity demand equal
k
to kв€€K dr . Even if this problem is still NP-hard, its solution is usually much simpler
than that of the TEMC problem and can be often obtained through a general-purpose
or a tailored branch-and-bound algorithm.
Let zj , j в€€ V2 and yj r , j в€€ V2 , r в€€ V3 , be the optimal solution of P2 . If the
ВЇ ВЇ
allocation problem associated with such binary variable values is feasible, an upper
bound is obtained. The above procedure is then embedded in a subgradient procedure
in order to determine improved lower and upper bounds.

A Benders decomposition procedure
We now illustrate a Benders decomposition method for solving the TEMC problem.
Generally speaking, a Benders decomposition method allows the determination of an
optimal solution of an MIP problem by solving several MIP problems with a single
continuous variable each, and several LP problems.
To simplify the exposition, the Benders decomposition method will be described
rв€€V3 dr , k в€€ K, and at least
k k
assuming the problem is well posed (i.e. iв€€V1 pi
one solution (zj , yj r ), j в€€ V2 , r в€€ V3 , satisп¬Ѓes all the constraints).
Let Вµk , i в€€ V1 , k в€€ K, and ПЂj r , j в€€ V2 , r в€€ V3 , k в€€ K, be the dual variables
k
i
corresponding to constraints (3.41) and (3.42), respectively. The dual of problem
(3.40)вЂ“(3.43) can be reformulated as
Maximize
(в€’pi )Вµk +
k k k
ВЇ
(dr yj r )ПЂj r (3.44)
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K
subject to
в€’Вµk + ПЂj r
k k
i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K,
cij r , (3.45)
i
Вµk i в€€ V1 , k в€€ K.
0, (3.46)
i

TLFeBOOK
100 DESIGNING THE LOGISTICS NETWORK

This way the optimal solution of problem (3.40)вЂ“(3.43) is determined by solv-
ing its dual. Since problem (3.40)вЂ“(3.43) always has a п¬Ѓnite optimal solution, its
dual (3.44)вЂ“(3.46) can be formulated as follows. Denote by в„¦ the feasible region
of problem (3.44)вЂ“(3.46) and by T the set of extreme points of в„¦. Moreover, let
Вµk (t), i в€€ V1 , k в€€ K, and ПЂj r (t), j в€€ V2 , r в€€ V3 , k в€€ K, be the dual solution cor-
k
i
responding to a generic extreme point t в€€ T . Then we can compute:
Maximize

(в€’pi )Вµk (t) +
k kk k
ВЇ
(dr yj r )ПЂj r (t) .
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K

The feasible region в„¦ (and, consequently, also T ) does not depend on the yj r , j в€€
ВЇ
V2 and r в€€ V3 values. This observation allows us to formulate the TEMC problem as
Minimize

k
fj zj + gj dr yj r
j в€€V2 rв€€V3 kв€€K

(в€’pi )Вµk (t) +
k kk k
+ max (dr yj r )ПЂj r (t)
i
tв€€T
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K

subject to (3.34)вЂ“(3.38), or equivalently (Benders reformulation):
Minimize
L (3.47)
subject to

k
fj z j + g j
L dr yj r
j в€€V2 rв€€V3 kв€€K

(в€’pi )Вµk (t) +
k kk k
+ (dr yj r )ПЂj r (t), t в€€ T (3.48)
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K

and constraints (3.34)вЂ“(3.38).
Problem (3.47), (3.48), (3.34)вЂ“(3.38) becomes intractable because of the large
number of constraints (3.48) (one for each extreme point of в„¦). For this reason, it is
convenient to resort to the relaxation of this formulation, named master problem, for
which only a subset T (h) вЉ† T of constraints (3.48) is present.

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 101

Minimize
L (3.49)
subject to

k
fj zj + gj
L dr yj r
j в€€V2 rв€€V3 kв€€K

(в€’pi )Вµk (t) +
k kk k
t в€€ T (h) , (3.50)
+ (dr yj r )ПЂj r (t),
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K

and constraints (3.34)вЂ“(3.38).
(h) (h)
Let zj , j в€€ V2 and yij , j в€€ V2 , r в€€ V3 , be an optimal solution to the master
problem, and let L(h) be the corresponding objective function value. Since the master
problem represents a relaxation of the formulation (3.47), (3.48), (3.34)вЂ“(3.38), the
value L(h) is a lower bound on the optimal solution value of the TEMC problem.
(h)
Starting from yj r , j в€€ V2 , r в€€ V3 , it is possible to determine the optimal solution
k,(h)
sij r , i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K, of the following demand allocation problem:
Minimize
kk
cij r sij r (3.51)
iв€€V1 j в€€V2 rв€€V3 kв€€K

subject to
k k
i в€€ V1 , k в€€ K,
sij r pi , (3.52)
j в€€V2 rв€€V3
(h)
k
sij r = dr yj r , j в€€ V2 , r в€€ V3 , k в€€ K, (3.53)
iв€€V1
k
i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K.
sij r 0, (3.54)
The optimal solutions of the master and demand allocation problems, therefore,
(h) (h) k,(h)
allow us to deп¬Ѓne a feasible solution zj , j в€€ V2 , yj r , j в€€ V2 , r в€€ V3 , sij r , i в€€
V1 , j в€€ V2 , r в€€ V3 , k в€€ K, for the TEMC problem, whose cost is equal to

(h) (h) k,(h)
U (h) = k k
fj z j + g j +
dr yj r cij r sij r . (3.55)
j в€€V2 iв€€V1 j в€€V2 rв€€V3 kв€€K
rв€€V3 kв€€K

Let Вµk (t (h) ), i в€€ V1 , k в€€ K, and ПЂj r (t (h) ), j в€€ V2 , r в€€ V3 , k в€€ K, t (h) в€€ T , be
k
i
the dual optimal solution of the demand allocation problem (3.51)вЂ“(3.54). Since the
optimum solution values of the primal and dual problems are equal, it follows that
(h)
(в€’pi )Вµk (t (h) ) +
k
(dr yj r )ПЂik (t (h) )
k
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K
k,(h)
k
= cij r sij r ,
iв€€V1 j в€€V2 rв€€V3 kв€€K

TLFeBOOK
102 DESIGNING THE LOGISTICS NETWORK

from which
(h) (h)
U (h) = k
fj zj + gj dr yj r
j в€€V2 rв€€V3 kв€€K
(h)
(в€’pi )Вµk (t (h) ) +
k
(dr yj r )ПЂik (t (h) ).
k
+ (3.56)
i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K
(h)
The implications of Equation (3.56) are clear. If L(h) < U (h) , the solution zj , j в€€
(h) k,(h)
V2 , yj r , j в€€ V2 , r в€€ V3 , sij r , i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K, is not optimal
for the TEMC problem. Furthermore,

(h) (h)
L(h) < k
fj zj + gj dr yj r
j в€€V2 rв€€V3 kв€€K
(h)
(в€’pi )Вµk (t (h) ) +
k
(dr yj r )ПЂik (t (h) ),
k
+ i
j в€€V2 rв€€V3 kв€€K
iв€€V1 kв€€K

i.e. t (h) в€€ T (h) . Therefore, the introduction of t (h) in the set T (h) , which deп¬Ѓnes the
/
constraints (3.50) of the master problem, yields an improvement of the relaxation
and consequently the procedure can be iterated. In the case L(h) = U (h) , the optimal
solution of the TEMC problem is obtained.
In a more schematic way, the Benders decomposition method can be described as
follows.
Step 0. (Initialization.) Select a tolerance value Оµ > 0; set LB = в€’в€ћ, UB = в€ћ,
h = 1, T (h) = в€….
Step 1. (Solution of the master problem.) Solve the master problem (3.49), (3.50),
(h) (h)
(3.34)вЂ“(3.38). Let zj , j в€€ V2 and yj r , j в€€ V2 , r в€€ V3 , be the correspond-
ing optimal solution and L(h) the corresponding objective function value; set
LB = L(h) ; if (UB в€’ LB)/LB < Оµ, then STOP.
Step 2. (Determination of a new feasible solution.) Determine the optimal solu-
k,(h)
tion sij r , i в€€ V1 , j в€€ V2 , r в€€ V3 , k в€€ K, of demand allocation problem (3.51)вЂ“
(3.54) and the corresponding dual solution Вµk (t (h) ), i в€€ V1 , k в€€ K, and ПЂj r (t (h) ),
k
i
j в€€ V2 , r в€€ V3 , k в€€ K; let U (h) be the objective function value obtained through
Equation (3.55); if U (h) < UB, then set UB = U (h) ; п¬Ѓnally, set T (h) = T (h) в€Є {t (h) }.
Step 3. Set h = h + 1 and go back to Step 1.
The above algorithm seeks an Оµ-optimal solution, i.e. a feasible solution with a
maximum gap Оµ from the optimal solution. The efп¬Ѓciency of this method can be
improved remarkably if some feasible solutions for the TEMC problem are available
at the beginning (e.g. the solution adopted in practice and those suggested on the
basis of the experience of the companyвЂ™s management). This yields, at Step 0 of
the algorithm, a better initial choice both for the value of UB and for the set T (1) .
In particular, UB can be set equal to the best value of the objective function value

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 103

Table 3.13 Distances (in kilometres) among the production sites and the demand points
through the DCs in the K9 problem.

i=1 i=2

r=1 r=2 r=3 r=1 r=2 r=3
j

1 400 600 1100 800 1000 1500
2 600 400 900 800 600 1100
3 1000 600 900 800 400 700
4 1600 1200 900 1200 800 500

available. Moreover, the dual solution of each feasible solution allows us to deп¬Ѓne a
constraint (3.50) for the initial master problem. Moreover, because of the presence
of constraints (3.34), the optimal solution of the master problem is such that each
demand point r в€€ V3 is served by one and only one DC jr в€€ V2 , i.e.

if j = jr ,
1,
(h)
yj r =
0, otherwise.

Therefore, the demand allocation problem (3.51)вЂ“(3.54) in Step 2 can be further
simpliп¬Ѓed as:
Minimize
k k
cijr r sijr r
iв€€V1 rв€€V3 kв€€K

subject to
k k
i в€€ V1 , k в€€ K,
sijr r pi ,
rв€€V3
k k
sijr r = dr , r в€€ V3 , k в€€ K,
iв€€V1
k
i в€€ V1 , r в€€ V3 , k в€€ K,
sijr r 0,

and can be therefore decomposed in |K| transportation problems, the kth of which
corresponds to:
Minimize
k k
cijr r sijr r
iв€€V1 rв€€V3

subject to
k k
i в€€ V1 ,
sijr r pi ,
rв€€V3

TLFeBOOK
104 DESIGNING THE LOGISTICS NETWORK
k k
sijr r = dr , r в€€ V3 ,
iв€€V1
k
i в€€ V1 , r в€€ V3 .
sijr r 0,

K9 is a German petrochemical company. The п¬ЃrmвЂ™s management intends to ren-
ovate its production and distribution network, which is presently composed of two
reп¬Ѓning plants, two DCs and hundreds of sales points (gas pumps and liqueп¬Ѓed gas
retailers). After a series of meetings, it was decided to relocate the DCs, leaving the
position and features of the two production plants unchanged. The products of K9 are
subdivided into two homogeneous commodities (represented by the indices k = 1, 2):
fuel for motor transportation and liqueп¬Ѓed gas (the latter sold in cylinders). There are
four potential sites suited to receive a DC and, among these, two must be selected.
A DC j, j = 1, . . . , 4, is economically feasible if its level of activity is higher than
в€’ +
qj = 1 000 000 hectolitres per year and lower than qj = 2 500 000 hectolitres per
year; for intermediate values, the cost increases approximately with a linear trend
characterized by a п¬Ѓxed cost of 10 million euros per year and by a marginal cost of
в‚¬0.25 per hectolitre. Transportation costs cij r , i в€€ V1 , j в€€ V2 , r в€€ V3 , k = 1, 2, are
k

equal to the cost per kilometre and hectolitre (equal to в‚¬0.67 for k = 1, and в‚¬0.82
for k = 2) multiplied by the distance between production plant i в€€ V1 and demand
point r в€€ V3 through site j в€€ V2 (see Table 3.13).
The market is subdivided into three districts (r = 1, 2, 3) characterized by demand
values equal to
d1 = 800 000 hectolitres per year;
1

d2 = 600 000 hectolitres per year;
1

d3 = 700 000 hectolitres per year;
1

d1 = 300 000 hectolitres per year;
2

d2 = 400 000 hectolitres per year;
2

d3 = 500 000 hectolitres per year.
2

Finally, the production plants have the following capacities:
p1 = 1 200 000 hectolitres per year;
1

p2 = 1 500 000 hectolitres per year;
1

p1 = 500 000 hectolitres per year;
2

p2 = 800 000 hectolitres per year.
2

To determine the optimal allocation of the two DCs, a TEMC model with p =
2 is built and solved. The decision variables sij r , i = 1, 2, j = 1, . . . , 4, r =
k

1, 2, 3, k = 1, 2, represent the quantity (in hectolitres) of product k transported yearly

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 105

from production plant i to demand point r through DC j , whereas transportation costs
cij r , i = 1, 2, j = 1, . . . , 4, r = 1, 2, 3, k = 1, 2, can be obtained from Tables 3.14
k

and 3.15.
в€— в€—
In the optimal TEMC solution, the п¬Ѓrst and third DCs are opened (z1 = 1, z2 = 0,
в€— в€—
z3 = 1, z4 = 0) and the yearly cost amounts to 33.19 million euros. The п¬Ѓrst
centre serves the п¬Ѓrst sales district, while the second one is used for the second and
в€— в€— в€—
third sales district (y11 = y32 = y33 = 1). Moreover, the decision variables sij r , k

i = 1, 2, j = 1, . . . , 4, r = 1, 2, 3, k = 1, 2, take the following values:
1,в€—
s111 = 800 000 hectolitres per year;
1,в€—
s232 = 600 000 hectolitres per year;
1,в€—
s233 = 700 000 hectolitres per year;
2,в€—
s111 = 300 000 hectolitres per year;
2,в€—
s133 = 100 000 hectolitres per year;
2,в€—
s232 = 400 000 hectolitres per year;
2,в€—
s233 = 300 000 hectolitres per year

(for the sake of brevity, the variables that take zero value are not reported).
In order to apply the Benders decomposition method, the following initial solution
is used:
(1)
z1 = 1;
(1)
z2 = 1;
(1)
y11 = 1;
(1)
y22 = 1;
(1)
y23 = 1;
1,(1)
s111 = 800 000 hectolitres per year;
1,(1)
s123 = 400 000 hectolitres per year;
1,(1)
s222 = 600 000 hectolitres per year;
1,(1)
s223 = 300 000 hectolitres per year;
2,(1)
s111 = 300 000 hectolitres per year;
2,(1)
s122 = 200 000 hectolitres per year;
2,(1)
s222 = 200 000 hectolitres per year;
2,(1)
s223 = 500 000 hectolitres per year;

TLFeBOOK
106 DESIGNING THE LOGISTICS NETWORK

corresponding to an initial upper bound:
UB = U (1) = 37.138 million euros per year.
k,(1)
LB is set equal to в€’в€ћ. The solution sij r , i = 1, 2, j = 1, . . . , 4, r = 1, 2, 3, k =
1, 2, corresponds to the following dual solution of the problem of demand allocation,
1,(1)
= 1.34;
Вµ1
Вµ2,(1) = 1.64;
1
1,(1)
ПЂ11 = 4.02;
1,(1)
ПЂ22 = 4.02;
1,(1)
ПЂ23 = 7.37;
2,(1)
ПЂ11 = 4.92;
2,(1)
ПЂ22 = 4.92;
2,(1)
ПЂ23 = 9.02,
which allows us to initialize the set T (1) of constraints of the master problem. The
master problem therefore provides the following optimal solution,
(2)
z3 = 1;
(2)
z4 = 1;
(2)
y32 = 1;
(2)
y41 = 1;
(2)
y43 = 1,
whose objective function value allows us to update LB:
LB = L(2) = 16.757 million euros per year.
The optimal solutions of the demand allocation problem and its dual are
1,(2)
s132 = 600 000 hectolitres per year;
1,(2)
s241 = 800 000 hectolitres per year;
1,(2)
s243 = 700 000 hectolitres per year;
2,(2)
s132 = 400 000 hectolitres per year;
2,(2)
s241 = 300 000 hectolitres per year;
2,(2)
s243 = 200 000 hectolitres per year;

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 107

Table 3.14 Transportation costs (in euros per hectolitre)
k
cij r , i = 1, 2, j = 1, . . . , 4, r = 1, 2, 3, for product k = 1 (Part I) in the K9 problem.

i=1 i=2

r=1 r=2 r=3 r=1 r=2 r=3

1 2.68 4.02 7.37 5.36 6.7 10.05
2 4.02 2.68 6.03 5.36 4.02 7.37
3 6.7 4.02 6.03 5.36 2.68 4.69
4 10.72 8.04 6.03 8.04 5.36 3.35

Table 3.15 Transportation costs (in euros per hectolitre)
k
cij r , i = 1, 2, j = 1, . . . , 4, r = 1, 2, 3, for product k = 2 (Part II) in the K9 problem.

i=1 i=2

r=1 r=2 r=3 r=1 r=2 r=3

1 3.28 4.92 9.02 6.56 8.2 12.3
2 4.92 3.28 7.38 6.56 4.92 9.02
3 8.2 4.92 7.38 6.56 3.28 5.74
4 13.12 9.84 7.38 9.84 6.56 4.1

1,(2) 1,(2)
= 2.68; = 6.03;
Вµ2 ПЂ43
2,(2) 2,(2)
= 3.28; = 4.92;
Вµ2 ПЂ32
1,(2) 2,(2)
= 4.02; = 13.12;
ПЂ32 ПЂ41
1,(2) 2,(2)
ПЂ41 = 10.72; = 7.38.
ПЂ43
Hence, U (2) = 38.984 million euros per year. Since UB < U (2) , the value of UB is
not updated. The procedure continues until a Оµ-optimal solution is generated.

3.5 Logistics Facility Location in the Public Sector
As explained in Chapter 1, relevant logistics issues have to be tackled when planning
a number of public services (п¬Ѓre п¬Ѓghting, transport of the disabled, ambulance dis-
patching, to name a few). In such contexts, it is often of primary importance to ensure
not only a low logistics cost, but also an adequate service level to all users. As a result,

TLFeBOOK
108 DESIGNING THE LOGISTICS NETWORK

speciп¬Ѓc models have to be applied when locating public facilities. For example, in
the p-centre model described below, the service time of the most disadvantaged user
is to be minimized, whereas in the location-covering model one has to determine the
least-cost set of facilities such that each user can be reached within a given maximum
travel time.

p-centre models
3.5.1
In the p-centre model the aim is to locate p facilities on a graph in such a way that the
maximum travel time from a user to the closest facility is minimized. The p-centre
model п¬Ѓnds its application when it is necessary to ensure equity in servicing users
spread on a wide geographical area.
The problem can be modelled on a directed, undirected or mixed graph G(V , A, E),
where V is a set of vertices representing both user sites and road intersections, while
A and E (the set of arcs and edges, respectively) describe the road connections among
the sites. Exactly p facilities have to be located either on a vertex or on an arc or edge.
For p 2, the p-centre model is NP-hard.
If G is a directed graph, there exists an optimal solution of the p-centre problem
such that every facility location is a vertex (vertex location property). If G is undirected
or mixed, the optimal location of a facility could be on an internal point of an edge.
In what follows, a solution methodology is described for the 1-centre problem. The
reader should consult specialized books for a discussion of the other cases. If G is
directed, the 1-centre is simply the vertex associated with the minimum value of the
maximum travel time to all the other vertices. In the case of an undirected or mixed
graph, the 1-centre can correspond to a vertex or an internal edge point. To simplify the
discussion, we will refer only to the case of the undirected graph (A = в€…), although
the procedure can be easily applied in the case of mixed graph. For each (i, j ) в€€ E, let
aij be the traversal time of edge (i, j ). Furthermore, for each pair of vertices i, j в€€ V ,
j
denote by ti the shortest travel time between i and j , corresponding to the sum of the
travel times of the edges of the shortest path between i and j . Note that, on the basis
of the deп¬Ѓnition of travel time, the result is
j
(i, j ) в€€ E.
ti aij ,

Finally, denote by П„h (phk ) the travel time along edge (h, k) в€€ E between vertex
h в€€ V and a point phk of the edge. In this way, the travel time П„h (phk ) along the edge
(h, k) between the vertex k в€€ V and phk results as (see Figure 3.9)

П„k (phk ) = ahk в€’ П„h (phk ).

The 1-centre problem can be solved by the following algorithm proposed by
Hakimi.

Step 1. (Computation of the travel time.) For each edge (h, k) в€€ E and for each
vertex в€€ V , determine the travel time Ti (phk ) from i в€€ V to a point phk of the

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 109

i

tik
tih

П„ h(phk) П„ h(phk)
h k
phk

Figure 3.9 Computation of the travel time Ti (phk ) from an user i в€€ V to a facility in phk .

Ti ( phk)
tik+ ahk
tih+ ahk

tih tik

phk
h k

Figure 3.10 Travel time Ti (phk ) versus the position of point phk along edge (h, k).

edge (h, k) (see Figure 3.10):

Ti (phk ) = min[tih + П„h (phk ), tik + П„k (phk )]. (3.57)

Step 2. (Finding the local centre.) For each edge (h, k) в€€ E, determine the local
в€—
centre phk as the point on (h, k) minimizing the travel time from the most disad-
vantaged vertex,
в€—
phk = arg min max{Ti (phk )},
iв€€V

where maxiв€€V {Ti (phk )} corresponds to the superior envelope of the functions
Ti (phk ), i в€€ V (see Figure 3.11).

TLFeBOOK
110 DESIGNING THE LOGISTICS NETWORK
max{Ti ( phk)}
i в€€V

phk
*
h k
phk

Figure 3.11 Determination of the local centre of edge (h, k) в€€ E.

Villahermosa

3
Infantes 2
Montiel
9 Villanueva
8 4 de la Fuente
Infantes-Montiel
Santa Cruz
crossing
de los Canamos
7

5
Almedina 10
6
Terrinches
1
11
Torre de
Principe

Figure 3.12 Location problem in La Mancha region.

в€—
Step 3. (Determination of the 1-centre.) The 1-centre p в€— is the best local centre phk ,
(h, k) в€€ E, i.e.
pв€— = arg min min max{Ti (phk )} .
iв€€V
(h,k)в€€E

In the La Mancha region of Spain (see Figure 3.12) a consortium of town councils,
located in an underpopulated rural area, decided to locate a parking place for ambu-
lances. A preliminary examination of the problem revealed that the probability of
receiving a request for service during the completion of a previous call was extremely
low because of the small number of the inhabitants of the zone. For this reason the

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 111

Table 3.16 Vertices of La Mancha 1-centre problem.

Vertex Locality

2 Infantes
3 Villahermosa
4 Villanueva de la Fuente
6 Terrinches
7 Santa Cruz de los Canamos
8 Montiel
9 Infantes-Montiel crossing
10 Almedina
11 Puebla del Principe

team responsible for the service decided to use only one vehicle. In the light of this
observation, the problem was modelled as a 1-centre problem on a road network G
where all the connections are two-way streets (see Table 3.16). Travel times were
calculated assuming a vehicle average speed of 90 km/h (see Table 3.17).
j
Travel times ti , i, j в€€ V , are reported in Table 3.18. For each edge (h, k) в€€ E and
for each vertex i в€€ V the travel time Ti (phk ) from vertex i to a point phk of the edge
(h, k) can be deп¬Ѓned through Equation (3.57). This enables the construction, for each
edge (h, k) в€€ E of the function maxiв€€V {Ti (phk )}, whose minimum corresponds to
в€—
the local centre phk . For example, Figure 3.13 depicts the function maxiв€€V {Ti (p23 )},
в€—
and Table 3.19 gives, for each edge (h, k) в€€ E, both the position of phk and the value
в€—
maxiв€€V {Ti (phk )}.
Consequently the 1-centre corresponds to the point pв€— on the edge (8, 10). There-
fore, the optimal positioning of the parking place for the ambulance should be located
on the road between Montiel and Almedina, at 2.25 km from the centre of Montiel.
The villages least advantaged by this location decision are Villanueva de la Fuente
and Torre de Juan Abad, since the ambulance would take an average time of 11.5 min
to reach them.

3.5.2 The location-covering model
In the location-covering model the aim is to locate a least-cost set of facilities in such
a way that each user can be reached within a maximum travel time from the closest
facility. The problem can modelled on a complete graph G(V1 в€ЄV2 , E), where vertices
in V1 and in V2 represent potential facilities and customers, respectively, and each
edge (i, j ) в€€ E = V1 Г— V2 corresponds to a least-cost path between i and j .

TLFeBOOK
112 DESIGNING THE LOGISTICS NETWORK

Table 3.17 Travel time (in minutes) on the road network edges in the La Mancha problem.

(i, j ) aij (i, j ) aij

(1,2) 12 (1,11) 8
(2,3) 9 (2,9) 8
(3,4) 11 (2,10) 9
(4,5) 9 (3,9) 4
(5,6) 2 (4,8) 10
(6,7) 3 (5,8) 6
(7,8) 4 (6,11) 5
(8,9) 1 (7,10) 5
(8,10) 7 (1,10) 6
(10,11) 4

j
Table 3.18 Travel times (in minutes) ti , i, j в€€ V , in the La Mancha problem.

i

j 1 2 3 4 5 6 7 8 9 10 11

1 0 12 18 23 15 13 11 13 14 6 8
2 12 0 9 19 15 16 13 9 8 9 13
3 18 9 0 11 11 12 9 5 4 12 16
4 23 19 11 0 9 11 14 10 11 17 16
5 15 15 11 9 0 2 5 6 7 10 7
6 13 16 12 11 2 0 3 7 8 8 5
7 11 13 9 14 5 3 0 4 5 5 8
8 13 9 5 10 6 7 4 0 1 7 11
9 14 8 4 11 7 8 5 1 0 8 12
10 6 9 12 17 10 8 5 7 8 0 4
11 8 13 16 16 7 5 8 11 12 4 0

Let fi , i в€€ V1 , be the п¬Ѓxed cost of potential facility i; pj , j в€€ V2 , the penalty
incurred if customer j is unserviced; tij , i в€€ V1 , j в€€ V2 , the least-cost travel time
between potential facility i and customer j ; aij , i в€€ V1 , j в€€ V2 , a binary constant
equal to 1 if potential facility i is able to serve customer j , 0 otherwise (given a user-
deп¬Ѓned maximum time T , aij = 1, if tij T , i в€€ V1 , j в€€ V2 , otherwise aij = 0).
The decision variables are binary: yi , i в€€ V1 , is equal to 1 if facility i is opened, 0
otherwise; zj , j в€€ V2 , is equal to 1 if customer j is not served, otherwise it is 0.
The location-covering problem is modelled as follows:
Minimize
fi yi + pj z j (3.58)
j в€€V2
iв€€V1

TLFeBOOK
DESIGNING THE LOGISTICS NETWORK 113
в€—
Table 3.19 Distances of the local centres phk from vertices h (in kilometres) and
в€—
maxiв€€V {Ti (phk )} (in minutes) in the La Mancha problem.

в€— в€— в€— в€—
(h, k) Оіh (phk ) maxiв€€V {Ti (phk )} (h, k) Оіh (phk ) maxiв€€V {Ti (phk )}

(1,2) 18.00 19.0 (1,11) 12.00 16.0
(2,3) 6.00 17.0 (2,9) 12.00 14.0
(3,4) 0.00 18.0 (2,10) 13.50 17.0
(4,5) 13.50 15.0 (3,9) 6.00 14.0
(5,6) 0.00 15.0 (4,8) 15.00 13.0
(6,7) 3.75 13.5 (5,8) 9.00 13.0
(7,8) 2.25 12.5 (6,11) 4.50 15.0
(8,9) 0.00 13.0 (7,10) 0.00 14.0
(8,10) 2.25 11.5 (1,10) 9.00 17.0
(10,11) 6.00 16.0

max{Ti ( p23)}
i в€€V

17

Оі 2 ( p23)
0.75 3.00 3.75 6.00 9.00 9.75 11.25 13.50

Figure 3.13 Time maxiв€€V {Ti (p23 )} versus
position Оі2 (p23 ) of p23 in the La Mancha problem.

subject to

aij yi + zj j в€€ V2 ,
1, (3.59)
iв€€V1
yi в€€ {0, 1}, i в€€ V1 ,
zj в€€ {0, 1}, j в€€ V2 .

The objective function (3.58) is the sum of the п¬Ѓxed costs of the open facilities and
the penalties corresponding to the unserviced customers. Constraints (3.59) impose
that, for each j в€€ V2 , zj is equal to 1 if the facilities opened do not cover customer j
(i.e. if iв€€V1 aij yi = 0).

TLFeBOOK
114 DESIGNING THE LOGISTICS NETWORK

Table 3.20 Distances (in kilometres) between municipalities of
the consortium in Portugal (Part I).