Source-linked AI summary
Real-time City-scale Ridesharing via Linear Assignment Problems
Andrea Simonetto, Julien Monteil, Claudio Gambella
TL;DR
Urban ridesharing has been associated with mobility benefits, but those benefits have appeared limited to centralized systems. This paper develops a federated linear-assignment algorithm and finds that small and medium enterprises with 5-10% market shares can achieve similar benefits, provided city-scale vehicle numbers are carefully planned.
Problem
Ridesharing benefits appear limited to centralized systems, motivating investigation of a computationally efficient approach distributable among multiple companies.
Method
The paper formulates dynamic ridesharing as a linear assignment problem between customer requests and available vehicles within a federated optimization architecture.
Results
Small and medium enterprises with 5-10% market shares can achieve similar benefits to a more global ridesharing service in simulations using New York and Melbourne-area datasets.
Takeaways & Limitations
Real-time urban-scale ridesharing can benefit smaller operators, while city-scale vehicle circulation must be carefully planned to preserve those benefits.
Takeaways & Limitations
In two-company scenarios with upfront customer-share allocation, achieving a monopolistic setting’s service rate requires more vehicles, exposing possible negative effects of multi-company ridesharing.
Abstract
from arXiv · showhide
In this paper, we propose a novel, computational efficient, dynamic ridesharing algorithm. The beneficial computational properties of the algorithm arise from casting the ridesharing problem as a linear assignment problem between fleet vehicles and customer trip requests within a federated optimization architecture. The resulting algorithm is up to four times faster than the state-of-the-art, even if it is implemented on a less dedicated hardware, and achieves similar service quality. Current literature showcases the ability of state-of-the-art ridesharing algorithms to tackle very large fleets and customer requests in almost near real-time, but the benefits of ridesharing seem limited to centralized systems. Our algorithm suggests that this does not need to be the case. The algorithm that we propose is fully distributable among multiple ridesharing companies. By leveraging two datasets, the New York city taxi dataset and the Melbourne Metropolitan Area dataset, we show that with our algorithm, real-time ridesharing offers clear benefits with respect to more traditional taxi fleets in terms of level of service, even if one considers partial adoption of the system. In fact, e.g., the quality of the solutions obtained in the state-of-the-art works that tackle the whole customer set of the New York city taxi dataset is achieved, even if one considers only a proportion of the fleet size and customer requests. This could make real-time urban-scale ridesharing very attractive to small enterprises and city authorities alike. However, in some cases, e.g., in multi-company scenarios where companies have predefined market shares, we show that the number of vehicles needed to achieve a comparable performance to the monopolistic setting increases, and this raises concerns on the possible negative effects of multi-company ridesharing.
1 Introduction
The paper addresses city-scale, real-time ridesharing by proposing a computationally efficient algorithm that supports distributed operation while maintaining comparable service quality. Simulations and prior evidence motivate reduced fleet requirements, but multi-company settings may require careful vehicle planning and regulation.
- 1 Introduction: The proposed algorithm combines linear assignment, context mapping, and capacitated vehicle routing within a federated architecture.It assigns new requests to available vehicles while supporting distributed computation.
- 1 Introduction: Urban-scale ridesharing must handle several thousands of vehicles and millions of daily trips as customers and schedules arrive dynamically.The paper focuses on real-time optimization using New York City and Melbourne data.
- 1 Introduction: The method is fully distributable among companies without requiring disclosure of proprietary vehicle locations or routing services.A central coordinator receives limited information needed to solve the assignment problem while preserving assignment optimality.
- 1 Introduction: The implementation is more than four times faster than the referenced state-of-the-art approach while delivering similar service quality on a denser network graph.The reported implementation runs near real-time on a one-core laptop, compared with a dedicated 24-core machine in the comparison work.
- 1 Introduction: Multi-company scenarios with predefined customer shares require more vehicles to match monopolistic service rates, creating potential congestion and pollution concerns.The paper therefore identifies vehicle limits tied to demand and city-authority intervention as important conditions.
- 1 Introduction: Single-request vehicle assignments can achieve high service rates in dynamic settings, suggesting that optimal myopic multi-request search is unnecessary.The paper reports comparable service quality to prior literature and finds that small market shares can produce equivalent quality.
2 Problem formulation
The paper formulates dynamic ridesharing as repeated real-time assignments of customer requests to available vehicles under time, detour, capacity, and route constraints. Its one-to-one assignment design enables a fast linear assignment formulation while retaining the ability for vehicles to serve multiple customers over time.
- Dynamic service model: At each optimization instant, requests from the preceding sampling window are assigned to available vehicles and corresponding routes.The service runs at times t_k and processes requests submitted during (t_{k-1}, t_k].
- Request representation: A trip request contains origin, destination, pickup and delivery time windows, and additional time constraints Ω.The formulation represents a request as r = (O, D, t_O, t_D, Ω).
- Request constraints: The request constraints include maximum waiting time δ, maximum detour time Δ, and maximum journey length Γ.These limits respectively constrain pickup delay, extra route time, and total journey length.
- Assignment design: At each optimization run, at most one new request is assigned to a vehicle, reducing the problem to a linear assignment problem.The one-to-one choice still allows vehicles to serve multiple customers across successive service instances.
- Optimization formulation: The assignment minimizes vehicle-request costs, with infeasible pairings assigned infinite cost and constraints enforcing request coverage and at most one new request per vehicle.The implementation defines c_ij as the route duration for serving scheduled customers and the new customer j.
- Solution method: Because linear assignment constraints are totally unimodular, the continuous relaxation is exact and efficient assignment algorithms can be exploited.The resulting rectangular assignment formulation is applied after costs c_ij are precomputed.
3 Federated optimization architecture approach
The federated architecture distributes vehicle-level cost computation while centrally solving a linear assignment problem for dynamic ridesharing. It reduces communication and computational demands while preserving optimality for the assignment problem and supporting reactive rebalancing of unserved requests.
- Architecture: The architecture decomposes ridesharing into local vehicle computations and centralized optimization, with limited communication between physical entities and the server.Vehicle blocks compute assignment costs, while the optimization module solves the resulting assignment problem.
- Operational flow: At each sampling period, the ridesharing logic batches requests, obtains vehicle insertion costs, solves an optimal assignment, and sends assignments with routes to customers and vehicles.Unserviceable customers trigger a rebalancing module that repeats the process for idle vehicles with loosened time constraints.
- Architecture: Context mapping filters geographically suitable vehicles before requesting insertion costs, reducing communication and computational requirements.It selects nearby idle vehicles and a limited number of available occupied vehicles for each request.
- Optimization module: Each assignment specifies the served request, its insertion position, and the resulting vehicle route; infinite assignment costs defer unaccommodated customers to rebalancing.The assignment cost is linked to a particular insertion and route.
- Computational properties: The approach is computationally lighter than Alonso-Mora et al. because it replaces integer linear programming with linear assignment and omits request shareability-graph construction.Its cost computation scales linearly in vehicles and new requests, while the assignment problem has at most n^2 variables in the worst case.
- Distributed implementation: A distributed implementation lets multiple companies share limited information while the central agent still reaches the optimal assignment.The coordinator receives request locations and bids but cannot infer all company vehicle locations.
4 Numerical implementation and results
Numerical simulations show that the algorithm maintains high service quality with scaled-down fleets and demand, while reducing computational time and supporting real-time operation. Results also examine rebalancing, cost functions, sampling periods, distance metrics, and DARP solution methods.
- Fleet scaling: 150, 300, and 600 vehicles—5%, 10%, and 20% of the benchmark fleet—produce nearly unaffected performance when customer demand is scaled proportionally.The simulations use the same percentage of ride requests for each fleet size.
- Service quality: 10% market share appears sufficient for a very high service level, with 300 vehicles handling 10% of current demand.The 300-vehicle fleet represents slightly more than 2% of the current taxi fleet.
- Rebalancing: 25%: service rate drops without reactive fleet rebalancing, whereas accepting or refusing rebalancing vehicles otherwise yields similarly high service levels.The deterioration is reported for the no-rebalancing case.
- Cost functions: TD performs best among the tested cost functions, while WT favors shorter waiting times and DT favors shorter detours.TD keeps trip lengths small and makes vehicles more available.
- Sampling period: 5 s gives the best service rate, whereas 30 s provides lower detour times with comparable service rate.The longer sampling period makes more requests available for assignment at once.
- DARP algorithms: The insertion heuristic offers the best trade-off between service level and computational time, while LNS takes about twice as long.LNS can slightly improve service rate and waiting times for smaller fleets but requires larger vehicle detours.
5 Conclusions and open research questions
The paper presents a computationally efficient dynamic ridesharing algorithm and concludes that small-market-share enterprises can achieve benefits comparable to global services when city-scale vehicle numbers are carefully planned. It identifies demand forecasting, multimodal integration, and inter-company competition as open research directions.
- The algorithm combines federated optimization with a suitably defined linear assignment problem for dynamic ridesharing.
- Small and medium enterprises with 5–10% market shares can achieve benefits similar to those of more global ridesharing services.
- Comparable benefits require careful planning of the number of vehicles circulating across the city.
- Future work should examine demand forecasting for scheduling and rebalancing, especially in low market share regimes (≤ 5%).
- Further research should study intelligent public transportation, dedicated systems, and traditional transport within multimodal and multi-legged ridesharing.
- Competition among ridesharing companies, including incentives and penalties, remains important for emerging mobility-on-demand systems.