# Algorithms for Location Problems Based on Angular Distances

Authors: Lev A. Kazakovtsev; Predrag S. Stanimirović; Idowu A. Osinuga; Mikhail N. Gudyma; Alexander N. Antamoshkin
Journal: Advances in Operations Research
 (2014)

---

## Abstract

This paper describes four mathematical models for the single-facility location problems based on four special distance metrics and algorithms for solving such problems. In this study, algorithms of solving Weber problems using four distance predicting functions (DPFs) are proposed in accordance with four strategies for manipulator control. A numerical example is presented in this proposal as an analytical proof of the optimality of their results.


---

## Body

## 1. Introduction

Generally, the purpose of a location problem is to determine locations of one or several new facilities on a plane or in a space where some objects (facilities) have been already placed [1]. Usually, the number of possible arrangements for new facilities is infinite [2].Location problems occur frequently in real life. Some of them include the distribution systems such as locating warehouses within supply chain to minimize average transportation time to market, locating hazardous material so as to minimize its exposure to the public, determining bank account and lockboxes location to maximize clearing time or float, and problems of locating a computer, telecommunication equipment, and wireless base stations [3]. Many of such practical problems of this kind involve emergency facilities such as hospitals, fire stations, accident rescue, or civil defense. The usual objective here is to minimize the maximum among weighted distances between facilities to be located and all demand points. Details of other useful applications can be found in [4, 5]. Similar problems are formulated in approximation theory, problems of estimation in statistics [6], signal and image processing, and so forth [7–9].Distance is the length of the shortest path between two points. However, the path depends on properties of space and a way of movement in it. In continuous spaces, the most commonly used metrics are rectangular or Manhattan (l
1), Euclidean (l
2), and Tchebychev (l
∞). Indeed, many results have been generalized for n-dimensional space; however, practical applications usually occur within the context of two-dimensional and three-dimensional spaces. Therefore, in the subsequent sections, DPF is used for modeling distances in 2-dimensional space (unless it is otherwise stated).The Euclidean distance between two points does not reflect the cost of moving between them in the systems which use rotating mechanisms (telescopic boom, etc.) as transportation means. These systems include automated lifting cranes and manipulators.This kind of problems lies behind many important applications. Unfortunately, there exist only a few algorithms which can guarantee optimality.This paper therefore intends to describe challenging DPFs that are less exploited in the location problem, in addition to describing their similarities for new developments in location research.The paper is organized as follows. An overview of various distance metrics and location optimization algorithms is given in Section2. Section 3 describes four versions of the mathematical distance functions which cause the objective functions to differ significantly from those that have been exploited so far. In addition, Section 3 features the relationship among the enumerated metrics. Sections 4–6 describe algorithms for solving location problems with the listed distance predicting functions. In Section 7, we present a numerical example.


## 2. Preliminaries

Models involving various DPFs may occur in emergency situations. For instance, the model proposed in [10] calculates the response time between the fire calls and arrival of fire engines. In [11], DPF was presented to be of value in farming activities. Some of the circumstances discussed include planning an irrigation channel between a pond and a field as well as calculating distances among different geographic regions. With the increasing importance of geographic information systems (GIS), a DPF may be incorporated into a GIS to calculate distance measurements in geographic regions.Westwood [12] has considered optimal mix of trucking and tramping of a truck transportation network for the movement of goods and raw materials among distributing centers, depots, and producers, utilizing a DPF. In some distribution problems, only the general locations and demands of customers are known. A DPF may be employed to estimate the expected travel distance.DPF is necessary for the estimation of actual distances between the new and existing facilities [13–15]. The most widely used measure of distance between a facility and a customer is the l
p metric which defines the distance between two points X
=
(
x
1
,
…
,
x
N
) and Y
=
(
y
1
,
…
,
y
N
) in an N-dimensional space by
(1)
l
p
(
X
,
Y
)
=
(
∑
1
=
1
N
‍
|
x
i
-
y
i
|
p
)
1
/
p
,
p
≥
1
.
In the case p
=
1, the l
p distance is the rectilinear (rectangular) distance, while in the case p
=
2 it reduces to the usual Euclidean distance. The two cases above and the Tchebychev norm (p
=
+
∞) [16] are the most widely used within the l
p metrics so far [17].The straight-line Euclidean distance model (p
=
2) is not applicable in cases such as street travel in a city where each travel follows a grid pattern. The appropriate distance function which calculates the distance in this situation is the rectangular distance function (p
=
1).There exist several well-documented location problems based upon the assumption of a planar model. For instance, the most famous is the classical Weber problem where a single facilityX
∈
R
2 is to be located such that the weighted sum of distances between new and existing facilities is minimized as follows:
(2)
arg
min
⁡
X
∈
R
2
F
(
X
)
=
∑
i
=
1
m
‍
w
i
∥
X
-
A
i
∥
2
=
∑
i
=
1
m
‍
w
i
(
x
1
-
a
1
i
)
2
+
(
x
2
-
a
2
i
)
2
.
Here, w
i
,
i
=
1
,
m
¯ are a nonnegative weighting coefficients for m facilities and A
i
=
(
a
1
i
,
a
2
i
), i
=
1
,
m
¯ are coordinates of the existing facilities. Also, ∥
·
∥
2 is the Euclidean distance which corresponds to a classical Weber problem.The choice of distance functions is an important factor in location model representation. Thel
p metrics have received the most attention from location analysts. However, many other types of distances have been exploited in the facility location problems. A review of metrics exploited in many variations of location problems includes central metrics [18], weighted one-infinity norm [19], mixed distances [20, 21], continuous and network distances [22–24], various round and block norms [11, 25], and location problems on a sphere and arbitrary surface [9, 26].Very little has been done to include special cases of the class of metrics in location models. Späth [27] introduced Jaccard metric in minisum problem while in the research of [28], using Jaccard metric and Jaccard median was reported to be of value for classification and other problems in scientific fields such as biology, botany, psychology, paleontology, cognitive sciences, and computer science. A finite descent algorithm for the solution of minisum problem with Jaccard metric was developed in [29].Some of recent efforts in this direction are those presented in [16] for facility location models where the cities have road networks with streets that are either straight line emanating from a fixed center or straight lines through the central point. Also road networks with only one main street and the other crossing it at right angles were suggested in [30].Moscow metric or Moscow-Karlsruhe metric, considered in this paper, was used in [31] based on its applicability in the construction of Voronoi diagram on R
2 for cities similar to Karlsruhe.Many authors proposed approximate approaches to the location problems with various or arbitrary distance functions [8, 26]. Such approaches transform the problem into a discrete location problem [32]. However, methods for discrete location problems take many computational resources [32, 33] with no guarantee of the appropriate precision of the result.In [30], investigation was carried out on the Weber problem in the plane, under the assumption that the distance function is measured with the lift metric. The proposed algorithm for finding the optimal solution is based on known algorithm with underlying rectilinear distances. Authors [34] further considered French metro metric as the underlying in the minisum problem. The transformation of the considered Weber problem is reduced to the analogous optimization problem based on rectangular distances using polar coordinates. The algorithm stated in [34] is applied on the optimal location of the office of the delivery service in the subway of the city Novosibirsk, Russia. In this paper, the British Rail metric [35] which assumes that any path between two points includes the central point (origin) was considered.


