company. By using MAD12 (see Table 2.27), ± = 0.1 comes out to give the most

precise forecast. With this value of the smoothing constant we obtain MAPD12 =

0.79%, which corresponds to a very good accuracy.

2.9.2 Forecast control

A forecasting method works correctly if the errors are random and not systematic.

Typical systematic errors occur when the demand value is constantly underestimated

or overestimated, and a seasonal variation is not taken into account. Forecasting

control can be done through a tracking signal or a control chart. The tracking signal

St , 1 < t T , is de¬ned as the ratio between the cumulative error and the MADt ,

Et

St = ,

MADt

TLFeBOOK

66 FORECASTING LOGISTICS REQUIREMENTS

St

SMAX

Interval of

acceptable

values

0

t

’SMAX

Need of a

corrective

action

Figure 2.18 Use of a tracking signal for a forecasting control.

where

t

Et = ek .

k=2

The tracking signal is greater than zero if the forecast systematically underestimates

the demand; vice versa, a negative value of St indicates a systematic overestimate of

the demand. For this reason, a forecast is assumed to be unbiased if the tracking signal

falls in the range ±Smax . The value of Smax is established heuristically, and usually

varies between 3 and 8. If the tracking signal is outside this interval, the parameters of

the forecasting method should be modi¬ed or a different forecasting method should

be selected (see Figure 2.18).

Unlike tracking signals, control charts are based on the plot of single errors et . Under

the hypothesis that the expected value of the errors is zero, a forecast is effective if each

error ek , k = 2, . . . , t, is in the con¬dence interval ±mσt , where σt is the standard

deviation of the errors. An estimate of σt can be obtained as

σt = MSEt .

The parameter m can be related to the probability that the error be in the interval

±mσt . If the errors are normally distributed with zero mean, the error belongs to

the interval ±2σt with a probability around 97.7%, and to the interval ±3σt with

a probability around 99.8%. Finally, it is worth observing that the interval ±3σt

corresponds approximately to the band ±4 of the tracking signal.

In addition to the previous analytical check, it is useful to verify visually whether the

error pattern reveals the possibility of improving the forecast by introducing suitable

modi¬cations. Here are three of the most common pathological situations.

• The errors have an expected value different from zero; this means that the

forecast is biased (see Figure 2.19).

TLFeBOOK

FORECASTING LOGISTICS REQUIREMENTS 67

et

0

t

Figure 2.19 Nonzero mean error.

• The error pattern shows a positive or negative trend; in this case, the accuracy

of the forecasting method is progressively diminishing.

• The error pattern is periodic; this can happen if an existing seasonal effect has

not been identi¬ed.

By using the tracking signal (±4 band) and the control chart (±3σT ), we can mon-

itor the demand forecast of sports goods for Browns supermarkets. The forecasting

technique is the exponential smoothing method with ± = 0.3. The demand history

for the last few months, and the required forecasts (both in hundreds of dollars), are

reported in Table 2.28. The tracking signal St , t = 2, . . . , T , is always in the inter-

val ±4. On the basis of this preliminary evaluation, we can state that the forecast is

under control. To make a further check, the expected value and the standard deviation

of the error at time period t = T are estimated. The results are ’3.02 and 45.36,

respectively. We observe that, since the average error is much less than the average

demand, we can consider the forecast unbiased. Furthermore, since all errors are in

the interval ±3σT , even this test suggests that the forecast is under control. Finally,

the examination of the control chart (see Figure 2.20) does not show any systematic

error.

2.10 Questions and Problems

2.1 In containerized freight transportation, empty containers have to be periodically

allocated to depots in order to satisfy future customer demands. How would

you forecast the demand for carrier ISO 20 refrigerated containers?

TLFeBOOK

68 FORECASTING LOGISTICS REQUIREMENTS

Table 2.28 Demand entries and forecasts (in hundreds of dollars) in the Browns problem.

2

|et |

t dt pt et Et St et

MADt MSEt

1 975 ” ” ” ” ” ” ” ”

2 995 975.00 20.00 20.00 20.00 20.00 1.00 400.00 ”

’29.00 ’9.00 ’0.37

3 952 981.00 29.00 24.50 841.00 1241.00

4 982 972.30 9.70 9.70 19.57 0.70 0.04 94.09 667.55

’52.21 ’51.51 ’1.86

5 923 975.21 52.21 27.73 2725.88 1353.66

’26.06 ’0.96

6 985 959.55 25.45 25.45 27.27 647.86 1177.21

’65.18 ’91.24 ’2.72

7 902 967.18 65.18 33.59 4248.81 1791.53

’9.63 ’100.87 ’3.34

8 938 947.63 9.63 30.17 92.7 1508.39

’62.61 ’2.01

9 983 944.74 38.26 38.26 31.18 1463.86 1502.03

’61.22 ’123.83 ’3.59

10 895 956.22 61.22 34.52 3747.61 1782.73

’111.68 ’3.46

11 950 937.85 12.15 12.15 32.28 147.56 1601.04

’33.17 ’0.91

12 1020 941.50 78.50 78.50 36.48 6162.77 2057.21

13 ” 965.05 ” ” ” ” ” ” ”

et

100

80

60

40

20

0

-20

-40

-60

-80

t

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

Figure 2.20 Control chart for the demand forecasting of

sports goods in the Browns problem.

2.2 Illustrate a logistics system where there is little need for forecasting.

2.3 To what extent are the forecasting practices different in an MTS and in an MTA

system?

2.4 How would you predict the future demand of a new product?

2.5 Your company is planning to add extra capacity to a plant currently manufactur-

ing 110 000 items per year. You are asked to suggest how much capacity should

be added to the factory. After an accurate sales forecast over the next few years

TLFeBOOK

FORECASTING LOGISTICS REQUIREMENTS 69

Table 2.29 Number of installed heaters by Hot Spot and service requests.

Installed heaters

Less than two More than two Service

Year years ago years ago Total requests

1995 260 000 69 500 329 500 18 672

1996 265 000 74 200 339 200 19 076

1997 287 800 82 850 370 650 20 994

1998 313 750 90 550 404 300 23 249

1999 345 350 97 150 442 500 25 025

2000 379 050 105 950 485 000 28 111

2001 416 950 111 550 528 500 30 985

2002 459 100 117 000 576 100 33 397

2003 502 550 123 200 625 750

you are quite sure that the most likely value of the annual demand is 140 000

items and that the MSE is equal to 108 . You also know that your company

loses $3 for each unit of unused capacity and $7 for each unit of unsatis¬ed

