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. Main subject of this article is an mathematical approach to solve a capacitated dynamic location problem over a given (limited) number of periods. There are no restrictions to demand development over the periods. (That means there is no linear growth in demand needed like in older approaches).
Table of contents
1. The dynamic location problem
1.1. Capacity expansion
1.2. Modernisation
2. Fields of application
3. The basic dynamic location problem formulation
3.1. Solution techniques
4. The dynamic capacitated plant location problem
4.1. Mathematical formulation of the DCPLP
4.2. Linear programming formulation of the DCPLP
4.3. Lagrangian formulation of the DCPLP
4.4. The dynamic algorithm for solving the subproblem
4.5. Subgradient optimisation procedure
4.6. Heuristic for converting the solution into a feasible solution
5. Conclusion
Appendix
References
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[1].
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[2]. 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 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[4].
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[5], 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[6] 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[7] applications, including the placement of schools, hospitals and other public services. The decision is often determinated by social, environmental or political constraints.
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[8] or the expansion of the two stages in a multicommodity case[9]. 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[10] could be described as:
illustration not visible in this excerpt
subject to
illustration not visible in this excerpt
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;
illustration not visible in this excerpt
by a facility in location i in period t;
illustration not visible in this excerpt
The first term in objective function Abbildung in dieser Leseprobe nicht enthalten describes the transportation costs of delivering demands to the markets and the second term is the set-up cost, depending on the amount of the installed capacity. Constraints (2) require the demand at each market to be served. The meaning of constraints (3) is to show, that the total demand should not exceed the total available capacity in this period. One should see, that the total available capacity is the capacity installed in t and all the former periods. Constraints (4) should prevent, that the minimisation leads to an economically impossible solution.
3.1. Solution techniques
The solution of a dynamic location problem, like the one shown in section 3, can be obtained by different solution techniques.
The linear programming relaxation ignores the integer constraints, but maintains all other constraints.[11] In the basic formulation ((1)-(4)), this seems to be no argument for not using this technique, but in realistic problems. For example, facility installation decisions require integer decision variables, because it is impossible to install only a fraction of a facility. Nevertheless, in practice linear programming relaxation often gives solutions extremely close to the optimal integer solution, but it is not known how general this is. The violation by rounding the solution is relative small and even if the rounded solution is infeasible in the mathematical sense, it is acceptable for practical purposes.[12]
An other very important reason for not using the linear programming relaxation is, that the computation time growths rapid with an increasing number of decision variables. A comparison between the linear programming and the Lagrangian relaxation shows that for a five-location modernisation problem the linear programming relaxation requires even more computation time for the three periods case, than the Lagrangian relaxation requires for the eleven time periods case.[13]
The Lagrangian relaxation is used in nearly every dynamic location problem. The reason is, that complicating constraints of an underlying problem can be incorporated into the objective function. The resulting Lagrangian problem is easier to solve, than the underlying problem.[14] This problem can also be separated into subproblems with less decision variables. Branch and bound heuristics are often used to transform the resulting infeasible solution into a feasible one. A solution technique based on Lagrangian relaxation is presented in the next chapter.
[...]
[1] See Fong, C.O./Srinivasan, V., SLOT heuristic (Management Science 1986) pp. 1140.
[2] See Canel, C./Khumawala, B.M. a.o., Closing cost (Computers & Operations Research 2001) pp. 413-414.
[3] See Erlenkotter, D., Price-sensitive demands (Management Science 1977) pp. 378.
[4] See Girard, A./Gu, X.D./Mason, L.G., Modernisation (Operations Research 1990) pp. 415
[5] See Luss, H., Network application (Operations Research 1982) pp. 936-938.
[6] See Luss, H., Heavy process industrie (Operations Research 1982) pp. 938-939.
[7] See Luss, H., Public services (Operations Research 1982) pp. 938.
[8] See Melachrinoudis, E./Min, H., Two-echelon plant problem (European Journal of Operational Research 2000) pp. 1
[9] See Fernandez, F.R./Hinojosa, Y./Puerto, J., Multicommodity (European Journal of Operational Research 2000) pp. 271-272.
[10] In approach to Erlenkotter, D., Problem formulation (1981) pp. 133 and Shulman, A., Problem formulation (1991) pp. 425-426.
[11] Girard, A./Gu, X.D./Mason, L.G., Linear programming (Operations Research 1990) pp. 416.
[12] Girard, A./Gu, X.D./Mason, L.G., Linear programming solution (Operations Research 1990) pp. 416.
[13] Girard, A./Gu, X.D./Mason, L.G., Comparison (Operations Research 1990) pp. 422-423.
[14] Fisher, M.L., Lagrangian relaxation (1981) pp. 1-2.
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.