Advanced
ALGORITHM FOR WEBER PROBLEM WITH A METRIC BASED ON THE INITIAL FARE†
ALGORITHM FOR WEBER PROBLEM WITH A METRIC BASED ON THE INITIAL FARE†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 157-172
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : February 14, 2014
  • Accepted : July 24, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
LEV A. KAZAKOVTSEV
REDRAG S. STANIMIROVIC

Abstract
We introduce a non-Euclidean metric for transportation systems with a defined minimum transportation cost (initial fare) and investigate the continuous single-facility Weber location problem based on this metric. The proposed algorithm uses the results for solving the Weber problem with Euclidean metric by Weiszfeld procedure as the initial point for a special local search procedure. The results of local search are then checked for optimality by calculating directional derivative of modified objective functions in finite number of directions. If the local search result is not optimal then algorithm solves constrained Weber problems with Euclidean metric to obtain the final result. An illustrative example is presented. AMS Mathematics Subject Classification : 90B85.
Keywords
1. Introduction
Weber problem [29] is a continuous optimization problem for finding a point X * ∈ ℝ n satisfying
PPT Slide
Lager Image
Here, A i ∈ ℝ n , i = 1, . . . , N are some known demand points, w i ∈ ℝ, wi ≥ 0 are some weighting coefficients, ∥ · ∥ : ℝ n → ℝ is a vector norm [20] .
Main appearances of the Weber problem include the warehouse location [10 , 7] , positioning computer and communication networks [14] , locating base stations of wireless networks. Solving a Weber problem (searching for a centroid) is a step of many clustering algorithms [25 , 19 , 9] .
The problem (1) was originally formulated by Weber [29] with Euclidean norm (∥ · ∥ = l 2 (·)) and it is generalized to lp norms and other metrics [29 , 6] .
Detailed explanation of various norms and metrics is presented in [21 , 18 , 8] . The lp norms play an important role in the theory and practice of location problems. The most common distance metrics in continuous space are Euclidean ( l 2 ), rectangular ( l 1 ) and Chebyshev ( l ) metrics but other metrics are also important for specific cases [1 , 8 , 23] . Various distance metrics can be used for solving clustering problems [26 , 30] . In [16] , authors consider norm approximation and approximated solution for Weber problems with an arbitrary metric using random search [15] . Problems with barriers are described in [18] . In special cases, such problems can be transformed into discrete problems [22] .
In the case of public transportation systems, the price usually depends on distance. However, some minimum price is usually defined. For example, the initial fare of the taxi cab may include some distance, usually 1-5 km. Having rescaled the distances so that this distance included in the initial price is equal to 1, we can define the price function dP as
PPT Slide
Lager Image
where ∥ · ∥ is a vector norm. We use the term ”taxi metric” to denote the metric defined by (2). In this paper, we consider ∥ · ∥ as Euclidean norm in ℝ 2 only (∥ · ∥ 2 ).
In clustering problems, such metric can be used to describe the distance between the samples and the core of the cluster [27] with fixed core diameter. A metric which neglects the distances smaller than some pre-defined observational error ε is equivalent with our ”taxi” metric:
PPT Slide
Lager Image
The Radar Screen [3] metric is a very similar norm metric with the distance function defined by
PPT Slide
Lager Image
The Weber problem with the Radar Screen metric is a special case of the problem considered in [11] . Unlike (3), our distance function (2) is convex and our approach significantly differs from that proposed in [11] .
The paper is organized as follows. In Chapter 2, we restate some basic definitions and describe existing algorithms and investigate some features of the objective function. In Chapter 3, we restate the algorithm for the Weber problem with new metric. In chapter 4, we give a simple example and results of the algorithm.
2. Preliminaries
The single-facility Weber problem (1) in ℝ 2 (planar problem) with ”taxi metric” (2) can be formulated as
PPT Slide
Lager Image
Here,
PPT Slide
Lager Image
The problem proposed by Weber is based on the Euclidean metric
PPT Slide
Lager Image
The most common algorithm for Weber problem with the metrics induced by the lp norms is Weiszfeld procedure [28 , 10] .
For the simplicity, we assume that
PPT Slide
Lager Image
Lemma 2.1. If
PPT Slide
Lager Image
then any point X SE is a solution of problem (4). Moreover, any X′ SE is not a minimizer of (4).
Proof . Let us assume that X SE . Then for arbitrary ∀ X ∈ ℝ 2 we have
PPT Slide
Lager Image
which implies f ( X ) = min{ f ( X ), X ∈ ℝ 2 }. □
Lemma 2.1 describes the case when the non-iterative solution is possible. More several cases when the non-iterative approach is applicable are described in [2] .
Let us denote the set
PPT Slide
Lager Image
Lemma 2.2. If X is the solution of the problem (4) and X R 0 then X is the solution of Weber problem (5) and vice versa .
Proof . Under the assumption X R 0 we have f ( X ) = fE ( X ). □
Lemma 2.3. The objective function of problem (4) is convex .
Proof . The sum of convex functions fi ( X ) = max{1, || X Ai || 2 }, i = 1, . . . , N is convex. □
For any arbitrary point X ∈ ℝ 2 , let us denote the sets of demand point indices
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
and a set of points (a region)
PPT Slide
Lager Image
The regions R ( X ) of any point X ∈ ℝ 2 are bounded by arcs [11 , 12] of radius 1 with centres in points Ai , i = 1, . . . , N (see Fig. 1 ). In [4] , authors prove that the quantity of regions is quadratically bounded by the number of demand points.
PPT Slide
Lager Image
Illustration of the problem (4), its regions and unions U1, U2.
An algorithm for solving constrained Weber problems with regions bounded by arcs is proposed in [17] .
Let our problem have M different regions Rk , k = 1, . . . , M :
PPT Slide
Lager Image
Note that R 0 was introduced above. The border point of each region belong to at least one other region.
The algorithm for enumerating all the disc intersection points is given in [5] . Let our problem has I disc intersections D 1 , . . . , DI .
Lemma 2.4. If X is a solution of the problem (4) and X Rk , k = 0, . . . , M and S > ( X ) ≠ ∅ then X is the solution of the following constrained Weber problem with the Euclidean metric:
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof . The value of the objective function for X Rk is
PPT Slide
Lager Image
Since the first summand in (14) is constant, we have an equivalent problem (12) with the constraint (13). □
The solution of constrained optimization problems with convex objective functions coincides with the solution of the corresponding unconstrained problem or lays on the border of the forbidden region [12] (moreover, the solution of the constrained problem is said to be visible from the solution of the unconstrained problem).
Corollary 2.5. If X is a solution of problem (4) then it is the solution of the unconstrained problem (12) or i ∈ {1, . . . , N } which satisfies Ai X 2 = 1.
Let us denote by Uq , q = 1, . . . , NU the unions of regions Rk , k = 1, . . . , M surrounded by the region R 0 :
PPT Slide
Lager Image
Denote also the borders of those unions by
PPT Slide
Lager Image
and set of points of all the borders as
PPT Slide
Lager Image
Lemma 2.6. If X ∗∗ is the unique solution of the problem (5) and X is a solution of the problem (4) then
PPT Slide
Lager Image
Proof . Let us consider a constrained problem with the Euclidean metric
PPT Slide
Lager Image
PPT Slide
Lager Image
Let X′ be a solution of this problem.
As the objective function of this problem is convex, two cases are possible.
Case 1. X′ = X ∗∗ .
Case 2. Solution X′ of this constrained problem lies on the borderline of the feasible set, i.e. X′ B . Moreover, X′ is visible from X ∗∗ .
In Case 1, in accordance with Lemma 2.2, X′ X ∗∗ unless X′ B . Thus, if X ∗∗ Uq′ then X′ Uq′ . From X′ R 0 , we have X′ Bq′ . Let us denote the set (see Fig. 1 )
PPT Slide
Lager Image
From f ( X ) = fE ( X ) ∀ X R 0 , X′ is the solution of the constrained problem
PPT Slide
Lager Image
From the convexity of the objective function f (·) immediately follows that S is convex. Let us denote a set X′S of optimizers of the constrained problem (15) – (16). From
PPT Slide
Lager Image
we have
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
Therefore, the set S does not contain any barriers Bq of the unions Uq ( q = 1, . . . , NU ) except the points from X′S and ∃ X′ X′S : X′ Uq′ . Since X′ Uq′ and ( S R 0 ) ⊂ B , we have
PPT Slide
Lager Image
Since X is the optimizer of (4), f ( X ) ≤ f ( X′ ). Thus, X S and X Ul′ . □
Lemma 2.7. Let X′ S be the set of solutions of the constrained problem (12)-(13). Let Gk be the set of border points of region Rk. Then the set G X′S is finite unless S > ( X ) = ∅∀ X X′S .
Proof . The case || Ai X || 2 ≤ 1∀ i = 1, ..., N , X X′ Let X X′S be an arbitrary point. If S > ( X ) ≠ ∅ then, being the Weber problem with the Euclidean metric, problem (12) has a strictly convex objective function unless all its demand points Ai , i S > ( X ) are collinear. In this case, the problem has exactly one solution.
If the demand points are collinear, the solution coincides with one of demand point Ai , i′ S > ( X ) or all points of some line segment Ai′ Ai′′ , i′ S > ( X ), i′′ S > ( X ) are solutions. The border G is formed by arcs. Thus, it has finite number of intersections with the line segment. □
The algorithms proposed in the next section are based on the lemmas above. Algorithms for both constrained and unconstrained Weber problem with Euclidean metric are well investigated, see [12 , 13 , 29] . We use these algorithms as subroutines in our algorithm.
3. Algorithm description
Our algorithm starts the local search procedure from the initial point which is calculated by the Weiszfeld procedure as the solution of the unconstrained Weber problem with the Euclidean metric (5). If the solution X satisfies X R 0 (i.e. ∥ X Ai 2 ≥ 1, i = 1, . . . , N ) then, in accordance with Lemma 2.2, X is the solution of problem (4). Otherwise, algorithm continues further search from point X .
Having solved problem (12) with constraint X R ( X ), we obtain a new solution X or a set of solutions. If the unique solution all points from the solution set belong to the border of the union of regions Uq′ then, in accordance with Lemma 2.6, we have the optimal solution.
If the unique solution X or every point of the solution set does not contain any border points of region R ( X ), due to convexity of the objective function, we have the solution final and algorithm stops.
If the solution X lays on the borderline of region R ( X ) or the solution set contains any border points then we must solve the constrained Weber problem for the regions containing X . If there are some better solutions, continue with the best solution. Otherwise, stop.
Since the objective function is convex, we can use any local search procedure. The following heuristics provides the significant speed-up. First, the value of the objective function is calculated for the circle intersection points of the region R ( X ) (i.e. its angular points) where X if the solution of the unconstrained Weber problem (5). This intersection X ∗∗ with the best result is chosen as an initial point for the further search. The local search procedure continues then with the neighbor intersection points (i.e. the intersection points which are the ends of the arcs starting from X ∗∗ ). When the local search stops at some intersection X ∗∗ , our algorithm checks if this point is the local minimum in each of its neighbor regions. If it is not the local (and global) minimum, the search continues with solving constrained Weber problem as described above.
If a temporal solution X ∗∗ is an intersection point, the algorithm checks if this point is the local minimum in each of its regions. The angular point of the convex region is the point of minimum of the function in this region if all possible directional derivatives are non-negative. But our regions can be non-convex.
Let us denote P ( Rk ) such a convex polygon that all its vertices coincide with the angular points of the region Rk . Then region
PPT Slide
Lager Image
is convex.
Let us denote two rays l 1 and l 2 with initial point X ∗∗ and an angle ϕ ∈ (0, π ) between them such that all points of the region ϱ ( Rk ) are situated between l 1 and l 2 and both l 1 and l 2 are tangent to the borderline of the region ϱ ( Rk ). All possible directions from X ∗∗ in the region ϱ ( Rk ) lay between l 1 and l 2 .
From the convexity of region ϱ ( Rk ) and the objective function (12), if
PPT Slide
Lager Image
then X ∗∗ is the minimum point of (12) in ϱ ( Rk ). Here,
PPT Slide
Lager Image
are directional derivatives with directions l 1 and l 2 correspondingly. From ϱ ( Rk ) ⊂ Rk , this point X ∗∗ is the minimum point in Rk .
If X ∗∗ is the point of local minimum for all regions which it joins then X ∗∗ is the solution of problem (4) and solving the constrained Weber problem (12), (13) is not needed. The experiments on the randomly generated problems and the rescaled problems from [24] show that solving the constrained Weber problem is not needed in most cases.
In our algorithm, regions Rk are enumerated as follows. The number k is an array of N digits, one digit for each of the demand points. The i th digit is set to 1 if || X Ai || < 1 for all internal points X of region Rk . If || X Ai || > 1 then the i th digit is set to 0. For example, region R 6 (see Fig. 1 ) in new notation is R 11100 . Using this method of enumeration, it is not necessary to enumerate all regions at the first steps of the algorithm.
Analogous method of enumeration is used for intersection points Dj . The index j contains N digits. If || Dj Ai || > 1 then the i th digit is set to 0. If || Dj Ai || < 1 then the i th digit is set to 1. If || Dj Ai || = 1 then the i th digit is set to 2. For example, the angulous point D 1 (see Fig. 1 ) of regions R 1 , R 2 , R 5 and R 6 in the proposed algorithm is denoted as D 12200 (it is an internal point of the circle with center in A 1 , border point of circles with centers in A 2 and A 3 and it is situated outside circles with centers in A 4 and A 5 ).
With this notation, it is easy to determine the region or regions for any arbitrary point X . We use the following algorithm (here, k is an array of digits).
Note that the region R 0 , see (7), in this notation is R 000...0 .
Algorithm 3.1. Determine the region index
  • Require:CoordinatesX= (x1,x2) ot the point, coordinates of the demand points
  • Step 1:fori= 1, . . . ,Ndo:
  • Step 1.1:If ∥Ai−X∥ = 1 thenk[i] = 2;
  • Step 1.2:else if ∥Ai−X∥ < 1 thenk[i] = 1;
  • Step 1.3:elsek[i] = 0;
  • Step 1.4:Continue Step 1;
  • Step 2:Rarray[1] = {k};Nr= 1;
  • Step 3:Foriindo:
  • Step 3.1:ifk[i] = 2 then
  • Step 3.2:Parray=Rarray;
  • Step 3.3:forjindo:
  • Step 3.3.4:Rarray[j][k] = 0;Parray[j][k] = 1; Continue Step 2.3;
  • Step 3.4:Add all elements ofParrayto the end of the arrayRarray;Nr=Nr∗ 2;
  • Step 3.5:Continue Step 2;
  • Step 4:STOP, returnRarrayand number of its elementsNr.