demand. How much capacity should your company buy? (Hint: suppose that

the forecasting error can be assumed to be normally distributed.)

2.6 Hot Spot is a ¬rm based in the USA whose core business is the maintenance

of home heaters. The company usually forecasts service requests on the basis

of the number of installed heaters. Make a forecast of the service requests in

2003 in New Jersey by using data in Table 2.29.

To this purpose use

(a) a single regression analysis (service requests versus total installed heat-

ers);

(b) a multiple regression analysis (service requests versus the number of

heaters installed less than two years ago and at least two years).

Which technique is the most accurate? Why?

2.7 Sunshine Ltd is one of the world™s leading suppliers of fast-moving goods in

household care and personal product categories. According to management, its

facial soap sales depend mainly on the promotion expenditure that the com-

pany and its competitor make. Table 2.30 reports facial soap sales in Canada

versus (a) Sunshine promotion expenditure, and (b) the competitor™s promo-

tion expenditure divided by the Sunshine promotion expenditure. Make a sales

forecast for the next two periods under the hypotheses that Sunshine increases

its promotion expenditure to 14.5 millions of Canadian dollars and the com-

TLFeBOOK

70 FORECASTING LOGISTICS REQUIREMENTS

Table 2.30 Sunshine Ltd facial soap sales (in millions of Canadian dollars) in Canada.

Sunshine Competitor™s promotion

Period promotion expenditure/Sunshine Sales of facial

(trimester, year) expenditure promotion expenditure soaps in Canada

I 2001 6.0 1.2 46.8

II 2001 6.8 1.2 52.7

III 2001 7.5 1.4 60.5

IV 2001 7.5 1.5 56.6

I 2002 9.0 1.5 64.4

II 2002 10.5 1.7 74.1

III 2002 12.0 1.8 72.2

IV 2002 12.0 1.5 78.0

I 2003 13.5 1.4 87.8

II 2003 13.5 1.5 95.6

Table 2.31 Number of light trucks sold by Mitsumishi.

Year

Month 2000 2001 2002 2003

January 22 882 23 478 24 768 24 765

February 19 981 17 019 19 351 21 739

March 18 811 20 967 23 953 25 153

April 19 352 19 759 18 855 20 515

May 27 226 22 200 28 414 24 038

June 14 932 24 162 18 537 26 151

July 18 531 20 275 22 845

August 8 523 7 949 9 451

September 13 064 14 328 15 842

October 13 733 16 691 16 409

November 12 597 13 784 13 881

December 7 645 10 986 11 230

petitor™s promotion expenditure remains the same as in the second trimester of

2003.

2.8 Mitsumishi is a Korean company whose number of light trucks sold between

January 2000 and June 2003 is reported in Table 2.31.

The company usually carries out a promotion in May and/or in June. The sales

improvement achieved during the last few promotions are shown in Table 2.32.

TLFeBOOK

FORECASTING LOGISTICS REQUIREMENTS 71

Table 2.32 Light trucks sales improvement of Mitsumishi.

Period Sales improvement (%)

May 2000 +30

May 2001 +20

June 2001 +15

May 2002 +25

June 2003 +30

Table 2.33 Sales of the new spiced food (in hundreds of kilograms)

produced by Mare Nostrum.

Year

Month 2001 2002 2003

January 130 000 141 988 156 467

February 129 720 142 376 158 137

March 129 703 143 636 159 140

April 129 633 144 543 161 156

May 129 632 147 534 162 835

June 129 854 148 919 165 479

July 130 436 150 961

August 132 751 152 748

September 133 334 152 977

October 133 761 154 387

November 135 286 156 856

December 136 800 157 349

(a) Using a classical decomposition method, forecast the sales for the next

six months.

(b) Plot a control chart of the error over the last three months. Are you able

to detect any anomaly?

2.9 Mare Nostrum, a canned tuna manufacturer based in Sicily (Italy), has marketed

a new spiced food line in June 2002. Now the management wishes to project

sales for improved planning of production and logistics operations. Sales data

for one and a half years are reported in Table 2.33.

(a) Plot the data on a graph. What important observations can you make

about the demand pattern? Which data are relevant and should be used

for forecasting purposes?

TLFeBOOK

72 FORECASTING LOGISTICS REQUIREMENTS

Table 2.34 Demand of refrigerated trucks (in europallets) between

Antwerp and Brussels over the last ten weeks.

Week

Day 1 2 3 4 5 6 7 8 9 10

Monday 67 68 76 75 75 82 77 88 84 84

Tuesday 54 57 59 57 58 69 65 57 72 56

Wednesday 47 49 49 52 57 59 52 54 68 59

Thursday 40 45 46 43 48 49 55 50 59 52

Friday 60 63 68 69 72 69 68 66 63 69

(b) Using the classical time series decomposition analysis, predict the expect-

ed sales over the next six months.

(c) Repeat the forecast by applying the Holt method.

(d) Estimate the MAPD of both methods using the last six months. Which

approach seems to work best?

2.10 The Belgian Trucking Company needs to determine the number of refrigerated

trucks to satisfy the transportation demand between Antwerp and Brussels on a

daily basis. The volume of the demand for the last weeks is given in Table 2.34.

(a) Using the Winters method, predict the expected number of pallets to be

transported for the next week.

(b) Estimate the error in the above forecast using the last three weeks.

(c) Construct a 95% con¬dence interval on the forecasting. (Hint: assume a

normal distribution of demand.)

2.11 Annotated Bibliography

An in-depth treatment of the forecasting methods is reported in:

1. Montgomery DC, Johnson LA and Gradiner JS 1990 Forecasting and Time

Series Analysis. McGraw-Hill, New York.

For a detailed description of the statistical methods, the reader can refer to:

2. Sandy R 1990 Statistics for Business and Economics. McGraw-Hill, NewYork.

The results of the survey reported in Table 2.1 are taken from:

3. Sanders NR and Manrodt KB 1994 Forecasting practices in US corporations:

survey results. Interfaces 24(2), 92“100.

TLFeBOOK

3

Designing the Logistics Network

3.1 Introduction

In business logistics the network planning process consists of designing the system

through which commodities ¬‚ow from suppliers to demand points, while in the public

sector it consists of determining the set of facilities from which users are serviced. In

both cases the main issues are to determine the number, location, equipment and size

of new facilities, as well as the divestment, displacement or downsizing of facilities.

Of course, the objectives and constraints vary depending on the sector (private or pub-

lic) and on the type of facilities (plants, CDCs, RDCs, regional and ¬eld warehouses,

retail outlets, dumpsites, incinerators, ambulance parking places, ¬re stations, etc.).

