Long-term planning versus short-term planning in the asymptotical location problem

Alessio Brancolini; Giuseppe Buttazzo; Filippo Santambrogio; Eugene Stepanov

ESAIM: Control, Optimisation and Calculus of Variations (2009)

  • Volume: 15, Issue: 3, page 509-524
  • ISSN: 1292-8119

Abstract

top
Given the probability measure ν over the given region Ω ⊂ ℝ n , we consider the optimal location of a set Σ composed by n points in Ω in order to minimize the average distance Σ ↦ ∫ Ω dist ( x , Σ ) d ν (the classical optimal facility location problem). The paper compares two strategies to find optimal configurations: the long-term one which consists in placing all n 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 n → ∞ , although the optimization costs in both cases have the same asymptotic orders of vanishing.

How to cite

top

Brancolini, Alessio, et al. "Long-term planning versus short-term planning in the asymptotical location problem." ESAIM: Control, Optimisation and Calculus of Variations 15.3 (2009): 509-524. <http://eudml.org/doc/245773>.

@article{Brancolini2009,
abstract = {Given the probability measure $\nu $ over the given region $\Omega \subset \mathbb \{R\}^n$, we consider the optimal location of a set $\Sigma $ composed by $n$ points in $\Omega $ in order to minimize the average distance $\Sigma \mapsto \int _\Omega \mathrm \{dist\}(x,\Sigma )\,\{\rm d\}\nu $ (the classical optimal facility location problem). The paper compares two strategies to find optimal configurations: the long-term one which consists in placing all $n$ 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 $n\rightarrow \infty $, although the optimization costs in both cases have the same asymptotic orders of vanishing.},
author = {Brancolini, Alessio, Buttazzo, Giuseppe, Santambrogio, Filippo, Stepanov, Eugene},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {location problem; facility location; Fermat-Weber problem; $k$-median problem; sequential allocation; average distance functional; optimal transportation; Fermat-weber problem; -median problem},
language = {eng},
number = {3},
pages = {509-524},
publisher = {EDP-Sciences},
title = {Long-term planning versus short-term planning in the asymptotical location problem},
url = {http://eudml.org/doc/245773},
volume = {15},
year = {2009},
}

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
PB - EDP-Sciences
VL - 15
IS - 3
SP - 509
EP - 524
AB - Given the probability measure $\nu $ over the given region $\Omega \subset \mathbb {R}^n$, we consider the optimal location of a set $\Sigma $ composed by $n$ points in $\Omega $ in order to minimize the average distance $\Sigma \mapsto \int _\Omega \mathrm {dist}(x,\Sigma )\,{\rm d}\nu $ (the classical optimal facility location problem). The paper compares two strategies to find optimal configurations: the long-term one which consists in placing all $n$ 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 $n\rightarrow \infty $, although the optimization costs in both cases have the same asymptotic orders of vanishing.
LA - eng
KW - location problem; facility location; Fermat-Weber problem; $k$-median problem; sequential allocation; average distance functional; optimal transportation; Fermat-weber problem; -median problem
UR - http://eudml.org/doc/245773
ER -

References

top
  1. [1] L. Ambrosio, Minimizing movements. Rend. Accad. Naz. Sci. XL Mem. Mat. Appl. 19 (1995) 191–246. Zbl0957.49029MR1387558
  2. [2] L. Ambrosio, N. Gigli and G. Savarè, Gradient flows in metric spaces and in the spaces of probability measures, Lectures in Mathematics. ETH Zurich, Birkhäuser (2005). Zbl1090.35002MR2129498
  3. [3] G. Bouchitté, C. Jimenez and M. Rajesh, Asymptotique d’un problème de positionnement optimal. C. R. Acad. Sci. Paris Ser. I 335 (2002) 1–6. Zbl1041.90025MR1947712
  4. [4] A. Brancolini and G. Buttazzo, Optimal networks for mass transportation problems. ESAIM: COCV 11 (2005) 88–101. Zbl1103.49002MR2110615
  5. [5] G. Buttazzo and E. Stepanov, Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem. Ann. Scuola Norm. Sup. Cl. Sci. II (2003) 631–678. Zbl1127.49031MR2040639
  6. [6] G. Buttazzo and E. Stepanov, 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. Zbl1089.49040MR2118415
  7. [7] G. Buttazzo, E. Oudet and E. Stepanov, Optimal transportation problems with free Dirichlet regions, Progress in Nonlinear Differential Equations and their Applications 51. Birkhäuser (2002) 41–65. Zbl1055.49029MR2197837
  8. [8] G. Dal Maso, An introduction to Γ -convergence. Birkhauser, Basel (1992). Zbl0816.49001MR1201152
  9. [9] L. Fejes Töth, Lagerungen in der Ebene auf der Kugel und im Raum, Die Grundlehren der Math. Wiss. 65. Springer-Verlag, Berlin (1953). Zbl0052.18401MR57566
  10. [10] F. Morgan and R. Bolton, Hexagonal economic regions solve the location problem. Amer. Math. Monthly 109 (2002) 165–172. Zbl1026.90059MR1903153
  11. [11] S.J.N. Mosconi and P. Tilli, Γ -convergence for the irrigation problem. J. Convex Anal. 12 (2005) 145–158. Zbl1076.49024MR2135803
  12. [12] E. Paolini and E. Stepanov, Qualitative properties of maximum distance minimizers and average distance minimizers in ℝ n . J. Math. Sciences (N.Y.) 122 (2004) 105–122. Zbl1099.49029MR2084183
  13. [13] F. Santambrogio and P. Tilli, Blow-up of optimal sets in the irrigation probem. J. Geom. Anal. 15 (2005) 343–362. Zbl1115.49029MR2152486
  14. [14] E. Stepanov, Partial geometric regularity of some optimal connected transportation networks. J. Math. Sciences (N.Y.) 132 (2006) 522–552. Zbl1121.49039MR2197342
  15. [15] A. Suzuki and Z. Drezner, The p -center location. Location Sci. 4 (1996) 69–82. Zbl0917.90233
  16. [16] A. Suzuki and A. Okabe, 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. 
  17. [17] T. Suzuki, Y. Asami and A. Okabe, Sequential location-allocation of public facilities in one- and two-dimensional space: comparison of several policies. Math. Program. Ser. B 52 (1991) 125–146. Zbl0734.90051MR1111083
  18. [18] http://cvgmt.sns.it/papers/brabutsan06/. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.