- Source: Weber problem
In geometry, the Weber problem, named after Alfred Weber, is one of the most famous problems in location theory. It requires finding a point in the plane that minimizes the sum of the transportation costs from this point to n destination points, where different destination points are associated with different costs per unit distance.
The Weber problem generalizes the geometric median, which assumes transportation costs per unit distance are the same for all destination points, and the problem of computing the Fermat point, the geometric median of three points. For this reason it is sometimes called the Fermat–Weber problem, although the same name has also been used for the unweighted geometric median problem. The Weber problem is in turn generalized by the attraction–repulsion problem, which allows some of the costs to be negative, so that greater distance from some points is better.
Definition and history of the Fermat, Weber, and attraction-repulsion problems
In the triangle case, the Fermat problem consists in locating a point D with respect to three points A, B, C in such a way that the sum of the distances between D and each of the three other points is minimized. It was formulated by the famous French mathematician Pierre de Fermat before 1640, and it can be seen as the true beginning of both location theory, and space-economy. Torricelli found a geometrical solution to this problem around 1645, but it still had no direct numerical solution more than 325 years later. E. Weiszfeld published a paper in 1937 with an algorithm for the Fermat-Weber problem. As the paper was published in Tohoku Mathematical journal, and Weiszfeld immigrated to USA and changed his name to Vaszoni, his work was not widely known. Kuhn and Kuenne independently found a similar iterative solution for the general Fermat problem in 1962, and, in 1972, Tellier found a direct numerical solution to the Fermat triangle problem, which is trigonometric. Kuhn and Kuenne's solution applies to the case of polygons having more than three sides, which is not the case with Tellier's solution for reasons explained further on.
The Weber problem consists, in the triangle case, in locating a point D with respect to three points A, B, C in such a way that the sum of the transportation costs between D and each of the three other points is minimized. The Weber problem is a generalization of the Fermat problem since it involves both equal and unequal attractive forces (see below), while the Fermat problem only deals with equal attractive forces. It was first formulated, and solved geometrically in the triangle case, by Thomas Simpson in 1750. It was later popularized by Alfred Weber in 1909. Kuhn and Kuenne's iterative solution found in 1962, and Tellier's solution found in 1972 apply to the Weber triangle problem as well as to the Fermat one. Kuhn and Kuenne's solution applies also to the case of polygons having more than three sides.
In its simplest version, the attraction-repulsion problem consists in locating a point D with respect to three points A1, A2 and R in such a way that the attractive forces exerted by points A1, A2, and the repulsive force exerted by point R cancel each other out as it must do at the optimum. It constitutes a generalization of both the Fermat and Weber problems. It was first formulated and solved, in the triangle case, in 1985 by Luc-Normand Tellier. In 1992, Chen, Hansen, Jaumard and Tuy found a solution to the Tellier problem for the case of polygons having more than three sides.
Torricelli’s geometrical solution of the Fermat triangle problem
Evangelista Torricelli’s geometrical solution of the Fermat triangle problem stems from two observations:
Point D is at its optimal location when any significant move out of that location induces a net increase of the total distance to reference points A, B, C, which means that the optimal point is the only point where an infinitesimal movement towards one of the three reference points induces a reduction of the distance to that point that is equal to the sum of the induced changes in the distances to the two other points; in fact, in the Fermat problem, the advantage to reduce the distance from A by one kilometer is equal to the advantage to reduce the distance from B by one kilometer or the distance from C by the same length; in other words, the activity to be located at D is equally attracted by A, B, C;
According to an important theorem of Euclidean geometry, in a convex quadrilateral inscribed in a circle, the opposite angles are supplementary (that is their sum is equal to 180°); that theorem can also take the following form: if we cut a circle with a chord AB, we get two circle arcs, let us say AiB, AjB; on arc AiB, any ∠AiB angle is the same for any chosen point i, and, on arc AjB, all the ∠AjB angles are also equal for any chosen point j; moreover, the ∠AiB, ∠AjB angles are supplementary.
It can be proved that the first observation implies that, at the optimum, the angles between the AD, BD, CD straight lines must be equal to 360° / 3 = 120°. Torricelli deduced from that conclusion that:
If any triangle △ABD, whose ∠ADB angle is equal to 120°, generates an ABDE convex quadrilateral inscribed in a circle, the ∠ABE angle of the △ABE triangle must be equal to (180° − 120°) = 60°;
One way to determine the set of locations of D for which the ∠ADB angle is equal to 120° is to draw an equilateral △ABE triangle (because each angle of an equilateral triangle is equal to 60°), where E is located outside the △ABC triangle, and draw a circle round that triangle; then all the D' points of the circumference of that circle that lie within the △ABC circle are such that the ∠AD'B angle is equal to 120°;
The same reasoning can be made with respect to triangles △ACD, △BCD;
This leads to draw two other equilateral triangles △ACF, △BCG, where F, G are located outside the △ABC triangle, as well as two other circles round these equilateral triangles, and to determine the location where the three circles intersect; at that location, the angles between the AD, BD, CD straight lines is necessarily equal to 120°, which proves that it is the optimal location.
Simpson’s geometrical solution of the Weber triangle problem
Simpson's geometrical solution of the so-called "Weber triangle problem" (which was first formulated by Thomas Simpson in 1750) directly derives from Torricelli's solution. Simpson and Weber stressed the fact that, in a total transportation minimization problem, the advantage to get closer to each attraction point A, B or C depends on what is carried and on its transportation cost. Consequently, the advantage of getting one kilometer closer to A, B or C varies, and the ∠ADB, ∠ADC, ∠BDC angles no more need to be equal to 120°.
Simpson demonstrated that, in the same way as, in the Fermat triangle problem case, the constructed triangles △ABE, △ACF, △BCG were equilateral because the three attractive forces were equal, in the Weber triangle problem case, the constructed triangles △ABE, △ACF, △BCG, where E, F, G are located outside the △ABC triangle, must be proportional to the attractive forces of the location system.
The solution is such that:
In the constructed triangle △ABE, the AB side is proportional to the attractive force wC pointing towards C, the AE side is proportional to the attractive force wB pointing towards B, and the BE side is proportional to the attractive force wA pointing towards A;
In the constructed triangle △BCG, the BC side is proportional to the attractive force wA pointing towards A, the BG side is proportional to the attractive force wC pointing towards B, and the CG side is proportional to the attractive force wB pointing towards C;
The optimal point D is located at the intersection of the two circumferences drawn round the △ABE, △BCG constructed triangles.
A third triangle of forces △ACF, where F is located outside the △ABC triangle, can be drawn based on the AC side, and a third circumference can be traced round that triangle. That third circumference crosses the two previous ones at the same point D.
Tellier’s geometrical solution of the attraction-repulsion triangle problem
A geometrical solution exists for the attraction-repulsion triangle problem. Its discovery is rather recent. That geometrical solution differs from the two previous ones since, in this case, the two constructed force triangles overlap the △A1A2R location triangle (where A1 and A2 are attraction points, and R, a repulsion one), while, in the preceding cases, they never did.
This solution is such that:
In the constructed triangle △RA2H, which partly overlaps the △A1A2R location triangle, the RA2 side is proportional to the attractive force wA1 pointing towards A1, the RH side is proportional to the attractive force wA2 pointing towards A2, and the A2H side is proportional to the repulsive force wR pushing away from point R;
In the constructed triangle △RA1I, which partly overlaps the △A1A2R location triangle, the RA1 side is proportional to the attractive force wA2 pointing towards A2, the RI side is proportional to the attractive force wA1 pointing towards A1, and the A1I side is proportional to the repulsive force wR pushing away from point R;
The optimal point D is located at the intersection of the two circumferences drawn round the △RA2H and △RA1I constructed triangles.
This solution is useless if one of the forces is greater than the sum of the two other ones or if the angles are not compatible. In some cases, no force is larger than the two other ones, and the angles are not compatible; then, the optimal location lies at the point that exerts the greater attractive force.
Tellier’s trigonometric solution of the Fermat and Weber triangle problems
More than 332 years separate the first formulation of the Fermat triangle problem and the discovery of its non-iterative numerical solution, while a geometrical solution existed for almost all that period of time. Is there an explanation for that? That explanation lies in the possibility of the origins of the three vectors oriented towards the three attraction points not coinciding. If those origins do coincide and lie at the optimum location P, the vectors oriented towards A, B, C, and the sides of the △ABC location triangle form the six angles ∠1, ∠2, ∠3, ∠4, ∠5, ∠6, and the three vectors form the ∠αA, ∠αB, ∠αC angles. It is easy to write the following six equations linking six unknowns (the angles ∠1, ∠2, ∠3, ∠4, ∠5, ∠6) with six known values (angles ∠A, ∠B, ∠C, whose values are given, and angles ∠αA, ∠αB, ∠αC, whose values depend only on the relative magnitude of the three attractive forces pointing towards the A, B, C attraction points):
∠
1
+
∠
2
=
∠
C
;
∠
3
+
∠
4
=
∠
A
;
∠
5
+
∠
6
=
∠
B
;
∠
1
+
∠
6
+
∠
α
A
=
180
∘
;
∠
2
+
∠
3
+
∠
α
B
=
180
∘
;
∠
4
+
∠
5
+
∠
α
C
=
180
∘
.
{\displaystyle {\begin{aligned}\angle 1+\angle 2&=\angle C;\\\angle 3+\angle 4&=\angle A;\\\angle 5+\angle 6&=\angle B;\\[4pt]\angle 1+\angle 6+\angle \alpha _{A}&=180^{\circ };\\\angle 2+\angle 3+\angle \alpha _{B}&=180^{\circ };\\\angle 4+\angle 5+\angle \alpha _{C}&=180^{\circ }.\end{aligned}}}
Unfortunately, this system of six simultaneous equations with six unknowns is undetermined, and the possibility of the origins of the three vectors oriented towards the three attraction points not coinciding explains why. In the case of non-coincidence, we observe that all the six equations are still valid. However, the optimal location P has disappeared because of the triangular hole that exists inside the triangle. In fact, as Tellier (1972) has shown, that triangular hole had exactly the same proportions as the "forces triangles" we drew in Simpson's geometrical solution.
In order to solve the problem, we must add to the six simultaneous equations a seventh requirement, which states that there should be no triangular hole in the middle of the location triangle. In other words, the origins of the three vectors must coincide.
Tellier's solution of the Fermat and Weber triangle problems involves three steps:
Determine the angles ∠αA, ∠αB, ∠αC that are such that the three attractive forces wA, wB, wC cancel each other to ensure equilibrium. This is done by means of the following independent equations:
cos
∠
α
A
=
−
w
B
2
+
w
C
2
−
w
A
2
2
w
B
w
C
;
cos
∠
α
B
=
−
w
A
2
+
w
C
2
−
w
B
2
2
w
A
w
C
;
cos
∠
α
C
=
−
w
A
2
+
w
B
2
−
w
C
2
2
w
A
w
B
;
{\displaystyle {\begin{aligned}\cos \angle \alpha _{A}=-{\frac {w_{B}^{2}+w_{C}^{2}-w_{A}^{2}}{2\,w_{B}w_{C}}};\\\cos \angle \alpha _{B}=-{\frac {w_{A}^{2}+w_{C}^{2}-w_{B}^{2}}{2\,w_{A}w_{C}}};\\\cos \angle \alpha _{C}=-{\frac {w_{A}^{2}+w_{B}^{2}-w_{C}^{2}}{2\,w_{A}w_{B}}};\end{aligned}}}
Determine the value of angle ∠3 (this equation derives from the requirement that point D must coincide with point E):
tan
∠
3
=
k
sin
k
′
1
+
k
cos
k
′
;
{\displaystyle \tan \angle 3={\frac {k\sin k'}{1+k\cos k'}};}
where
k
=
C
B
¯
C
A
¯
×
sin
∠
α
B
sin
∠
α
A
,
k
′
=
(
∠
A
+
∠
B
+
∠
α
C
)
−
180
∘
.
{\displaystyle {\begin{aligned}k&={\frac {\overline {CB}}{\overline {CA}}}\times {\frac {\sin \angle \alpha _{B}}{\sin \angle \alpha _{A}}},\\[4pt]k'&=(\angle A+\angle B+\angle \alpha _{C})-180^{\circ }.\end{aligned}}}
Solve the following system of simultaneous equations where ∠3 is now known:
∠
1
+
∠
2
=
∠
C
;
∠
3
+
∠
4
=
∠
A
;
∠
5
+
∠
6
=
∠
B
;
∠
1
+
∠
6
+
∠
α
A
=
180
∘
;
∠
2
+
∠
3
+
∠
α
B
=
180
∘
;
∠
4
+
∠
5
+
∠
α
C
=
180
∘
.
{\displaystyle {\begin{aligned}\angle 1+\angle 2&=\angle C;\\\angle 3+\angle 4&=\angle A;\\\angle 5+\angle 6&=\angle B;\\[4pt]\angle 1+\angle 6+\angle \alpha _{A}&=180^{\circ };\\\angle 2+\angle 3+\angle \alpha _{B}&=180^{\circ };\\\angle 4+\angle 5+\angle \alpha _{C}&=180^{\circ }.\end{aligned}}}
Tellier’s trigonometric solution of the triangle attraction-repulsion problem
Tellier (1985) extended the Fermat–Weber problem to the case of repulsive forces. Let us examine the triangle case where there are two attractive forces wA1, wA2, and one repulsive force wR. Here as in the previous case, the possibility exists for the origins of the three vectors not to coincide. So the solution must require their coinciding. Tellier's trigonometric solution of this problem is the following:
Determine angle ∠e:
cos
∠
e
=
−
w
A
1
2
+
w
A
2
2
−
w
R
2
2
w
A
1
w
A
2
;
{\displaystyle \cos \angle e=-{\frac {w_{A1}^{2}+w_{A2}^{2}-w_{R}^{2}}{2\,w_{A1}w_{A2}}};}
Determine angle ∠p:
cos
∠
p
=
−
w
A
1
2
+
w
R
2
−
w
A
2
2
2
w
A
1
w
R
;
{\displaystyle \cos \angle p=-{\frac {w_{A1}^{2}+w_{R}^{2}-w_{A2}^{2}}{2\,w_{A1}w_{R}}};}
Determine angle ∠c:
∠
c
=
180
∘
−
∠
p
;
{\displaystyle \angle c=180^{\circ }-\angle p;}
Determine angle ∠d:
∠
d
=
∠
e
−
∠
c
;
{\displaystyle \angle d=\angle e-\angle c;}
Determine the value of angle ∠3 (this equation derives from the requirement that point D must coincide with point E):
tan
∠
3
=
x
y
;
{\displaystyle \tan \angle 3={\frac {x}{y}};}
where
x
=
sin
∠
f
−
R
A
1
¯
R
A
2
¯
×
sin
∠
d
sin
(
∠
e
−
∠
b
)
sin
∠
c
;
y
=
R
A
1
¯
R
A
2
¯
×
sin
∠
d
cos
(
∠
e
−
∠
b
)
sin
∠
c
−
cos
∠
f
;
{\displaystyle {\begin{aligned}x&=\sin \angle f-{\frac {\overline {RA_{1}}}{\overline {RA_{2}}}}\times {\frac {\sin \angle d\sin(\angle e-\angle b)}{\sin \angle c}};\\[4pt]y&={\frac {\overline {RA_{1}}}{\overline {RA_{2}}}}\times {\frac {\sin \angle d\cos(\angle e-\angle b)}{\sin \angle c}}-\cos \angle f;\end{aligned}}}
Determine ∠1:
∠
1
=
180
∘
−
∠
e
−
∠
3
;
{\displaystyle \angle 1=180^{\circ }-\angle e-\angle 3;}
Determine ∠5:
∠
5
=
180
∘
−
∠
b
−
∠
c
−
∠
1
;
{\displaystyle \angle 5=180^{\circ }-\angle b-\angle c-\angle 1;}
Determine ∠2:
∠
2
=
∠
a
−
∠
5.
{\displaystyle \angle 2=\angle a-\angle 5.}
Iterative solutions of the Fermat, Weber and attraction-repulsion problems
When the number of forces is larger than three, it is no longer possible to determine the angles separating the various forces without taking into account the geometry of the location polygon. Geometric and trigonometric methods are then powerless. Iterative optimizing methods are used in such cases. Kuhn and Kuenne (1962) suggested an algorithm based on iteratively reweighted least squares generalizing Weiszfeld's algorithm for the unweighted problem. Their method is valid for the Fermat and Weber problems involving many forces, but not for the attraction–repulsion problem. In this method, to find an approximation to the point y minimizing the weighted sum of distances
∑
i
=
1
n
w
i
‖
x
i
−
y
‖
,
{\displaystyle \sum _{i=1}^{n}w_{i}\,\|x_{i}-y\|,}
an initial approximation to the solution y0 is found, and then at each stage of the algorithm is moved closer to the optimal solution by setting yj + 1 to be the point minimizing the sum of weighted squared distances
∑
i
=
1
n
w
i
‖
x
i
−
y
j
‖
‖
x
i
−
y
‖
2
{\displaystyle \sum _{i=1}^{n}{\frac {w_{i}}{\|x_{i}-y_{j}\|}}\|x_{i}-y\|^{2}}
where the initial weights wi of the input points are divided by the distances from each point to the approximation from the previous stage.
As the unique optimal solution to a weighted least squares problem, each successive approximation may be found as a weighted average:
y
j
+
1
=
∑
i
=
1
n
w
i
x
i
|
x
i
−
y
j
|
∑
i
=
1
n
w
i
|
x
i
−
y
j
|
{\displaystyle y_{j+1}={\frac {\displaystyle \sum _{i=1}^{n}{\frac {w_{i}x_{i}}{|x_{i}-y_{j}|}}}{\displaystyle \sum _{i=1}^{n}{\frac {w_{i}}{|x_{i}-y_{j}|}}}}}
The Varignon frame provides an experimental solution of the Weber problem.
For the attraction–repulsion problem one has instead to resort to the algorithm proposed by Chen, Hansen, Jaumard and Tuy (1992).
Interpretation of the land rent theory in the light of the attraction–repulsion problem
In the world of spatial economics, repulsive forces are omnipresent. Land values are the main illustration of them. In fact a substantial portion of land value theory, both rural and urban, can be summed up in the following way.
In the case where everybody is attracted by a single attraction point (the rural market or the urban central business district), competition between the various bidders who all want to locate at the center will generate land values that will transform the unique attraction point of the system into a repulsion point from the land value point of view, and, at the equilibrium, each inhabitant and activity will be located at the point where the attractive and the repulsive forces exerted by the center on them will cancel out.
The attraction–repulsion problem and the New Economic Geography
The Tellier problem preceded the emergence of the New Economic Geography. It is seen by Ottaviano and Thisse (2005) as a prelude to the New Economic Geography (NEG) that developed in the 1990s, and earned Paul Krugman a Nobel Memorial Prize in Economic Sciences in 2008. The concept of attractive force is akin to the NEG concept of agglomeration or centripetal force, and the concept of repulsive force is akin to the NEG concept of dispersal or centrifugal force.
Notes
References
Chen, Pey-Chun, Hansen, Pierre, Jaumard, Brigitte and Hoang Tuy, 1992, "Weber's Problem with Attraction and Repulsion," Journal of Regional Science 32, 467–486.
Kuhn, Harold W. and Robert E. Kuenne, 1962, "An Efficient Algorithm for the Numerical Solution of the Generalized Weber Problem in Spatial Economics." Journal of Regional Science 4, 21–34.
Ottaviano, Gianmarco and Jacques-François Thisse, 2005, « New Economic Geography: what about the N? », Environment and Planning A 37, 1707–1725.
Simpson, Thomas, 1750, The Doctrine and Application of Fluxions, London.
Tellier, Luc-Normand and Boris Polanski, 1989, "The Weber Problem: Frequency of Different Solution Types and Extension to Repulsive Forces and Dynamic Processes", Journal of Regional Science, vol 29, no. 3, p. 387–405.
Tellier, Luc-Normand, 1972, "The Weber Problem: Solution and Interpretation", Geographical Analysis, vol. 4, no. 3, pp. 215–233.
Tellier, Luc-Normand, 1985, Économie spatiale: rationalité économique de l'espace habité, Chicoutimi, Gaëtan Morin éditeur, 280 pages.
Tellier, Luc-Normand, 2013, « Annexe 1: Solution géométrique du cas triangulaire du problème d’attraction–répulsion », annex of the paper of Pierre Hansen, Christophe Meyer and Luc-Normand Tellier, « Modèles topodynamique et de la Nouvelle économie géographique : compatibilité, convergence et avantages comparés », in Marc-Urbain Proulx (ed.), 2013, Sciences du territoire II : méthodologies, Québec, Presses de l’Université du Québec.
Weber, Alfred, 1909, Über den Standort der Industrien, Tübingen, J.C.B. Mohr) — English translation: The Theory of the Location of Industries, Chicago, Chicago University Press, 1929, 256 pages.
Wesolowski, Georges, 1993, «The Weber problem: History and perspective», Location Science, Vol. 1, p. 5–23.
External links
"Weber problem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Kata Kunci Pencarian:
- Heinrich Martin Weber
- Pemikatan seksual
- Talcott Parsons
- Persoalan pertemuan
- Marianne Weber
- Indonesia
- X (media sosial)
- Penyakit menular
- Karl Mannheim
- Pengadilan Rakyat (Bayern)
- Weber problem
- Fermat–Weber problem
- Alfred Weber
- Geometric median
- Thomas Simpson
- K-means clustering
- Spatial analysis
- Rendezvous problem
- Max Weber
- Smallest-circle problem