The aim generally pursued in business logistics is the minimization of the annual

total logistics cost subject to side constraints related to facility capacity and required

customer service level (recall the discussion in Chapter 1). As a rule, the cost to

be minimized is associated with facility operations (manufacturing, storage, sorting,

consolidation, selling, incineration, parking, etc.), and to transportation between facil-

ities, or between facilities and users. Also, when designing the logistics network for

a utility company, different objectives, such as achieving equity in servicing users,

may have to be considered.

Research in logistics network design dates back to the early location theories of

the 19th century. Since then a variety of models and solution methodologies has been

proposed and analysed. In this chapter some of the most important facility location

problems are examined. To put this analysis in the right perspective, a number of

relevant issues are ¬rst introduced and discussed.

When location decisions are needed. Facility location decisions must obviously

be made when a logistics system is started from scratch. They are also required as a

consequence of variations in the demand pattern or spatial distribution, or following

modi¬cations of materials, energy or labour cost. In particular, location decisions are

often made when new products or services are launched, or outdated products are

withdrawn from the market.

Introduction to Logistics Systems Planning and Control G. Ghiani, G. Laporte and R. Musmanno

© 2004 John Wiley & Sons, Ltd ISBN: 0-470-84916-9 (HB) 0-470-84917-7 (PB)

TLFeBOOK

74 DESIGNING THE LOGISTICS NETWORK

Location decisions may be strategic or tactical. Whereas facilities are purchased

or built, location decisions involve sizeable investments. In this case, changing sites or

equipment is unlikely in the short or medium term. This may be true even if facilities

are leased. On the other hand, if space and equipment are rented (e.g. from a public

warehouses) or operations are subcontracted, location decisions can be reversible in

the medium term.

Location and allocation decisions are intertwined. Location decisions are strictly

related to those of de¬ning facility area boundaries (i.e. allocating demand to facili-

ties). For example, in a two-echelon distribution system (see Figure 3.1), opening a

new RDC must be accompanied by a rede¬nition of the sales districts along with a dif-

ferent allocation of the RDCs to the CDCs and of the CDCs to the production plants.

For this reason location problems are sometimes referred to as location“allocation

problems.

Location decisions may affect demand. Facility location may affect the demand

volume. For example, opening a new RDC may lead to the acquisition of customers

who previously could not be served at a satisfactory level of service because they

lived too far away.

3.2 Classi¬cation of Location Problems

Location problems come in a variety of forms, which can be classi¬ed with respect

to a number of criteria. The classi¬cation proposed below is logistics-oriented.

Time horizon. In single-period problems, facility location decisions must be made

at the beginning of the planning horizon on the basis of the forecasted logistics require-

ments. In multi-period problems one has to decide, at the beginning of the planning

horizon, a sequence of changes to be made at given time instants within the planning

horizon.

Facility typology. In single-type location problems, a single type of facility (e.g.

only RDCs) are located. Instead, in multi-type problems several kinds of facility (e.g.

both CDCs and RDCs) are located.

Material ¬‚ows. In single-commodity problems it can be assumed that a single homo-

geneous ¬‚ow of materials exists in the logistics system, while in multicommodity

problems there are several items, each with different characteristics. In the latter case

each commodity is associated with a speci¬c ¬‚ow pattern.

Interaction among facilities. In complex logistics systems there can be material

¬‚ows among facilities of the same kind (e.g. component ¬‚ows among plants). In this

case, optimal facility locations depend not only on the spatial distribution of ¬nished

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 75

Production plants

Supply points RDCs

Figure 3.1 A two-echelon single-type location problem.

product demand but also on the mutual position of the facilities (location problems

with interaction).

Dominant material ¬‚ows. Single-echelon location problems are single-type prob-

lems such that either the material ¬‚ow coming out or the material ¬‚ow entering the

facilities to be located is negligible. In multiple-echelon problems, both inbound and

outbound commodities are relevant. This is the case, for example, when DCs have to

be located taking into account both the transportation cost from plants to DCs and the

transportation cost from DCs to customers. In multiple-echelon problems, constraints

aiming at balancing inbound and outbound ¬‚ows have to be considered.

Demand divisibility. In some distribution systems it is required, for administrative

or book-keeping reasons, that each facility or customer be supplied by a single centre,

while in others a facility or a customer may be served by two or more centres. In the

former case demand is said to be divisible while in the latter it is indivisible.

In¬‚uence of transportation on location decisions. Most location models assume

that transportation cost between two facilities, or between a facility and an user, is

computed as a suitable transportation rate multiplied by the freight volume and the

distance between the two points. Such an approach is appropriate if vehicles travel by

means of a direct route. However, if each vehicle makes collections or deliveries to

several points, then a transportation rate cannot easily be established. In such cases the

routes followed by the vehicles should be taken explicitly into account when locating

the facilities (location-routing models). To illustrate this concept, consider Figure 3.2,

where a warehouse serves three sales districts located at the vertices of triangle ABC.

Under the hypothesis that the facility ¬xed cost is independent of the site, there can

be two extreme cases.

TLFeBOOK

76 DESIGNING THE LOGISTICS NETWORK

A

O

B C

Figure 3.2 The optimal location of a warehouse depends on the way customers are serviced.

• Each customer requires a full-load supply and, therefore, the optimal location

of the DC is equal to the Steiner point O.

• A single vehicle can service all points and hence the facility can be located at

any point of the triangle ABC perimeter.

The interdependence between facility locations and vehicle routes is particularly

strong when dealing with mail distribution, solid waste collection or road mainte-

nance, as the users are located almost continuously on the road network.

Retail location. When planning a store network, the main issue is to optimally

locate a set of retail outlets that compete with other stores for customers. In such a

context, predicting the expected revenues of a new site is dif¬cult since it depends

on a number of factors such as location, sales area and level of competition. Retail

location problems can be modelled as competitive location models, the analysis of

which is also beyond the scope of this textbook. The reader should again consult the

references quoted in the last section of this chapter for further details.

Modelling and solving location problems

In the remainder of this chapter, some selected facility location problems are modelled

and solved as MIP problems. An optimal solution can be determined in principle

by means of a general-purpose or tailored branch-and-bound algorithm. Such an

approach only works for relatively simple problems (such as the single-echelon single-

commodity (SESC) problem) whenever instance size is small. For multiple-echelon

multiple-commodity problems, determining an optimal solution can be prohibitive

even if the number of potential facilities is relatively small (less than 100). As a result,

heuristic procedures capable of determining a ˜good™ feasible solution in a reasonable

amount of time can be very useful. To evaluate whether a heuristic solution provides