The algorithm above returns a set (an array) Rarray of region indexes k such that X Rk . Steps 1 to 1.4 form an array of digits describing the distance from the given point to each of the demand points: digits 0,1 and 2 mean distance more than 1, less than 1 and equal to 1, correspondingly. In Steps 3 to 3.5, array Rarray of indexes is formed. Initially, it contains one element coinciding with the array k formed in Steps 1 to 1.4. For each demand point having distance equal to 1 from the given point (digit 2 in array k ), array Rarray is duplicated: instead of digit 2, digit 0 is substituted in the first copy of the initial array Rarray and digit 1 in its second copy. Thus, array Rarray contains 2 e 1 indexes where e 1 is quantity of the demand points having distance equal to 1 from point X .
For any intersection point Dj , the index j is known and we can start this algorithm for such point from Step 2 assuming k = j .
For determining the set of the neighbor intersection points for a given intersection point Dj , we use the following algorithm.
Algorithm 3.2. Form a list of neighbor angular points
  • Require:An indexj∗of the intersection pointDj∗(here,j∗is an array of digits 0,1,2), a set of all intersection pointsDall.
  • Step 1:Dneighbour= ∅;
  • Step 2:For eachDiincalDall\ {Dj∗} do: Comment: here, the indexesj∗andiare considered as arrays of digits.
  • Step 2.1:ncommon= 0;bok= 1.
  • Step 2.2:Fork= 1, . . . ,Ndo:
  • Step 2.2.1:Ifi[k] = 2 andj∗[k] = 2 thenncommon=ncommon+ 1; ;
  • Step 2.2.2:else ifj∗[k] ≠ 2 andj∗[k] ≠i[k] thenbok= 0; break Step 2.2 and go to Step 2.3.
  • Step 2.2.5:Continue Step 2.2.
  • Step 2.3:ifncommon> 0 andbok= 1 thenDneighbour=Dneighbour∪{Di}.
  • Step 2.4:Continue Step 2.
  • Step 3:STOP, returnDneighbour.
