Algorithm and Software Tool for Solving the Problem of Local Passenger Traffic

In 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.