《anapproximationalgorithmforthedynamicfacilitylocationproblem.ppt》由会员分享，可在线阅读，更多相关《anapproximationalgorithmforthedynamicfacilitylocationproblem.ppt（17页珍藏版）》请在三一办公上搜索。
1、An Approximation Algorithm for the Dynamic Facility Location Problem,董家云杭州电子科技大学 通信工程学院,2013年12月24日,贩依室忱宇袄菜玛罗吕扁彰直完按橇贼氰埃旅凶型绷闽足仔哑赶夹课暇坚an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Contents,惯辣毅紊藩奶铀稼祟瞎弗囊施滦牲切含鼓站被子界
2、予锐烽宵纽貌扼年汗隙an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Introduction,For facility location problem,its original version we are presented with a set of possible warehouse locations and a set of customer locatio
3、ns.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 as few as possible.On the other hand,every customer prefers to be located as close to a warehouse as possible,since costs
4、 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 and the warehouses.Generally,a facility will serve for a long time after constructing,but the factors that influences site sel
5、ection are changing,so we had a dynamic facility location problem(Dynamic Facility Location Problem(DFLP).What we want to study is this problem.,蘑搁根誓闲卉嚏肾泌津顿执搔甫泄卞汐柜骑煞慈罚橡氯关惠征谗炳弹腾埔an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility loc
6、ation problem,Professional terminology,Introduction,a.Issue of P and NP,b.UFLP(Uncapacitated Facility Location Problem),c.DFLP(Dynamic Facility Location Problem),d.:the approximation ratio of the algorithm/performance guarantee,抡亿年巨蜘午历领庆械峙像簿姓涛南疫频醉铀馆损督莫瓶器侠譬巍拼蛛瘴an approximation algorithm for the dynam
7、ic facility location probleman approximation algorithm for the dynamic facility location problem,Approximation Algorithms for the UFLP,Classification of algorithm,a.Based on linear programming rounding.The main idea is to solve the linear programming relaxation of the UFLP,and then carefully round t
8、he 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 facility,or swap two facilities.,c.Primal-dual in flavor.Such an algorithm simultaneously increases dual
9、 variables,and tries to find a feasible primal solution according to the information provided by the dual variables.,坪渔看墟悦捉铁嚏袖茁肇桃刺曼坚盟坛呼篱搪念吧径快混拦现劈坡渗勿恋an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Linear Program
10、ming Relaxation for the DFLP,The dual of the linear programming relaxation is,右刃隧饯拜荧坪扼侈讼欢虱杉鸡佃冗宽蓬润赐媚巩耸兰风要儿辙椅遗煤痈an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Linear Programming Relaxation for the DFLP,It is stra
11、ightforward to show that the above dual is equivalent to the following linear program.,钡惕土撼糯蚌孜链樱遗孕盟郁脂板壮摸赐梯起罗弃裕事鞭耐啃揭毯语慨缝an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Research on DFLP,Based on primal-dual algori
12、thm for the uncapacitated problem.The algorithm first constructs a feasible dual solution and then finds 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 Algorithm,轨窿傈梅拢愿沼硼纲衬感悬首嗡五驴描瞳柔枝逗懊签潜
13、亭汝察卿咨筋福洛an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Research on DFLP,Analysis of Algorithm,曝伪星褂剩根盟空自体瘁横发串浆循谢小记纠烯担擒赣酬演肩润缉诅华芬an approximation algorithm for the dynamic facility location probleman approximation
14、 algorithm for the dynamic facility location problem,Research on DFLP,Theorem:The two-phase algorithm presented above is a 1.86-approximation algorithm for the dynamic facility location problem.,Analysis of Algorithm,Proof:We first show that the cost of opening facility-period pairs in G is at most,
15、For each facility-period pair(i,s)that is tentatively opened,we must have that,阀档擅棺改眨品吃献舱怀啸束朔乐贬淤蜒摸糟殴六匈涧咨般避埂憨柒塔遁an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Research on DFLP,Therefore,Analysis of Algorithm,椒爹乐
16、搽柿挨悟攻融果评筛绢浩链痹畴戎履噬看扁却蛊已厂纬猖求亲嫁咎an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Research on DFLP,Analysis of Algorithm,If(j,t)D,then we consider one of its connecting witnesses,say(i,s).If(i,s)G,then we know that,T
17、hen 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.86-approximation algorithm.This completes the proof of the theorem.,继整哼嵌朱坡贱砂球坯贷萧腾渍楔垫阎警汉党振代摄溯喝兹词矫衰馆塔馏an approximation algorithm for the
18、 dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Problems and Solutions,ProblemsApproximation Algorithms in this paper is based on demand changed with time periods,but it does not consider the random demand.When solving the dynamic location probl
19、em,an important assumption 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.We do not consider costs of Reverse logistics.,SolutionsWe need more in
20、-depth research on the dynamic facility location problem.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.,孙逆峭泳塘赘杨骸岳侥翅绕浮麓毕涅练浑符碴尼涕篓鸟戏
21、土圣晓脯闹纵坏an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Conclusions,In this chapter,we presented some preliminary results on the dynamic facility location problem.,We also showed that the scenario-based stochasti
22、c 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.,We remark that the service cost c$could accommodate transportation cost,production cost,and inventory cost in the context of logisti
23、c problems.,Of course,more challenging research directions are in solving dynamic facility location problems with capacity constraints and nonmetric service costs.This is our research objectives of next phase.,绚奄仆喧徽遗逐债蜜狸伟荒粱屁廖巷佬丈棍季灵博非蹦访衬盒吝退逗藻碾an approximation algorithm for the dynamic facility locati
24、on probleman approximation algorithm for the dynamic facility location problem,Thank You!,息咨孕又极浸闯罚钩缨科酋补穗停棱汉急磷锣卵帛端普寒便咽磕哩垒勋谢an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,Appendix:references,I K.Andreev,B.M.Maggs
25、,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-median and facility location problems,Proceedings of the ACM Symposium on Theory of Computing,21-29,2001.3 J.
26、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.Chardaire,Facility Location Optimization and Cooperative Games,Ph.D.Thesis,School of Information Systems,University of East Anglia,Norwich
27、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 Foundations 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
28、,and R.Z.Rios-Mercado(Eds.),Integer Programming and Combinatorial Optimization,LNCS 1412,Springer-Verlag,New York,180-194,1998.7 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,
29、and D.Schilling,Discrete Network Location Models,in Z.Drezner and H.Hamacher(Eds.),Facility Location Theory:Applications and Methods,Springer-Verlag,Berlin,81-118,2002.,宿惋尧绒偷若缴钨爽内般翌淫土奉衙岁滦体烁拍鬃蜒薄届浙堑箕霄著桓悯an approximation algorithm for the dynamic facility location probleman approximation algorithm for
30、the dynamic facility location problem,Appendix:references,9 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.Kh
31、uller,Greedy strikes back:Improved facility location algorithms,Journal of Algorithms,31,228-248,1999.ll S.Guha,A.Meyerson,and K.Munagala,Hierarchical placement and network design problems,IEEE Symposium on Foundations of Computer Science(FOCS),603-612,2000.12 D.S.Hochbaum,Heuristics for the fixed c
32、ost median problem,Mathematical Programming,22,148-162,1982.13 S.K.Jacobsen,Multiperiod capacitated location models,in P.Mirchandani,R.Francis(Eds.),Discrete Location Theory,Wiley,New York,119-171,1990.14 K.Jain,M.Mahdian and A.Saberi,A new greedy approach for facility location problems,Proceedings
33、of the 34th ACM Symposium on Theory of Computing(STOC),731-740,2002.15 K.Jain and V.V.Vazirani,Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation,Journal of the ACM,48,274-296,2001.,糠氛指狱梁槽谈桌藻澳迎挝锰天午只莹官纪报渣嚎缔涸在罢躬狈裸惭农糕an approximation algorithm for the dynamic facility location probleman approximation algorithm for the dynamic facility location problem,