In Steps 2 to 2.4, all known intersetion points are scanned. For the indexes of the intersection points, the notation from 3.1 is used: digit 2 in the k th position of the index means that distance from the intersection point to the k th demand point is equal to 1. In Steps 2.2 to 2.2.5, searching for digits 2 in indexes is organized.
Our algorithm for solving problem (4) is organized as follows.
Algorithm 3.3. Solving the location problem (4)
  • Require:Set ofNdemand pointsAwith coordinatesof the demand points and their weightswi,i= 1, . . . ,N.
  • Step 1:Solve the Weber problem with Euclidean metric (5) implementing Weiszfeld procedure, store the result toX∗.
  • Step 2:ifthen STOP and returnX∗.
  • Step 3:Determine the regionRk∗=R(X∗) with Algorithm 3.1. The result is indexkwhich is an array ofNdigits. If a set of regions is returned then we use the first one.
  • Step 4:Form the setDallof all intersection points of the circles with centres inAi,i= 1, . . . ,Nand radius 1.
  • Step 5:Form the setDof all angular points (intersections) of the regionRk; SetDchecked=D.
  • Step 6:F∗∗= +∞.
  • Step 7:For each elementDjof the setDdo:
  • Step 7.1:Iff(Dj)
  • Step 7.2:Continue Step 7.
  • Step 8:bfound= 1.
  • Step 9:whilebfound= 1 do:
  • Step 9.1:bfound= 0; Call Algorithm 3.2 to form the setDneighbourof the neighbor intersections ofX∗∗.
  • Step 9.2:ForX′inDneighbour\Dcheckeddo:
  • Step 9.2.1:Iff(X′)
  • Step 9.3:Dchecked=Dchecked∪Dneighbour.
  • Step 9.4:Continue Step 9.
  • Step 10:Form the setLof regions joint by the setX∗∗with Algorithm 3.1;
  • Step 11:Ltosearch= ∅.
  • Step 12:For each regionRkinLdo:
  • Step 12.1:For the convex regionϱ(Rk) =Rk∩P(Rk), calculate two directions (rays with initial pointX)l1andl2tangent to the borderline of the regionRk.
  • Step 12.2:Ifthen
  • Step 12.2.1:Ltosearch=Ltosearch∪ {Rk}.
  • Step 12.3:Continue Step 12.
  • Step 13:WhileLtosearch≠ ∅ do:
  • Step 13.1:For each elementRkinLtosearchdo:
  • Step 13.1.1:Solve the constrained Weber problem (12)–(13) using the modified Weiszfeld procedure[11,4], store the result toX′.
  • Step 13.1.2:Iff(X′)
  • Step 13.1.3:Continue Step 13.1.
  • Step 13.2:Continue Step 13.
  • Step 14:STOP and returnX∗∗.
