Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ALGORITHM FOR THE LOCATION PROBLEM WITH NON-EUCLIDEAN METRIC BASED ON ANGULAR DISTANCES

Kazakovtsev L.A. 1
1 Siberian State Aerospace University
1799 KB
Author investigates the continuous single-facility planar min-sum Weber location problem with a metric based on angle distances and propose an algorithm based on an algorithm for the Weber problem with rectangular (Manhattan) metric. The considered problem is decomposed into a series of Weber problems with the rectangular metric which are solved with standard procedure. An example of a problem solved is given. The metric for distance measuring may be different in various instances. For the mechanisms with a rotating telescopic boom (lifting cranes, manipulators etc.), the Euclidean distance between two points does not reflect the cost of moving of an object between two points. Author considers 2 strategies of optimal control for such systems with corresponding distance functions and proposes an algorithm for Weber problem solving. For the algorithm proposed, an analytical proof of the optimality of the result is given.
anglular distance
location problems
Weber problem
1. Farahani R.Z., Hekmatfar M. (editors) Facility Location Concepts, Models, Algorithms and Case Studies. – Springer-Verlag Berlin Heidelberg, 2009.
2. Wesolowsky G. The Weber Problem:History and Perspectives // Location Science. – 1993. – №1. – Р. 5–23
3. Staminirovic P.S.,Ciric M. Single-Facility Weber Location Problem Based on the Lift Metric, URL: http://arxiv.org/abs/1105.0757 (дата обращения: 01.07.2012).
4. Oniyide O.R., Osinuga I.A. On the Existence of Best Sample in Simple Random Sampling // J. Math. Assoc. Nigeria. –
2006. – №33(2B). – Р. 290–294.
5. Ferreira S.G., Jorge P. The Existence and Uniqueness of the Norm Solution to Certain and non-Linear Problems. – Signal Processing. – 1996. – № 55.– Р. 137–139.
6. Deza M.M., Deza E. Encyclopedy of Distances. – Springer Verlag, 2009. – С. 325.
7. Weisstein E. W. French Metro Metric; From MathWorld. A Wolfram Web Resource, URL http://mathworld.wolfram.com/FrenchMetroMetric.html (дата обращения: 01.07.2012).
8. Love R.F., Morris J.G. Computation Procedure for the Exact Solution of Location-Allocation Problems with Rectangular Distances // Naval Research Logistics Quart. –
1975. – № 22. – Р. 441–453.

Задачи размещения [1] - частный случай задач оптимизации, где главными параметрами являются координаты точек и расстояния между ними. В общем случае, цель задачи размещения включает в себя определение местоположения одного или нескольких новых объектов на плоскости или в пространстве, где уже имеются некоторые объекты, причем число возможных расположений для нового объекта обычно бесконечно [2]. Такие модели обычно включают евклидовы расстояния или другие соответствующие расстояния и непрерывны по своей природе. Поскольку модели непрерывны, они удобны с точки зрения математического анализа и в некоторых случаях могут быть вычислены точные решения.

В качестве примеров можно привести задачи оптимального размещения складов, размещения оборудования компьютерных и телекоммуникационных сетей, базовых станций беспроводных сетей и др. [3]. Подобные задачи формулируются и в теории аппроксимации, задачах оценивания в статистике [4], обработке сигналов и изображений и др. [5].

В данной работе уделяется внимание выбору функции расстояния. Расстояние - длина кратчайшего пути между двумя точками. Но путь зависит от свойств как пространства, так и способа перемещения в нем. В непрерывных пространствах чаще всего используются метрики: прямоугольная или манхэттенская (l1), евклидова (l2) и чебышевская (l).

Постановка задачи Вебера с метриками, основанными на угловом расстоянии

Рассмотрим пример (рис. 1). Подъемный кран или иной манипулятор на неподвижной платформе 1 имеет вращающуюся стрелу 2 с подвижным подъемным механизмом 3, перемещающимся вдоль стрелы. Вся конструкция имеет 3 степени свободы: высота h крюка 4, угол поворота стрелы φ и положение подъемного механизма на стреле r (радиус).

Если механизм переносит груз из некоторой точки A = (ar, aφ, ah) в точку B = (br, bφ, bh), механизм затрачивает некоторую энергию (совершает работу) по изменению высоты Δh = |ah - bh|, угла Δφ = δφ(aφ,bφ), и положения подъемного механизма (радиуса) Δr = |ar - br|. Здесь

?