a tight upper bound (UB) on the optimal solution value, it is useful to determine a

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 77

lower bound (LB) on the optimal solution value. This yields a ratio (UB ’ LB)/LB

which represents an overestimate of relative deviation of the heuristic solution value

from the optimum.

3.3 Single-Echelon Single-Commodity

Location Models

The SESC location problem is based on the following assumptions:

• the facilities to be located are homogeneous (e.g. they are all regional ware-

houses);

• either the material ¬‚ow coming out or the material ¬‚ow entering such facilities

is negligible;

• all material ¬‚ows are homogeneous and can therefore be considered as a single

commodity;

• transportation cost is linear or piecewise linear and concave;

• facility operating cost is piecewise linear and concave (or, in particular, con-

stant).

The second assumption is the most restrictive. It holds in contexts where locating

production plants whose ¬nished product (e.g. steel) weighs much less than the raw

materials (iron and coal in the example) used in the manufacturing process. Another

application arises in warehouse location for a distribution company (see Figure 3.3),

whereas the goods are purchased at a price inclusive of transportation cost up to the

warehouses. We examine the case where inbound ¬‚ows are negligible, although the

same methodology can be applied without any change to the case where they are

important and outbound ¬‚ows are negligible. Moreover, to simplify the exposition, it

is assumed that the facilities to be located are warehouses and the demand points are

customers.

The problem can be modelled through a bipartite complete directed graph G(V1 ∪

V2 , A), where the vertices in V1 stand for the potential facilities, the vertices in V2

represent the customers, and the arcs in A = V1 — V2 are associated with the material

¬‚ows between the potential facilities and the demand points.

In what follows, we further assume that

• the demand is divisible (see Section 3.2).

Let dj , j ∈ V2 , be the demand of customer j ; qi , i ∈ V1 , the capacity of the potential

facility i; ui , i ∈ V1 , a decision variable that accounts for operations in potential

facility i; sij , i ∈ V1 , j ∈ V2 , a decision variable representing the amount of product

sent from site i to demand point j ; Cij (sij ), i ∈ V1 , j ∈ V2 , the cost of transporting

sij units of product from site i to customer j ; Fi (ui ), i ∈ V1 , the cost for operating

TLFeBOOK

78 DESIGNING THE LOGISTICS NETWORK

RDCs Demand points

Figure 3.3 RDC location.

potential facility i at level ui . Then the problem can be expressed in the following

way.

Minimize

Cij (sij ) + Fi (ui ) (3.1)

i∈V1 j ∈V2 i∈V1

subject to

sij = ui , i ∈ V1 , (3.2)

j ∈V2

sij = dj , j ∈ V2 , (3.3)

i∈V1

i ∈ V1 ,

ui qi , (3.4)

i ∈ V1 , j ∈ V2 ,

sij 0, (3.5)

i ∈ V1 .

ui 0, (3.6)

Variables ui , i ∈ V1 , implicitly de¬ne a location decision since a facility i ∈ V1 is

open if only if ui is strictly positive. Variables sij , i ∈ V1 , j ∈ V2 , determine customer

allocations to facilities. The objective function (3.1) is the sum of the facility operating

costs plus the transportation cost between facilities and users. Constraints (3.2) state

that the sum of the ¬‚ows outgoing a facility equals its activity level. Constraints (3.3)

ensure that each customer demand is satis¬ed, while constraints (3.4) force the activity

level of a facility not to exceed the corresponding capacity.

Model (3.1)“(3.6) is quite general and can be easily adapted to the case where, in

order to have an acceptable service level, some arcs (i, j ) ∈ A having a travel time

larger than a given threshold cannot be used (we remove the corresponding decision

variables sij , for the appropriate i ∈ V1 and j ∈ V2 (see Figure 3.4)). In the remainder

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 79

1 1

...

...

i j

...

...

|V1| |V2|

Figure 3.4 Graph representation of the single-echelon location problem (note that the arcs

(1, j ) and (|V1 |, 1) are absent, given that the corresponding travel times are longer than the

given threshold).

of this section two particular cases of the SESC location problem are examined in

detail. In the ¬rst case, the transportation cost per unit of commodity is constant, and

facility operating costs consist of ¬xed costs. In the second case, transportation costs

are still linear but facilities operating costs are piecewise linear and concave. Both

problems are NP-hard and can be modelled as MIP problems. Hence they can be

solved through general purpose (or tailored) branch-and-bound algorithms.

3.3.1 Linear transportation costs and facility ¬xed costs

If the transportation costs per unit of ¬‚ow are constant, then

Cij (sij ) = cij sij , i ∈ V1 , j ∈ V2 .

Moreover, if facility costs Fi (ui ) are described by a ¬xed cost fi and a constant

marginal cost gi , then

fi + gi ui , if ui > 0,

Fi (ui ) = i ∈ V1 . (3.7)

if ui = 0,

0,

Equation (3.7) leads to the introduction in problem (3.1)“(3.6) of a binary variable

yi replacing ui , for each i ∈ V1 , whose value is equal to 1 if potential facility i is

open, and 0 otherwise. If gi is negligible, then Equation (3.7) is replaced by

Fi (yi ) = fi yi , i ∈ V1 ,

and constraints (3.2) and (3.4) become

i ∈ V1 .

sij qi yi ,

j ∈V2

TLFeBOOK

80 DESIGNING THE LOGISTICS NETWORK

The new set of variables easily allows the imposition of lower and upper bounds on

the number of open facilities. For instance, if exactly p facilities have to be opened,

then

yi = p.

i∈V1

Finally, introducing xij variables, i ∈ V1 , j ∈ V2 , representing the fraction of

demand dj satis¬ed by facility i, we can write

sij = dj xij , i ∈ V1 , j ∈ V2 ,

(3.8)

ui = dj xij , i ∈ V1 .

j ∈V2

The SESC problem can hence be formulated as an MIP problem as follows.

Minimize

cij xij + fi y i (3.9)

i∈V1 j ∈V2 i∈V1

subject to

xij = 1, j ∈ V2 , (3.10)

i∈V1

i ∈ V1 ,

dj xij qi yi , (3.11)

j ∈V2

yi = p, (3.12)

i∈V1

i ∈ V1 , j ∈ V2 ,

xij

0 1, (3.13)

yi ∈ {0, 1}, i ∈ V1 , (3.14)

where

cij = cij dj , i ∈ V1 , j ∈ V2 , (3.15)

is the transportation cost incurred for satisfying the entire demand dj of customer

j ∈ V2 from facility i ∈ V1 . It is worth noting that on the basis of constraints (3.10),

