Source-linked AI summary
A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers
Tai-Yu Ma, Saeid Rasulkhani, Joseph Y. J. Chow, Sylvain Klein
TL;DR
The paper addresses the lack of integrated optimization for ridesharing trips that combine door-to-door service with transfers to and from public transit. It proposes online dispatch and idle-vehicle relocation algorithms customized for this multimodal setting. Experiments report substantial reductions in vehicle travel, passenger journey time, and operating cost, while the study notes that perceived user costs remain unevaluated.
Problem
Existing ridesharing-transit cooperation does not integrate vehicle dispatch and idle-vehicle repositioning with transit stations for a passenger’s complete multimodal trip.
Method
The paper designs an end-to-end rideshare strategy and adapts anticipatory dispatch and relocation algorithms for trips using rideshare, public transit, and transfers.
Results
Cost savings can be substantial for users and operators, with vehicle miles reduced 47.0% to 54.6% and user journey time reduced 60.5% in a 5-minute-headway scenario.
Takeaways & Limitations
The integrated bimodal operation can provide significant improvements across network types and demand patterns, including when non-myopic algorithms perform poorly in a unimodal instance.
Takeaways & Limitations
Perceived user costs are not quantified, and demand evaluation remains an open research question because the strategy has not been implemented in practice.
Abstract
from arXiv · showhide
We propose a ridesharing strategy with integrated transit in which a private on-demand mobility service operator may drop off a passenger directly door-to-door, commit to dropping them at a transit station or picking up from a transit station, or to both pickup and drop off at two different stations with different vehicles. We study the effectiveness of online solution algorithms for this proposed strategy. Queueing-theoretic vehicle dispatch and idle vehicle relocation algorithms are customized for the problem. Several experiments are conducted first with a synthetic instance to design and test the effectiveness of this integrated solution method, the influence of different model parameters, and measure the benefit of such cooperation. Results suggest that rideshare vehicle travel time can drop by 40-60% consistently while passenger journey times can be reduced by 50-60% when demand is high. A case study of Long Island commuters to New York City (NYC) suggests having the proposed operating strategy can substantially cut user journey times and operating costs by up to 54% and 60% each for a range of 10-30 taxis initiated per zone. This result shows that there are settings where such service is highly warranted.
1. Introduction
The paper motivates tighter coordination between mobility-on-demand services and public transit, proposing integrated dispatch and idle-vehicle relocation for multimodal door-to-door trips.
- 1. Introduction: Existing first- and last-mile partnerships improve connectivity but do not jointly optimize rideshare dispatch, idle-vehicle repositioning, and transit-station coordination.The paper identifies the absence of an integrated dispatch and fleet-management algorithm for these multimodal trips.
- 1. Introduction: Integrated ridesharing can offer door-to-door, rideshare-to-transit-to-rideshare, and rideshare-to-transit-to-walk trips through coordinated transit transfers.The proposed service may use different vehicles for pickup and drop-off at separate stations, with a single discounted fare option.
- 1. Introduction: The study proposes a rideshare strategy leveraging transfers to and from transit networks for end-to-end service.The strategy is designed to support a broader set of trip options than conventional door-to-door ridesharing.
- 1. Introduction: It modifies anticipatory dispatch and idle-relocation algorithms and tests their integration in synthetic instances and a Long Island Railroad–NYC case study.The experiments also examine algorithm-parameter selection for effective operation.
2. Literature Review
Prior work addresses multimodal transit coordination, dynamic ridesharing dispatch, and idle-vehicle relocation, but these strands largely remain separate. Queueing-based anticipatory costs and relocation models provide foundations for integrating vehicle supply decisions with transit-enabled service.
- Prior research: Existing research spans public-transit collaboration, multimodal transfer routing, dynamic ridesharing dispatch, and idle-vehicle relocation.Studies include MaaS and symbiotic network frameworks, multimodal and freight transfer models, dynamic routing, and shared-mobility rebalancing.
- Dynamic dispatch: Dynamic mobility-on-demand studies commonly make decisions under stochastic demand, while many anticipatory strategies model systems in isolation from other operators.Markov decision processes and approximate dynamic programming offer theoretical approaches, but full future-state evaluation is intractable and existing studies generally focus on isolated systems.
- Anticipatory dispatch: Queue-based dispatch assigns new requests by insertion cost while approximating future operating costs with queue delay.The cost function combines tour duration, passenger journey time, and a queue-delay term proportional to tour length squared; beta controls the degree of look-ahead, with beta = 0 yielding myopic behavior.
- Research gap: Prior multimodal studies consider transit access, transfer points, or integrated routes, but the reviewed strands do not establish a unified dynamic dispatch-and-repositioning framework for ridesharing with transit.The cited work includes dial-a-ride, intermodal passenger trips, freight transfers, and static transfer-point routing.
- Idle-vehicle relocation: Idle-vehicle relocation models rebalance vehicles under stochastic demand by minimizing access time and relocation cost while constraining queue intensity and available supply.The formulation includes relocation flows, customer-to-vehicle assignments, ordered vehicle relocation, service reliability, and supply-demand constraints.
3. Proposed non-myopic dynamic vehicle dispatching and routing policy for ridesharing with transit transfers
The proposed policy integrates real-time rideshare dispatch, transit-transfer selection, and non-myopic idle-vehicle relocation. It evaluates direct and multimodal options while dynamically updating vehicle tours, relocation zones, and demand estimates.
- System model: The operating model uses a complete graph of transit stations, request points, and relocation-zone centroids, with Poisson request arrivals and empirically estimated zone service rates.Vehicles are homogeneous and capacitated, while a dispatching center makes real-time routing and dispatch decisions; at most two intermodal transfers are allowed.
- Integrated framework: The integrated framework combines dynamic dispatch, transit-transfer decisions, and idle-vehicle relocation under three initiating events: new requests, relocation epochs, and arrivals at exit stations.Procedure P1 evaluates rideshare-only, rideshare-transit-walk or walk-transit-rideshare, and rideshare-transit-rideshare options; procedure P2 relocates idle vehicles.
- P1: Dynamic dispatch and routing: Each request is assigned the fastest feasible option among nearby vehicles, using candidate entry and exit stations and mode-specific travel, waiting, transit, and walking times.For transit-enabled options, the algorithm evaluates pairs of k-nearest entry and exit stations and updates the request’s pickup or drop-off point accordingly.
- P2: Idle-vehicle relocation: Idle vehicles are reassigned at each relocation interval using predicted demand, anticipated station-exit arrivals, and a mixed-integer optimization model, after which changed zones are inserted into vehicle tours.The relocation procedure identifies idle vehicles and current zones, solves the model, and updates tours for vehicles assigned elsewhere.
- P2: Idle-vehicle relocation: Relocation zones adapt to demand by updating centroids with a three-step moving average of demand-weighted pickup coordinates.The centroids are distinct from customer pickup and drop-off points and are recalculated each epoch to reflect spatiotemporal demand intensity.
- Algorithm design: P1 is a polynomial-time heuristic based on TSPPD insertion, while P2 uses a mixed-integer solver for a p-median relocation problem and requires coordinated time frames with transit schedules.The implementation uses Christofides initialization, 2-opt improvement, and k-nearest transit stations to keep online dispatch computationally timely.
4. Numerical experiments
The experiments evaluate the integrated rideshare-transit strategy through synthetic simulations, varying demand, dispatch look-ahead, relocation policies, and transit options. Results show that transit transfers substantially reduce vehicle travel and passenger journey times, especially with shorter headways and higher demand.
- Experimental design: The evaluation uses mean vehicle travel time as operating cost and mean passenger journey time as customer inconvenience.Journey time is measured from passenger arrival to drop-off, and additional measures are left for future implementation studies.
- Experimental design: The simulation varies arrival intensity, dispatch look-ahead β, relocation cost scaling θ, relocation policies, and rideshare-only versus rideshare-transit options.Arrival intensities of λ=100 and 400 customers/hour are tested, alongside four relocation policies.
- Transit-transfer results: 60.5% lower user journey time is achieved at λ=400 with a 5-minute transit headway.Vehicle traveled miles also fall by 54.6% in this high-arrival scenario.
- Transit-transfer results: 47.0% and 54.6% reductions in vehicle traveled miles occur for λ=100 and λ=400, respectively, with 5-minute transit headways.The reported reductions indicate lower operating cost when transit transfers are available.
- Transit-transfer results: Shorter transit headways increase the share of customers receiving transit-transfer options.The study evaluates this sensitivity using the rideshare-transit experiment and Table 5.
- Transit-transfer results: WTR/RTW account for 63%-77.5% of options at λ=100 and 45%-54.5% at λ=400, while RTR remains around 6% or less.RTR is less frequently adopted because its first- and last-mile connecting rides have higher operating cost.
5. New York City and Long Island Railroad case study
The Long Island–NYC case study evaluates integrated rideshare–transit operations using realistic regional demand, comparing them with rideshare-only service across fleet sizes, demand patterns, and coverage expansions. Transit transfers substantially reduce journey times and vehicle travel, increase effective capacity, and make selected commuter flows and coverage extensions more attractive.
- Case-study setting: The study models 72 operational zones across five counties using 2010–2011 regional travel-survey demand aggregated to 2,096 transportation analysis zones.The case focuses on Long Island Railroad access to New York City, where door-to-door trips can take 1–3 hours.
- 5.3 Results: Increase in effective service capacity: 54.3% lower passenger journey time and 60.2% lower vehicle travel time result from adding transit to the 10-vehicle-per-zone scenario.At 20 vehicles per zone, the reductions remain 32.1% and 63.7%, respectively, relative to rideshare-only service.
- 5.3 Results: Increase in effective service capacity: Adding shared transit increases effective available vehicle capacity by 4 times while reducing trip length by 28%.The capacity effect is attributed to focusing rideshare vehicles on first- and last-mile trips rather than direct door-to-door service.
- 5.3 Results: Increase in effective service capacity: Transit transfers shorten rideshare trips and increase capacity: average passenger trips per vehicle rise from 0.85 to 1.61 at 10 vehicles per zone, with further gains at larger fleets.The transit option provides more capacity for rebalancing because average rideshare trips are shorter.
- 5.4 Results: Demand distributions: Transit is most advantageous for trips in the 30–300 minute range, while RTW accounts for 31.0–36.8% of customers and WTR and RTR each remain below 5%.The results identify Long Island–NYC commuter flows as settings where the proposed strategy is highly warranted; Brooklyn–Manhattan trips do not use LIRR transfers.
- 5.5 Results: Service coverage expansion decision support: Extending coverage to Nassau County is preferred to Suffolk County because it adds more customers with lower vehicle travel time and only a 0.34%–1.31% journey-time increase.For the rideshare-only system, extending coverage can sharply increase journey and vehicle travel times, whereas the transit-integrated system is less affected.
6. Conclusions
The study proposes door-to-door multimodal ridesharing with integrated transit and dynamic dispatch and idle-vehicle relocation. Experiments indicate substantial user and operator savings, while perceived user costs remain unevaluated.
- 6. Conclusions: 32% lower user journey time and 64% lower vehicle travel time are achieved by transit-rideshare versus rideshare-only service for a 20-vehicle-per-zone fleet.The rideshare-only nonmyopic relocation algorithm does not significantly improve the LIRR case study, whereas the bimodal system outperforms it.
- 6. Conclusions: The proposed system supports rideshare-only, rideshare-transit-rideshare, and rideshare-transit-walk trips in either direction.It integrates dynamic dispatch and idle-vehicle relocation to provide complete door-to-door multimodal service.
- 6. Conclusions: Cost savings can benefit both users and operators, but their magnitude varies with network type and user demand patterns.The study reports that bimodal operation can improve performance even when nonmyopic algorithms perform poorly in unimodal operation.
- 6. Conclusions: Perceived user costs remain unquantified because transfer and in-vehicle times may have different perceived values, leaving demand evaluation open.The authors retain simpler assumptions to compare supply-side algorithms more directly.
Appendix
The appendix evaluates how dispatch and relocation parameters affect system performance. Nonmyopic dispatch performs best at calibrated beta values, while relocation benefits from sufficiently large theta under high demand.
- Appendix: β values of 4/T̅(v,x) and 5/T̅(v,x) produce the most effective mean vehicle travel-time results for low- and high-arrival cases.The study tests 31 beta values and finds that nonzero beta can improve system performance, although effectiveness depends on calibration.
- Appendix: The appendix examines beta through Table A1 and Fig. A1 and theta through Fig. A2, whose panels report passenger journey time and vehicle travel time.The displayed evaluations vary dispatch and relocation parameters across customer-arrival conditions.
- Appendix: θ≥1.2 reduces mean passenger journey time by 7.1% and mean operation cost by 2.6% versus no idle vehicle relocation under high arrival intensity.Theta has little impact under low customer arrival intensity but affects relocation effectiveness when demand is high.
3. Impact of different idle vehicle relocation policy
The relocation-policy experiments show that nonmyopic relocation is strongest when demand leaves idle vehicles available, while its advantage disappears when all vehicles become busy. Additional switching and adaptive policies can further improve operations.
- 3. Impact of different idle vehicle relocation policy: Nonmyopic relocation outperforms alternative policies at λ=50 and λ=100 when idle vehicles remain available for rebalancing.At λ=200 and λ=400, all vehicles become busy after 20 and 40 minutes, respectively, producing similar performance across policies.
- 3. Impact of different idle vehicle relocation policy: Nonmyopic relocation obtains non-dominated solutions versus myopic relocation for passenger wait time, journey time, and vehicle trip length under the M/M/s approximation.The comparison assumes exponentially distributed service times.
- 3. Impact of different idle vehicle relocation policy: Allowing idle vehicles to switch en route to pick up new customers is evaluated as an alternative to prohibiting such switching.The experiment varies customer arrival intensity under the nonmyopic relocation model.
- 3. Impact of different idle vehicle relocation policy: Dynamic zone-centroid adjustment improves system performance more substantially than adaptive service-rate learning across customer-arrival intensities.Both strategies improve performance, but the centroid adjustment has the larger effect.