АЛГОРИТМ ТА ПРОГРАМНИЙ ЗАСІБ ДЛЯ ВИРІШЕННЯ ПРОБЛЕМИ МІСЦЕВИХ ПАСАЖИРСЬКИХ ПЕРЕВЕЗЕНЬ
DOI:
https://doi.org/10.17721/2519-481X/2025/87-08Ключові слова:
оптимізація міського транспорту, алгоритм спільного використання поїздок, зіставлення маршрутів, інтелектуальні транспортні системиАнотація
У контексті сучасної урбанізації та глобальних екологічних проблем, оптимізація систем пасажирських перевезень стала важливою галуззю досліджень, особливо в галузі енергозбереження та зменшення впливу на навколишнє середовище. Це дослідження розглядає конкретний аспект цієї широкої проблеми: ефективне використання вільних місць у приватних транспортних засобах для збільшення пропускної здатності транспорту без розширення дорожньої інфраструктури. Центральна ідея полягає в перерозподілі пасажирів, які користуються схожими або перекриваючимися маршрутами з власниками приватних автомобілів, використовуючи сучасні інформаційні технології для полегшення зіставлення та комунікації в режимі реального часу.
Робота починається з викладу концептуальної основи проблеми, підкреслюючи, що численні міські жителі щодня долають значні відстані, тоді як доступна транспортна інфраструктура залишається обмеженою. З огляду на це, значного підвищення ефективності транспорту можна досягти, використовуючи вільні місця в приватних транспортних засобах. Хоча соціально-економічні та мотиваційні фактори, такі як екологічна обізнаність, фінансові стимули або альтруїстична поведінка, можуть стимулювати такі ініціативи, стаття зосереджується виключно на технічних та алгоритмічних аспектах рішення, навмисно виключаючи суб'єктивний вимір мотивації водіїв.
Побудовано формальну постановку проблеми, яка моделює мережу міських доріг як математичний граф, де перехрестя представлені як вузли, а сегменти доріг (квартали) як ребра. Маршрут кожного водія та пасажира визначається як послідовність перехресть, а основною умовою для призначення пасажира водієві є повне включення маршруту пасажира до маршруту водія. Це обмеження, яке називається «Правилом жорсткості маршруту» (3R), гарантує, що ні водій не змінює свій маршрут, ні пасажир не відхиляється від запланованого шляху.
Архітектура алгоритму зосереджена на методах обробки рядків, де послідовності маршрутів кодуються як рядки, а включення перевіряється за допомогою операцій з підрядками. Ключова функція I(d, p) вводиться для кількісної оцінки кількості перекриваючих кварталів між маршрутом водія d та маршрутом пасажира p. Ця функція служить основою для перевірки сумісності маршрутів та, зрештою, розрахунку ефективності певного розподілу.
Ефективність системи визначається цільовою функцією E, яка представляє загальну кількість обслуговуваних пасажирських кварталів. Метою оптимізації є максимізація E шляхом ефективного призначення запитів пасажирів відповідним маршрутам водіїв. Алгоритм ітеративно розглядає маршрути водіїв та вибирає найкращі пасажирські маршрути на основі максимального включення, гарантуючи, що кожен маршрут використовується лише один раз. Емпіричний приклад ілюструє, як різні стратегії призначення забезпечують різний рівень ефективності, що вимірюється загальною кількістю виконаних кварталів.
Для впровадження цієї моделі було розроблено програмне рішення з інтерфейсом користувача для введення та обробки даних про маршрут. Крім того, запропоновано методологію оцінки екологічних переваг за рахунок економії палива, перетворюючи результати системи на кількісно вимірний екологічний вплив. Експериментальні результати підтверджують стабільність та ефективність алгоритму в обробці тисяч маршрутів, при цьому програмне забезпечення послідовно розподіляє пасажирів відповідно до визначених обмежень та максимізує показник ефективності.
Посилання
1. Leandro do C. Martins, Rocio de la Torre, Canan G. Corlu, Angel A. Juan, Mohamed A. Masmoudi (2021). Optimizing ride-sharing operations in smart sustainable cities: Challenges and the need for agile algorithms. Computers & Industrial Engineering, V.153, 107080.
2. Aydin, O. F., Gokasar, I., & Kalan, O. (2020). Matching algorithm for improving ride-sharing by incorporating route splits and social factors. PloS one, 15(3), e0229674. https://doi.org/10.1371/journal.pone.0229674
3. Ma, S., Zheng, Y., & Wolfson, O. (2013). T-Share: A Large-Scale Dynamic Taxi Ridesharing Service. IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, 410–421.
4. Zhou, Lunwei and Kang, Liujiang and Sun, Huijun and Bao, Yue and Lai, Qingying and Xu, Qianwen and Mashhoodi, Bardia and Ge, Ying-En. (2025) Real-Time Simultaneous Ride-Sharing Matching and Route Planning Based on Adjustable Passenger Pick-Up and Drop-Off Points. Available at SSRN: https://ssrn.com/abstract=5225975 or http://dx.doi.org/10.2139/ssrn.5225975 .
5. Danassis, P., Sakota, M., Filos-Ratsikas, A. et al (2022). Putting ridesharing to the test: efficient and scalable solutions and the power of dynamic vehicle relocation. Artif Intell Rev 55, 5781–5844. https://doi.org/10.1007/s10462-022-10145-0.
6. Cao, Y., Wang, S., & Li, J. (2021). The Optimization Model of Ride-Sharing Route for Ride Hailing Considering Both System Optimization and User Fairness. Sustainability, 13(10), 5610.
7. Connor Riley, Pascal Van Hentenryck, Enpeng Yuan (2020). Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control. INFORMS Journal on Computing, 32(3), 530–547.
8. Md Tawhidur Rahman, Kakan Dey, David R. Martinelli, Sabya Mishra (2021). Modeling and evaluation of a ridesharing matching system from multi-stakeholders’ perspective. IET Intelligent Transport Systems, 15(4), 369–377.
9. Shimamoto, H. (2025). A Matching Model for Ride-Sharing: A Non-Cooperative Game Approach Between Drivers and Riders. Smart Cities, 8(2), 40. https://doi.org/10.3390/smartcities8020040.
10. Hasan, Mohd. (2021). Ride-Sharing Optimization Algorithms for Urban Commuting. Transportation Research Part B: Methodological, 121, 145–161.
11. Guan, L., Pei, J., Liu, X., Zhou, Z., & Pardalos, P. M. (2020). Ridesharing in urban areas: multi-objective optimisation approach for ride-matching and routeing with commuters’ dynamic mode choice. International Journal of Production Research, 60(5), 1439–1457. https://doi.org/10.1080/00207543.2020.1859635.
12. Dastani,Z., Koosha, H., Karimi, H. et al (2024). User preferences in ride-sharing mathematical models for enhanced matching. Sci Rep 14, 27338. https://doi.org/10.1038/s41598-024-78469-1.
