Задача про розміщення об'єктів

Зада́ча про розмі́щення об'є́ктів, відома також як ана́ліз розташува́ння обла́днання або зада́ча k-це́нтра — це гілка дослідження операцій і обчислювальної геометрії, яка досліджує оптимальне розташування об'єктів з метою мінімізувати ціни перевезень з урахуванням таких обмежень, як розміщення небезпечних матеріалів поблизу житла та об'єктів конкурентів. Ці методи також знаходять застосування у кластерному аналізі.

Задача про розміщення об'єктів з мінімізацією

Проста задача про розміщення об'єктів — це задача Вебера, в якій розміщується один об'єкт з метою мінімізації зваженої суми відстаней до заданої множини точок. Складніші завдання цієї дисципліни виникають за обмежень на розміщення об'єктів і за використання складніших критеріїв оптимізації.

У базовому формулюванні задача про розміщення об'єктів складається з потенційних точок забудови L, де об'єкти можуть бути створені, і точок D, які слід обслужити. Мета — вибрати підмножину F точок розміщення об'єктів з метою мінімізувати суму відстаней від кожної точки обслуговування до найближчого обслуговувального об'єкта, плюс суму вартостей розміщення об'єктів.

Задачу про розміщення об'єктів на загальних графах NP-складно розв'язати оптимально, зведенням, наприклад, від задачі про покриття множини. Розроблено кілька алгоритмів для задач про розміщення об'єктів і багатьох варіантів цієї задачі.

Без припущень про властивості відстаней між клієнтами та місцями розташування об'єктів (зокрема, без допущення, що відстань задовольняє нерівність трикутника), задача відома як неметри́чна зада́ча про розмі́щення об'є́ктів і її можна апроксимувати з множником O (log n)Шаблон:Sfn. Множник тісний, що випливає зі Шаблон:Нп із задачі покриття множини.

Якщо ми припускаємо, що відстані між клієнтами та місцями розміщення об'єктів неорієнтовані й задовольняють нерівність трикутника, ми говоримо про задачу метри́чного розмі́щення об'є́ктів (МРО). МРО залишається NP-складною задачею і її важко апроксимувати зі множником, кращим ніж 1,463Шаблон:Sfn. На даний час кращий апроксимаційний алгоритм має коефіцієнт 1,488Шаблон:Sfn.

Мінімаксне розміщення об'єктів

Мініма́ксна зада́ча про розмі́щення об'є́ктів шукає розміщення, яке мінімізує максимальні відстані до місць розміщення, де відстань від деякої точки до місць розміщення — це відстань від точки до найближчого місця розміщення. Формальне визначення таке: Якщо задано множину точок P ⊂ ℝ^d, потрібно знайти множину точок S ⊂ ℝ^d, |S| = k, таку, що значення max_p ∈ P(min_q ∈ S(d(p, q))) буде мінімальним.

У разі евклідової метрики при k = 1 задача відома як задача про найменшу обмежувальну сферу або задача про 1-центр. Вивчення задачі простежується щонайменше до 1860 року, див. докладніше в статті «Обмежувальна сфера».

NP-складність

Доведено, що точне розв'язання задачі k-центра є NP-складнимШаблон:Sfn Шаблон:Sfn Шаблон:Sfn. Виявлено, що апроксимація задачі буде теж NP-складною, якщо похибка мала. Рівень похибки в апроксимаційному алгоритмі вимірюється коефіцієнтом апроксимації, який визначається як відношення апроксимованого розв'язку до оптимального. Доведено, що апроксимація задачі k-центра є NP-складною, якщо коефіцієнт апроксимації менший, ніж 1,822 (для розмірності 2)Шаблон:Sfn або 2 (для розмірності >2)Шаблон:Sfn.

Алгоритми

Точний розв'язок

Існують алгоритми, що дають точний розв'язок задачі. Один із таких алгоритмів дає розв'язок за час $n^{O (\sqrt{k})}$ Шаблон:Sfn Шаблон:Sfn.

Апроксимація 1 + ε

Апроксимація 1 + ε знаходить розв'язок з апроксимаційним коефіцієнтом, що не перевершує 1 + ε. Така апроксимація NP-складна у випадку довільного ε. Запропоновано підхід, заснований на концепції Шаблон:Не перекладено, зі складністю виконання $O (2^{O (k \log k / ε^{2})} d n)$ Шаблон:Sfn. Доступний альтернативний алгоритм, що також ґрунтується на базових наборах. Він працює за час $O (k^{n})$ Шаблон:Sfn. Автор стверджує, що час роботи значно менший від часу гіршого випадку і існує можливість розв'язати деякі задачі в разі малих k (приміром, k < 5).

Виділення віддалених точок

Через складність задачі, непрактично шукати точний розв'язок або близьку апроксимацію. Замість цього для великих k широко використовують апроксимацію з коефіцієнтом 2. Ця апроксимація відома під назвою «Алгоритм виділення віддалених точок» (ВВТ = Шаблон:Lang-en) або як алгоритм Шаблон:Не перекладено Шаблон:Sfn. Алгоритм досить простий: вибираємо як центр довільну точку множини, знаходимо найдальшу з решти множини і вважаємо її наступним центром. Продовжуємо процес, поки не наберемо k центрів.

Легко бачити, що алгоритм працює за лінійний час. Оскільки доведено, що апроксимація з коефіцієнтом, меншим від 2, NP-складна, ВВТ вважають кращою апроксимацією.

Пізніше за допомогою техніки рамкової декомпозиції часову складність виконання покращено до O(n log k)Шаблон:Sfn.

Максимінне розміщення об'єктів

Задача максимі́нного розмі́щення об'є́ктів шукає розміщення, яке максимізує мінімальні відстані до сторін. У випадку евклідової метрики задача відома як задача про найбільшу порожню сферу. Плоский випадок (найбільшого порожнього кола) можна розв'язати за час Θ(n \log n)Шаблон:Sfn Шаблон:Sfn.

Вільно поширюване програмне забезпечення для розв'язування задач розміщення об'єктів

Назва (за абеткою)	Ліцензія	Коротка інформація
FLP Spreadsheet Solver	Creative Commons Attribution 4.0 International License	Система на основі Microsoft Excel і VBA з відкритим кодом для розв'язування задачі про розміщення об'єктів із посиланням на ГІС загального доступу (посилання). Відео уроки Шаблон:Webarchive Шаблон:Sfn.
ODL Studio	LGPL	Обмежений кластерний компонент в ODL Studio розв'язує задачу про P-медіану (розміщення з мінімізацією зваженої суми відстаней). Програма включає плани розміщення, звіти та завантаження/вивантаження в Excel. (Уроки з ODL Studio Шаблон:Webarchive)
SITATION	freeware	Може розв'язувати задачі п'яти класів: P-медіана, P-центр, покриття множинами, максимальне покриття і задача з фіксованими витратами без обмеження пропускної здатності[1] Шаблон:Webarchive Шаблон:Sfn.

Див. також

Примітки

Література

Посилання

INFORMS section on location analysis Шаблон:Webarchive, професійна спільнота з вивчення проблем розміщення.
Бібліографія щодо задач розміщення, зібрана Тревором Гале, яка містить понад 3400 статей.
Бібліотека алгоритмів розміщення
Утиліта для розміщення виробництва (у вебваріанті).
Оптимізатор розміщення виробництва Шаблон:Webarchive, заснований на MATLAB, засіб для розв'язування задач розміщення виробництва.

Шаблон:Бібліоінформація

Задача про розміщення об'єктів

Зміст