Пошук оптимального шляху

Короткий огляд

Пошук найкоротшого шляху в дорожній мережі – це процес аналізу, спрямований на визначення найбільш ефективного способу пересування між точками на карті. Цей інструмент може бути корисним для створення оптимальних маршрутів з кількома зупинками або вимірювання відстані та часу подорожі між різними місцями розташування. З кожним запитом наша технологія може знаходити оптимальні маршрути для одного або декількох транспортних засобів. Наприклад, вона може допомогти водіям знайти оптимальні маршрути для доставки товарів або визначити оптимальну відстань від дому до роботи для різних пасажирів.

Можливості алгоритму

Наша бібліотека надає можливість побудувати найбільш оптимальний маршрут між двома точками на карті. Вона має наступні основні функції:

Пошук оптимального шляху на карті, враховуючи стежки та перешкоди: Ми враховуємо не тільки дороги, але й бездоріжжя, такі як стежки, пішохідні доріжки та перешкоди, які можуть вплинути на вибір оптимального маршруту.
Пошук оптимального шляху лише дорогами: Якщо вам потрібно знайти маршрут виключно дорогами, ми надаємо цю можливість. Це корисно, наприклад, для транспортних засобів, яким дозволено пересуватися тільки дорогами.
Встановлення різних швидкостей для доріг: Ми маємо можливість призначати різні швидкості різним дорогам. Наприклад, вищі швидкості можуть бути встановлені для головних автомагістралей, а нижчі – для вузьких провулків.
Встановлення прямокутних перешкод: Ви можете визначити прямокутні перешкоди на карті, які необхідно враховувати при побудові оптимального маршруту. Це корисно, коли є відомі перешкоди, такі як будівлі або озера (їхнє наближення).
Обмеження радіуса пошуку для доріг: Ви можете обмежити радіус пошуку для доріг, щоб зменшити час пошуку та зосередитися лише на певній області.
Контроль продуктивності та точності: Ми надаємо можливість контролювати продуктивність і точність алгоритму. Ви можете налаштувати його для досягнення бажаного балансу між швидкістю пошуку та точністю побудови маршруту.

Далі ми надамо більш детальний опис кожної з цих функцій та розглянемо приклади їх застосування.

Підхід до рішення

Хоча прокладання шляху є нетривіальною задачею, існує кілька хороших і надійних алгоритмів, які визнаються в спільноті розробників.

У нашій реалізації ми використовували модифікований алгоритм Лі. У нас є сітка клітинок на площині. Від початкової точки хвиля поширюється у 8 напрямках (включаючи діагоналі) до сусідніх клітинок, обчислюючи час, необхідний для досягнення кожної з них. Сусідня клітинка може містити перешкоду або дорогу. Дороги можуть мати різні коефіцієнти швидкості. Таким чином, ми “маркуємо” нашу сітку часом, який потрібен для досягнення кожної клітинки від початкової клітинки в межах певного радіуса або до досягнення кінцевої точки. Якщо ми досягаємо кінцевої точки, ми будуємо зворотний шлях, використовуючи нашу сітку.

Щоб визначити оптимальний маршрут дорожньою мережею, необхідно виконати кілька кроків. Спочатку потрібно визначити дороги та вказати швидкість руху на кожній з них. Також слід враховувати наявність штучних і природних перешкод, які можуть вплинути на проходження шляху. Після цього необхідно вказати початкову та кінцеву точки пошуку. Як тільки ці попередні кроки виконано, можна перейти до фактичного прокладання шляху. Результатом буде шлях, представлений, наприклад, у вигляді списку координат точок.

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

Демо-проект на GitHub

Щоб краще зрозуміти функціональність нашої бібліотеки, розглянемо приклад її використання. Цей код ілюструє, як налаштувати дороги та перешкоди в алгоритмі прокладання шляху та знайти оптимальний маршрут.

Приклад складається з наступних кроків:

Створення списку інформації про дороги (RoadInfo), який включає інформацію про дорожній сегмент (Segment) і швидкість руху (Velocity).
Додавання швидкісних доріг до списку.
Додавання повільних кільцевих доріг до списку.
Створення генератора шару шляхів (WayLayerGenerator) та додавання доріг до генератора.
Пошук кількох маршрутів від початкової точки (startPoint) до кінцевих точок (goalPoint01, goalPoint02, goalPoint03) з використанням вказаного радіуса (radius).
Підготовка шару доріг (roadsLayer) для відображення на карті та додавання дорожніх об’єктів.
Підготовка шару шляхів (wayLayer) для відображення на карті та створення геометричних об’єктів для кожного знайденого маршруту.
Відображення карти за допомогою функції ShowMap, збереження карти в зазначеному шляху.