variables xij , i ∈ V1 , j ∈ V2 , cannot take a value larger than 1. Therefore, rela-

0, i ∈ V1 , j ∈ V2 .

tions (3.13) can be written more simply in the form xij

1, i ∈ V1 , j ∈ V2 , are fundamental in a context where the con-

Relations xij

straints (3.10) are relaxed, as in the Lagrangian procedure described below.

The SESC formulation (3.9)“(3.14) is quite general and can sometimes be simpli-

¬ed. In particular, if constraint (3.12) is removed, the model is known as capacitated

plant location (CPL). If relations (3.11) are also deleted, the so-called simple plant

location (SPL) model is obtained. If ¬xed costs fi are the same for each i ∈ V1 ,

dj = 1 for each j ∈ V2 and qi = |V2 | for each i ∈ V1 , then formulation (3.9)“(3.14)

is known as a p-median model.

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 81

Koster Express is an American LTL express carrier operating in Oklahoma (USA).

The carrier service is organized through a distribution subsystem, a group of termi-

nals and a long-haul transportation subsystem. The distribution subsystem uses a set

of trucks, based at the terminals, that pick up the outgoing goods from 1:00 p.m. to

7:00 p.m., and deliver the incoming goods from 9:00 a.m. to 1:00 p.m. The terminals

are equipped areas where the outgoing items are collected and consolidated on pallets,

the incoming pallets are opened up, and their items are classi¬ed and directed to the

distribution. At present the ¬rm has nine terminals (located in Ardmore, Bartlesville,

Duncan, Enid, Lawton, Muskogee, Oklahoma City, Ponca City and Tulsa). The long-

haul transportation subsystem provides the transport, generally during the night, of

the consolidated loads between the origin and destination terminals. For that purpose,

trucks with a capacity between 14 and 18 pallets (and a maximum weight of between

0.8 and 1 ton) are used. During the last six years, the long-haul transportation subsys-

tem has had two hubs in Duncan and Tulsa. The Duncan hub receives the goods from

Ardmore, Lawton, Oklahoma City and Duncan itself, while the Tulsa hub collects

the items coming from the other terminals. In each hub the goods assigned to the

terminals of the other hub are sent on large trucks, generally equipped with trailers.

For example, goods coming from Enid and destined to Oklahoma City are brought to

the Tulsa hub, from where they are sent to the Duncan hub together with the goods

coming from Bartlesville, Muskogee, Ponca City and Tulsa itself and directed to the

terminals served by the Duncan hub; ¬nally, they are sent to Oklahoma City. Goods

destined to other terminals of the same hub are stocked for a few hours until the trucks

coming from the other hub arrive, and only then are they sent to their destinations.

For example, goods to Lawton coming from Ardmore are sent to the Duncan hub,

stocked until the arrival of the trucks from the Tulsa hub and then, sent to Lawton,

together with the goods coming from all the other terminals.

Recently, the ¬rm was offered a major growth opportunity with the opening of new

terminals in Altus, Edmond and Stillwater. At the same time the management decided

to relocate its two hubs. The team hired to carry out a preliminary analysis decided

to consider only the transportation cost from each terminal to the hub and vice versa

(neglecting, therefore, both the transportation cost between the two hubs and the cost,

yet considerable, associated with the possible divestment of the pre-existing hub).

Under the hypothesis that each terminal can accommodate a hub, the problem can be

formulated a p-median problem in the following way.

Minimize

cij xij

i∈V1 j ∈V2

subject to

xij = 1, j ∈ V2 ,

i∈V1

TLFeBOOK

82 DESIGNING THE LOGISTICS NETWORK

Table 3.1 Distances (in miles) between terminals in the Koster Express problem (Part I).

Altus Ardmore Bartlesville Duncan Edmond Enid

Altus 0.0 169.8 291.8 88.2 153.9 208.2

Ardmore 169.8 0.0 248.6 75.9 112.5 199.0

Bartlesville 291.8 248.6 0.0 231.5 146.0 132.4

Duncan 88.2 75.9 231.5 0.0 93.5 137.5

Edmond 153.9 112.5 146.0 93.5 0.0 88.8

Enid 208.2 199.0 132.4 137.5 88.8 0.0

Lawton 54.2 115.8 238.7 34.1 100.7 145.0

Muskogee 274.2 230.4 92.2 213.5 145.7 166.4

Oklahoma City 141.1 100.5 151.4 80.9 14.4 87.6

Ponca City 245.0 202.2 70.2 184.8 91.9 64.5

Stillwater 209.2 162.6 115.0 145.3 53.0 65.8

Tulsa 248.0 204.6 45.6 187.8 102.2 118.4

|V2 |yi , i ∈ V1 ,

xij

j ∈V2

yi = 2,

i∈V1

xij ∈ {0, 1}, i ∈ V1 , j ∈ V2 ,

yi ∈ {0, 1}, i ∈ V1 ,

where V1 = V2 represent the set of old and new terminals; yi , i ∈ V1 , is a binary

decision variable whose value is equal to 1 if terminal i accommodates a hub, 0

otherwise; xij , i ∈ V1 , j ∈ V2 , is a binary decision variable whose value is equal

to 1 if the hub located in terminal i serves terminal j , 0 otherwise; however, due to

the particular structure of the problem constraints, variables xij cannot be fractional

and greater than 1, therefore xij ∈ {0, 1}, i ∈ V1 , j ∈ V2 can be replaced with

xij 0, i ∈ V1 , j ∈ V2 .

Since the goods incoming and outgoing every day from each terminal can be

transferred by a single truck with a capacity of 14 pallets, the daily transport cost (in

dollars) between a pair of terminals i ∈ V1 and j ∈ V2 is given by cij = 2—0.74—lij ,

where 0.74 is the transportation cost (in dollars per mile), and lij is the distance (in

miles) between the terminals (see Tables 3.1 and 3.2).

The optimal solution leads to the opening of two hubs located in Duncan and

Stillwater (the daily total cost being $1081.73). Terminals in Altus, Ardmore, Duncan

and Lawton are assigned to the Duncan hub, while the Stillwater hub serves the

terminals in Bartlesville, Edmond, Enid, Muskogee, Oklahoma City, Ponca City,

Stillwater and Tulsa.

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 83

Table 3.2 Distances (in miles) between terminals in the Koster Express problem (Part II).

Lawton Muskogee Oklahoma City Ponca City Stillwater Tulsa

Altus 54.2 274.2 141.1 245.0 209.2 248.0

Ardmore 115.8 230.4 100.5 202.2 162.6 204.6

