СПОСІБ ДИНАМІЧНОЇ МАРШРУТИЗАЦІЇ ДОСТАВКИ ТОВАРУ В УМОВАХ ОБМЕЖЕНОСТІ ІНФОРМАЦІЇ ПРО СТАН ДОРОЖНЬОГО РУХУ

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

Корисна модель належить до інформаційних технологій на дорожньому транспорті, зокрема до способів динамічної маршрутизації в міській транспортній логістиці щодо доставки товару в умовах обмеженості інформації про стан дорожнього руху на вулично-дорожній мережі (ВДМ) міста. Як показує аналіз відомих аналогів динамічної маршрутизації в міській транспортній логістиці [1, 2], до теперішнього часу при вирішенні практичних аспектів цього завдання велика увага приділялась використанню ПС-даних. При цьому, як правило, використовувались основні переваги GPS/Galileo-технологій, що пов'язані з широкою зоною покриття, інтеграцією з іншими системами, отриманням даних про реальну конфігурацію сукупності ділянок ВДМ міста, а також відповідних атрибутів цих ділянок (обмеження за швидкістю, затори, час очікування на перехресті, дані про трафік у реальному часі тощо). Між тим, у більшості існуючих сучасних способів динамічної маршрутизації вирішуються в основному проблеми планування оптимальних маршрутів доставки товарів в транспортній логістиці при імітаційному аналізі впливу динаміки транспортних потоків на процеси доставки вантажів [1, 2]. При цьому оптимізація маршруту здійснюється за допомогою класичних методів дискретної оптимізації для транспортно-логістичних задач невеликої розмірності з використанням історичних ГІС-даних. В цьому контексті слід зазначити, що в сучасних умовах використання GPS/Galileo-технологій для вирішення динамічної маршрутизації транспортних засобів має свої недоліки. Зокрема, отримання відповідних даних за допомогою GPS/Galileo-сигналів у щільних міських каньйонах складної конфігурації, тунелях може бути не завжди коректним, що суттєво знижує точність інформації про трафік на ділянках ВДМ. Разом з тим, важливу роль набуває використання мережевих систем Vehicular Ad-Hoc Network (VANET) у покращенні дорожньої безпеки, підвищення ефективності функціонування транспортно-логістичних систем, наданні зручних сервісів для учасників транспортного процесу. VANET є самоорганізуючою мережею, яка використовується в транспортному середовищі для зв'язку між транспортними засобами (V2V технологія), транспортним засобом та придорожньою інфраструктурою (V2I технологія) і персональними мобільними пристроями [3]. Передбачається, що для вирішення транспортно-логістичних задач мандрівники мають доступ до інформації про дорожній рух в режимі реального часу через інфраструктури V2V/V2I та приймають рішення про вибір маршруту. Між тим, VANET створює унікальні проблеми завдяки своїй динамічній природі, що потребують значних зусиль для їх вирішення. Зокрема, ці проблеми пов'язані як з маршрутизацією передачі даних у високо динамічному V2V/V2I інформаційному середовищі, так і з динамічною маршрутизацією логістичних шляхів в нестаціонарному середовищі при забезпеченні стійкого VANET зв'язку. Найближчим аналогом є спосіб динамічної маршрутизації транспортних засобів [4], що включає здійснення моніторингу поточного стану ВДМ в режимі реального часу за допомогою сенсорів (датчиків) дорожнього руху у сполученні з технологіями "Internet of Things" (IoT) та "Artificial intelligence" (AI). Саме такий підхід забезпечує високу точність вимірювань характеристик динаміки транспортних потоків, а також можливість збору та аналізу даних у реальному часі. Основні недоліки такого способу динамічної маршрутизації [4] полягають в тому, що функціональні можливості блока вхідних даних про динамічні характеристики транспортних потоків на ділянках ВДМ обмежені тільки ручним режимом їх введення. Крім того, імітаційні дослідження щодо оптимізації маршруту тут здійснюються в рамках розв'язку симетричної динамічної задачі комівояжера (DTSP), що не дозволяє у повній мірі враховувати реальну конфігурацію та стан трафіку на ділянках ВДМ. Також на даний момент часу є загальний недолік збору даних про трафік за допомогою дорожніх датчиків в реальних умовах функціонування ВДМ, який не дозволяє у повній мірі ефективно впровадити зазначений спосіб динамічної маршрутизації. Це, в першу чергу, висока вартість сучасних сенсорів, наприклад, цифрових відеокамер з комп'ютерним зором, а також обмежена зона покриття, що вимагає встановлення великої кількості датчиків для отримання повної картини. В основу корисної моделі поставлена задача виконати спосіб динамічної маршрутизація в міській транспортній логістиці в режимі реального часу та умовах обмеженості інформації про стан дорожнього руху на ділянках ВДМ під час моніторингу трафіку. Формування раціональної мережі моніторингу трафіка забезпечують, з одного боку, отриманням достовірної інформації про поточний стан ВДМ, а з іншого боку, зменшують обсяг спостережень за динамікою транспортних потоків на ділянках ВДМ. Поставлена задача вирішується тим, що спосіб динамічної маршрутизації доставки товару в умовах обмеженості інформації про стан дорожнього руху, що включає використання сенсорів датчиків дорожнього руху на ділянках ВДМ, згідно з корисною моделлю, динамічну маршрутизацію здійснюють в режимі реального часу та умовах обмеженості інформації про стан дорожнього руху на основі поточних ІоТ-даних, що надходять від дорожніх датчиків руху, які розташовані і вимірюють інтенсивність транспортного потоку на відповідних ділянках ВДМ. На першому етапі здійснюють формування раціональної мережі моніторингу транспортних потоків на ВДМ шляхом реалізації покрокової ітераційної процедури знаходження репрезентативних елементарних ділянок в межах певних однорідних кластерів ВДМ, на яких рекомендується розміщувати сенсори (датчики) датчики руху, що здійснюють вимірювання динамічних параметрів транспортних потоків: інтенсивність (q), щільність ((), середня швидкість ((((). Відповідно, на інших ділянках ВДМ розміщено сенсори (датчики) дорожного руху, які вимірюють в реальному режимі часу величини інтенсивності транспортного потоку (q). В рамках досліджуваної ВДМ завжди існують визначена кількість однорідних кластерів ділянок ВДМ, що за своїми статичними та динамічними властивостями формування транспортних потоків на цих ділянках є подібними. Це означає, що динаміка транспортних потоків в області всіх режимів його формування, і, відповідно, форми кривих залежності q=q((((), мають якісно однаковий характер для всіх ділянок однорідного кластера транспортних потоків, і можуть відрізнятися тільки своїми кількісними значеннями q і ііі. Також це означає, що нормувальні коефіцієнти формування q=q(((() для набору ділянок певного кластеру ВДМ є постійними. Таким чином, знаючи такі нормувальні коефіцієнти, можна побудувати криві залежності q=q(((() для кожної ділянки однорідного кластера. Тоді, за виміряними експериментальними даними q, р, ррр, отриманими від сенсорів (датчиків) дорожнього руху на репрезентативній ділянці кластера, та експериментальними даними q, отриманих від сенсорів (датчиків) дорожнього руху на інших ділянках цього кластера, при відомих нормувальних коефіцієнтах можна побудувати сімейство градуювальних кривих залежності q=q(((() для сукупності ділянок кожного однорідного кластера ВДМ. Далі, для кожної градуювальної кривої за відомими експериментальними даними q можна визначати Залежності інтенсивності q та щільності т від середньої швидкості ввв транспортного засобу розглядаються в області щільного транспортного потоку, коли реалізуються режими синхронізованого руху та широкого рухомого кластеру транспортних засобів. Тут середня швидкість транспортного потоку є вже змінною. Знаходження значень динамічної характеристики иии здійснюється при використанні даних, отриманих із градуювальної кривої залежності q від (v). Нижче наведена процедура побудови сімейства градуювальних кривих для сукупності ділянок кожного однорідного кластера досліджуваної ВДМ. Для цього розглянемо функціональну залежність q=q(((() у вигляді поліному q(((()=a0+a1111+ … annnnn (1) і обмежимося кубічним членом. Функціональну залежність (1) справедливо розглядати при певних значеннях Ф ( =const). Проте у загальному випадку, особливо в області щільного транспортного потоку, в const, тому маємо більш складну залежність q=q((((). Між тим, для проведення імітаційного моделювання достатньо розглядати залежність у такому наближенні, оскільки вона якісно у повній мірі передає основні особливості поведінки транспортних потоків в області високої щільності (синхронізований рух, широкий рухомий кластер, затор). Введемо наступні характеристики транспортного потоку на репрезентативній ділянці r, що належить однорідному кластеру j: - середня швидкість транспортних засобів в транспортному потоці на r ділянці кластеру j ВДМ; - інтенсивність транспортного потоку (кількість транспортних засобів (N), що рухається за певний переріз ділянки r за час вимірювання , нормованої на 1 год, авт/год; - щільність транспортного потоку (кількість транспортних засобів (N), що рухається на ділянці r довжиною lrj, нормованої на 1 км, авт/км. На першому етапі проводять експериментальні (за допомогою сенсорів (датчиків) дорожнього руху) вимірювання qrj, ,rj, ,,,rj на певній ділянці ВДМ, що є репрезентативною (r) для певного j однорідного кластеру ділянок досліджуваної ВДМ. Визначають експериментальні середні значення qqrj ± qrj, rj ± rj, ,,,rj ± rj. Тут Тqrj, ,,,,rj, ,,rj - відповідні довірчі інтервали стандартного відхилення. За отриманими експериментальними даними будують залежності qrj=qrj((((). Отримані залежності в рамках регресійного аналізу апроксимують за допомогою поліномів (1), визначаючи відповідні набори коефіцієнтів a0, a1, …, an для репрезентативних ділянок. Крім того, із отриманих поліноміальних залежностей qrj=qrj((((), а також натурних даних, визначаються ааmaxmrj (згідно з правилами дорожнього руху), ((minmrj, qrj(((maxm), ))rj((qmaxm)), qrj(((minm), (qmax)rj, qrj((vv=0). Останнє значення відповідає стану затору. На підставі цих даних формують нормувальні коефіцієнти, які характеризують форму кривих залежності q=q((vv) на відповідних і ділянках однорідного кластеру j ВДМ, а саме: , , . (2) В рамках певного кластеру ВДМ, форми кривих залежності q=q((vv) і )((vv)=)((vv) для всіх ділянок цього кластеру ВДМ є подібними і можуть відрізнятися тільки своїми числовими значення динамічних характеристик транспортного потоку, які відносяться до цих кривих. Це означає, що нормувальні коефіцієнти для набору ділянок певного кластеру j ВДМ є однаковими. Тоді, для будь-якої ділянки і певного кластеру j ВДМ, числові значення поліноміальних коефіцієнтів а0*, а1*…, аn* для q*ij=q*ij((vv) i-ої ділянки можна визначити, розв'язуючи лінійну систему з трьох рівнянь для кубічної апроксимації: . (3) Tyт (qmax*)ij - максимальне значення інтенсивності транспортного потоку на ділянці i кластеру j ВДМ; - значення інтенсивності транспортного потоку, що відповідає на ділянці і кластеру j; - значення інтенсивності TF, що відповідає на ділянці і кластеру j. , , , визначаються за результатами усереднення відповідних історичних даних за певні проміжки часу. Після визначення згідно з (2) поліноміальних коефіцієнтів а0*, a1*, …, аn*, згідно з (1) будується функціональна залежність для кожної i-ої ділянки відповідного кластера r. Таким чином, в результаті проведення зазначеної процедури формується сімейство градуювальних кривих апроксимованої залежності q=q((vv) на ділянках ВДМ для всієї сукупності однорідних кластерів, що утворюють досліджувану ВДМ. Тоді, процедура моделювання онлайн дискретної оптимізації з динамічним оновленням маршруту здійснюється за допомогою вибраного АІ метода за ІоТ даними щодо q, отриманими в реальному режимі часу з кожної ділянки досліджуваної ВДМ. Тут, при проведенні оптимізації за критерієм часу використовуються градуювальні криві апроксимованої залежності q=q((vv) для визначення середніх значень швидкості транспортного потоку дvv на ділянках ВДМ в певні моменти часу. Тоді, час проходження кожної ділянки i кластера j визначається як , де , - довжина, середня швидкість транспортного потоку на ділянці і кластера j відповідно. Запропонований спосіб динамічної маршрутизації передбачає реалізацію через інформаційну систему, яка призначена для здійснення реоптимізації маршруту в реальному режимі часу при зміні стану ВДМ внаслідок зміну характеристик транспортного потоку на ділянках ВДМ в процесі доставки вантажів. Інформаційна система передбачає зведення задачі оптимізації маршруту доставки вантажу в множину пунктів до асиметричної динамічної задача комівояжера DTSP у вигляді двонаправлено орієнтованого зваженого графу в контексті ВДМ. Загальна схема роботи інформаційної системи показана на фіг. 1. Оптимізація маршруту здійснюється за критерієм довжини або часу. Для оптимізації за довжиною достатньо використання структурних даних ділянок ВДМ. Для оптимізації за часом використовуються вхідні дані структурних параметрів ділянок ВДМ та значення , отриманих безпосередньо від сенсорів руху на репрезентативних ділянках та з градуювальних кривих сімейства q=q(((() для інших ділянок в рамках кожного однорідного кластеру ВДМ. Інформаційна система передбачає (згідно з фіг. 1): 1 - вхідні дані: депо та пункти призначення; 2 - створення графу; 3 - отримання поточного стану завантаження ділянок ВДМ; 4 - обчислення очікуваного часу проходження кожної ділянки ВДМ; 5 - оновлення графу відповідно до поточного стану ВДМ; 6 - оптимізація маршруту з використанням АСОmоd; 7 - рух до наступного пункту призначення за оптимальним маршрутом; 8 - ГІС-дані; 9 - дані сенсорів (датчиків) дорожнього руху; 10 - історичні дані щодо ВДМ; 11 - блок розгалуження для перевірки умови, яка може мати дві відповіді: "так" (істинна) або "ні" (хибна); 12 - блок "виконання завершено". Зважаючи на наведене, користувач вводить множину пунктів доставки вантажу та депо (пункт відправлення та повернення). Після цього, система формує двонаправлено орієнтований зважений граф, вузли якого відповідають пунктам доставки вантажу та депо. Кожне ребро графу містять послідовність ділянок ВДМ, проходження яких визначає оптимальний маршрут між відповідною парою пунктів доставки вантажу у певний момент часу доби. Кожна така ділянка ВДМ з послідовності характеризуються певним ідентифікатором (назвою дороги), довжиною, кількістю смуг та напрямком руху по ній. Формування графу виконується на основі ПС-даних. Необхідні дані дозволяє отримати Routes API сервісу Bing Maps. Після формування графу виконується процедура оновлення графу відповідно до поточного стану ВДМ в певний момент часу доби. Процедура оновлення передбачає, що для кожної ділянки ВДМ із сукупності ділянок, що характеризують кожне ребро графу, в режимі реального часу отримуються дані про поточну інтенсивність транспортних потоків від сенсорів (датчиків) дорожнього руху, розташованих на відповідній ділянці. Із використанням цих даних та градуювальних кривих сімейства q=q((vv), сформованих на основі історичних даних про характеристики ВДМ для репрезентативних ділянок однорідних кластерів, визначається поточне значення середньої швидкості транспортного потоку на кожній ділянці ВДМ за відповідним напрямком руху. Маючи значення поточної швидкості на ділянках ВДМ та значення структурних параметрів кожної ділянки, визначається очікуваний час проходження відповідної ділянки. Це дозволяє визначати очікуваний час проходження кожного ребра графу як суму очікуваних часів проходження тої послідовності ділянок ВДМ, що характеризує відповідне ребро графу. Таким чином, ваги ребер оновленого графу характеризуються очікуваним часом проходження кожного з цих ребер, який враховує як поточний стан динаміки транспортного потоку, так і реальну конфігурацію ВДМ. Після оновлення графу виконується процедура оптимізації маршруту доставки вантажу на графі за допомогою модифікованого мурашиного алгоритму ACOmod [5]. Відповідно до визначеного оптимального маршруту користувачу пропонується рух в наступний пункт доставки вантажу. При прибутті користувача в цей пункт здійснюється наступне оновлення графу відповідно до поточного стану ВДМ. Після чого виконується процедура реоптимізації маршруту з використанням ACOmod на оновленому графі. При цьому в рамках запропонованого ACOmod реалізована можливість фіксації оптимальної конфігурації частково пройденого маршруту перед оновленням цього графу. Таким чином, в рамках запропонованої адаптивної системи динамічної маршрутизації процедура реоптимізації маршруту проводиться до тих пір, поки користувач не буде направлений назад в депо, виконавши доставку в усі задані пункти. Як підтвердження можливості застосування способу динамічної маршрутизації доставки товару в умовах обмеженості інформації про стан дорожнього руху наводиться наступний приклад. Для проведення імітаційних досліджень було вибрано 19 пунктів на ВДМ міста Києва (пронумеровані від 0 до 18), які відповідають адресам відділень поштового оператора. Необхідно знайти оптимальний за часом маршрут для транспортного засобу, який 25.09.2023 в 07:30:00 відправляється з депо (пункт 0), виконує доставку товару в пункти 1-18 і повертається в депо. Масив вхідних даних щодо динамічних характеристик транспортного потоку формувався з використанням даних ррр, ,qq, ,,, за результатами натурних експериментів, проведених на репрезентативних ділянках, та даних q, отриманих в режимі реального часу від сенсорів (датчиків) дорожнього руху, розташованих на ділянках досліджуваної ВДМ. У таблиці наведено результати імітаційного дослідження динамічної маршрутизації доставки вантажу у вказані пункти поштового оператора (частина кроків реоптимізації, які не призвели до перебудови оптимального маршруту не відображено). Тут колонка "current" - очікуваний час поточного оптимального маршруту у момент часу доби, коли здійснено реоптимізацію; "previous" - очікуваний час оптимального маршруту, отриманого за результатами попередньої реоптимізації, але для поточного динамічного стану ВДМ; "initial" - очікуваний час оптимального маршруту, отриманого за результатами оптимізації на момент відправки з депо, але для поточного динамічного стану ВДМ. У дужках наведено частину маршруту, яка перебудовується в результаті реоптимізації. ТаблицяРезультати динамічної маршрутизації доставки вантажу на ВДМ містаПоточний часПоточний оптимальний маршрутОчікуваний час проходження оптимального маршруту, с«current»«previous»«initial»07:30:000*1-18-2-4-7-13-9-5-12-10-15-11-8-17-16-3-6-14-010390——07:40:140-1*18-2-4-13-9-5-7-12-10-15-11-(17-8)-16-3-6-14-010486105251052507:55:200-1-18*2-4-13-(9-12-10-15-17-11-8-16-3-6-5-7-14)-010438104861052508:04:050-1-18-2*4-13-(9-14-3-16-15-11-17-8-10-6-12-5-7)-012632176961566308:13:200-1-18-2-4*13-9-14-3-16-15-11-17-8-10-6-12-5-7-011845118451347708:23:130-1-18-2-4-13*9-14-3-16-15-11-17-8-10-6-12-5-7-011887118871413608:37:270-1-18-2-4-13-9*14-3-16-15-11-17-8-10-6-12-5-7-012220122201501508:52:170-1-18-2-4-13-9-14*3-16-15-11-17-8-10-6-12-5-7-011800118001472709:01:280-1-18-2-4-13-9-14-3*(10-15-11-17-8-16-6)-12-5-7-010732108321259009:13:050-1-18-2-4-13-9-14-3-10*15-11-17-8-16-6-12-5-7-010704107041325210:21:010-1-18-2-4-13-9-14-3-10-15-11-17-8-16-6-12-5-7*010746107461674210:29:060-1-18-2-4-13-9-14-3-10-15-11-17-8-16-6-12-5-7-0*—1074616742 Як видно з таблиці, при проведенні імітаційних досліджень за допомогою запропонованого способу динамічної маршрутизації доставки товару в умовах обмеженості інформації про стан дорожнього руху, було виявлено низку ефектів, що пов'язані з перебудовою оптимального маршруту. Так, наприклад, в моменти часу доби 07:55:20; 08:04:05; 09:01:28 відбувається суттєва перебудова оптимального маршруту. Також у всіх випадках в поточні моменти часу доби спостерігається суттєве збільшення часу доставки товару за "initial" конфігурацією оптимального маршруту, відносно часу вихідного оптимального маршруту, побудованого у 07:30:00. Ці ефекти обумовлені суттєвим збільшенням та перерозподілом кількості транспортних засобів на ділянках ВДМ у відповідні моменти часу доби. При цьому проведення реоптимізації дозволяє знаходити в режимі реального часу такі оптимальні маршрути, які призводять до суттєвого зниження часу доставки товару у відповідні пункти. Наприклад, о 08:04:05 "initial" - 15663 с, "current" - 12632 с. Це означає, що після проведення реоптимізації маршруту в пункті доставки 2, зменшується час доставки товару за оновленим оптимальним маршрутом на Цt = 15663 с - 12632 с = 3031 с, тобто спостерігається економічний ефект у 19.4 %. ДЖЕРЕЛА ІНФОРМАЦІЇ: 1. Tsoukas, V., Boumpa, E., Chioktour, V., Kalafati, M., Spathoulas, G., & Kakarountas, A. (2023). Development of a Dynamically Adaptable Routing System for Data Analytics Insights in Logistic Services. Analytics, 2 (2), 328-345. https://doi.org/10.3390/analvtics2020018. 2. Lyu, Z., Pons, D., Zhang, Y., & Ji, Z. (2021). Freight Operations Modelling for Urban Delivery and Pickup with Flexible Routing: Cluster Transport Modelling Incorporating Discrete-Event Simulation and GIS. Infrastructures, 6 (12), 180. https://doi.org/10.3390/infrastructures6120180. 3. Saoud, В., Shayea, I., Yahyad, A., Zaid Ahmed Shamsan, Z., Alhammadi, A., Alawad, M, Alkhrijah, Ya. (2024), Artificial Intelligence, Internet of things and 6G methodologies in the context of Vehicular Ad-hoc Networks (VANETs): Survey, ICT Express, 22. https://doi.org/10.1016/i.icte.2024.05.008. 4. Danchuk, V., Соmі, A., Weiß, C, & Svatko, V. (2023). The optimization of cargo delivery processes with dynamic route updates in smart logistics. Eastern-European Journal of Enterprise Technologies, 2 (3 (122), 64-73. https://doi.org/100.15587/1729-4061.2023.277583. 5. Danchuk, V., Hutarevych, O. ADAPTABLE DYNAMIC ROUTING SYSTEM IN URBAN TRANSPORT LOGISTICS PROBLEMS USING GIS DATA. Scientific Journal of Silesian University of Technology. Series Transport, 2024, 125, pp. 19-31. https://doi.org/10.20858/sisutst.2024.125.2