Цей код будує та відображає дорожні шляхи на карті для визначених точок, використовуючи інформацію про дороги та генератор шару шляхів.

Параметри пошуку

Прокладання шляху виконується за допомогою класу WayLayerGenerator, розташованого в просторі імен Aspose.Gis.GeoTools.WayAnalyzer.

Клас WayLayerGenerator має метод FindTheWay для знаходження шляху від початкової точки до цільової. Щоб створити екземпляр класу WayLayerGenerator, ми передаємо WayOptions як параметри (всі параметри необов’язкові):

StartPoint: Початкова точка
GoalPoint: Цільова точка
Radius: Радіус пошуку
Scale: Масштаб сітки
IsMoveOnlyRoad: Чи шукати шлях лише дорогами

Особливістю тут є параметр Scale. Якщо він вказаний у конструкторі, ми фіксуємо постійний масштаб для наступних пошуків. Якщо параметр Scale не встановлено, але StartPoint і GoalPoint встановлені, ми обчислюємо масштаб як відстань між початковою та кінцевою точками, поділену на 100. У всіх інших випадках значення за замовчуванням Scale дорівнює 1. Для досвідчених користувачів краще встановити Scale або безпосередньо StartPoint і GoalPoint для найбільш ефективного представлення доріг та перешкод у сітці (особливо якщо їх багато).

Щоб використовувати метод FindTheWay, нам потрібно вказати початкову та кінцеву точки. Ми також можемо встановити радіус пошуку (відстань, на яку поширюється хвиля). За замовчуванням радіус обчислюється як відстань між початковою та кінцевою точками, помножена на 3. Початкова і кінцева точки можуть бути близькими або дуже віддаленими одна від одної, тому, виходячи з відстані між ними, ми обчислюємо масштаб нашої сітки. Якщо поточний масштаб не відповідає попередньому, ми перераховуємо сітку. Масштаб можна зафіксувати, використовуючи параметр Scale. У цьому випадку він не обчислюється, і сітка не перераховується.

Перед початком пошуку нам потрібно визначити карту доріг та перешкод, використовуючи відповідні методи AddRoad та AddBlock класу WayLayerGenerator.

Для методу AddRoad нам потрібно вказати:

startPoint: Початкова точка дороги
endPoint: Кінцева точка дороги
velocity: Швидкість руху на дорозі

Для методу AddBlock нам потрібно вказати:

x: X-координата верхнього лівого кута блоку
y: Y-координата верхнього лівого кута блоку
sizeX: Розмір по осі X
sizeY: Розмір по осі Y

Ці методи дозволяють нам визначити карту доріг та перешкод перед початком процесу прокладання шляху.

Приклади коду

Ось кілька прикладів коду, які ілюструють, як налаштувати дороги та перешкоди в алгоритмі прокладання шляху та знайти оптимальний маршрут.

Приклад 1: Пошук шляху між початковою та кінцевою точками.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(5, 7);
Point goalPoint = new Point(15, 13);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

Приклад 2: Встановлення параметра масштабу та наявність негативних координат для точки.

WayOptions mapGeneratorOptions = new WayOptions(1);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(-50, -70);
Point goalPoint = new Point(150, 130);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

Приклад 3: Встановлення параметра IsMoveOnlyRoad та радіуса пошуку.

WayOptions mapGeneratorOptions = new WayOptions();
mapGeneratorOptions.IsMoveOnlyRoad = true;
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddRoad(new Point(100, 100), new Point(140, 150), 10);
generator.AddRoad(new Point(140, 150), new Point(190, 100), 10);
Point startPoint = new Point(100, 100);
Point goalPoint = new Point(190, 100);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 100);

Приклад 4: Встановлення параметра масштабу для швидшого пошуку.

WayOptions mapGeneratorOptions = new WayOptions(10);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(50, 70);
Point goalPoint = new Point(1650, 1300);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 2500);

Приклад 5: Приклад множинного пошуку.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddBlock(200, 1700, 1500, 100, 0);
generator.AddBlock(1700, 200, 100, 1600, 0);
generator.AddBlock(200, 200, 1500, 100, 0);
generator.AddRoad(new Point(1000, 1150), new Point(200, 600), 10);
generator.AddRoad(new Point(50, 450), new Point(150, 1850), 10);

Point startPoint = new Point(1000, 1000);
Point goalPoint = new Point(1900, 1000);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 3500);

Point startPoint = new Point(50, 50);
Point goalPoint = new Point(70, 70);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

Ці приклади коду будують та відображають дорожні шляхи на карті для визначених точок, використовуючи інформацію про дороги та генератор шару шляхів.

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