Bartlesville 238.7 92.2 151.4 70.2 115.0 45.6

Duncan 34.1 213.5 80.9 184.8 145.3 187.8

Edmond 100.7 145.7 14.4 91.9 53.0 102.2

Enid 145.0 166.4 87.6 64.5 65.8 118.4

Lawton 0.0 220.6 88.0 191.9 152.5 194.9

Muskogee 220.6 0.0 140.4 142.5 119.2 48.1

Oklahoma City 88.0 140.4 0.0 104.7 66.6 107.6

Ponca City 191.9 142.5 104.7 0.0 41.9 96.5

Stillwater 152.5 119.2 66.6 41.9 0.0 71.2

Tulsa 194.9 48.1 107.6 96.5 71.2 0.0

Demand allocation

¯ ¯

For a given set V1 ⊆ V1 of open facilities, an optimal demand allocation to V1 can be

determined by means of the following LP model.

Minimize

cij xij (3.16)

¯

i∈V1 j ∈V2

subject to

xij = 1, (3.17)

¯

i∈V1

¯

i ∈ V1 ,

dj xij qi , (3.18)

j ∈V2

¯

i ∈ V1 , j ∈ V2 .

xij 0, (3.19)

—

In an optimal solution of problem (3.16)“(3.19), some xij values may be fractional

(i.e. the demand of a vertex j ∈ V2 can be satis¬ed by more than one vertex i ∈ V1 )

because of capacity constraints (3.18). However, in the absence of a capacity constraint

(as in the SPL and p-median models), there exists at least one optimal solution such

that the demand of each vertex j ∈ V2 is satis¬ed by a single facility i ∈ V1 (single

¯

assignment property). This solution can be de¬ned as follows. Let ij ∈ V1 be a facility

such that

ij = arg min cij .

¯

i∈V1

Then, the allocation variables can be de¬ned as follows:

if i = ij ,

1,

—

xij =

0, otherwise.

TLFeBOOK

84 DESIGNING THE LOGISTICS NETWORK

A Lagrangian heuristic for the capacitated plant location problem

Several heuristic methods have been developed for the solution of SESC problem

(3.9)“(3.14). Among them, Lagrangian relaxation techniques play a major role. They

usually provide high-quality upper and lower bounds within a few iterations. For

the sake of simplicity, in the remainder of this section, a Lagrangian procedure is

illustrated for the CPL problem, although this approach may be used for the general

SESC model (3.9)“(3.14). The fundamental step of the heuristic is the determination

of a lower bound, obtained by relaxing demand satisfaction constraints (3.10) in a

Lagrangian fashion. Let »j ∈ be the multiplier associated with the j th constraint

(3.10). Then the relaxed problem is:

Minimize

cij xij + fi yi + xij ’ 1

»j (3.20)

i∈V1 j ∈V2 j ∈V2

i∈V1 i∈V1

subject to

i ∈ V1 ,

dj xij q i yi , (3.21)

j ∈V2

i ∈ V1 , j ∈ V2 ,

xij

0 1, (3.22)

y1 ∈ {0, 1}, i ∈ V1 . (3.23)

It is easy to check that problem (3.20)“(3.23) can be decomposed into |V1 | sub-

problems. Indeed, for a given vector » ∈ |V2 | of multipliers, the optimal objective

value of problem (3.20)“(3.23), LBCPL (»), can be determined by solving, for each

potential facility i ∈ V1 , the following subproblem:

Minimize

(cij + »j )xij + fi yi (3.24)

j ∈V2

subject to

dj xij qi yi , (3.25)

j ∈V2

j ∈ V2 ,

xij

0 1, (3.26)

yi ∈ {0, 1}, (3.27)

and then by setting

LBi (») ’

LBCPL (») = »j ,

CPL

j ∈V2

i∈V1

where LBi (») is the optimal objective function value of subproblem (3.24)“(3.27).

CPL

LBi (») can be easily determined by inspection, by observing that

CPL

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 85

• for yi = 0, Equation (3.25) implies xij = 0, for each j ∈ V2 , and therefore

LBi (») = 0;

CPL

• for yi = 1, subproblem (3.24)“(3.27) is a continuous knapsack problem (with

an objective function to be minimized); it is well known that this problem can

be solved in polynomial time by means of a ˜greedy™ procedure.

By suitably modifying the optimal solution of the Lagrangian relaxation, it is pos-

sible to construct a CPL feasible solution as follows.

Step 1. (Finding the facilities to be activated.) Let L be the list of potential facilities

i ∈ V1 sorted by nondecreasing values of LBi (»), i ∈ V1 (note that LBi (»)

CPL CPL

|V2 | ). Extract from L the minimum number of facilities capable

0, i ∈ V1 , » ∈

¯

to satisfy the total demand j ∈V2 dj . Let V1 be the set of facilities selected. Then

¯

V1 satis¬es the relation:

qi dj .

¯ j ∈V2

i∈V1

Step 2. (Customer allocation to the selected facilities.) Solve the demand allocation

¯

problem (3.16)“(3.19) considering V1 as the set of facilities to be opened. Let

UBCPL (») be the cost (3.24) associated with the optimal allocation.

The heuristic ¬rst selects the facilities characterized by the smallest LBi (»)

CPL

values and then optimally allocates the demand to them.

Thus for each set of multipliers » ∈ |V2 | , the above procedure computes both

a lower and upper bound (LBCPL (») and UBCPL (»), respectively). If these bounds

coincide, an optimal solution has been found. Otherwise, in order to determine the

multipliers corresponding to the maximum possible lower bound LBCPL (») (or at

least a satisfactory bound), the classical subgradient algorithm can be used. This

method also generates, in many cases, better upper bounds, since the feasible solutions

generated from improved lower bounds are generally less costly. Here is a schematic

description of the subgradient algorithm.

0. Set LB = ’∞, UB =

Step 0. (Initialization.) Select a tolerance value µ

∞, k = 1 and »k = 0, j ∈ V2 .

j

Step 1. (Computation of a new lower bound.) Solve the Lagrangian relaxation (3.20)“

(3.23) using »k ∈ |V2 | as a vector of multipliers. If LBCPL (»k ) > LB, set LB =

LBCPL (»k ).

Step 2. (Computation of a new upper bound.) Determine the corresponding feasible

solution. Let UBCPL (»k ) be its cost. If UBCPL (»k ) < UB, set UB = UBCPL (»k ).

Step 3. (Check of the stopping criterion.) If (UB ’ LB)/LB µ, STOP. LB and UB

—

represent the best upper and lower bound available for zCPL , respectively.

