Decomposition of the continuous weber problem with french metro metric

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Krasnoyarsk State Agrarian University

Decomposition of the continuous weber problem with french metro metric

Kazakovtsev L.A.

Stanimirovic P.S.

Osinuga I.A.3

Correct solution of the location (optimal facility placement) problems as one of most important tools of the Operations Research determine the efficiency of using transportation resources in logistics, agriculture and industry. Problems with non-standard (other than Euclidean) metric take place in real life but they are less investigated. Here, we propose a method for transformation of the Weber problem with French metro metric into series of problems with l1 metric which are solved by an algorithm based on the Weiszfeld procedure.

In general, the aim of location problem involves the location of one or more new facilities in the plane, when the number of possible locations is usually infinite. Such models typically include Euclidean distances, or other related distances, and are continuous in nature.

Lot of systems in the public and private sectors are characterized by facilities that provide homogeneous services at their locations to a given set of fixed points (so called demand points). Examples include warehouse location, positioning a computer and communication networks, locating base stations of wireless networks etc [1]. Such problem has been found useful in approximation theory, location research, statistical estimation problem [2], signal and image processing as well as in other engineering applications [3].

The distance between two points is the length of the shortest path connecting them. The metric by which the distance between two points is measured may be different in various instances [1, 4, 5, 6]. In calculating distance between two points, the most common distance metrics in a continuous space are those known as the class of distance metrics, primarily rectangular (l1), Euclidean (l2) and Chebyshev (l?) metric. location plane infinite metric

As follows from the name of the considered metric, French capital city is the center of the country and the most important roads lead to Paris. So, if you want to travel from some part of France to another part, you probably have to go through Paris. Moscow is even more 'radial' system than Paris. The scheme of Moscow subway is radial. Location problem in any transportation system with the only crossroad (center) is a problem with French metro metric.

We restate a single-facility Weber problem as problem of searching for such a point X that the sum of weighted distances from this point to some existing points A1,...,Am (demand points) is minimal.

(1)

Here, wi is a weight corresponding to the ith point.

The French metro metric (or the radial metric) in the plane R2 is defined by [7,8].

(2)

Here, c is any real, 0 is the zero point (0,0) and

, (3)

where A=(a1,a2) and B=(b1,b2).

We illustrate the situation graphically in Fig. 1.

Fig. 1: Illustration of the French Metro metric

Here, 2 cases are shown, Case 1: both points A,B belong to the same line (ray), A = cB, c is a constant (here, c = 0.5) and Case 2: A ?cB,. In French metro metric, if both points lay on the same ray (Case 1), the distance between them is calculated as the Euclidean distance. Otherwise (Case 2), the distance is calculated as the sum of the distances from both points to the zero point.

For the Weber problem (and location problem, in general) several techniques were proposed [2, 3, 6, 9].

In [8], the author convinced that minimum norm problem can be cast as fixed point problem and showed the existence and uniqueness of the minimum solution of operator equation of the form x = T x if T is non expansive. The [9] investigates a reformulation of the unconstrained form of the classical Weber problem into an unconstrained minimum norm problem. The classical Weber problem is established with the Euclidean norm underlying in the definition of the distance function. The work [2] is dedicated to an estimation problem formulated as an equivalent minsum norm problem and its resolution by an appropriate application of classical projection theorem. Detailed explanation of various metrics is presented in [1, 10]. Several factors affect in the process of metric choosing, the most important one is the nature of the problem.

The lp norms play an important role in the theory and practice of location problems. In general, these norms are arbitrary and have received the most attention from location analysts. But other types of distances have been exploited in the facility location problems. A review of exploited metrics is presented in [11]: central metrics [10], lift metric [1], distance functions based on altered norms [12],- mixed norms [13], block and round norms [14].

The simplest and most commonly used technique of solving the Weber problem is known as the “Weiszfeld procedure” [15]. The procedure is readily generalized to lp distances [12]. Solution of continuous Weber problem in l1 distance is described in [16]. The three-dimensional Fermat-Weber facility location problem with Chebyshev distance is investigated in [15] and Weber problem in discrete coordinates considered in [5].

If the underlying distance function is defined by l1 metric, the distance between Ai and X is given by

(4)

The optimization problem can be transformed into two separate optimization problems with objective functions

(5)

(6)

The well-known algorithm [7] is used to solve these problems.

Our aim is transformation of the problem (1-3) into series of problems (5).

First, we divide our set of points {A1,...,Am} into d subsets so that all points of each of the subsets

