Перейти до вмісту
Технології та розробка

Планування маршрутів на відкритих рушіях: VROOM і Valhalla

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

АвторArtem ShevchenkoЗасновник і архітектор систем
  • 8 хв читання
  • 1 перегляд
Планування маршрутів на відкритих рушіях: VROOM і Valhalla

Порядок доставок для кількох авто з часовими вікнами клієнтів, вантажопідйомністю та перервами водіїв — це завдання, яке в інформатиці має власну назву: задача маршрутизації транспортних засобів (VRP). Розв’язувати її з нуля чи купувати підписку не потрібно. Існують відкриті рушії, які роблять це вже багато років, а їхній код і документація публічні.

Два елементи: оптимізатор і рушій маршрутів

Планування маршруту складається з двох кроків. Спершу треба знати, скільки триває проїзд від кожної точки до кожної іншої справжніми дорогами: це робить рушій маршрутів, наприклад OSRM або Valhalla, на даних OpenStreetMap. Потім оптимізатор, наприклад VROOM, укладає з цього порядок точок для кожного авто.

Згідно з документацією, VROOM підтримує: багато авто й кілька баз, часові вікна, вантажопідйомність у кількох вимірах (наприклад, вага й палети), перерви водіїв, забір і доставку в одному рейсі та необхідні допуски, наприклад лише авто з гідробортом до певного клієнта. Відстані бере з OSRM, Valhalla чи openrouteservice без додаткової роботи, а також приймає власну матрицю.

До даних для VROOM можна також дописати пріоритет замовлення та ліміти кількості завдань, часу проїзду і дистанції. Слід пам’ятати, що VROOM сам доріг не знає. Кожне обмеження, що залежить від мапи, наприклад заборона в’їзду, має вже міститися в матриці проїздів, яку він отримує від рушія маршрутів.

Рушії маршрутів різняться тим, що вміють, окрім прокладання одного маршруту. OSRM рахує матрицю часу й відстаней між багатьма точками одразу, тобто саме те, чого потребує оптимізатор. Valhalla теж рахує матрицю, а до того ізохрони, тобто територію, до якої авто доїде за заданий час, і зіставляє записаний слід проїзду з дорогами на мапі. Ізохрон OSRM не має; їх мають Valhalla, GraphHopper і openrouteservice.

Вантажівка — не легковик

Тут починається різниця, яка для перевізника має значення. Відкритий OSRM має профілі для автомобіля, велосипеда і пішохода, але не має профілю вантажівки. Valhalla має: враховує висоту, ширину, довжину і масу транспортного засобу, навантаження на вісь і небезпечний вантаж. Тому для вантажного автопарку ми пропонуємо пару VROOM і Valhalla, а для бусів і авто для доставки, де габарити рідко обмежують маршрут, часто досить OSRM. Наскільки точно мапа описує обмеження на ваших маршрутах, варто перевірити на власних даних, перш ніж обіцяти результат.

У Valhalla параметри авто подають у моделі витрат для вантажівки: висоту, ширину й довжину в метрах, масу в тоннах, навантаження на вісь, кількість осей та інформацію про небезпечний вантаж. Якщо їх не вказати, рушій прийме значення за замовчуванням, наприклад висоту 4,11 м і масу 21,77 т. Тому параметри кожного авто в автопарку варто вписати окремо.

Профіль вантажівки мають також openrouteservice (профіль driving-hgv: довжина, ширина, висота, навантаження на вісь, маса й небезпечний вантаж) та відкрите ядро GraphHopper (профіль truck, який оминає дороги із забороною в’їзду для вантажівок і порівнює обмеження ширини, висоти й маси на дорозі з параметрами авто). Спільне правило: обмеження вантажівки потраплять у план VROOM лише тоді, коли матрицю проїздів порахує рушій із профілем вантажівки. З матрицею з OSRM цих обмежень у плані не буде.

Коли правила нестандартні, беруться за солвер: Google OR-Tools або Timefold Solver у версії Community. Обидва потребують більше програмістської роботи, але дають змогу описати майже будь-яке обмеження.

OR-Tools — це бібліотека, яку вбудовують у власний сервіс. Підтримує, зокрема, часові вікна, вантажопідйомність, забір із доставкою, окремі початок і кінець маршруту для кожного авто, перерви та пропуск точки зі штрафом, коли її неможливо обслужити. Доріг сама не рахує: матрицю часу їй треба подати, наприклад з OSRM або з Valhalla. Timefold Solver ділить обмеження на жорсткі, середні й м’які та дає змогу перерахувати план протягом дня, залишаючи на місці завдання, які хтось закріпив. Для планування маршрутів ми натомість не пропонуємо функцій VRP із pgRouting: документація позначає їх як експериментальні й попереджає, що вони можуть призвести до збою сервера.