TLFeBOOK

86 DESIGNING THE LOGISTICS NETWORK

Table 3.3 Distances (in kilometres) between potential production plants

and markets in the Goutte problem.

Brossard Granby Sainte-Julie Sherbrooke Valley¬eld Verdun

Brossard 0.0 76.1 30.4 139.4 72.6 11.7

Granby 76.1 0.0 71.0 77.2 144.5 83.7

LaSalle 20.8 92.9 47.2 156.1 47.5 11.7

Mascouche 54.7 113.3 52.9 187.2 93.0 45.2

Montr´ al

e 13.5 85.5 28.0 148.7 67.3 9.3

Sainte-Julie 30.4 71.0 0.0 138.2 94.5 38.1

Sherbrooke 139.4 77.2 138.2 0.0 207.9 146.9

Terrebonne 47.8 106.5 46.2 180.2 86.7 38.9

Valley¬eld 72.6 144.5 94.5 207.9 0.0 63.4

Verdun 11.7 83.7 38.1 146.9 63.4 0.0

Step 4. (Updating of the Lagrangian multipliers.) Determine the subgradient of the

j th relaxed constraint,

k k

sj = xij ’ 1, j ∈ V2 ,

i∈V1

|V2 |

where xij is the solution of the Lagrangian relaxation (3.20)“(3.23) using »k ∈

k

as Lagrangian multipliers. Then set

»k+1 = »k + β k sj ,

k

j ∈ V2 , (3.28)

j

j

where β k is a suitable scalar coef¬cient. Let k = k + 1 and go back to Step 1.

This algorithm attempts to determine an µ-optimal solution, i.e. a feasible solution

with a maximum user-de¬ned deviation µ from the optimal solution.

Computational experiments have shown that the initial values of the Lagrangian

multipliers do not signi¬cantly affect the behaviour of the procedure. Hence multi-

pliers are set equal to 0 in Step 0. Formula (3.28) can be explained in the following

way. If, at the kth iteration, the left-hand side of constraint (3.10) is higher than the

right-hand side ( i∈V1 xij > 1) for a certain j ∈ V2 , the subgradient sj is positive

k k

and the corresponding Lagrangian multiplier has to be increased in order to heavily

penalize the constraint violation. Vice versa, if the left-hand side of constraint (3.10)

is lower than the right-hand side ( i∈V1 xij < 1) for a certain j ∈ V2 , the associated

k

k

subgradient sj is negative and the value of the associated multiplier must be decreased

to make the service of the unsatis¬ed demand fraction 1 ’ i∈V1 xij more attractive.

k

Finally, if the j th constraint (3.10) is satis¬ed ( i∈V1 xij = 1), the corresponding

k

multiplier is unchanged.

The term β k in Equation (3.28) is a proportionality coef¬cient de¬ned as

±(UB ’ LBCPL (»k ))

k

β= ,

|V2 | k 2

j =1 (sj )

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 87

Table 3.4 Plant operating costs (in Canadian dollars per year) and capacity

(in hectolitres per year) in the Goutte problem.

Site Fixed cost Capacity

Brossard 81 400 22 000

Granby 83 800 24 000

LaSalle 88 600 28 000

Mascouche 91 000 30 000

Montr´ al

e 79 000 20 000

Sainte-Julie 86 200 26 000

Sherbrooke 88 600 28 000

Terrebonne 91 000 30 000

Valley¬eld 79 000 20 000

Verdun 80 200 21 000

Table 3.5 Demands (in hectolitres per year) of the sales districts in the Goutte problem.

Site Demand

Brossard 14 000

Granby 10 000

Sainte-Julie 8 000

Sherbrooke 12 000

Valley¬eld 10 000

Verdun 9 000

where ± is a scalar arbitrarily chosen in the interval (0, 2]. The use of parameter

β k in Equation (3.28) limits the variations of the multipliers when the lower bound

LBCPL (»k ) approaches the current upper bound UB.

Finally, note that the {LBCPL (»k )} sequence produced by the subgradient method

does not decrease monotonically. Therefore, there could exist iterations k for which

LBCPL (»k ) < LBCPL (»k’1 ) (this explains the lower bound update in Step 1). In

practice, LBCPL (»k ) values exhibit a zigzagging pattern.

The procedure is particularly ef¬cient. Indeed, it generally requires, for µ ≈ 0.01,

only a few thousand iterations for problems with hundreds of vertices in V1 and in V2 .

Goutte is a Canadian company manufacturing and distributing soft drinks. The

¬rm has recently achieved an unexpected increase of its sales mostly because of the

launch of a new beverage which has become very popular with young consumers.

The management is now considering the opportunity of opening a new plant to which

some of the production of the other factories could be moved.

TLFeBOOK

88 DESIGNING THE LOGISTICS NETWORK

The production process makes use of water, available anywhere in Canada in an

unlimited quantity at a negligible cost, and of sugar extracts which compose a modest

percentage of the total weight of the ¬nished product. For this reason, supply costs

are negligible compared to ¬nished product distribution costs, and the transportation

costs are product independent. Table 3.3 provides the distances between potential

plants and markets.

The management has decided to undertake a preliminary analysis in order to eval-

uate the theoretical minimum cost plant con¬guration for different service levels. In

this study, the logistics system is assumed to be designed from scratch.

The annual operating costs and capacities of the potential plants are shown in

Table 3.4, while the annual demands of the sales districts are reported in Table 3.5.

The maximum distance between a potential plant and a market is successively

set equal to ∞ and 70 km. The trucks have a capacity of 150 hectolitres and a cost

(inclusive of the crew™s wages) of 0.92 Canadian dollars per kilometre.

The Goutte problem is then modelled as a CPL formulation:

Minimize

cij 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 = {Brossard, Granby, LaSalle, Mascouche, Montr´ al, Sainte-Julie, Sher-

e

brooke, Terrebonne, Valley¬eld, Verdun} and V2 = {Brossard, Granby, Sainte-Julie,

Sherbrooke, Valley¬eld, Verdun}; xij , i ∈ V1 , j ∈ V2 , is a decision variable repre-

senting the fraction of the annual demand of market j satis¬ed by plant i; yi , i ∈ V1 ,

is a binary decision variable, whose value is equal to 1 if the potential plant i is

open, 0 otherwise. Transportation costs cij , i ∈ V1 , j ∈ V2 (see Table 3.6), are

calculated through Equations (3.15), observing that trucks always travel with a full

load on the outward journey and empty on the return journey. For example, since

the distance between the potential plant located in Granby and the sales district of