lay on the same ray. If the initial set {A1,...,Am} contains zero point (0, 0) then such point forms a separate subset. To perform this step, first of all, we must move from Cartesian coordinates to polar (radial) ones. In polar coordinates, each point is described by the angle aR2 and radial distance aR1. Let's assume that the angle is the second coordinate and the radial distance is the first coordinate for each point.

So, in polar (radial) coordinates Ai = (aiR1,aiR2), where

(7)

(8)

Let's assume that for the zero points (0, 0), the angle coordinate aiR2 = ?1.

The distance between the facility placed X and the ith demand point Ai is

(9)

Here, X = (xR1,xR2).

And the objective function (1) splits into 2 sums:

(10)

Where

. (11)

Taking into account xR2 = aiR2 and having eliminated the constant, we have the new objective function

, (12)

, (13)

Here, we replaced our set of points {Ai} with a new set {Aвij}, Aвij = ( a1вij, aiR2) ,

So, if the angle coordinate xR2 of the optimal point X is known, having solved the problem (12-13), we have the coordinate xR1.

Having solved the problem (12-13) for all variants of xR1= aiR2, we can have a set of candidate solutions and chose the best one using full search.

So, our algorithm is:

Step 0 (initialization). XF

Step 1. Divide the set of the demand points C={A1,...,Am} into subclasses

C={C1, C2,...,Cd} with the equivalent second (angle) coordinate aiR2=бj.

Step 2. For each j: 1jd do

Solve the problem (12-13) using algorithm for l1 metric..

Add the result (optimal point X) as the candidate solution to the set XF.

Step 3. For each X from XF do

estimate F(X) using formulas 1,2 and chose the best result as the global optimum.

Step 4. Stop.

So, the continuous Weber problem with French metro metric can be decomposed into series of problems with l1 metric which can be solved with standard Weiszfeld procedure for the rectangle metric.

References

1. P. S. Staminirovic and M. Ciric: Single-facility Weber location problem based on the Lift metric, 2011. http://arxiv.org/abs/1105.0757.

2. O. R. Oniyide and I. A. Osinuga: On the existence of best sample in simple random sampling. J.Math. Assoc. Nigeria, 33(2B) (2006), 290-294.

3. S. G. Ferreira, P. Jorge: The existence and uniqueness of the norm solution to certain and non-linear problems. Signal Processing 55 (1996), 137-139.

4. R. G. Brown: Advanced Mathematics: Precalculus with discrete Mathematics and data analysis, (A.M.Gleason, ed.), Evanston, Illinois: McDougal Littell. ISBN 0-395- 77114-5, 1997.

5. L. Kazakovtsev: International conference on problems of modern Agrarian Science: Collected scientific works. http://kgau.ru/img/konferenc/2010/e21.doc.

6. I. A. Osinuga: On LP bound Lipschitzian Optimization, Unpublished M.Sc. Thesis, University of Ibadan, Nigeria, 2000.

7. E. W. Weisstein: French Metro Metric; From MathWorld - A Wolfram Web Resource, http://mathworld.wolfram.com/FrenchMetroMetric.html

8. M. M. Deza and E. Deza: Encyclopedy of Distances, Springer Verlag, 2009, 325.

9. I. A. Osinuga and O. M. Bamigbola: On the minimum solution to Weber problem, 25th SAMSA Conference Proceeedings, Windhoek, Namibia, 2 (2007), 54-60.

10. M. J. Hodgson, R. T. Wong and J. Honsaker: The P-Centroid problem on an inclined plane. Operations Research 35 (1987), 221-233.

11. Z. Drezner and H. Hawacher: F acility location: applications and theory, Springer- Verlag, Berlin, Heidelberg, 2004.

12. R. F. Love and J. G. Morris: C omputation procedure for the exact solution of location-allocation problems with rectangular distances. Naval Research Logistics Quarterly 22 (1975), 441-453.

13. P. Hansen, J. Perreur and J. F. Thisse: Location theory, dominance and convexity: Some further results. Oper. Res. 28 (1980), 1285-1295.

14. J. F. Thisse, J .E. Ward and R. E. Wendell: S ome properties of location problem with block and round norms. Operations Research 32 (1984), 1309-1327.

15. G. Wesolowsky: The Weber problem: History and perspectives. Location Science 1 (1993), 5-23.

16. R. Z. Farahani and M. Hekmatfar editors: F acility Location Concepts, Models, Algorithms and Case Studies, Springer-Verlag Berlin Heidelberg, 2009.

Размещено на Allbest.ru