Гайша, O.O.O.O.ГайшаЛєнков, С.В.С.В.Лєнков2026-06-162026-06-162025-11-20Гайша, O., Лєнков, С. (2025). ALGORITHM AND SOFTWARE TOOL FOR SOLVING THE PROBLEM OF LOCAL PASSENGER TRAFFIC. Збірник наукових праць Військового інституту Київського національного університету імені Тараса Шевченка(87), 70–79. https://doi.org/10.17721/2519-481X/2025/87-0810.17721/2519-481X/2025/87-08https://ir.library.knu.ua/handle/15071834/23326In the context of contemporary urbanization and global environmental challenges, the optimization of passenger transportation systems has emerged as a significant area of research, particularly in the domain of energy conservation and ecological impact reduction. This study addresses a specific aspect of this broad issue: the efficient utilization of empty seats in private vehicles to increase transportation throughput without expanding road infrastructure. The central idea lies in the redistribution of passengers who share similar or overlapping routes with private car owners, leveraging modern information technologies to facilitate real-time matching and communication.The work begins by outlining the conceptual foundation of the problem, emphasizing that numerous urban residents travel considerable distances daily, while the available transportation infrastructure remains constrained. In light of this, substantial transport efficiency gains can be achieved by utilizing vacant seats in private vehicles. While socio-economic and motivational factors such as environmental awareness, financial incentives, or altruistic behavior may drive such initiatives, the paper focuses solely on the technical and algorithmic aspects of the solution, deliberately excluding the subjective dimension of driver motivation.A formal problem statement is constructed, modeling the city road network as a mathematical graph where intersections are represented as nodes and road segments (quarters) as edges. Each driver's and passenger's route is defined as a sequence of intersections, and the core condition for assigning a passenger to a driver is the full inclusion of the passenger's route within the driver's route. This constraint, referred to as the "Route Rigidity Rule" (3R), ensures that neither the driver alters his route nor the passenger deviates from his intended path.The algorithm’s architecture is centered on string processing techniques, where route sequences are encoded as strings and inclusion is checked using substring operations. A key function, I(d, p), is introduced to quantify the number of overlapping quarters between a driver's route d and a passenger's route p. This function serves as the basis for verifying route compatibility and ultimately calculating the effectiveness of a particular distribution.The effectiveness of the system is defined through an objective function E, representing the total number of passenger-quarters served. The optimization goal is to maximize E by efficiently assigning passenger requests to appropriate driver routes. The algorithm iteratively considers driver routes and selects the best-fitting passenger routes based on maximum inclusion, ensuring each route is used only once. An empirical example illustrates how different assignment strategies yield varying levels of effectiveness, measured in the total number of quarters fulfilled.To operationalize this model, a software solution was developed featuring a user interface for inputting and processing route data. Furthermore, a methodology is proposed to estimate environmental benefits through fuel savings, translating the system’s output into quantifiable ecological impact. Experimental results confirm the algorithm’s stability and efficiency in handling thousands of routes, with the software consistently distributing passengers in accordance with defined constraints and maximizing the effectiveness metric.У контексті сучасної урбанізації та глобальних екологічних проблем, оптимізація систем пасажирських перевезень стала важливою галуззю досліджень, особливо в галузі енергозбереження та зменшення впливу на навколишнє середовище. Це дослідження розглядає конкретний аспект цієї широкої проблеми: ефективне використання вільних місць у приватних транспортних засобах для збільшення пропускної здатності транспорту без розширення дорожньої інфраструктури. Центральна ідея полягає в перерозподілі пасажирів, які користуються схожими або перекриваючимися маршрутами з власниками приватних автомобілів, використовуючи сучасні інформаційні технології для полегшення зіставлення та комунікації в режимі реального часу.Робота починається з викладу концептуальної основи проблеми, підкреслюючи, що численні міські жителі щодня долають значні відстані, тоді як доступна транспортна інфраструктура залишається обмеженою. З огляду на це, значного підвищення ефективності транспорту можна досягти, використовуючи вільні місця в приватних транспортних засобах. Хоча соціально-економічні та мотиваційні фактори, такі як екологічна обізнаність, фінансові стимули або альтруїстична поведінка, можуть стимулювати такі ініціативи, стаття зосереджується виключно на технічних та алгоритмічних аспектах рішення, навмисно виключаючи суб'єктивний вимір мотивації водіїв.Побудовано формальну постановку проблеми, яка моделює мережу міських доріг як математичний граф, де перехрестя представлені як вузли, а сегменти доріг (квартали) як ребра. Маршрут кожного водія та пасажира визначається як послідовність перехресть, а основною умовою для призначення пасажира водієві є повне включення маршруту пасажира до маршруту водія. Це обмеження, яке називається «Правилом жорсткості маршруту» (3R), гарантує, що ні водій не змінює свій маршрут, ні пасажир не відхиляється від запланованого шляху.Архітектура алгоритму зосереджена на методах обробки рядків, де послідовності маршрутів кодуються як рядки, а включення перевіряється за допомогою операцій з підрядками. Ключова функція I(d, p) вводиться для кількісної оцінки кількості перекриваючих кварталів між маршрутом водія d та маршрутом пасажира p. Ця функція служить основою для перевірки сумісності маршрутів та, зрештою, розрахунку ефективності певного розподілу.Ефективність системи визначається цільовою функцією E, яка представляє загальну кількість обслуговуваних пасажирських кварталів. Метою оптимізації є максимізація E шляхом ефективного призначення запитів пасажирів відповідним маршрутам водіїв. Алгоритм ітеративно розглядає маршрути водіїв та вибирає найкращі пасажирські маршрути на основі максимального включення, гарантуючи, що кожен маршрут використовується лише один раз. Емпіричний приклад ілюструє, як різні стратегії призначення забезпечують різний рівень ефективності, що вимірюється загальною кількістю виконаних кварталів.Для впровадження цієї моделі було розроблено програмне рішення з інтерфейсом користувача для введення та обробки даних про маршрут. Крім того, запропоновано методологію оцінки екологічних переваг за рахунок економії палива, перетворюючи результати системи на кількісно вимірний екологічний вплив. Експериментальні результати підтверджують стабільність та ефективність алгоритму в обробці тисяч маршрутів, при цьому програмне забезпечення послідовно розподіляє пасажирів відповідно до визначених обмежень та максимізує показник ефективності.enоптимізація міського транспортуалгоритм спільного використання поїздокзіставлення маршрутівінтелектуальні транспортні системиurban transportation optimizationride-sharing algorithmroute matchingintelligent transport systemsСтаття