anapproximationalgorithmforthedynamicfacilitylocationproblem

1、an approximation algorithm for the dynamic facility location problem董家云杭州电子科技大学 通信工程学院 2013年12月24日contentsintroduction1approximation algorithms for the uflp2linear programming relaxation for the dflp3research on dflp 4problems and solutions5conclusions6reference7introductionu for facility location p

2、roblem, its original version we are presented with a set of possible warehouse locations and a set of customer locations. our objective is to decide on which of these possible warehouse locations we want to actually build warehouses. since maintaining a warehouse incurs high costs, we want to build

3、as few as possible. u on the other hand, every customer prefers to be located as close to a warehouse as possible, since costs rise with the distance to the nearest warehouse. this means that we are looking for a placement of the warehouses that minimizes the sum of the costs caused by the customers

4、 and the warehouses. u generally, a facility will serve for a long time after constructing, but the factors that influences site selection are changing, so we had a dynamic facility location problem (dynamic facility location problem (dflp). what we want to study is this problem. professional termin

5、ologyintroductiona. issue of p and npb. uflp (uncapacitated facility location problem)c. dflp (dynamic facility location problem)d. : the approximation ratio of the algorithm / performance guaranteeapproximation algorithms for the uflp classification of algorithma. based on linear programming roundi

6、ng. the main idea is to solve the linear programming relaxation of the uflp, and then carefully round the optimal fractional solution into a feasible integer solution.b. one starts with a feasible solution, and then improves the solution by some simple operations such as open one facility, close one

7、 facility, or swap two facilities. c. primal-dual in flavor. such an algorithm simultaneously increases dual variables, and tries to find a feasible primal solution according to the information provided by the dual variables. linear programming relaxation for the dflpthe dual of the linear programmi

8、ng relaxation is linear programming relaxation for the dflpit is straightforward to show that the above dual is equivalent to the following linear program.research on dflpbased on primal-dual algorithm for the uncapacitated problem. the algorithm first constructs a feasible dual solution and then fi

9、nds a feasible integer primal solution based on the dual solution. phase 2: finding a feasible primal solution phase 1: finding a feasible dual solution approximation algorithmresearch on dflp analysis of algorithmresearch on dflptheorem: the two-phase algorithm presented above is a 1.86-approximati

10、on algorithm for the dynamic facility location problem. analysis of algorithmproof: we first show that the cost of opening facility-period pairs in g is at most for each facility-period pair (i, s) that is tentatively opened, we must have thatresearch on dflptherefore analysis of algorithmresearch o

11、n dflp analysis of algorithmif (j,t) d, then we consider one of its connecting witnesses, say (i,s). if (i,s) g, then we know thatthen we know the total facility cost f and total service cost c satisfying ( opt is the total of an optimal solution )it is known that such an algorithm would imply a 1.8

12、6-approximation algorithm. this completes the proof of the theorem. problems and solutionsp problems1. approximation algorithms in this paper is based on demand changed with time periods, but it does not consider the random demand.2. when solving the dynamic location problem, an important assumption

13、 is that transfer costs are fixed for each period, and has nothing to do with the pending transfer of the actual useful lives of the logistics network nodes and we also ignore considering transfer method.3. we do not consider costs of reverse logistics.p solutions1. we need more in-depth research on

14、 the dynamic facility location problem. 2. when making location decisions, not only we need refer to the results of models, but also measure the impact of location factors comprehensively, so as to ensure the siting decision-making more scientific and reasonable.conclusionsp in this chapter, we pres

15、ented some preliminary results on the dynamic facility location problem.p we also showed that the scenario-based stochastic facility location problem is a special case of the dynamic facility location problem. this leads to a 1.86-approximation algorithm for solving the stochastic problem. p we rema

16、rk that the service cost c$ could accommodate transportation cost, production cost, and inventory cost in the context of logistic problems.p of course, more challenging research directions are in solving dynamic facility location problems with capacity constraints and nonmetric service costs. this i

17、s our research objectives of next phase.appendix :referencesi k. andreev, b. m. maggs, a. meyerson, and r. k. sitaraman, designing overlay multicast networks for streaming, spaa, 149-158, 2003. 2 v. arya, n. garg, r. khandekar, a. meyerson, k. munagala, and v. pandit , local search heuristic for k-m

18、edian and facility location problems, proceedings of the acm symposium on theory of computing, 21-29, 2001. 3 j. d. camm, t. e. chorman, f. a. dill, j. r. evans, d. j. sweeney, and g. w. wegryn, blending or/ms, judgement, and gis: restructuring p&gs supply chain, interfaces, 27, 128-142, 1997. 4 p.

19、chardaire, facility location optimization and cooperative games, ph.d. thesis, school of information systems, university of east anglia, norwich nr4 7tj, uk, 1998.5 m. charikar and s. guha, improved combinatorial algorithms for facility location and k-median problems, proceedings of the 40th ieee fo

20、undations of computer science (focs), 378-388, 1999. 6 f. a. chudak, improved approximation algorithms for uncapacited facility location, in r.e. bixby, e.a. boyd, and r.z. rios-mercado (eds.), integer programming and combinatorial optimization, lncs 1412, springer-verlag, new york, 180-194, 1998. 7

21、 f. a. chudak and d. b. shmoys,improved approximation algorithms for the uncapacitated facility location problem, siam journal. on computing, 33(1), 1-25, 2003. 8 j. current, m. daskin, and d. schilling, discrete network location models, in z. drezner and h. hamacher (eds.), facility location theory

22、: applications and methods, springer-verlag, berlin, 81-118, 2002. appendix :references9 m. s. daskin, l. v. snyder, and r. t. berger, facility location in supply chain design, working paper, no. 03-010, department of industrial engineering and management sciences, northwestern university, evanston, illinois, 60208-3119, u.s.a. lo s. guha and s. khuller, greedy strikes back: improved facility location algorithms, journal of algorithms, 31, 228-248, 1999. ll s. guha, a. meyerson, and k. munagala, hierarchica