4. Numerical example
Let us solve the problem shown in Fig. 2
PPT Slide
Lager Image
Example problem scheme and its objective function graph.
Here, N = 7, A 1 = (0, 0.25), A 2 = (0.25, 0), A 3 = (0.25, 0.75), A 4 = (1.35, 0.25), A 5 = (1, 0.77), A 6 = (3.45, 0.2), A 7 = (3.55, 0.4), w 1 = w 6 = 1, w 2 = 9, w 3 = 4, w 4 = 3, w 5 = w 7 = 2.
The result of Weiszfeld procedure at Step 1 of Algorithm 3.3 is
PPT Slide
Lager Image
At Step 2, this point is not in R 0000000 since ∥ A 1 X ∥ < 1. Thus, the algorithm goes on.
At Step 3, from ∥ A 1 X ∥ < 1, ∥ A 2 X ∥ < 1, ∥ A 3 X ∥ < 1, ∥ A 5 X ∥ < 1, R ( X ) = R 11101000 .
At Step 4, our algorithm forms a set Dall of all 22 intersection points.
At Step 5, the set of angular points (intersections) of region R 1110100 is
PPT Slide
Lager Image
After Step 6 and three iterations in Steps 7 to 7.2, we have
PPT Slide
Lager Image
At Step 8, a boolean variable bfound is set to 1 and our algorithm start the iteration (Step 9).
At Step 9.1, bfound is reset to 0. Algorithm 3.2 returns the list of the neighbor intersections for D 1212100 :
PPT Slide
Lager Image
At Step 9.2 to 9.2.1, the algorithm estimates the objective function for these intersections except D 1210200 , D 1112200 and after these iterations, we have
PPT Slide
Lager Image
At Step 9.3, the algorithm adds Dneighbour to the set Dchecked and we have Dchecked = { D 1212100 , D 1210200 , D 1112200 , D 2012100 , D 2211100 }.
Step 9 is then repeated.
At the second iteration of Step 9.1, bfound is reset to 0. Algorithm 3.2 returns the list of the neighbor intersections for D 1212100 :
PPT Slide
Lager Image
At Step 9.2 to 9.2.1, the algorithm estimates the objective function for these intersections except D 2012100 , D 1212100 and after two iterations, we have
PPT Slide
Lager Image
At Step 9.3, Dchecked = { D 1212100 , D 1210200 , D 1112200 , D 2012100 , D 2211100 , D 0221100 , D 2121100 }, Step 9 is then repeated.
At the third iteration of Step 9.1, bfound is reset to 0. Algorithm 3.2 returns the list of the neighbor intersections for D 1212100 :
PPT Slide
Lager Image
At Step 9.2 to 9.2.1, the algorithm estimates the objective function for the intersections D 0201200 and D 002210 and after two iterations, we have no improvement of X ∗∗ = D 0221100 and F ∗∗ = 26.209559.
Thus, bfound = 0 and the iterations of Step 9 finish.
At Step 10, the list of the regions joint by X ∗∗ = D 022110 is
PPT Slide
Lager Image
Algorithm sets Ltosearch = ∅.
In region R 0001100 , the direction l 1 is a ray on the line connecting X ∗∗ and D 0201200 ( d 7 in Fig. 3 ), l 2 is a ray on the line connecting X ∗∗ and D 0022100 ( d 2 in Fig. 3 ).
PPT Slide
Lager Image
Neighbor regions and directions for directional derivatives calculations (Steps 12 to 12.3 of Algorithm 3.3).
In region R 0011100 , the direction l 1 is a ray on the line tangent to the circle with center in A 3 ( d 1 in Fig. 3 ), l 2 is a ray on the line connecting X ∗∗ and D 2211100 ( d 4 in Fig. 3 ).
In region R 0111100 , the direction l 1 is a ray on the line tangent to the circle with center in A 2 ( d 3 in Fig. 3 ), l 2 is a ray on the line tangent to the circle with center in A 3 ( d 6 in Fig. 3 ).
In region R 010110 , the direction l 1 is a ray on the line tangent to the circle with center in A 2 ( d 8 in Fig. 3 ), l 2 is a ray on the line connecting X ∗∗ and D 2121100 ( d 5 in Fig. 3 ).
In Steps 12 to 12.2, our algorithm calculates all directional derivatives
PPT Slide
Lager Image
All values are positive (Step 12.2).
Thus, Ltosearch = ∅ and iterations in Steps 13 to 13.2 are not performed.
The resulting point is X ∗∗ = (0.177025, 0.375000), value of the objective function is F ∗∗ = 26.209559.
5. Conclusion
The location problems for the systems with the minimum transportation cost can be formulated as the problems with a special metric
PPT Slide
Lager Image
The proposed algorithm is able to solve such problems. The implemented local search heuristic reduces the computational complexity to the complexity of solving few constrained and one unconstrained Weber problems with Euclidean metric. However, the computational complexity of the proposed algorithm is subject to the further research.
BIO
Lev A. Kazakovtsev was awarded the candidate of technical sciences degree at the Research Institute of Control Systems, Wave Processes and Technologies (Krasnoyarsk, Russian Federation) in 2002. He is an associate professor of the Krasnoyarsk State Agrarian University (Chair of Mathematical Modeling and Informatics) and Deputy Director of the Department of Information Technologies of the Siberian State Aerospace University. His research interests include the location problems, discrete optimization, random search algorithms.
Department of Information Technologies, Siberian State Aerospace University named after M. F. Reshetnev, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660093, Russian Federation.
e-mail: levk@bk.ru
Predrag S. Stanimirovic received his M.Sc. in 1990 and Ph.D in 1996 at the University of Niˇs, Faculty of Sciences and Mathematics. He is a Full Professor at the same faculty since 2002. His research interests include operation research, linear programming, nonlinear programming, generalized inverses and symbolic computations.
Faculty of Sciences and Mathematics, University of Niˇs, Viˇsegradska 33, 18000 Niˇs, Serbia.
e-mail: pecko@pmf.ni.ac.rs
References
Brown R.G. 1997 Advanced Mathematics: Precalculus with discrete Mathematics and data analysis, (A.M.Gleason, ed.) McDougal Littell Evanston, Illinois
Chen R. Noniterative Solution of Some Fermat-Weber Location Problems, Advances in Operations Research (2011) http://downloads.hindawi.com/journals/aor/2011/379505.pdf. Article ID 379505, Published online    DOI : 10.1155/2011/379505
Deza M.M. , Deza E. 2009 Encyclopedya of Distances Springer Verlag Berlin, Heilderberg
Drezner Z. , Mehrez A. , Wesolowsky G.O. (1991) The facility location problem with limited distances Transportation Science 25 183 - 187    DOI : 10.1287/trsc.25.3.183
Drezner Z. , Wesolowsky G.O. (1980) A maximin location problem with maximum distance constraints AIIE Transact. 12 249 - 252    DOI : 10.1080/05695558008974513
Drezner Z. , Klamroth K. , Schobel A. , Wesolowsky G.O. 2002 The Weber problem, in Z. Drezner and H.W. Hamacher (editors), Facility Location: Applications and Theory Springer-Verlag 1 - 36
Drezner Z. , Scott C. , Song J.S. (2003) The central warehouse location problem revisited IMA Journal of Managemeng Mathematics 14 321 - 336    DOI : 10.1093/imaman/14.4.321
Drezner Z. , Hamacher M. 2004 Facility location: applications and theory Springer-Verlag Berlin, Heidelberg
Gordon S. , Greenspan H. , Goldberger J. Applying the Information Bottleneck Principle to Unsupervised Clustering of Discrete and Continuous Image Representations Computer Vision. Proceedings. Ninth IEEE International Conference on, Vol.1 (2003) 370 - 377
Farahani R.Z. , Hekmatfar M. 2009 Facility Location Concepts, Models, Algorithms and Case Studies Springer-Verlag Berlin Heidelberg
Fernandes I.F. , Aloise D. , Aloise D.J. , Hansen P. , Liberti L. 2012 On the Weber facility location problem with limited distances and side constraints, Optimization Letters, issue of 22 published online    DOI : 10.1007/s11590-012-0538-9.
Hansen P. , Peeters D. , Thisse J.F. (1981) Constrained location and the Weber-Rawls problem North-Holland Mathematics Studies 59 147 - 166
Idrissi H. , Lefebvre O. , Michelot C. (1988) A primal-dual algorithm for a constrained FermatWeber problem involving mixed norms, Revue francaise d’automatique, d’informatique et de recherche operationnelle Recherche Operationnelle 22 313 - 330
Kazakovtsev L.A. (2013) Wireless coverage optimization based on data provided by built-in measurement tools WASJ Special Volume on Techniques and Technologies 22 8 - 15
Antamoshkin A.N. , Kazakovtsev L.A. (2013) Random search algorithm for the p-median problem Informatica (Ljubljana) 37 267 - 278
Kazakovtsev L.A. (2012) Adaptation of the probability changing method for Weber problem with an arbitrary metric Facta Universitatis, (Niš) Ser. Math. Inform. 27 289 - 254
Kazakovtsev L.A. (2013) Algorithm for Constrained Weber Problem with feasible region bounded by arcs Facta Universitatis, (Niš) Ser. Math. Inform. 28 271 - 284
Klamroth K. 2002 Single-facility location problems with barriers Springer Verlag Berlin, Heilderberg
Liao K. , Guo D. (2008) A Clustering-Based Approach to the Capacitated Facility Location Problem Transactions in GIS 12 323 - 339    DOI : 10.1111/j.1467-9671.2008.01105.x
Minkowski H. 2001 Gesammelte Abhandlungen, zweiter Band Chelsea Publishing
Perreur J. , Thisse J.F. (1974) Central metric and optimal location J. Regional Science 14 411 - 421    DOI : 10.1111/j.1467-9787.1974.tb00463.x
Stanimirovic I.P. (2013) Successive computation of some efficient locations of the Weber problem with barriers J. Appl. Math. Comput. 42 193 - 11    DOI : 10.1007/s12190-012-0637-x
Staminirović P.S. , Cirić M. , Kazakovtsev L.A. , Osinuga I.A. (2012) Single-facility Weber location problem based on the Lift metric Facta Universitatis, (Niš) Ser. Math. Inform. 27 31 - 46
Taillard E. Location problems web resource available at
Thaillard E.D. (2003) Heuristic Methods for Large Centroid Clustering Problems Journal of Heuristics 9 51 - 73    DOI : 10.1023/A:1021841728075
Vimal A. , Valluri S.R. , Karlapalem K. An Experiment with Distance Measures for Clustering International Conference on Management of Data COMAD 2008 Mumbai, India (2008) 241 - 244
Voevodski K. , Balcan M.F. , Roglin H. , Teng S.H. , Xia Y. Min-sum Clustering of Protein Sequences with Limited Distance Information Proceedings of the First International Conference on Similarity-based Pattern Recognition (SIMBAD’11) Venice, Italy (2011) 192 - 206
Weiszfeld E. (1937) Sur le point sur lequel la somme des distances de n points donnes est minimum Tohoku Mathematical Journal 43 335 - 386
Wesolowsky G. (1993) The Weber problem: History and perspectives Location Science 1 5 - 23
Ying Y. , Li P. (2012) Distance Metric Learning with Eigenvalue Optimization Journal of Machine Learning Research 13 1 - 26