Рис. 1. Схема механизма

В некоторой области, доступной манипулятору (h < H, r < R, где H - высота крана, R - полезная длина стрелы), имеется множество {Ai} из m точек (потребителей). В каждую i-ю точку Ai = (air, aiφ, aih) требуется доставить wi поддонов некоторого груза (стройматериалов, например). Задача состоит в нахождении некоторой точки X = (xr, xφ, xh), в которой должен быть размещен полный объем грузов таким образом, чтобы затраты на перемещение грузов манипулятором были минимальны. В общем случае, задача формулируется как

 (1)

Здесь wi - неотрицательный весовой коэффициент, L(X,Ai) - функция расстояния, определяющая затраты на перемещение груза из точки X в точку Ai. Если данная функция пропорциональна евклидову расстоянию (L(X, Ai) = ||X, Ai||), то мы имеем классическую задачу Вебера с евклидовой метрикой. Но затраты (энергии, времени и т.д.) механизма не пропорциональны евклидову расстоянию. В зависимости от способа вычисления этих затрат сформулируем 2 стратегии управления манипулятором и 2 соответствующие задачи.

Стратегия 1. Минимизировать стоимость движения механизмов. Пусть стоимость вертикального перемещения крюка на 1 м составляет Ch, стоимость вращения стрелы - Cφ за 1 радиан, стоимость движения подъемного механизма вдоль стрелы (изменения радиуса) - Cr за 1 м. Тогда функция расстояния равна

(2)

и целевая функция

(3)

Стратегия 2. Минимизировать длину пути, совершаемого грузом, при условии, что одновременно осуществляется только один вид движения (вертикальное, поворот стрелы, изменение радиуса). В этом случае

(4)

Вертикальная составляющая пути |xh - aih| не зависит от других составляющих. Длина горизонтальной составляющей - это расстояние в метрике Карлсруэ (Москвы) [6].

Планировка городов Москва, Карлсруэ включает улицы 2 типов: «лучи» из центра и непересекающиеся «кольца» вокруг центра. Из точки A можно попасть в B двумя путями:

  1. двигаясь по «лучу» к центру, затем по другому «лучу» из центра к B (как в случае метрики French metro [7]);
  2. двигаясь вдоль «луча» из точки A, затем двигаясь по кольцевой улице.

Алгоритм на основе процедуры для метрики l1

В метрике l1 функция расстояния между точками Ai = (ai1, ai2) и X = (x1, x2) на плоскости в прямоугольных координатах задана выражением

 (5)

В этом случае задача оптимизации (1) разбивается на 2 независимые задачи с целевыми функциями

 (6)

 (7)

Обе задачи сводятся к обобщенной задаче с целевой функцией

 (8)

Данная задача решается известным алгоритмом (см., например, [1]).

В случае Стратегии 1 (см. предыдущий раздел) целевая функция задачи Вебера (1) является суммой 3 независимых функций

 (9)

 (10)

 (11)

 (12)

Решение задачи (9) - точка , где ,  и - решения (точки минимума) задач (9), (10) и (11) соответственно, причем задачи (10) и (12) соответствуют обобщенной задаче (8) и могут быть решены соответствующим алгоритмом ([1], [8]).

Лемма 1. Обозначим через XS множество точек минимума задачи (11). Существует индекс , для которого  или .

Доказательство. Пусть - одна из точек минимума функции (11) и

.

Перейдем к полярной системе координат, такой, что (рис. 2) и условимся, что значения всех углов выражены так, что (случай  исключен, т.к. ). Такой переход возможен, т.к., независимо от выбора , можно вычесть величину  из величин всех углов  и из самого угла , получив требуемую систему координат. В новой системе координат значения

останутся прежними, следовательно, не изменится и значение целевой функции (11).

Рис. 2. Иллюстрация к Лемме 1

Разобьем множество индексов координат точек-потребителей  на 2 подмножества:

 и

Тогда

?

?

Если , то

?

Поскольку  и

?

?

Поскольку

 ,

т. е. и, поскольку  то, если  то

Если  то

 и

Таким образом, если , то  не является точкой минимума целевой функции, если только все значения  не являются таковыми.

Аналогично доказывается, что, если , то  не является точкой минимума целевой функции, если только все значения  не являются таковыми.

Таким образом, если - точка минимума целевой функции и все значения  не являются таковыми, то оба подмножества Q- и Q+ не пусты.