## 3. Location Problems with Metrics Based on Angular Distances

For the sake of motivation, let us consider an example illustrated in Figure1. A crane or other manipulator on a static platform (denoted by 1) has a rotating boom (2) with a mobile lifting mechanism (3) moving along the boom. The whole structure has three degrees of freedom: the height h of the hook (4), the rotation angle φ, and the position of the lifting mechanism on the boom r (radius).Figure 1
Mechanism scheme.Polar or cylindrical coordinate system [36] is useful to describe the position and movement of the hook of the crane or manipulator. The origin of the coordinates must coincide with the axis of rotation of the boom.The following notations are used below. Any pointY
=
(
y
r
,
y
φ
,
y
h
) in our coordinate system is described with 3 coordinates: height y
h, radius y
r, and angle y
φ. Radius y
r is the Euclidean distance between the point Y and the axis of rotation; height y
h is the distance between Y and a surface perpendicular to the axis. The following equations can be used to convert the Cartesian coordinates of a point Υ
=
(
y
1
,
y
2
) on a plane into polar coordinates:
(3)
y
r
=
(
y
1
)
2
+
(
y
2
)
2
,
y
φ
=
{
0
,
y
1
=
0
,
y
2
=
0
π
2
,
y
1
=
0
,
y
2
>
0
-
π
2
,
y
1
=
0
,
y
2
<
0
arctan
(
y
2
y
1
)
,
y
1
≠
0
.
In a 3D space, for Υ
=
(
y
1
,
y
2
,
y
3
), an additional coordinate y
h
=
y
3 is added.If the mechanism transfers a load from a pointA
=
(
a
r
,
a
φ
,
a
h
) to a point B
=
(
b
r
,
b
φ
,
b
h
) then it spends some energy to change the height for the value Δ
h
=
|
a
h
-
b
h
|, to modify the angle for
(4)
Δ
φ
=
δ
φ
(
a
φ
,
b
φ
)
=
min
⁡
K
∈
Z
{
|
a
φ
-
b
φ
-
2
K
π
|
}
and the position of the lifting mechanism (radius) for Δ
r
=
|
a
r
-
b
r
|.In some region accessible by the manipulator (h
<
H
,
r
<
R, where H is the height of the crane, R is the effective length of the boom), there is a set of m points (customers) A
i, i
=
1
,
…
,
m. Arbitrary ith point A
i
=
(
a
r
i
,
a
φ
i
,
a
h
i
) is required to deliver a w
i cargo pallets with some freight (building materials, e.g.). The location problem searches for a point X
=
(
x
r
,
x
φ
,
x
h
) such that the cost of placing the whole volume of freight reaches its minimum. In general, the problem is to find appropriate point X from the following minimization problem:
(5)
arg
min
⁡
X
∈
R
n
F
(
X
)
=
∑
i
=
1
m
‍
w
i
L
(
X
,
A
i
)
.
Here, w
i
,
i
=
1
,
m
¯ are nonnegative weighting coefficients, and L
(
X
,
A
i
) is the distance function which determines the cost of moving goods from the point X to the point A
i. The classical Weber problem with the underlying Euclidean metric assumes the Euclidean distance L
(
X
,
A
i
)
=
∥
X
-
A
i
∥
2. However, expenses (energy, time, etc.) of mechanism are not proportional to Euclidean distance. Four strategies for manipulator control and four corresponding location problems depending on the method of calculating these expenses are formulated.Strategy 1.
Minimize the cost of the mechanism movement. If the cost of moving the hook vertically for1
m is C
h, the cost of the boom rotation is C
φ for 1 radian and the cost of the lifting mechanism movement along the boom (radius change) is C
r for 1
m. Then the distance between X and A
i is defined by
(6)
L
(
X
,
A
i
)
=
C
r
|
x
r
-
a
r
i
|
+
C
φ
δ
φ
(
x
φ
,
a
φ
i
)
+
C
h
|
x
h
-
a
h
i
|
∀
i
=
1
,
m
¯
,
and the objective function from (5) is
(7)
F
(
X
)
=
∑
i
=
1
m
‍
w
i
(
C
r
|
x
r
-
a
r
i
|
+
C
φ
min
⁡
K
∈
Z
{
|
a
φ
-
b
φ
-
2
K
π
|
}
+
C
h
|
x
h
-
a
h
i
|
)
.
Then the termlifting crane metric can be used to denote the distance function (6). The Weber problem corresponding to the objective function (7) was described in [37].Strategy 2.
Minimize the length of freight path provided only one type of movement (vertical movement, boom rotation, or radius change) is allowed to be performed in a single unit of time. Under this assumption, we have a mixed norm considered in [21]:
(8)
L
(
X
,
A
i
)
=
|
x
h
-
a
h
i
|
+
{
x
r
+
a
r
i
,
δ
φ
(
a
φ
i
,
x
φ
)
≥
2
min
⁡
{
x
r
;
a
r
i
}
δ
φ
(
a
φ
i
,
x
φ
)
+
|
a
r
i
-
x
r
|
,
δ
φ
(
a
φ
i
,
x
φ
)
<
2
mmmmmmmmmmxximmmmmmmmmnmm
∀
i
=
1
,
m
¯
.
The vertical component of the path|
x
h
-
a
h
i
| is independent of other components. The length of the horizontal component is the distance in Karlsruhe (Moscow) metric [35].Urban planning in cities of Moscow or Karlsruhe includes streets of two types: “rays” from the center and disjoint “road rings” around the center. There exists three ways for transition from pointA
i to point X:(1)
moving along a “ring” street fromA
i and then moving along a “ray” up to X (Case A in Figure 2). This path is optimal if φ
=
δ
φ
(
a
φ
i
,
x
φ
)
≤
2 and x
r
≥
a
r
i;
(2)
moving along a “ray” fromA
i and then moving along a “ring” street up to X (Case B in Figure 2). This path is the shortest if φ
=
δ
φ
(
a
φ
i
,
x
φ
)
≤
2 and x
r
≤
a
r
i;
(3)
moving fromA
i along a “ray” up to the origin (center of the city), then along some other “ray” from the center to X if φ
=
δ
φ
(
a
φ
i
,
x
φ
)
≥
2 (see Case C in Figure 2). This case coincides with the French metro metric [34].Figure 2
Various paths in case of control Strategy2.Strategy 3.
Minimize the length of the path of the hook under assumption that the rotation is allowed with zero spread of the lifting mechanism only (when the boom is shortened). If the demand point is unreachable from the current point without rotating the boom then the spread of the lifting mechanism must be shortened first (a load moves to the origin), the boom rotates and then the spread of the lifting mechanism increases to reach the demand point. This assumption is actual for some manipulators with a telescopic boom. For such kind of manipulators, the vertical movement is impossible or allowed to be performed by rotating the boom in a vertical plane (changing the azimuth). For the simplicity, a 2D case is here considered:(9)
L
(
X
,
A
i
)
=
{
x
r
+
a
r
i
,
a
φ
i
≠
x
φ
|
x
r
-
a
r
i
|
a
φ
i
=
x
φ
mmmmmmi
∀
i
=
1
,
m
¯
.Strategy 4.
This strategy is quite similar to the previous one, except for one important condition. The load moves to the zero point in any case, no matter whether the rotation of the boom is required or not, so that the distance betweenX and A
i is defined by
(10)
L
(
X
,
A
i
)
=
{
x
r
+
a
r
i
,
X
≠
A
i
0
,
X
=
A
i
mmmmmm
∀
i
=
1
,
m
¯
.
In case of Strategy 4, the distance function for the working part of the manipulator can be described by British Rail metric (flower shop metric) [35], with considering an axis of rotation as the origin. Distance function in Strategy 3 corresponds to the French metro metric with polar coordinates. Algorithm for this case is considered in [34, 38]. This method is further developed and described in [39]. Algorithms for lifting crane metric (Strategy 1), Moscow-Karlsruhe metric (Strategy 2), and British Rail metric (Strategy 4) are shown in the subsequent sections.


## 4. Algorithm for the “Lifting Crane” Metric (Strategy1)

The distance function between pointsA
i
=
(
a
1
i
,
a
2
i
,
a
3
i
) and X
=
(
x
1
,
x
2
,
x
3
) in rectangular coordinates is defined by the following expression:
(11)
L
(
A
i
,
X
)
=
l
1
(
A
i
,
X
)
=
|
x
1
-
a
1
i
|
+
|
x
2
-
a
2
i
|
+
|
x
3
-
a
3
i
|
.
The optimization problem (5) based on the goal function (11) splits into three independent problems with objective functions:
(12)
f
1
(
x
1
)
=
∑
i
=
1
m
‍
w
i
|
x
1
-
a
1
i
|
,
f
2
(
x
2
)
=
∑
i
=
1
m
‍
w
i
|
x
2
-
a
2
i
|
,
f
3
(
x
3
)
=
∑
i
=
1
m
‍
w
i
|
x
3
-
a
3
i
|
.
Both problems can be reduced on the sequential application of a more general function (in (12)) on the sequential application of a more general problem with the following objective function:
(13)
f
(
x
)
=
∑
i
=
1
m
‍
w
i
|
x
-
a
i
|
.
The problem (13) can be solved using known algorithm (see, e.g., [1, 40]).In case of Strategy1 (see Section 3), the objective function (7) is the sum of three independent functions:
(14)
f
r
(
x
r
)
=
∑
i
=
1
m
‍
w
i
|
a
r
i
-
x
r
|
,
(15)
f
φ
(
x
φ
)
=
∑
i
=
1
m
‍
w
i
δ
φ
(
a
φ
i
,
x
φ
)
=
∑
i
=
1
m
‍
w
i
min
⁡
K
∈
Z
|
x
φ
-
a
φ
i
+
2
K
π
|
,
(16)
f
h
(
x
h
)
=
∑
i
=
1
m
‍
w
i
|
a
h
i
-
x
h
|
.
Solution of the problem (7) is a point X
*
=
(
x
r
*
,
x
φ
*
,
x
h
*
) whose coordinates x
r
*, x
φ
*, and x
h
* are solutions (minimizers) of functions (14), (15), and (16), respectively. Furthermore, it can easily be observed that problems (14) and (16) correspond to the generalized problem (13) and they can be solved by the appropriate algorithm proposed in [1, 40].Lemma 5.
LetX be a set of all minimizers of the objective function (15) and A
φ
=
(
a
φ
1
,
…
,
a
φ
m
) be the set of angular coordinates of the existing facilities (demand points). Then there exists a
φ
i
∈
A
φ such that a
φ
i
∈
X or (
a
φ
i
+
π
)
∈
X.Proof.
Letx
φ
*
∈
X be a minimizer of the function (15) and
(17)
x
φ
*
≠
a
φ
i
+
K
π
∀
i
=
1
,
m
¯
,
K
∈
{
0,1
}
.
Then we turn to the polar coordinate system such that x
φ
*
=
0 (Figure 3) and we assume that values of all angles satisfy -
π
<
a
φ
i
≤
π (the case a
φ
i
=
0 is excluded since x
φ
*
≠
a
φ
i). This transformation is possible since x
φ
*
+
K
π can be subtracted from values of all angles a
φ
i as well as from x
φ
* itself, regardless of any choice of x
φ
*. The values of the function δ
φ
(
a
φ
i
,
x
φ
)
=
min
⁡
K
∈
Z
|
x
φ
-
a
φ
i
-
2
K
π
| remain unchanged in the new coordinate system. Therefore, the values of the objective function (15) are unchanged.
Splitting the set of indices of coordinates{
a
φ
i
} into two subsets:
(18)
Q
+
=
{
i
∣
a
φ
i
>
0
}
,
Q
-
=
{
i
∣
a
φ
i
<
0
}
.
Then
(19)
L
(
x
φ
*
,
A
i
)
=
|
x
φ
*
-
a
φ
i
-
2
K
π
|
=
a
φ
i
∀
i
∈
Q
+
,
L
(
x
φ
*
,
A
i
)
=
|
x
φ
*
-
a
φ
i
-
2
K
π
|
=
-
a
φ
i
∀
i
∈
Q
-
.
IfQ
+
=
∅ then f
φ
(
x
φ
*
)
=
-
∑
i
=
1
m
w
i
a
φ
i.
Sincea
φ
i
<
0
∀
i
∈
Q
-  and  δ
φ
(
a
φ
i
,
a
φ
i
′
)
≤
π
∀
i
,
i
′
∈
Q
-, it follows that
(20)
L
(
A
1
,
A
i
)
=
min
⁡
K
∈
Z
{
|
a
φ
1
-
a
φ
i
+
2
K
π
|
}
=
|
a
φ
i
-
a
φ
1
|
∀
i
=
1
,
m
¯
.
Sincea
φ
i
≠
0
∀
i
=
1
,
m
¯, it results in |
a
φ
i
-
a
φ
1
|
<
|
a
φ
i
-
0
|
∀
i
=
1
,
m
¯, that is, δ
φ
(
a
φ
1
,
a
φ
i
)
<
δ
φ
(
x
φ
,
a
φ
i
). Further, since w
i
≥
0
∀
i
=
1
,
m
¯, if ∃
i
:
w
i
>
0 then f
φ
(
a
φ
1
)
<
f
φ
(
x
φ
).
Ifw
i
=
0
∀
i
∈
{
1
,
m
¯
} then f
φ
(
x
φ
)
=
0
∀
x
φ
∈
R and a
φ
i
∈
X
∀
i
=
1
,
m
¯.
Thus, ifQ
+
=
∅ then x
φ
* is not a minimizer of the objective function (15) unless all values a
φ
i are its minimizers.
Similarly, it can be proved that ifQ
-
=
∅ then x
φ
* is not a minimizer of (15) unless all values a
φ
i are its minimizers.
Thus, ifx
φ
* is a minimizer of the objective (15) and all values a
φ
i are not its minimizers then both subsets Q
- and Q
+ are nonempty.
We choose four indices, two for each of the subsetsQ
- and Q
+ (indices can coincide if the subset contains an index of a single point):
(21)
i
+
min
⁡
∈
Q
+
:
a
i
+
min
⁡
≤
a
φ
i
∀
i
∈
Q
+
,
i
+
max
⁡
∈
Q
+
:
a
i
+
max
⁡
≥
a
φ
i
∀
i
∈
Q
+
i
-
min
⁡
∈
Q
-
:
a
i
-
min
⁡
≤
a
φ
i
∀
i
∈
Q
-
,
i
-
max
⁡
∈
Q
+
:
a
i
-
max
⁡
≥
a
φ
i
∀
i
∈
Q
-
.
Then it is possible to choose an arbitrary value x
φ
′, provided that
(22)
max
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
)
<
x
φ
′
<
min
⁡
(
a
φ
i
+
min
⁡
,
π
+
a
φ
i
-
max
⁡
)
.
In this case, L
(
X
′
,
A
i
)
=
a
φ
i
-
x
φ
′
∀
i
∈
Q
+ and L
(
X
′
,
A
i
)
=
-
a
φ
i
+
x
φ
′
∀
i
∈
Q
-.
Thus, for each(23)
x
φ
′

∈

[
max
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
)
,
min
⁡
(
a
φ
i
+
min
⁡
,
π

+

a
φ
i
-
max
⁡
)
]
,
the value of the objective function in (15) is equal to
(24)
f
φ
(
x
φ
′
)
=
∑
i
∈
Q
+
‍
w
i
(
a
φ
i
-
x
φ
′
)
+
∑
i
∈
Q
-
‍
w
i
(
x
φ
′
-
a
φ
i
)
=
∑
i
∈
Q
+
‍
w
i
a
φ
i
-
∑
i
∈
Q
-
‍
w
i
a
φ
i
+
x
φ
′
(
∑
i
∈
Q
-
‍
w
i
-
∑
i
∈
Q
+
‍
w
i
)
=
C
0
+
Δ
W
x
φ
′
.
Here,(25)
Δ
W
=
∑
i
∈
Q
-
‍
w
i
-
∑
i
∈
Q
+
‍
w
i
;
C
0
=
∑
i
∈
Q
+
‍
w
i
(
a
φ
i
-
x
φ
′
)
+
∑
i
∈
Q
-
‍
w
i
(
x
φ
′
-
a
φ
i
)
=
∑
i
∈
Q
+
‍
w
i
a
φ
i
.
Forx
φ
*
=
0 it follows that f
(
x
φ
*
)
=
C
0.
IfΔ
W
>
0 then for x
φ
′′ to satisfy
(26)
max
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
)
<
x
φ
′′
<
x
φ
the following holds:
(27)
f
φ
(
x
φ
′′
)
=
C
0
+
Δ
W
x
φ
′′
<
f
φ
(
x
φ
*
)
.
This means that x
φ
* is not a minimizer of (15). Similarly, if Δ
W
>
0 then, for x
φ
′′ satisfying
(28)
x
φ
<
x
φ
′′
<
min
⁡
(
a
φ
i
+
min
⁡
,
π
+
a
φ
i
-
max
⁡
)
,
the following expression below is obtained:
(29)
f
φ
(
x
φ
′′
)
=
C
0
+
Δ
W
x
φ
′′
<
f
φ
(
x
φ
*
)
.
If Δ
W
>
0 then for x
φ
′′ which satisfies
(30)
x
φ
′′
∈
[
max
⁡
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
)
,
min
⁡
⁡
(
a
φ
i
+
min
⁡
,
π
+
a
φ
i
-
max
⁡
)
]
it follows that
(31)
f
φ
(
x
φ
′′
)
=
C
0
=
f
φ
(
x
φ
*
)
.
Thus, in this case x
φ
* is a minimizer, so the same is valid for all points inside the interval including the boundary points max
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
) and min
⁡
(
a
φ
i
+
min
⁡
,
π
+
a
φ
i
-
max
⁡
).
Valuex
φ
* is chosen arbitrarily. Thus, if x
φ
*
≠
a
φ
i
+
K
π  ∀
i
=
(
1
,
m
)
¯
,
K
∈
Z, then x
φ
* is not a minimizer of the objective function except for the case Δ
W
=
0. In this case, values max
⁡
(
a
φ
i
+
max
⁡
-
π
,
a
φ
i
-
min
⁡
) and min
⁡
(
a
φ
i
+
min
⁡
,
π
+
a
φ
i
-
max
⁡
) are its minimizers either. Values a
φ
i
+
max
⁡, a
φ
i
-
min
⁡, a
φ
i
+
min
⁡, and a
φ
i
-
max
⁡ are selected from one of three sets: {
a
φ
i
∣
i
=
1
,
m
¯
}, {
a
φ
i
+
π
∣
i
=
1
,
m
¯
}, or {
a
φ
i
-
π
∣
i
=
1
,
m
¯
}. Let us assume that the angles a
φ
i
+
π and a
φ
i
-
π are equivalent and give identical values of the objective function.Figure 3
Illustration for Lemma5.Thus, if we are required to find any minimizer off
φ
(
x
φ
), two sets have to be sought: {
a
φ
i
∣
i
=
1
,
m
¯
} and {
a
φ
i
+
π
∣
i
=
1
,
m
¯
}. Algorithm 6 is offered for solving this problem.Algorithm 6.
Solving the location problem with the “lifting crane” metric.Step  1. Solve the problem (14) using algorithm for (13). Store the result to x
r
*.Step  2. Solve the problem (16) using algorithm for (13). Store the result to x
h
*.Step  3. If f
φ
(
a
φ
1
+
π
)
<
f
φ
(
a
φ
1
) then x
φ
*
=
a
φ
1
+
π else x
φ
*
=
a
φ
1.Step  4. f
=
f
φ
(
x
φ
*
).Step  5. For each i
:
i
=
2
,
m
¯ perform the cycle.Step  5.1. If f
φ
(
a
φ
1
)
<
f then x
φ
*
=
a
φ
i; f
*
=
f
φ
(
a
φ
i
).Step  5.2. If f
φ
(
a
φ
1
+
π
)
<
f then x
φ
*
=
a
φ
i
+
π; f
*
=
f
φ
(
a
φ
i
+
π
).Step  5.3. End of cycle 5.Step  6. Display the result X
*
=
(
x
r
*
,
x
φ
*
,
x
h
*
). STOP.Let us estimate the computational complexity of Algorithm6. Let m be a number of existing facilities (demand points). The algorithm for the l
1 metric ([1, 40]) includes coordinates sorting in ascending order with the asymptotic complexity of O
(
m
log
⁡
m
) and summation of coordinate values with linear complexity. Thus, the general computational complexity of steps 1 and 2 is described by the asymptotic formula O
(
m
log
⁡
m
). Steps 5–5.3 define a cycle in which values of the objective function are calculated for each of m
-
1 coordinates a
φ
i and a
φ
i
+
π. Based on Steps 3 and 4, the objective function is estimated 2
m times. The objective function is linear (asymptotic complexity O
(
m
)), so the asymptotic complexity of Steps 3–5.3 and complete Algorithm 6 is equal to O
(
m
2
).


