Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

АЛГОРИТМ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ С НЕЕВКЛИДОВОЙ МЕТРИКОЙ, ОСНОВАННОЙ НА УГЛОВОМ РАССТОЯНИИ

Казаковцев Л.А. 1
1 Сибирский государственный аэрокосмический университет
Исследована непрерывная минсумная задача Вебера с единственным размещаемым объектом на плоскости с метрикой, основанной на угловом расстоянии, предложен алгоритм на основе алгоритма для задачи Вебера с прямоугольной (манхэттенской) метрикой. Производится декомпозиция рассматриваемой задачи в множество задач Вебера с прямоугольной метрикой, к которым применяется стандартная процедура. Дан пример решенной задачи. Метрика, с помощью которой определяется расстояние, различна в зависимости от ситуации. Для механизмов с вращающейся телескопической стрелой (подъемные краны, манипуляторы и др.) евклидово расстояние не отражает затраты на перемещение объекта между двумя точками. Автором рассмотрены 2 стратегии оптимального управления для таких систем с соответствующими функциями расстояния, предложен алгоритм решения задачи Вебера для одной из них. Для предлагаемого алгоритма дано аналитическое доказательство оптимальности результата.
угловое расстояние
задачи размещения
задача Вебера
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.


Библиографическая ссылка

Казаковцев Л.А. АЛГОРИТМ ДЛЯ ЗАДАЧИ РАЗМЕЩЕНИЯ С НЕЕВКЛИДОВОЙ МЕТРИКОЙ, ОСНОВАННОЙ НА УГЛОВОМ РАССТОЯНИИ // Фундаментальные исследования. – 2012. – № 9-4. – С. 918-923;
URL: http://www.fundamental-research.ru/ru/article/view?id=30422 (дата обращения: 11.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074