Given the probability measure over the given region , we consider the optimal location of a set composed by points in in order to minimize the average distance (the classical optimal facility location problem). The paper compares two strategies to find optimal configurations: the long-term one which consists in placing all points at once in an optimal position, and the short-term one which consists in placing the points one by one adding at each step at most one point and preserving the configuration built at previous steps. We show that the respective optimization problems exhibit qualitatively different asymptotic behavior as , although the optimization costs in both cases have the same asymptotic orders of vanishing.
Mots clés : location problem, facility location, Fermat-Weber problem, $k$-median problem, sequential allocation, average distance functional, optimal transportation
@article{COCV_2009__15_3_509_0, author = {Brancolini, Alessio and Buttazzo, Giuseppe and Santambrogio, Filippo and Stepanov, Eugene}, title = {Long-term planning versus short-term planning in the asymptotical location problem}, journal = {ESAIM: Control, Optimisation and Calculus of Variations}, pages = {509--524}, publisher = {EDP-Sciences}, volume = {15}, number = {3}, year = {2009}, doi = {10.1051/cocv:2008034}, mrnumber = {2542570}, zbl = {1169.90386}, language = {en}, url = {http://www.numdam.org/articles/10.1051/cocv:2008034/} }
TY - JOUR AU - Brancolini, Alessio AU - Buttazzo, Giuseppe AU - Santambrogio, Filippo AU - Stepanov, Eugene TI - Long-term planning versus short-term planning in the asymptotical location problem JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2009 SP - 509 EP - 524 VL - 15 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv:2008034/ DO - 10.1051/cocv:2008034 LA - en ID - COCV_2009__15_3_509_0 ER -
%0 Journal Article %A Brancolini, Alessio %A Buttazzo, Giuseppe %A Santambrogio, Filippo %A Stepanov, Eugene %T Long-term planning versus short-term planning in the asymptotical location problem %J ESAIM: Control, Optimisation and Calculus of Variations %D 2009 %P 509-524 %V 15 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv:2008034/ %R 10.1051/cocv:2008034 %G en %F COCV_2009__15_3_509_0
Brancolini, Alessio; Buttazzo, Giuseppe; Santambrogio, Filippo; Stepanov, Eugene. Long-term planning versus short-term planning in the asymptotical location problem. ESAIM: Control, Optimisation and Calculus of Variations, Tome 15 (2009) no. 3, pp. 509-524. doi : 10.1051/cocv:2008034. http://www.numdam.org/articles/10.1051/cocv:2008034/
[1] Minimizing movements. Rend. Accad. Naz. Sci. XL Mem. Mat. Appl. 19 (1995) 191-246. | MR | Zbl
,[2] Gradient flows in metric spaces and in the spaces of probability measures, Lectures in Mathematics. ETH Zurich, Birkhäuser (2005). | MR | Zbl
, and ,[3] Asymptotique d'un problème de positionnement optimal. C. R. Acad. Sci. Paris Ser. I 335 (2002) 1-6. | MR | Zbl
, and ,[4] Optimal networks for mass transportation problems. ESAIM: COCV 11 (2005) 88-101. | Numdam | MR | Zbl
and ,[5] Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem. Ann. Scuola Norm. Sup. Cl. Sci. II (2003) 631-678. | Numdam | MR | Zbl
and ,[6] Minimization problems for average distance functionals, in Calculus of Variations: Topics from the Mathematical Heritage of Ennio De Giorgi, D. Pallara Ed., Quaderni di Matematica 14, Seconda Universita di Napoli (2004) 47-83. | MR | Zbl
and ,[7] Optimal transportation problems with free Dirichlet regions, Progress in Nonlinear Differential Equations and their Applications 51. Birkhäuser (2002) 41-65. | MR | Zbl
, and ,[8] An introduction to -convergence. Birkhauser, Basel (1992). | MR | Zbl
,[9] Lagerungen in der Ebene auf der Kugel und im Raum, Die Grundlehren der Math. Wiss. 65. Springer-Verlag, Berlin (1953). | MR | Zbl
,[10] Hexagonal economic regions solve the location problem. Amer. Math. Monthly 109 (2002) 165-172. | MR | Zbl
and ,[11] -convergence for the irrigation problem. J. Convex Anal. 12 (2005) 145-158. | MR | Zbl
and ,[12] Qualitative properties of maximum distance minimizers and average distance minimizers in . J. Math. Sciences (N.Y.) 122 (2004) 105-122. | MR | Zbl
and ,[13] Blow-up of optimal sets in the irrigation probem. J. Geom. Anal. 15 (2005) 343-362. | MR | Zbl
and ,[14] Partial geometric regularity of some optimal connected transportation networks. J. Math. Sciences (N.Y.) 132 (2006) 522-552. | MR | Zbl
,[15] The -center location. Location Sci. 4 (1996) 69-82. | Zbl
and ,[16] Using Voronoi diagrams, in Facility location: a survey of applications and methods, Z. Drezner Ed., Springer Series in Operations Research, Springer Verlag (1995) 103-118.
and ,[17] Sequential location-allocation of public facilities in one- and two-dimensional space: comparison of several policies. Math. Program. Ser. B 52 (1991) 125-146. | MR | Zbl
, and ,[18] http://cvgmt.sns.it/papers/brabutsan06/.
Cité par Sources :