EuroEconomica, Vol 33, No 2 (2014)

The localization problem

Cătălin Angelo IOAN¹, Gina IOAN²

¹Danubius University of Galati, Department of Economics, catalin_angelo_ioan@univ-danubius.ro

²Danubius University of Galati, Department of Economics, ginaioan@univ-danubius.ro

Abstract. This paper solve completely the problem of determining a point that realizes the minimum weighted sum of the distances to an arbitrary number of points. There are treated the two cases corresponding to existing roads - using graph theory and where roads will built later - by analytical methods. The latter problem is solved, in principle, for n points and practical for three points.

Keywords: location, optimal

1 Introduction

The Localization Problem is of great practical importance. For a proper understanding of it we will, first, give an example.

Consider a firm that produces a good in a quantity Q wishing its distribution to beneficiaries in the quantities Q₁,...,Q_n. Distribution activity involves the use of means of transport (say, for example, trucks), assumed identical as if skills and performance. Distribution to the beneficiary k will require a number t_k= trucks if is integer and t_k= +1 trucks otherwise, where [a] is ​​the integer part of the number (i.e. the largest integer less than or equal to a).

The problem lies in determining the location of company headquarters so that total transport costs from the company to the beneficiaries to be minimal. Considering the points M_k of location of beneficiaries and M – the company site, h – the fuel for 1 km with load and s – without load, the total cost of transport (considering that after delivering, the trucks will return to the headquarter) will be: E= . Noting , the problem lies in the determination of M for which E= =minimal.

The problem presented can be solved in many cases. If there is a network of roads then it returns to the determination of the minimum length of the road in a graph, and if there is not exist, as if in the problem of the arrangement of a base at a site of production, the paths being replaced by the conveyor and being constructed after solving the problem, it is reduced to a purely geometric.

At the end of this introduction, note that the problem is not new, being made ​​in the mid-century XVII by Pierre de Fermat in a letter to Evangelista Torricelli challenging him to determine a point for which the sum of distances to the vertices of a triangle be minimal. The problem was solved geometrically leading to the so-called Fermat-Torricelli point. Subsequently, the problem was generalized in the sense above, proposing that the determination of the weighted average of the distances from the vertices of a triangle to be minimal. Solving the latter problem has benefited also from a purely geometric approach ([3]).

In the following, we will solve the issue presented in several aspects. First, we will completely solve the problem using graph theory, then we will attack the Euclidean appearance that does not imply predetermined roads. In the latter case, we obtain a series of results for both the n points problem and we will give the complete solution for 3 points but by purely analytical methods.

2 The solution of the problem using graph theory

Let the fixed nodes M_k, k= , n2 and the nides of potential location N_s, s= , m1, conveniently chosen in a region surrounding the points M_k so that the problem does not impossible charge with potential points (of course in the minimal sense). To solve the problem we will apply Bellman-Kalaba algorithm ([2]).

We will build therefore, for each node N_s, the effective distances matrix D_s,1=(d_ij), d_ij=d(M_i,M_j), i,j= where M_n+1=N_s, and d(M_i,M_j) is the length arc connecting M_i to M_j if exists, d(M_i,M_j)=¥ if between M_i and M_j is no arc and d(M_i,M_i)=0. Note now - the minimum length of roads from M_i to M_n+1 consisting of a single arc. Obviously, they are in the column "n +1" of the matrix D_s,1. If we note now at the step p: - the minimum length of roads from M_i to M_n+1 consisting of at most p arcs, we have: . It is clear that unless there is a path between M_i and M_n+1 with at most p arcs we get =¥. To do this, we will construct the matrix D_s,p obtained from the addition of each line of the matrix D_s,1 of the vector . The vector will be obtained from the matrix D_s,p by finding the minimum of the elements in the i-th line. The process is continued till we will obtain , i= . Finally, the vector will have like components the minimal distances from N_s to each of the points M_k, k= . After this, we will compute E_s= = . Doing this for all all potential nodes N_s, s= , is determined, finally, that for which is obtained .

3 The solution of the general problem

Let the points M_k(x_k,y_k)R², k= , p_k0, k= . Considering an arbitrary point M(x,y)R², we formulate the question of determining it such the expression:

= = (1)

be minimal.

Suppose first that i= such that: . Consider now the expression:

= = (2)

Because let note: u= 0.

We have therefore:

= (3)

We will prove that: 0.

Noting: a= , b= , c= , d= the inequality becomes:

and after squaring, this is equivalent to . If ab+cd0 then the statement is true, and if ab+cd0 then, after further squaring, it becomes: - true.

Therefore, (x,y)R² so if then the expression is minimum is reached at the point M_i(x_i,y_i).

It is obvious that due to the positivity of the quantities p_k, k= can not exist at least two indices ij such that , .

We therefore consider further that: , i= .

Compute now, first, the values: E_k= and minE= and suppose in what follows that , k= . We have now:

(4)

(5)

Considering the Hessian matrix: H_E= , the values of principal diagonal determinants are:

₁= 0, ₂= 0 (6)

so any stationary point will be a local minimum. Furthermore, since the function is strictly convex, it will have at most one global minimum point.

The problem thus reduces to determining the stationary points of E. If none exist, the minimum function E will be minE, and if they are (considering, for example, a point with coordinates (, )) then the minimum will be .

To determine the stationary points, the solve of the characteristic system is very difficult, in practice requiring computer implementation, but occurring complications relative to the convergence of the algorithms.

We can obtain an approximate solution as follows ([1]):

Let the function f(x,y)= . Its development in Mac-Laurin series give:

f(x,y)=

Substituting in the characteristic system, we obtain with the notations d_i= , i= :

(7)

By eliminating y between the two equations we obtain an equation of degree four in x that can provide approximate solutions. Calculating the value of E in these pairs (x,y) and considering the minimum values ​​obtained for one of the pairs (,), we obtain finally: .

The presented method does not claim to provide the exact answer, but it is an approximation of the actual location.

Returning to the original problem, we note now: z=x+iyC and z_k=x_k+iy_kC, k= . The determination of stationary points thus reduces to solving the equation:

=0 (8)

From the fact that , k= follows : zz_k, k= therefore z-z_k0.

Let now the trigonometric forms of complex numbers: , .

The equation becomes:

=0 (9)

from where:

(10)

Considering an arbitrary solution of the system ,the stationary point will be at the intersection of the lines that pass through z_k and with slope tg _k, k= .

Consider then, for krs, the straight lines:

(11)

the condition of intersection of all three is:

(12)

equivalent to:

(13)

the solution being given by the first two equations:

(14)

Therefore, for all the solutions of the system (10) we will check the equations (13) 1krsn, those which satisfy substituting in (14) for two arbitrary values kr and determining the pairs (x, y). After that we weill replace these pairs in the characteristic system:

(15)

If there is a pair (, ) then, finally, the minimum is . If none of the pairs (x, y) does not check the system, the minimum is minE.

4 The solution of the problem for three points

Returning to the system (10), we have for 1sn, fixed:

(16)

Adding, after squaring, we obtain successively:

(17)

(18)

, s= (19)

For n=3 we have with s= :

(20)

How it can construct a triangle with sides p₁, p₂ și p₃. Note now ₁= , ₂= , ₃= . After applying the cosine theorem, the system becomes:

(21)

from where:

(22)

From (22) we get:

(23)

From follows k₁=k₂=k₃=0 therefore:

(24)

Adding the three equations: . How follows from where: , pZ.

But implies -1p1 therefore p=0.

We obtain: . If ₃=-1 ₁=₂=-1. If ₃=1 ₁=₂=1. Let therefore: ₁=₂=₃= . We have:

, (25)

Finally, with the notations: =₃, =₂, we obtain:

, ,,-1,1, ++-1,1 (26)

It can be seen that the triplet of values (₁,₂,₃) verify the system (10) for n=3.

Considering as in the above, the straight lines:

(27)

the condition (13) becomes after (26) and a series of laborious calculations:

(28)

the system solution being:

(29)

Replacing the values of (29) for both =-1 and =1 in the system (15) for n=3, if a pair (x,y) checks it, this is the optimal solution (from the strict convexity only one of them may verify). If none of the solutions does not check the system, the minimum sought is minE.

5 Conclusions

The presented method provides, unlike the pure geometrical method, the advantage of actually determining the optimal point so when there is a graph, and if subsequent construction of paths through points.

6 References

Ioan C.A. (2006), Town and country planning, Zigotto Publishing, Galați

Ioan C.A., Ioan G. (2012), Methods of mathematical modeling in economics, Zigotto Publishing, Galați

Nicolescu, L., Boskoff, V., P. (1990), Practical problems of geometry, Tehnica Publishing, București

Refbacks

• There are currently no refbacks.