Brossard is 76.1 km, the transportation cost is 2 — 76.1 — 0.92 = 140.06 Cana-

dian dollars for transporting 150 hectolitres. Since the demand of the sales district

of Brossard is 14 000 hectolitres per year, the annual transportation cost for satisfy-

ing the entire demand of the Brossard market from the potential plant of Granby is

(14 000/150) — 140.06 = 13 072.32 Canadian dollars.

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 89

If the maximum distance between a plant and a market is set equal to in¬nity, the

optimal solution leads to the opening of three production plants (located in Brossard,

—

Granby and Valley¬eld) and the optimal xij values, i ∈ V1 , j ∈ V2 , are reported in

Table 3.7.

The annual total logistics cost equals to 265 283.12 Canadian dollars. The optimal

solution can be found by using the Lagrangian heuristic (with ± = 1.5). The results

of the ¬rst two iterations can be summarized as follows:

»1 = 0, j = 1, . . . , 6;

j

LBCPL (»1 ) = 0;

LB = 0;

y 1 = [1, 0, 0, 0, 1, 0, 0, 0, 0, 1]T ,

corresponding to the plants located in Brossard, Montr´ al and Verdun. This choice

e

guarantees the minimum number of open plants capable of satisfying the whole

demand (63 000 hectolitres per year) of the market at the lowest cost:

UBCPL (»1 ) = 282 537.24;

UB = 282 537.24;

sj = ’1, j = 1, . . . , 6;

1

β 1 = 70 634.31;

»2 = ’70 634.31, j = 1, . . . , 6;

j

LBCPL (»2 ) = ’529 969.24;

LB = 0;

y 2 = [1, 0, 0, 0, 1, 0, 0, 0, 1, 1]T ;

UBCPL (»2 ) = 353 542.24;

UB = 282 537.24;

s 2 = [’1.00, 2.60, 9.00, ’0.92, 3.50, 8.67]T ;

β 2 = 6887.15.

If the maximum distance between a potential plant and a market is 70 km, the

optimal solution leads to the opening of four plants (located in Brossard, Granby,

Sherbrooke and Valley¬eld). The demand allocation is reported in Table 3.8.

The annual total logistics cost would be 342 784.87 Canadian dollars, with an

increase of 77 501.75 Canadian dollars compared with the ¬rst solution found.

TLFeBOOK

90 DESIGNING THE LOGISTICS NETWORK

Table 3.6 Transportation costs (in Canadian dollars per year) cij , i ∈ V1 , j ∈ V2 ,

in the Goutte problem.

Brossard Granby Sainte-Julie Sherbrooke Valley¬eld Verdun

Brossard 0.00 9 337.37 2 984.80 20 514.58 8 903.08 1 296.97

Granby 13 072.32 0.00 6 964.54 11 370.67 17 727.19 9 238.67

LaSalle 3 565.18 11 390.41 4 627.23 22 978.23 5 823.52 1 296.97

Mascouche 9 396.60 13 897.49 5 195.76 27 550.19 11 410.15 4 992.43

Montr´ al

e 2 321.51 10 482.34 2 747.91 21 888.54 8 251.63 1 030.47

Sainte-Julie 5 223.40 8 705.67 0.00 20 348.76 11 587.82 4 210.70

Sherbrooke 23 933.68 9 475.56 13 565.84 0.00 25 505.04 16 220.97

Terrebonne 8 208.20 13 068.37 4 532.48 26 531.56 10 640.26 4 299.53

Valley¬eld 12 464.31 17 727.19 9 270.25 30 606.05 0.00 7 000.07

Verdun 2 017.50 10 265.19 3 742.85 21 627.96 7 777.85 0.00

Table 3.7 Fraction of the annual demand of the sales district j ∈ V2 satis¬ed by

the production plant i ∈ V1 (no limit on the distance) in the Goutte problem.

Brossard Granby Sainte-Julie Sherbrooke Valley¬eld Verdun

Brossard 1.00 0.00 0.75 0.00 0.00 0.22

Granby 0.00 1.00 0.25 1.00 0.00 0.00

LaSalle 0.00 0.00 0.00 0.00 0.00 0.00

Mascouche 0.00 0.00 0.00 0.00 0.00 0.00

Montr´ al

e 0.00 0.00 0.00 0.00 0.00 0.00

Sainte-Julie 0.00 0.00 0.00 0.00 0.00 0.00

Sherbrooke 0.00 0.00 0.00 0.00 0.00 0.00

Terrebonne 0.00 0.00 0.00 0.00 0.00 0.00

Valley¬eld 0.00 0.00 0.00 0.00 1.00 0.78

Verdun 0.00 0.00 0.00 0.00 0.00 0.00

3.3.2 Linear transportation costs and concave piecewise linear

facility operating costs

In this subsection we show how an SESC location problem with piecewise linear and

concave facility operating costs can still be modelled as an MIP model. Indeed, such a

problem can be transformed into model (3.9)“(3.14) by introducing dummy potential

facilities and suitably de¬ning costs and capacities. For the sake of simplicity, the

topic will be illustrated in three steps.

Case A. The operating cost Fi (ui ) of a facility i ∈ V1 is given by Equation (3.7) (see

TLFeBOOK

DESIGNING THE LOGISTICS NETWORK 91

Table 3.8 Fraction of the annual demand of the sales district i ∈ V2 satis¬ed by the

production plant i ∈ V1 (maximum distance of 70 km) in the Goutte problem.

Brossard Granby Sainte-Julie Sherbrooke Valley¬eld Verdun

Brossard 1.00 0.00 1.00 0.00 0.00 0.00

Granby 0.00 1.00 0.00 0.00 0.00 0.00

LaSalle 0.00 0.00 0.00 0.00 0.00 0.00

Mascouche 0.00 0.00 0.00 0.00 0.00 0.00

Montr´ al

e 0.00 0.00 0.00 0.00 0.00 0.00

Sainte-Julie 0.00 0.00 0.00 0.00 0.00 0.00

Sherbrooke 0.00 0.00 0.00 1.00 0.00 0.00

Terrebonne 0.00 0.00 0.00 0.00 0.00 0.00

Valley¬eld 0.00 0.00 0.00 0.00 1.00 1.00

Verdun 0.00 0.00 0.00 0.00 0.00 0.00

Figure 3.5):

fi + gi ui , if ui > 0,

Fi (ui ) = i ∈ V1 ,

if ui = 0,

0,

where, using Equation (3.8), ui = dj xij .

j ∈V2

Hence, this problem can be transformed into model (3.9)“(3.14) by rewriting the

objective function (3.9) as