Dynamiclocationproblems动态选址问题.doc

Dynamic location problemsFields of applicationNetworks:- This group includes communication, electric power, gas distribution and other networks.- The subject is to find a good expansion plan with a special interest on routing decisions.- Transportation costs are often the most important variable costs.Heavy process industries:- This group includes aluminium, cement, steel, caustic soda, nitrogenous fertiliser and related industries.- In these industries transportation costs are again important.Public services:- This group includes the placement of schools, hospitals and other public services. - The decision often depends on social, environmental and political constraints.Two-echelon plant location problem: - The two-echelon plant is a enterprise with two different distribution stages, a manufacturing plant and a warehouse facility.- These cases often include different facility types and commodities.- Transportation costs between the two stages are an important cost driver. Dynamic location problemsWhat is the reason for using dynamic instead of static location approaches?Capacity expansion:- An increasing demand made it necessary to find an optimal expansion schedule. This can only be solved by dynamic approaches.- Some dynamic location problems are also able to handle a decreasing demand in some periods.- The amount of 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. - The objective of expansion problems could be to satisfy every known demand with minimum costs (especially transportation costs), or profit maximisation.Modernisation: - Budget constraints made it necessary to modernise a network stepwise.- Dynamic approaches could help to concentrate modernisation on the most profitable locations first.- An example for a modernisation problem is the switching from analog to digital technology in the transition network for telecommunication lines.It is possible to combine the modernisation and the capacity expansion problem.Dynamic location problemsThe basic dynamic location problem could be described as: (1)subject to for all j, t (2) for all j, t (3) ; for all i, j, t (4)whereT = 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; = the transportation cost of serving a unit of demand at node (market) jby a facility in location i in period t; = the demand generated by node (market) j in period t; = the set-up cost per unit of capacity in location i in period t.The decision variables in this problem are: = a fraction of costumer js demand in period t served by location i; = the capacity installed in location i in period t.Dynamic location problemsSolution techniques:The following figure shows the growth in CPU time (in seconds) in a five location case dependent on the time horizon. One could see that arc path linear programming leads to fast growing CPU time. Real live problems often require integer solutions, which can be achieved by Lagrangian Relaxation and Branch and Bound heuristics.Rounded linear programming solutions are extremely close to the optimal solution but they are often violating some constraints. (These mathematical infeasible solutions are often acceptable for practical purposes.)The Dynamic Capacitated Plant Location Problem (DCPLP):- Is a special case of the dynamic location problems.- Different facility types can be part of the optimal solution.- Capacitated means that the capacity per facility type is limited.- Plant is defined as a collection of facilities in the same location. (- The number of facilities in the same plant-location is limited.)- The DCPLP allows to include economies of scale. Bigger facilities have lower costs per unit, but few plants with big facilities lead to higher transportation costs.The task of the DCPLP is to find a trade off between costs per unit and transportation costs.The mathematical formulation of the DCPLP:The DCPLP objective consists of three cost terms; transportation costs, costs per unit, and set-up costs. Transportation costs are given by (5)where = the set of facilities which can be placed in location ;= is a decision variable and stands for the fraction of costumer js demand in time t served by facility p in location i.Operational costs could be described as (6)where = the variable cost per unit of demand served by facility type p in period t.The set-up costs are defined as the discounted equipment costs, the cost of land, building and maintenance of this equipment and expressed by (7)where = a binary decision variable, which is equal to one if facility type p is placed in location i in period t and zero, otherwise; = the set-up cost of having a facility type p open in location i in period t.The linear programming formulation: (8)subject to for all j, t (9) for all i, t, p (10) 1 for all i, t, p (11) for all i, j, p (12)where = the capacity of facility type p; = the number of facilities type p existing in the beginning of the planning horizon.Lagrangian formulation of the DCPLP: (13)subject to for all i, t, p (10) 1 for all i, t, p (11) for all i, j, p (12) = the Lagrangian multipliers, different for every node j and period t.By introducing the new variable it is possible to reduce (13) to: (14)subject to for all i, t, p (10) 1 for all i, t, p (11) for all i, j, p (12)Subproblem i: (15)subject to for all t, p (10a) = 0, 1 for all t, p (11a) for all j, t, p (12a)Dynamic algorithm for solving the subproblem:Assumptions to reduce complexity:- At most one facility type can be placed in location i in a given time period.- Mixing of facilities in the same location is prohibited.(These assumptions seem to be very restrictive, but this requirement is typical in communication networks)- Lagrangian multiplier is assumed to be a fixed value.The optimal costs up to period t are the optimal costs of the former period t-1 and the costs caused by new facilities, opened or closed in period t are: (16) (17)where k = number of facilities of type p installed in time period t. is the capacity.The minimum cost of serving demands by facilities type p in period t, , can be found as the optimal solution of: (18)subject to for all p (19) (20) Subgradient optimisation:The fixed Lagrangian multiplier can not provide an optimal solution of the problem. The Lagrangian multiplier is to be interpreted as value of marginal changes in the corresponding restriction. The procedure is repeated till all multipliers are close to optimum. If (k) is the number of iterations, the multipliers for the (k+1)th iteration are updated by: (21)where .is a scalar often set to 2 and divided by 2 after every m iterations. is the best found feasible solution.Heuristic for converting the solution into a feasible soluti