# EuroEconomica, Vol 33, No 2 (2014)

**EuroEconomica**

*Issue 2(**33**)/20**14**
ISSN: 1582-8859*

**The
localization problem**

Cătălin
Angelo IOAN^{1},
Gina IOAN^{2}

^{1}*Danubius
University of Galati, Department of Economics,
**catalin_angelo_ioan@univ-danubius.ro*

^{2}*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_{1},...,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=
,
n2
and the nides of potential location N_{s},
s=
,
m1,
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**^{2},
k=
,
p_{k}0,
k=
.
Considering an arbitrary point M(x,y)**R**^{2},
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+cd0 then the statement is true, and if ab+cd0 then, after further squaring, it becomes: - true.

Therefore,
(x,y)**R**^{2}
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 ij
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:

_{1}=
0,
_{2}=
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 : zz_{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 krs, 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) 1krsn, those which satisfy substituting in (14) for two arbitrary values kr 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 1sn, fixed:

(16)

Adding, after squaring, we obtain successively:

(17)

(18)

, s= (19)

For n=3 we have with s= :