## 5. Algorithm for Moscow-Karlsruhe Metric (Strategy2)

In the case of Strategy2, defined in Section 3, the objective function of the Weber problem (5) is the sum
(32)
F
(
X
)
=
f
h
(
x
h
)
+
f
MK
(
x
r
,
x
φ
)
of two independent functions
(33)
f
h
(
X
)
=
∑
i
=
1
m
‍
w
i
|
x
h
-
a
h
i
|
,
(34)
f
MK
(
X
)
=
∑
i
=
1
m
‍
w
i
×
{
x
r
+
a
r
i
,
δ
φ
(
a
φ
i
,
x
φ
)
≥
2
min
⁡
(
x
r
,
a
r
i
)
δ
φ
(
a
φ
i
,
x
φ
)
+
|
a
r
i
-
x
r
|
,
δ
φ
(
a
φ
i
,
x
φ
)
<
2
.
Minimum of the goal function (32) is achieved in a point X
*
=
(
x
r
*
,
x
φ
*
,
x
h
*
), where x
h
* is a minimum point of the objective (33), and x
φ
* and x
r
* are minimizers of (34). So, problem (32) corresponds to the generalized problem (13). It can be solved by the appropriate algorithm from [1, 40, 41].Lemma7 provides a solution of the location problem with the objective function (34).Lemma 7.
LetX be a set of minimizers of the objective function (34) and A
=
{
A
1
,
…
,
A
m
} be the set of the polar coordinate pairs of the existing facilities (demand points) A
i
=
(
a
r
i
,
a
φ
i
).
Then there existX
*
=
(
x
r
*
,
x
φ
*
)
∈
X and A
i
=
(
a
r
i
,
a
φ
i
)
∈
A such that at least one of the following three conditions is correct: (
x
r
*
,
a
φ
i
)
∈
X
*
,
(
x
r
*
,
a
φ
i
+
2
)
∈
X
*, or
(
x
r
*
,
a
φ
i
-
2
)
∈
X
*.Proof.
Assume that the minimizerX
*
=
(
x
r
*
,
x
φ
*
) of the function (34) satisfies x
φ
*
≠
a
φ
i
±
2
∀
i
=
1
,
m
¯. Turning to the polar coordinate system with x
φ
*
=
0 (Figure 4), values of all angles a
φ
i are expressed so that -
π
<
a
φ
i
≤
π (the case a
φ
i
=
0 is excluded since x
φ
*
≠
a
φ
i). This transformation is possible because, regardless of the choice of x
φ
*, we can subtract x
φ
* from values of all angles a
φ
i and from the angle x
φ
* itself and obtain values of new coordinates. Values δ
φ
(
a
φ
i
,
x
φ
)
=
min
⁡
K
∈
Z
{
|
x
φ
-
x
φ
i
-
2
π
K
|
} remain the same in the new coordinate system.
Therefore, value of the objective function (34) remains unchanged.
Let us divide the set of indices included in coordinates{
a
φ
i
∣
i
=
1
,
m
¯
} into three subsets:
(35)
Q
+
*
=
{
i
∣
0
<
a
φ
i
<
2
}
,
Q
-
*
=
{
i
∣
-
2
≤
a
φ
i
<
0
}
,
Q
2
*
=
{
i
∣
|
a
φ
i
|
>
2
}
.
In addition, consider the following three subsets of indices with respect to an arbitrary angle x
φ
∈
(
-
π
,
π
]:
(36)
Q
+
(
x
φ
)
=
{
i
∣
∃
K
∈
Z
:
0
<
a
φ
i
-
x
φ
+
2
π
K
≤
2
}
,
Q
-
(
x
φ
)
=
{
i
∣
∃
K
∈
Z
:
-
2
≤
a
φ
i
-
x
φ
+
2
π
K
<
0
}
,
Q
2
(
x
φ
)
=
{
i
∣
∃
K
∈
Z
:
|
a
φ
i
-
x
φ
+
2
π
K
|
>
2
}
.
Then
(37)
δ
φ
(
x
φ
*
,
a
φ
i
)
=
{
a
φ
i
,
∀
i
∈
Q
+
*
,
-
a
φ
i
,
∀
i
∈
Q
-
*
,
a
φ
i
-
x
φ
,
∀
i
∈
Q
+
(
x
φ
)
*
,
-
a
φ
i
+
x
φ
,
∀
i
∈
Q
-
(
x
φ
)
*
.
The value of the objective function (34) at the point x
φ
*
=
0 is equal to
(38)
f
MK
(
x
r
*
,
x
φ
*
)
=
∑
i
∉
Q
2
*
‍
w
i
|
x
r
*
-
a
r
i
|
+
∑
i
∈
Q
+
*
‍
w
i
min
⁡
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
-
∑
i
∈
Q
-
*
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
+
∑
i
∈
Q
2
*
‍
w
i
(
x
r
*
+
a
r
i
)
.
For an arbitrary angle x
φ the following holds:
(39)
f
MK
(
x
r
*
,
x
φ
)
=
∑
i
∉
Q
2
(
x
φ
)
‍
w
i
|
x
r
*
-
a
r
i
|
+
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
(
a
φ
i
-
x
φ
)
+
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
(
x
φ
-
a
φ
i
)
+
∑
i
∈
Q
2
(
x
φ
)
‍
w
i
(
x
r
*
+
a
r
i
)
=
∑
i
∈
Q
2
(
x
φ
)
‍
w
i
(
x
r
*
+
a
r
i
)
+
∑
i
∉
Q
2
(
x
φ
)
‍
w
i
|
x
r
*
-
a
r
i
|
+
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
-
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
x
φ
-
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
x
φ
-
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
.
There exists certain interval (Figure4) [
x
φ
min
⁡
,
x
φ
max
⁡
] such that
(40)
Q
+
(
x
φ
)
=
Q
+
*
∧
Q
-
(
x
φ
)
=
Q
+
*
∧
Q
2
(
x
φ
)
=
Q
2
*
∀
x
φ
∈
[
x
φ
min
⁡
,
x
φ
max
⁡
]
.
When x
φ
∈
[
x
φ
min
⁡
,
x
φ
max
⁡
], some parts of (39) are constant. It can be designated as follows:
(41)
C
0
=
∑
i
∈
Q
2
(
x
φ
)
‍
w
i
(
x
r
*
+
a
r
i
)
+
∑
i
∉
Q
2
(
x
φ
)
‍
w
i
|
x
r
*
-
a
r
i
|
+
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
-
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
a
φ
i
,
Δ
W
=
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
-
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
.
Objective function is linear forx
φ
∈
[
x
φ
min
⁡
,
x
φ
max
⁡
], since
(42)
Δ
W
=
∑
i
∈
Q
-
(
x
φ
)
‍
w
i
min
⁡
⁡
{
x
r
*
,
a
r
i
}
-
∑
i
∈
Q
+
(
x
φ
)
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
=
w
i
x
r
-
w
i
x
r
=
0
implies
(43)
f
MK
(
x
r
*
,
x
φ
)
=
C
0
+
Δ
W
x
φ
=
C
0
.
Consider the following three cases.
Case  1. Δ
W
>
0. Choose x
φ
′ satisfying x
φ
min
⁡
<
x
φ
′
<
x
φ
*. Thus,
(44)
f
MK
(
x
r
*
,
x
φ
′
)
=
C
0
+
Δ
W
x
φ
′
<
C
0
=
f
MK
(
x
r
*
,
x
φ
*
)
;
that is, x
φ
′ is not a minimizer of the function (34).
Case  2. Δ
W
<
0. Choose x
φ
′ such that x
φ
max
⁡
>
x
φ
′
>
x
φ
*. Then,
(45)
f
MK
(
x
r
*
,
x
φ
′
)
=
C
0
+
Δ
W
x
φ
′
<
C
0
=
f
MK
(
x
r
*
,
x
φ
*
)
,
and x
φ
′ also is not a minimizer of (34).
Case  3. Δ
W
=
0. Then f
MK
(
x
r
*
,
x
φ
′
)
=
C
0
=
f
MK
(
x
r
*
,
x
φ
*
). In this case, if x
φ
′ is a minimizer of the function (34), then x
φ
* is its minimizer too.
Let us estimate values ofx
φ
min
⁡ and x
φ
max
⁡.
Froma
φ
i
∈
Q
+
(
x
φ
)
∧
a
φ
i
∈
Q
+
*
∀
i
∈
{
1
,
m
}
¯ it is immediately obtained that 0
<
a
φ
i
-
x
φ
≤
2
∀
i
∈
{
1
,
m
}
¯, which further implies 0
>
x
φ
≥
a
φ
i
-
2
∀
i
∈
{
1
,
m
}
¯. Finally, it is concluded that x
φ
≥
min
⁡
i
∈
Q
+
*
{
a
φ
i
}
-
2.
In the case,a
φ
i
∈
Q
-
(
x
φ
)
∧
a
φ
i
∈
Q
-
*
∀
i
∈
{
1
,
m
}
¯, it follows that 0
>
a
φ
i
-
x
φ
≥
-
2
∀
i
∈
{
1
,
m
}
¯, and further 0
<
x
φ
≤
a
φ
i
+
2
∀
i
∈
{
1
,
m
}
¯. Therefore, x
φ
≤
max
⁡
i
∈
Q
-
*
{
a
φ
i
}
+
2.
In the third case,a
φ
i
∈
Q
2
(
x
φ
)
∧
a
φ
i
∈
Q
2
*
∀
i
∈
{
1
,
m
}
¯. In a similar way |
a
φ
i
-
x
φ
|
<
2
∀
i
∈
{
1
,
m
}
¯, and 0
<
x
φ
≤
a
φ
i
+
2
∨
0
>
x
φ
≥
a
φ
i
-
2
∀
i
∈
{
1
,
m
}
¯, which further implies x
φ
≤
max
⁡
i
∈
Q
2
*
{
a
φ
i
}
+
2
∨
x
φ ≥ min
⁡
i
∈
Q
2
*
{
a
φ
i
}
-
2. Thus,
(46)
x
φ
min
⁡
=
max
⁡
{
max
⁡
i
∈
Q
+
*
{
a
φ
i
}
-
2
,
min
⁡
i
∈
Q
2
*
{
a
φ
i
}
-
2
}
;
x
φ
max
⁡
=
min
⁡
{
min
⁡
i
∈
Q
-
*
{
a
φ
i
}
+
2
,
max
⁡
i
∈
Q
2
*
{
a
φ
i
}
+
2
}
.
In caseΔ
W
=
0, if x
φ
*
∉
{
a
φ
i
} is a minimizer of (34), one of the values
(47)
max
⁡
i
∈
Q
+
*
{
a
φ
i
}
-
2
,
min
⁡
i
∈
Q
2
*
{
a
φ
i
}
-
2
,
min
⁡
i
∈
Q
-
*
{
a
φ
i
}
+
2
,
max
⁡
i
∈
Q
2
*
{
a
φ
i
}
+
2
is also its minimizer.Figure 4
Illustration for Lemma7.Assuming thatX
*
=
(
x
r
*
,
x
φ
*
) is a minimizer of the function (34) and the value of x
φ is known, then value of x
r
* can be calculated as follows.Divide the set of indices of the existing facilities{
A
i
} into two subsets defined by
(48)
Q
<
*
=
{
i
∣
δ
φ
(
a
φ
i
,
x
φ
*
)
≤
2
}
,
Q
>
*
=
{
i
∣
δ
φ
(
a
φ
i
,
x
φ
*
)
>
2
}
.
Then, the objective function (34) can be expressed as
(49)
f
MK
(
x
r
,
x
φ
*
)
=
∑
i
∈
Q
>
‍
w
i
(
a
r
i
+
x
r
*
)
+
∑
i
∈
Q
<
‍
w
i
|
x
r
*
,
a
r
i
|
+
∑
i
∈
Q
<
‍
w
i
min
⁡
{
x
r
*
,
a
r
i
}
δ
φ
(
a
φ
i
,
x
φ
*
)
=
∑
i
∈
Q
>
‍
w
i
(
a
r
i
+
x
r
*
)
+
∑
i
∉
Q
<
‍
w
i
|
x
r
*
-
a
r
i
|
+
∑
i
∈
Q
<
w
i
a
r
i
δ
φ
(
a
φ
i
,
x
φ
*
)
2
+
∑
i
∈
Q
<
w
i
a
r
i
δ
φ
(
a
φ
i
,
x
φ
*
)
(
|
x
r
-
a
r
i
|
+
x
r
)
2
.
This can be designated with
(50)
C
1
=
∑
i
∈
Q
>
‍
w
i
a
r
i
+
∑
i
∈
Q
<
w
i
a
r
i
δ
φ
(
a
φ
i
,
x
φ
*
)
2
,
C
1
′
=
∑
i
∈
Q
>
‍
w
i
+
∑
i
∈
Q
<
w
i
δ
φ
(
a
φ
i
,
x
φ
*
)
2
,
C
i
=
w
i
+
w
i
δ
φ
(
a
φ
i
,
x
φ
*
)
2
∀
i
=
1
,
m
¯
.
Then f
MK
(
x
r
,
x
φ
*
)
=
C
1
+
C
1
′
x
r
+
∑
i
∈
Q
<
C
i
|
x
r
-
a
r
i
|.This function is piecewise linear (a linear spline). The boundaries of each of its intervals (subdomains)a
r
i
,
i
=
1
,
m
¯ are its possible minimizers. If the derivative of this function is equal to 0 for any given interval [
a
r
i
,
a
r
i
′
], then all points of the interval are possible minimizers of the objective (34) including the points a
r
i and a
r
i
′. Thus, for finding a minimizer of (34), it is sufficient to determine the value of this function on a set of points
(51)
χ
=
{
(
a
r
i
,
a
φ
j
)
∣
i
=
1
,
m
¯
,
j
=
1
,
m
¯
}
∪
{
(
a
r
i
,
a
φ
j
+
2
)
∣
i
=
1
,
m
¯
,
j
=
1
,
m
¯
}
∪
{
(
a
r
i
,
a
φ
j
-
2
)
∣
i
=
1
,
m
¯
,
j
=
1
,
m
¯
}
∪
{
(
0,0
)
}
.
Cardinality of this set is |
χ
|
=
3
m
2
+
1. A full search procedure can be used to find the minimizer.Algorithm8 is proposed for solving the minimization problem with the objective function (32)–(34).Algorithm 8.
Solve the location problem with Moscow-Karlsruhe metric.Step  1. Solve the problem (33) using the algorithm for (13). Store the result to x
h
*.Step  2. x
φ
*
=
0;  x
r
*
=
0;  f
*
=
f
MK
(
0,0
).Step  3. For each i
:
i
=
1
,
m
¯ perform the following cycle.Step  3.1. For each j
:
j
=
2
,
m
¯ perform cycle.Step  3.1.1. f
=
f
MK
(
a
r
i
,
a
φ
j
).Step  3.1.2. If f
<
f
* then x
r
*
=
a
r
i;  x
φ
*
=
a
φ
j;  f
*
=
f.Step  3.1.3. f
=
f
MK
(
a
r
i
,
a
φ
j
+
2
).Step  3.1.4. If f
<
f
* then x
r
*
=
a
r
i;  x
φ
*
=
a
φ
j
+
2;  f
*
=
f.Step  3.1.5. f
=
f
MK
(
a
r
i
,
a
φ
j
-
2
).Step  3.1.6. If f
<
f
* then x
r
*
=
a
r
i;  x
φ
*
=
a
φ
j
-
2;  f
*
=
f.Step  3.1.7. End of cycle 3.1.Step  3.2. End of cycle 3.Step  4. Display the result X
*
=
(
x
r
*
,
x
φ
*
,
x
h
*
); Stop.Estimate the computational complexity of Algorithm8. Let m be a number of existing facilities (demand points). Step 1 of Algorithm 8 finds the solution of the Weber problem based on l
1 metric (see [1, 40]). Therefore, it involves coordinates sorting in ascending order with the asymptotic complexity O
(
m
log
⁡
m
) as well as summation of coordinate values with linear complexity. Thus, the total computational complexity of Step 1 is described by the asymptotic formula O
(
m
log
⁡
m
). Steps 3–3.2 define a nested loop cycle in which the values of the objective function are calculated for each of the m values of coordinates a
φ
i and a
φ
i
±
2. Based on Steps 3 and 4, the objective function is evaluated 1
+
3
m
2 times. The objective function is linear (asymptotic complexity O
(
m
)), so that the complexity of Steps 3–5.3 and complete Algorithm 8 is of the order O
(
m
3
).


## 6. Algorithm for Location Problem with British Rail Metric

Lemma9 is intended to shorten the set of possible facility locations (candidate solutions) in case of the Weber problem with underlying British Rail distance metric (which appears in Strategy 4).Lemma 9.
If(52)
∄
i
′
∈
{
1
,
m
}
¯
:
w
i
′
>
∑
i
=
1
m
‍
w
i
2
then the point O
=
(
0,0
) is a solution of the goal function (5) with distance function (10).Proof.
AssumeX
*
=
(
x
r
,
x
φ
) is a solution of (5) with distance function (10). Here, we use polar coordinates. If X
*
≠
A
i
=
(
a
r
i
,
a
φ
i
)
∀
i
∈
{
1
,
m
}
¯ and X
*
≠
(
0,0
) then
(53)
F
(
X
*
)
=
∑
i
=
1
m
‍
w
i
a
r
i
+
∑
i
=
1
m
‍
w
i
x
r
*
.
Compare this value with the value of the objective functions (5) and (10) in the point O:
(54)
F
(
O
)
=
∑
i
=
1
m
‍
w
i
a
r
i
.
Since x
r
*
>
0, under the assumption X
*
≠
(
0,0
) and w
i
≥
0
∀
i
=
1
,
m
¯, we get
(55)
F
(
X
*
)
>
F
(
O
)
and X
* is not a minimizer of the objective unless
(56)
X
*
∈
{
O
}
∪
{
A
i
∣
i
=
1
,
m
¯
}
or
(57)
w
i
=
0
∀
i
=
1
,
m
¯
.
If (57) holds, any point on the plane (including O) is a minimizer of the objective function.
AssumingX
*
=
A
i
′
i
′
∈
{
1
,
m
}
¯ and X
*
≠
O
=
(
0,0
)
) then
(58)
F
(
X
*
)
=
F
(
A
i
′
)
=
∑
i
∈
{
1
,
m
}
¯
∖
{
i
′
}
‍
w
i
(
a
r
i
+
x
r
)
=
∑
i
=
1
m
‍
w
i
a
r
i
+
x
r
∑
i
=
1
m
‍
w
i
-
w
i
′
a
r
i
′
-
w
i
′
x
r
=
∑
i
=
1
m
‍
w
i
a
r
i
+
a
r
i
′
∑
i
=
1
m
‍
w
i
-
2
·
w
i
′
a
r
i
′
=
F
(
O
)
+
a
r
i
′
∑
i
=
1
m
‍
w
i
-
2
·
w
i
′
a
r
i
′
.
Thus, F
(
A
i
′
)
<
F
(
O
) if and only if
(59)
a
r
i
′
∑
i
=
1
m
‍
w
i
-
2
·
w
i
′
a
r
i
′
≡
a
r
i
′
∑
i
=
1
m
‍
w
i
<
2
w
i
′
a
r
i
′
≡
∑
i
=
1
m
w
i
2
<
w
i
′
,
which was our original intention.The result of Lemma9 is perfectly consistent with the main result of the paper [42]. In [42], Chen proves that A
i is the solution of the classical Weber problem with Euclidean metric if ∃
i
′
∈
{
1
,
m
¯
}
:
w
i
′
≥
∑
i
=
1
m
w
i. It has been proved above that if this condition is not true in the case of British Rail metric, then the only possible solution is (
0,0
).Algorithm10 is proposed.Algorithm 10.
Solve the location problem with British Rail metric.Step  1. Compute W
=
∑
i
=
1
m
w
i.Step  2. For each i
=
1
,
m
¯ perform the following:Ifw
i
≥
W
/
2 then return X
*
=
A
i. STOP.Step  3. Return the result X
*
=
(
0,0
). STOP.Obviously, the asymptotic complexity of this algorithm isO
(
m
) (linear).


## 7. Numerical Example

In this example, attempt is made at solving a location problem based on the “lifting crane” metric. Polar coordinates of the existing facilities (demand points) and the corresponding weighting coefficients are given in Table 1.Table 1
Initial data.
i
a
r
i
a
h
i
a
φ
i
w
i
1
10
5
0
3
2
20
3
0
2
3
10
5
π
/
4
4
4
20
5
π
/
4
3
5
30
3
π
/
4
4SolutionStep  1. x
r
*
=
arg
min
⁡
x
r
∑
i
=
1
m
w
i
|
a
r
i
-
x
r
|
=
20.Step  2. x
h
*
=
arg
min
⁡
x
h
∑
i
=
1
m
w
i
|
a
h
i
-
x
h
|
=
5.Step  3. f
φ
(
a
φ
1
+
π
)
=
f
φ
(
0
+
π
)
=
∑
i
=
1
m
δ
φ
(
π
,
a
φ
i
)
=
3,75
π;f
φ
(
a
φ
1
)
=
f
φ
(
0
)
=
∑
i
=
1
m
δ
φ
(
π
,
a
φ
i
)
=
1,25
π.Conditionf
φ
(
a
φ
1
+
π
)
<
f
φ
(
a
φ
1
) is not fulfilled, so that x
φ
*
=
a
φ
1
=
0.Step  4. f
=
f
φ
(
x
φ
)
=
1,25
π.Step  5. For each i
=
2 to 5 perform cycle. Results of steps 5.1–5.3 are summarized in Table 2.Table 2
Solution (Steps  5.1–5.3).
Step
i
=
2
i
=
3
i
=
4
i
=
5
Step  5.1 valuef
φ
(
a
φ
i
)
1,25
π
π
1,25
π
1,25
π
Step  5.1 conditionf
φ
(
a
φ
i
)
<
f
*
False
False
False
False
Step  5.1 valuef
*
1,25
π
π
π
π
Step  5.1 valuex
φ
*
0
0,25
π
0,25
π
0,25
π
Step  5.2 valuef
φ
(
a
φ
i
+
π
)
3,75
π
5
π
6
π
6
π
Step  5.2 conditionf
φ
(
a
φ
i
+
π
)
<
f
*
False
False
False
False
Step  5.2 valuef
*
1,25
π
π
π
π
Step  5.2 valuex
φ
*
0
0,25
π
0,25
π
0,25
πStep  6. X
*
=
(
x
r
*
,
x
φ
*
,
x
h
*
)
=
(
20,1
(
1
/
4
)
π
,
5
).


## 8. Conclusion

This paper has presented a number of challenging DPFs in location problems that have been insufficiently attempted so far. The motivation is aimed at enriching the spectrum of problems for researchers to consider and creating new and more realistic decision tools for facilities location.For instance, when a transport mechanism with telescopic boom is used, optimal location problems are formulated as the Weber problem with metrics based on measurement of angular distance. Solution of the Weber problem with each of considered metrics is reduced to solving a problem with the rectangular metric (l
1) or searching in a discrete set of possible locations. All algorithms run in a polynomial time. Efficiency of the proposed algorithms has been proved analytically using a numerical example.



---

*Source: 701267-2014-09-25.xml*