Выберем 4 индекса, 2 для каждого из подмножеств (индексы могут совпадать, если подмножество содержит индекс единственной точки):

?

?

?

?

Выберем произвольное значение , такое, что

В этом случае

и

При этом значение целевой функции равно

Здесь

?

?

Для :

Если ΔW > 0, то для

,

 

т.е. значение  не является точкой минимума целевой функции.

Аналогично, если ΔW < 0, то для

?

?

Если ΔW = 0, то для

?

?

Таким образом, в этом случае  является точкой минимума, но таковыми являются все точки  интервала, включая граничные точки  и .

Значение  выбрано произвольно. Таким образом, если

,

то  не является точкой минимума целевой функции, за исключением случая ΔW = 0. Но и в этом случае значения

и

являются точками минимума. Значения , , и  выбраны из множества . Соответственно точкой минимума всегда является значение из множества , либо из множества , либо из множества , причем углы  и  равнозначны, дают равные значения целевой функции. Лемма доказана.

Таким образом, если требуется найти любую из точек минимума , достаточно произвести поиск в 2 множествах  и . Предлагается следующий алгоритм.

1. Решить задачу (10), используя алгоритм для (8). Сохранить результат в .

2. Решить задачу (12) алгоритмом для задачи (8). Сохранить результат как .

3. Если , то

, иначе .

4. .

5. Для каждого  цикл

5.1. Если , то

 

5.2. Если , то

 .

5.3. Конец цикла 5.

6. Вывод результата  Останов.

Оценим вычислительную сложность алгоритма. Пусть m - число точек-потребителей. Алгоритм для метрики l1 ([1], [8]) включает в себя этап сортировки координат по возрастанию с асимптотической сложностью O(m log m) и этап суммирования значений координат с линейной сложностью. Таким образом, общая вычислительная сложность этапов 1 и 2 описывается асимптотической формулой O(m log m). Шаги 5 - 5,3 содержат цикл, в котором вычисляются значения целевой функции для каждого из m - 1 значений координат  и . С учетом шагов 3 и 4 значение целевой функции оценивается 2m раз. Целевая функция - линейна (асимптотическая сложность O(m)), следовательно, сложность шагов 3?5.3 алгоритма определяется как O(m2), и асимптотическая сложность всего алгоритма также находится в множестве O(m2).

Пример решения задачи

Полярные координаты точек-потребителей и соответствующие весовые коэффициенты заданы в табл. 1.

Таблица 1 Исходные данные задачи

i

wi

1

10

5

0

3

2

20

3

0

2

3

10

5

π/4

4

4

20

5

π/4

3

5

30

3

π/4

4

 

Решение. Шаг 1.

Шаг 2.

Шаг 3.

?

?

Условие  не выполняется, .

Шаг 4.

Шаг 5. Для каждого i от 2 до 5 цикл. Результаты шагов 5.1-5.3 сведены в табл. 2.

Шаг 6.

Таблица 2 Решение (шаги 5.1-5.3 алгоритма)

i

Шаг 5.1. значение

Шаг 5.1.

условие

Шаг 5.1. значение f*

Шаг 5.1. значение

Шаг 5.2. значение

Шаг 5.2.

условие

 

Шаг 5.2. значение

f*

Шаг 5.2. значение

2

1,25π

Не выполн.

1,25π

0

3,75π

Не выполн.

1,25π

0

3

π

выполняется

π

0,25π

Не выполн.

π

0,25π

4

1,25π

Не выполн.

π

0,25π

Не выполн.

π

0,25π

5

1,25π

Не выполн.

π

0,25π

Не выполн.

π

0,25π

Выводы

Задачи оптимального размещения формулируются в виде задачи Вебера с метрикой, основанной на измерении углового расстояния в том случае, если для транспортировки предполагается использование механизмов с телескопической стрелой. Решение задач Вебера с рассмотренной метрикой, основанной на измерении углового расстояния, сводится к решению задач с прямоугольной метрикой (l1) и выполняется за полиномиальное время. Эффективность алгоритма доказана аналитически, приведен пример решения задачи.

Рецензенты:

  • Антамошкин А.Н., д.т.н., проф., зав. кафедрой математического моделирования и информатики ФГОУ ВПО «Красноярский государственный аграрный университет», г. Красноярск;
  • Ступина А.А., д.т.н., проф., зав. кафедрой «Экономика и информационные технологии менеджмента» института управления бизнес-процессами и экономики Сибирского федерального университета.

Работа поступила в редакцию 06.09.2012.