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

Albaladejo

5

Almedina 10

6

Terrinches

1

11

Torre de

Juan Abad Puebla del

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

1 Torre de Juan Abad

2 Infantes

3 Villahermosa

4 Villanueva de la Fuente

5 Albaladejo

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).

Almada Azenha Carregosa Corroios Lavradio

Almada 0.0 24.4 33.2 4.7 29.9

Azenha 24.4 0.0 13.2 18.2 14.8

Carregosa 33.2 13.2 0.0 27.1 11.1

Corroios 4.7 18.2 27.1 0.0 23.8

Lavradio 29.9 14.8 11.1 23.8 0.0

Macau 39.0 15.4 13.9 32.9 16.1

Moita 29.5 9.5 5.1 23.4 7.4

Montijo 38.8 18.7 7.2 32.7 16.6

Palmela 34.3 24.0 16.4 28.2 26.2