Як виглядає такий проєкт крок за кроком

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

  1. Замовлення й автопарк. Відправна точка — дані, які компанія вже має: замовлення з адресами, часовими вікнами клієнтів, вагою й кількістю палет, а також авто з вантажопідйомністю, базою і годинами роботи. Для вантажівок додаються розміри й маса, а за деяких вантажів — інформація, що вони небезпечні.
  2. Адреси на мапі. Оптимізатор працює з точками, а не з адресами. Перетворити адресу на точку, тобто геокодування, може Nominatim на даних OpenStreetMap. Photon, другий відкритий геокодер, підказує адресу вже під час введення і справляється з помилками в написанні. Адреса, яку геокодер не знайде, потрапляє до працівника на виправлення, а виправлена точка зберігається в картці клієнта.
  3. Матриця проїздів. Рушій маршрутів рахує час і відстані між усіма точками дня. Для вантажного автопарку це робить рушій із профілем вантажівки.
  4. Правила плану. До даних додаються обмеження: часові вікна, вантажопідйомність, перерви водіїв, необхідні допуски авто та пріоритети замовлень. Правило, яке не можна записати у VROOM, — сигнал взятися за OR-Tools або Timefold.
  5. Рішення диспетчера. Оптимізатор пропонує порядок точок для кожного авто. Диспетчер бачить план на мапі, змінює те, про що система не знає, і затверджує план, перш ніж він потрапить до водіїв.

Що треба запустити на сервері

На сервері потрібні три сервіси: оптимізатор, рушій маршрутів і геокодер. VROOM має готовий образ Docker vroom-docker, у якому є сам оптимізатор і vroom-express, тобто HTTP-сервіс, що приймає завдання. Рушій маршрутів у ньому обирають одним налаштуванням: OSRM, Valhalla або openrouteservice. OSRM і Valhalla також мають готові образи, а дані мапи — це витяг з OpenStreetMap, наприклад із сервісу Geofabrik.

Одне застереження стосується openrouteservice: його вбудована оптимізація працює лише в публічному API, а не на власному екземплярі. На власному сервері порядок точок укладає окремо запущений VROOM, а openrouteservice рахує проїзди.

Ліцензії та витрати

VROOM і OSRM мають ліцензію BSD, Valhalla — MIT, OR-Tools і Timefold Community — Apache 2.0. Ви не платите за ліцензію, а код вашої системи залишається закритим. Платять за впровадження і сервер. Мапа вимагає одного: підпису «© OpenStreetMap contributors» із посиланням на сторінку авторських прав OSM. Остерігайтеся платних версій: оптимізація маршрутів GraphHopper — це хмарний сервіс, а Timefold Enterprise потребує ліцензії.

Ліцензії BSD, MIT і Apache 2.0 дозволяють вбудувати рушій у закриту систему. Треба лише зберегти повідомлення про авторські права і текст ліцензії, а за Apache 2.0 також файл NOTICE, якщо проєкт його має. На Apache 2.0 є й відкрите ядро GraphHopper, яке можна запустити в себе. Платні його хмарні сервіси, а безкоштовний план призначений лише для некомерційного використання.

З ліцензією GPL інакше. Її мають openrouteservice і геокодер Nominatim (GPL версії 3), а також pgRouting (GPL версії 2). Обов’язок надати вихідний код виникає при передаванні програми, а текст GPLv3 прямо каже, що сама робота користувача з програмою через мережу, без передавання копії, передаванням не є. Тому такий інструмент ми пропонуємо запустити як окремий сервіс на вашому сервері, а не поєднувати його код із кодом вашої системи. Хто передає комусь змінену версію такої програми, мусить надати вихідний код змін на умовах GPL. Ліцензії AGPL не має жоден із названих тут інструментів. Оцінку для конкретного проєкту варто, втім, залишити юристові.

Дані OpenStreetMap надаються за ліцензією Open Database License (ODbL). Треба зазначити, що вони походять з OpenStreetMap і надаються за цією ліцензією, з посиланням на сторінку авторських прав OSM. Правила Фонду OpenStreetMap допускають підпис «© OpenStreetMap» або «© OpenStreetMap contributors», розміщений на мапі в куті чи поряд із нею. Вказати OpenStreetMap мусить і застосунок, що прокладає маршрути на цих даних. У системі, яку ми збудуємо, підпис «© OpenStreetMap contributors» із посиланням буде біля кожної мапи маршруту і в порталі клієнта.

З чого почати

Ми будуємо системи зі ШІ, інтеграціями та зчитуванням документів для інших галузей, але системи для логістики ще не будували. Тому пропонуємо почати не з обіцянок, а з проби. Досить даних із кількох звичайних днів: замовлення з адресами і часовими вікнами та список авто з вантажопідйомністю й базами. На цій основі ми можемо укласти план відкритим рушієм і покласти його поруч із планом, який підготував диспетчер. Таке порівняння покаже, чи правила добре описані і чи мапа знає обмеження на ваших маршрутах.

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

Якщо хочете перевірити, як такий рушій уклав би маршрути з ваших замовлень, опишіть свій процес.

Джерела

Теги

Поділитися статтею

Повернутися до блогу

Файли cookies

Ми використовуємо необхідні файли cookies та один функціональний, який вмикаємо лише за вашою згодою. Статистику відвідувань рахуємо на сервері, без cookies. Політика cookies