Introduction
Public transit in suburban and rural areas often faces a dilemma: traditional fixed-route services are predictable but frequently inefficient, while fully flexible "dial-a-ride" systems offer efficiency but lack the predictability required for spontaneous travel. This paper addresses the "last-mile" connectivity problem by proposing a hybrid model: the Feeder Service with Mandatory Stops (FSMS).
The FSMS bridges the gap between rigid and flexible systems by guaranteeing service at specific mandatory stops within a maximum wait time (headway), while dynamically routing vehicles to optional stops based on real-time demand. This ensures that the service remains accessible to passengers without reservations while optimizing routes for those who do.
The FSMS Framework
The core objective of the FSMS is to balance operational efficiency with passenger predictability. The system is defined by two types of service points:
- Mandatory Stops: These are visited during every trip cycle. By enforcing a maximum headway (e.g., a bus must arrive every 30 minutes), the system provides a reliable schedule for "spontaneous" passengers.
- Optional Stops: These are only included in a vehicle's route if a specific request is made, reducing unnecessary travel time and fuel consumption.
Optimizing such a system is computationally complex. It requires simultaneous vehicle routing, passenger-to-stop assignment, and the management of interdependent timetables. Because buses return to a starting hub to be reused, a delay in one trip can cascade, potentially violating the headway requirements of subsequent trips.
Methodology: Parameter Space Search (PSS)
To solve this NP-hard optimization problem, the researchers developed a novel metaheuristic framework called Parameter Space Search (PSS). Traditional optimization often involves searching for the best route directly, which is computationally expensive for large-scale transit networks.
Instead, PSS searches for the optimal parameters to feed into a fast, greedy construction algorithm. These "knobs" include variables such as maximum allowable walking distances for passengers or factors determining how much a timetable can shift to accommodate new requests.
The framework utilizes Simulated Annealing (SA) to navigate this parameter space. Unlike traditional parameter tuning, which occurs before an algorithm runs, PSS is an online process where the tuning itself constitutes the optimization. By finding the right logic for the greedy algorithm to follow, the system can produce high-quality solutions much faster than direct routing searches.
Experimental Setup and Results
The study evaluated the PSS framework using a suite of 42 benchmark instances (labeled $I_1$ to $I_{42}$), ranging from small-scale operations (2 buses, 10 requests) to large-scale suburban deployments (12 buses, 162 requests). These instances varied in terms of mandatory stop density, optional stop clusters, and vehicle capacities.
Performance and Efficiency
- Solution Quality: On small benchmark instances, the PSS heuristic outperformed LocalSolver—a high-end commercial optimization tool—by an average of 12.42%.
- Computational Speed: The heuristic proved remarkably efficient. Small instances were solved in approximately 2.1 seconds, while the largest and most complex instances were resolved in under two minutes.
- Scalability: The framework is highly parallelizable. Utilizing 12 threads resulted in a speedup factor of 2.6x compared to serial execution, making it viable for near-real-time applications.
Sensitivity Analysis
The researchers found that passenger density and fleet size are the primary drivers of service quality. Interestingly, increasing the number of optional stops only slightly impacted runtime while significantly reducing passenger walking times, suggesting that the system scales well as service coverage expands.
Conclusion and Future Directions
The FSMS model demonstrates that predictability does not have to come at the cost of flexibility. By utilizing Parameter Space Search, transit operators can provide a reliable, demand-responsive service that accommodates both scheduled and spontaneous riders.
While the current model assumes "static" demand (where requests are known before the first departure), future work aims to evolve this into a fully dynamic system. This would allow for real-time re-optimization as new requests arrive or traffic conditions change, further closing the gap between demand and service delivery in suburban transit.
Summary updated