-I-

Table of contents

1.  The dynamic location problem  1

1.1.  Capacity expansion  1

1.2.  Modernisation  2

2.  Fields of application  2

3.  The basic dynamic location problem formulation  3

3.1.  Solution techniques  4

4.  The dynamic capacitated plant location problem  5

4.1.  Mathematical formulation of the DCPLP  5

4.2.  Linear programming formulation of the DCPLP  7

4.3.  Lagrangian formulation of the DCPLP  7

4.4.  The dynamic algorithm for solving the subproblem  8

4.5.  Subgradient optimisation procedure  10

4.6.  Heuristic for converting the solution into a feasible solution  11

5.  Conclusion  12

Appendix 14   

  References  II

-1- 1.The dynamic location problem

Dynamic location problems were first formulated in the 1960`s. The idea was to enlarge the location planning problem by including time in the problem formulation. Pioneering work was done by A.S. Manne, who developed the SLOT heuristic procedure, an approach to solve

the problem under the assumption of linearly growing market demands ¹ . There are different reasons to enlarge a static location problem into a dynamic problem by introducing several time periods.

1.1. Capacity expansion

The first and most important reason is, that a dynamic model allows regarding changes in demand over a finite or an infinite time horizon. In most cases a fast growing industry, with an increasing demand, is the subject of the dynamic model. Especially the expanding telecommunication industry in the early 1990`s has to be mentioned in this context. Dynamic location problems made it also possible to solve location problems with a decreasing demand in some time periods or with an exchange in demand between the demand locations. Decreasing demand often leads to capacity reduction; existing facilities have to be shut down. The closing of facilities could lead to the recovering of salvage value or, in other

cases, to closing penalties ² . The amount of the salvage value (or closing costs) compared with the set-up costs (or reopening costs) has a strong effect on tending to change locations over the time horizon.

To obtain a realistic solution some models allow to establish capacity constraints for each production location. This is done to prevent solutions, with technically impossible facility sizes.

The objective of a dynamic location problem could be to satisfy every known demand with minimum costs, especially transportation costs. This is often the case, if the focused branch of industry is one of the (public) utilities, such as power-supply or water supply and distribution industries. Another objective might be profit maximisation; which can be achieved by

¹ See Fong, C.O./Srinivasan, V., SLOT heuristic (Management Science 1986) pp. 1140.

² See Canel, C./Khumawala, B.M. a.o., Closing cost (Computers & Operations Research 2001) pp. 413-414.

-2-pre-selecting demands or under the assumption, that the demand is influenced by pricing

decisions. 3

1.2. Modernisation

The second reason for using dynamic location approaches is the modernisation problem. The faced problem in these cases is to modernise an existing network of facilities. Budget constraints made it necessary to concentrate modernisation on the most profitable facility locations and use the resulting revenues to continue the modernisation process in the next time periods. A real-life example for modernisation is the switching from analog to digital

technology in the transition network for telecommunication lines ⁴ . It is possible to combine the modernisation an the capacity expansion problem.

2. Fields of application

Applications of dynamic location problems can be divided into the following main groups.

The first group is the network application ⁵ , including communication, electric power, gas distribution and other networks. The subject in this group is to find a good expansion plan over the given time horizon, often with special interest on routing decisions. The reason is, that in these networks the transportation costs are the most important variable costs.

Heavy process industries ⁶ are the oldest field of application for dynamic problems. Aluminium, caustic soda, cement, and nitrogenous fertiliser industries were examined first, but of course every related industry with relatively high transportation costs belongs to this group, too.

Another group can be named public services ⁷ applications, including the placement of schools, hospitals and other public services. The decision is often determinated by social, environmental or political constraints.

³ See Erlenkotter, D., Price-sensitive demands (Management Science 1977) pp. 378.

⁴ See Girard, A./Gu, X.D./Mason, L.G., Modernisation (Operations Research 1990) pp. 415

⁵ See Luss, H., Network application (Operations Research 1982) pp. 936-938.

⁶ See Luss, H., Heavy process industrie (Operations Research 1982) pp. 938-939.

⁷ See Luss, H., Public services (Operations Research 1982) pp. 938.

-3-A new field of application is the so-called dynamic two-echelon plant location problem. These problems deal with relocation and phase-out in a combined manufacturing plant and

warehouse facility case ⁸ or the expansion of the two stages in a multicommodity case ⁹ . In contrary to the other groups, the new subjects here are the different distribution stages.

3.The basic dynamic location problem formulation

This section describes a basic dynamic location problem without specific assumptions. The subjects are caused by general assumptions, appearing in nearly every dynamic formulation.

The basic dynamic location problem ¹⁰ could be described as:

= min( Z

I

subject to

∑

1 i

∑

≥ t t 0 Y for all i, j, t (4) X ;

i ij where

T = the number of periods in the planning horizon; I = the index set of facility locations; J = the index set of demand locations in the network; t C = the transportation cost of serving a unit of demand at node (market) j

ij

by a facility in location i in period t; t D = the demand generated by node (market) j in period t;

j t F = the set-up cost per unit of capacity in location i in period t.

i

The decision variables in this problem are:

⁸ See Melachrinoudis, E./Min, H., Two-echelon plant problem (European Journal of Operational Research 2000)

pp. 1

⁹ See Fernandez, F.R./Hinojosa, Y./Puerto, J., Multicommodity (European Journal of Operational Research

2000) pp. 271-272.

¹⁰ In approach to Erlenkotter, D., Problem formulation (1981) pp. 133 and Shulman, A., Problem formulation

(1991) pp. 425-426.