High-capacity public transit networks—such as subways, commuter rails, and bus rapid transit lines—are highly efficient at moving large volumes of people across metropolitan areas. However, their efficiency relies on spatial rigidity: they operate on fixed tracks or routes and stop only at designated hubs. This rigidity creates the first-mile/last-mile (FMLM) connectivity gap, which is the physical and psychological friction commuters experience when trying to travel between their actual origin or destination and the nearest high-capacity transit station.
As Mo et al. demonstrate in their study on the Impact of Built Environment on First- and Last-Mile Travel Mode Choice, if this initial or final leg is inefficient, inconvenient, or stressful, the perceived utility of the entire transit network collapses, pushing commuters toward private vehicles. Traditional transit-oriented development assumes a narrow walking radius of roughly 500 meters around stations. While expanding this catchment area to a 2-kilometer "bikeable" or "scooter-accessible" radius can exponentially increase potential network coverage (Xia et al. in From walkability to bikeability), it introduces a massive coordination problem: how do cities seamlessly integrate flexible, on-demand feeder fleets with rigid, fixed-schedule transit trunks?
To solve this, researchers have turned to On-Demand Multimodal Transit Systems (ODMTS). Designing these systems requires overcoming severe computational bottlenecks, balancing operational flexibility with predictability, and ensuring social equity.
The Computational Bottleneck of Multimodal Routing
An ODMTS coordinates a fleet of flexible vehicles—such as automated shuttles, ride-hailing cars, or micro-mobility options—to dynamically route passengers to and from fixed transit lines. Mathematically, designing an ODMTS is a complex bilevel optimization problem.
In this mathematical "game," the transit agency acts as the leader, choosing routes, fleet sizes, and schedules to minimize operational costs. The riders act as followers, dynamically choosing their individual paths to minimize their own travel time and discomfort based on the agency's choices.
If a model attempts to optimize the agency's routing decisions while explicitly tracking individual passenger choices and transfer limits in real time, the problem becomes highly non-convex and combinatorially explosive. Standard optimization solvers quickly stall, making it impossible to plan routes for real-world cities.
Transforming Constraints via Transfer-Expanded Graphs
One of the primary reasons ODMTS optimization fails to scale is the "transfer constraint." Commuters strongly dislike transferring between vehicles; a route requiring three or four transfers is practically unusable. Therefore, optimization models must enforce a strict upper bound on the number of transfers a passenger experiences.
In a standard transit graph, nodes represent physical locations (stations or intersections) and edges represent transit links. To enforce a transfer limit on this standard graph, an algorithm must keep track of the complete history of each passenger's path to know how many transfers they have already made. This history-dependence destroys the substructure required for efficient shortest-path algorithms.
To bypass this bottleneck, Dalmeijer et al. introduced a framework detailed in Transfer-Expanded Graphs for On-Demand Multimodal Transit Systems. The core intuition is to bake the passenger's history directly into the graph's geometry.
Instead of a single physical network, the graph is duplicated into multiple parallel "layers," where each layer corresponds to the exact number of transfers a passenger has completed so far (e.g., Layer 0, Layer 1, Layer 2).
[ Layer 2: Two Transfers ] ---> (Destination)
^
| (Transfer Edge 2)
[ Layer 1: One Transfer ] ---> [Fixed Rail Line]
^
| (Transfer Edge 1)
[ Layer 0: Zero Transfers ] ---> [On-Demand Shuttle]
When a passenger boards an initial on-demand shuttle, they move along Layer 0. When they transfer to a fixed rail line, their path traverses a directed vertical edge that connects Layer 0 to Layer 1.
By restructuring the network this way, the hard non-convex constraint of limiting transfers is transformed into a standard, history-independent shortest-path problem on an expanded graph. This geometric transformation allows complex, city-wide transit networks to be optimized in minutes rather than hours.
Decoupling the Bilevel Game with Path-Based Formulations
Even with optimized graphs, the interaction between agency routing and rider choice remains a major scaling bottleneck. If the agency adjusts a shuttle route, riders alter their paths, which shifts the demand patterns and forces the agency to re-adjust its routes.
Guan et al. resolved this interdependence in Path-Based Formulations for the Design of On-demand Multimodal Transit Systems with Adoption Awareness through a framework called P-Path. Instead of simulating the agency and rider decisions in an iterative, bilevel loop, the authors pre-calculate a comprehensive set of attractive, behaviorally realistic paths for every origin-destination pair in the city.
Because the set of acceptable rider paths is fixed beforehand, the bilevel problem collapses into a single-level mixed-integer linear program. The optimization engine no longer has to predict how riders will react to route changes; it simply selects the most cost-effective combination of shuttle routes that satisfies the pre-calculated paths. This decoupling allowed the authors to scale ODMTS design to massive metropolitan areas like Atlanta, solving models with 17 million variables in just a few hours.
Balancing Predictability and Flexibility
Once the mathematical framework is established, the operational structure of the feeder fleet must be determined. Fully fixed routes (like traditional buses) provide predictability but suffer from low utilization and long walking distances in low-density areas. Conversely, fully flexible door-to-door services (like ride-hailing) offer convenience but lack the capacity to handle high-volume surges efficiently (Zheng et al. in Designing a New Shuttle Service to Meet Large-Scale Instantaneous Peak Demands).
The modern consensus focuses on hybrid, semi-flexible systems that merge the benefits of both approaches:
- Semi-Flexible Routing: Montenegro et al. propose a demand-responsive feeder service in A demand-responsive feeder service with a maximum headway at mandatory stops. Their system guarantees service at "mandatory stops" within a strict maximum wait time to maintain predictability, while using a Parameter Space Search (PSS) metaheuristic to dynamically detour to "optional stops" based on real-time requests.
- Multi-Hub Routing: To handle peak-hour commuting surges, Lam et al. developed the Peak-Hour Vehicle Routing Problem (PHVRP) framework in Peak-Hour Vehicle Routing for First-Mile Transportation. Instead of forcing a shuttle to deliver passengers to a single pre-assigned station, the algorithm dynamically routes vehicles to any of several nearby transit hubs, balancing the traffic load across the broader network.
- Fleet Co-Utilization: To make these flexible fleets economically viable, researchers look beyond single-use passenger vehicles. Auad demonstrates in Ridesharing and Fleet Sizing For On-Demand Multimodal Transit Systems that integrating ridesharing directly into the first- and last-mile shuttle equations can reduce overall transit system costs by up to 35%. Taking this further, Manchella et al. introduce the PassGoodPool framework in Joint Passengers and Goods Fleet Management With Reinforcement Learning, which co-optimizes fleets to carry both passengers and freight, using reinforcement learning to assign package deliveries to passenger shuttles during off-peak transit hours.
Network Integration and Social Equity
An optimized feeder service is only effective if it integrates well into the broader urban network and serves the populations that need it most.
Wang et al. point out in Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand that transit planning often over-indexes on high-demand corridors while ignoring how new routes connect to the existing network structure. They utilize advanced linear algebra techniques—specifically the Lanczos method and stochastic trace estimation—to optimize route structures so that they maximize global network connectivity, ensuring that first-mile feeders hook into a highly cohesive web.
Finally, designing these systems requires balancing efficiency with equity. Low-income households are disproportionately affected by the last-mile barrier, as they frequently reside in transit deserts and lack personal vehicles. Expanding traditional fixed-route bus lines into these low-density neighborhoods is often financially unfeasible for cities.
Pramanik et al. address this spatial mismatch in Equity Promotion in Public Transportation. They developed a randomized, linear-programming-based algorithm that strategically allocates a transit agency's limited budget between traditional fixed-route infrastructure and subsidized, on-demand ride-hailing services. This approach mathematically guarantees social equity bounds, ensuring that first-mile/last-mile innovations serve as a tool for public accessibility rather than a premium service.
Key Foundational Work
Development of an integrated flexible transport systems platform for rural areas using argumentation theory (2012) — contributed 1 concept elements to this direction.
A Polymorphic Dynamic Network Loading Model (2008) — contributed 1 concept elements to this direction.