Source-linked AI summary
Quantifying the benefits of vehicle pooling with shareability networks
Paolo Santi, Giovanni Resta, Michael Szell, Stanislav Sobolevsky, Steven Strogatz, Carlo Ratti
TL;DR
The paper models taxi-trip sharing as a shareability-network problem, balancing collective sharing opportunities against passenger delay and enabling efficient optimization on large datasets. Applied to New York City trips, the framework finds substantial savings with feasible online matching and rapid saturation at lower trip densities.
Problem
The paper addresses how to identify optimal taxi-trip sharing strategies while controlling passenger delay through a systematic network formulation.
Method
The method represents trips as network nodes, connects combinable trips, and uses matching algorithms under bounded pickup and delivery delays, including a 1-minute online window.
Results
40% savings in total travel time are achievable with omniscient matching, while an online model saves 32% at ∆= 5 min; near-maximum shareability is reached around 100,000 daily trips.
Takeaways & Limitations
Taxi sharing appears computationally feasible in New York City and potentially effective in cities with taxi densities substantially lower than New York's.
Takeaways & Limitations
The paper identifies psychological willingness to share, generalizability to other cities, and missing empty-trip data as areas requiring further assessment.
Abstract
from arXiv · showhide
Taxi services are a vital part of urban transportation, and a considerable contributor to traffic congestion and air pollution causing substantial adverse effects on human health. Sharing taxi trips is a possible way of reducing the negative impact of taxi services on cities, but this comes at the expense of passenger discomfort quantifiable in terms of a longer travel time. Due to computational challenges, taxi sharing has traditionally been approached on small scales, such as within airport perimeters, or with dynamical ad-hoc heuristics. However, a mathematical framework for the systematic understanding of the tradeoff between collective benefits of sharing and individual passenger discomfort is lacking. Here we introduce the notion of shareability network which allows us to model the collective benefits of sharing as a function of passenger inconvenience, and to efficiently compute optimal sharing strategies on massive datasets. We apply this framework to a dataset of millions of taxi trips taken in New York City, showing that with increasing but still relatively low passenger discomfort, cumulative trip length can be cut by 40% or more. This benefit comes with reductions in service cost, emissions, and with split fares, hinting towards a wide passenger acceptance of such a shared service. Simulation of a realistic online system demonstrates the feasibility of a shareable taxi service in New York City. Shareability as a function of trip density saturates fast, suggesting effectiveness of the taxi sharing system also in cities with much sparser taxi fleets or when willingness to share is low.
Results
The study compares omniscient and realistic online taxi-sharing models, showing that a one-minute decision window still preserves substantial savings when passengers tolerate modest delays.
- Model comparison: The Oracle model uses the complete shareability network and therefore provides a theoretical upper bound, while the Online model uses only a short time slice of requests.The Oracle can incorporate future requests; the Online model reflects decisions made in real time.
- Online versus Oracle: At Δ = 5 min, the Online model saves 32% of total travel time versus 40% in the optimal Oracle model.Accounting for empty trips reduces these savings to 24% and 30%, respectively.
- Online versus Oracle: At Δ = 1 min, the Oracle model allows sharing for 94.5% of trips, whereas the Online model allows fewer than 30%.The online penalty is greatest when tolerated passenger delay is very low.
- Online versus Oracle: The Online model retains virtually all available sharing opportunities when Δ reaches 5 min.The model restricts decisions to trips starting within δ = 1 min of one another.
- Three-trip sharing: Increasing shareable group size from k = 2 to k = 3 raises saved trips from about 50% to about 60% at Δ = 300 sec.The improvement becomes noticeable only above a threshold near Δcrit ≈ 150 sec and remains below the 66.7% theoretical maximum.
Discussion
The analysis finds that New York City has substantial, implementable taxi-sharing potential, and that shareability reaches near-maximum levels at relatively low trip densities.
- Implementation: New York City offers ample sharing opportunities with minimal passenger discomfort and without rerouting already-started trips.The authors report that a system using δ = 1 min could calculate and dispatch sharing options immediately after requests.
- Density dependence: At around 100,000 trips, or 25% of New York City’s daily average, shareability already reaches saturation and near-maximum levels.The resulting shareability values are well fit by saturation curves of the form f(x) = Kx^n/(1+Kx^n).
- Density dependence: The fast saturation suggests taxi-sharing systems could remain effective in cities with much lower taxi-fleet densities than New York.The density analysis was produced by randomly removing increasing fractions of vehicles from the New York dataset.
- Future work: Future work should examine psychological barriers, incentive and fare systems, other cities, passenger search times, and passengers transported per vehicle.The authors also propose applying shareability networks to other social-sharing settings such as cars, bikes, and equipment.
Trip data.
The study uses comprehensive origin-destination records for New York City taxi trips during 2011, covering all 13,586 taxicabs and 172 million passenger trips.
- Trip data: The dataset contains origin-destination data for all 172 million passenger trips made by 13,586 New York City taxicabs during 2011.It includes 39,437 unique driver IDs, averaging 2.9 drivers per taxi.
- Trip data: Each record includes vehicle ID, pickup and drop-off coordinates, and corresponding origin and destination times.Times are accurate to the second, and positions were collected using GPS technology.
- Trip data: Pickup and drop-off locations were associated with the closest street intersections in Manhattan’s road map.The study uses these mapped locations for its network-based analysis.
Map data and map matching.
The study constructs Manhattan’s street network from selected OpenStreetMap road classes and uses polynomial-time matching algorithms for two-trip sharing.
- Map data and map matching: The Manhattan street network was built from OpenStreetMap data filtered to primary, secondary, tertiary, residential, unclassified, road, and living-street classes.Several other road classes, including footways, were deliberately excluded.
- Map data and map matching: For k = 2, maximum matching and weighted maximum matching run in O(n√n) and O(n^2 log n), respectively.Here n denotes the number of nodes in the shareability network.
- Map data and map matching: For k > 2, fast approximate solutions exist but become computationally infeasible for k > 3.The higher-dimensional problem therefore has a narrower computationally practical range.
Subsampling of vehicles.
The study tests how results generalize to lower taxi densities and lower willingness to share by subsampling vehicles from the New York dataset.
- The authors generated lower-density scenarios to assess generalizability beyond New York’s taxi density and under lower willingness to share.
- For each day, they randomly selected a percentage of taxis and deleted those vehicles’ corresponding trips from the dataset.
- The sampling fraction c was varied from 95% downward to create multiple vehicle-density conditions.
Data set and pre-processing
The analysis uses comprehensive New York taxi-trip records and a street-intersection network, while focusing the sharing framework on occupied-trip matching rather than taxi dispatch.
- Data set: The dataset contains 172 million passenger trips made by all 13,586 New York taxicabs during 2011.Each record includes vehicle, time, and origin-destination information; explicit passenger counts are unavailable.
- Pre-processing: Street intersections were extracted from Manhattan road data to construct a directed network reflecting one-way streets.The street network was manually cleaned for obvious inconsistencies and redundancies.
- Implementation: The static sharing implementation can build on existing taxi dispatching systems without revisiting empty-taxi search and scheduling.This separates trip-sharing optimization from dispatching implementation issues.
- Empty trips: The analysis compares occupied-trip durations with between-trip durations, which include empty trips and other taxi downtime.The available records cannot distinguish empty travel from shift changes, breaks, or maintenance.
- Empty trips: Efficiently matching occupied trips may be more important than empty-taxi routing, especially when taxis do not find passengers quickly.A thorough assessment of empty-trip improvement requires explicit, frequently sampled empty-trip data.
A network-based approach for sharing taxi rides
The paper models taxi-trip sharing as a shareability network and reduces two-trip optimization to graph matching. This yields polynomial-time exact solutions for minimizing performed trips or total travel cost, while larger groups require approximation.
- Network formulation: Shareability networks represent trips as nodes and connect pairs that can be combined under spatial, temporal, and delay constraints.The delay bound ∆ regulates network density and service quality.
- Network formulation: Maximum matching minimizes the number of performed trips when at most two trips can be combined.The minimum feasible-set cardinality is n − |Mmax|.
- Optimization criteria: Maximum weighted matching minimizes total travel cost by maximizing savings from combined trips.Each link weight is c(Ti) + c(Tj) − c(Ti,j).
- Generalization: For k > 2, the problem becomes weighted matching on k-bounded hyper-networks and is NP-complete in general, although constant-factor approximations are available.The paper reports polynomial-time exact computation for at most two trips and constant-factor approximation for fixed larger k.
- Feasibility: The feasible-set condition ensures every original trip appears exactly once, either individually or in one combined trip.In the two-trip case, combined trips correspond to matching edges.
Building the shareability network
The shareability network is constructed by testing whether trip pairs admit a route satisfying pickup, delivery, and delay constraints. Pairwise construction takes O(n^2) time, while extending the procedure to k trips takes O(n^k).
- Trip-pair feasibility: Each trip is characterized by origin, destination, start time, and arrival time, with feasibility governed by the maximum tolerated delay ∆.Combined routes must satisfy the paper’s pickup and delivery conditions.
- Trip-pair feasibility: A trip pair is shareable when at least one route connects both origins and destinations while satisfying the feasibility conditions.The method evaluates possible route orderings and includes a network link when one route passes.
- Complexity: Building the shareability network from n trips requires O(n^2) time.There are O(n^2) candidate pairs, and each pair’s feasibility can be checked in O(1).
- Complexity: Temporal filtering reduces candidate pairs using start and arrival-time conditions, although worst-case construction remains O(n^2).The filter is a necessary but not sufficient feasibility condition.
- Generalization: Extending construction to combinations of up to k trips yields O(n^k) time and requires considering exponentially many route orderings as k grows.The approach assumes k remains small.
Runtime and feasibility considerations
The study evaluates whether the theoretically polynomial algorithms are fast enough for realistic taxi-sharing workloads. In New York City, approximately 600 trips arrive every two minutes, defining the practical network scale examined.
- Practical workload: Approximately 600 taxi trips are requested every two minutes in New York City.This forms the typical number of nodes in the practical shareability-network workload.
Oracle and Online model
The Oracle model retains all spatially and temporally feasible sharing links, including opportunities requiring advance reservations. The Online model filters links between trips whose start times differ by more than δ, supporting real-time on-demand operation.
- Oracle model: The Oracle model retains every link whose trips can be combined without exceeding delay ∆, even when their starting times are widely separated.Such cases may require a reservation system.
- Online model: The Online model removes sharing opportunities whose starting times differ by more than δ.This filtering adapts the network to real-time, on-demand taxi service without advance reservations.
Computing travel times
The study estimates street-level and intersection-to-intersection travel times from taxi-trip data, using route optimization and iterative error minimization. Applied to about 150 million New York City weekday trips, the estimates produce time-of-day speed patterns described as reasonable.
- Data representation: Trip origins and destinations are mapped from raw GPS coordinates to nearby street intersections before travel-time estimation.Trips are represented by origin, destination, and observed travel time; equivalent origin-destination trips are aggregated using their average travel time.
- Optimization objective: The objective is to estimate each street’s travel time so routed estimates minimize average relative error against observed trip times.The process operates independently on time-sliced subsets, such as the 24 hours of the day.
- Iterative estimation: The heuristic filters loop, excessively short or long, and excessively fast or slow trips before iteratively recomputing routes and street travel times.Street offsets determine whether estimated travel times are increased or reduced, and iterations continue when the new relative error improves.
- Network-wide travel times: Dijkstra routing converts estimated street travel times into travel times between arbitrary intersections after all street times have been estimated.Initially, routes use a common speed; remaining streets are filled using neighboring estimated speeds.
- Evaluation: About 150 million New York City weekday trips from 2011 were used, with estimated speeds around 5.5 m/sec during rush hours and peaks around 8.5 m/sec at midnight.The reported speed variation across times of day is presented as evidence that the estimates are reasonable.
Robustness of day of week (Oracle model)
Weekend and weekday analyses show no major difference in trip-sharing opportunities. Weekend demand is lower, averaging approximately 350,000 trips per day versus approximately 418,000 on weekdays.
- Robustness of day of week: 17% fewer trips occurred per weekend day than per weekday, approximately 350K versus approximately 418K trips per day.The comparison uses 104 weekend days and the weekday analysis as reference.
- Robustness of day of week: No major difference was found in trip-sharing opportunities between weekends and weekdays.The weekend replication produced only minimal differences in total trip travel-time savings.
Shareable trips versus trips per day (Oracle model)
Shareability approaches saturation as daily trip density increases, while larger sharing groups offer additional savings only under favorable demand and passenger-tolerance conditions. Double sharing is computationally easier and remains effective when customers are less patient.
- Shareability versus trip density: Typical New York City days contain around 400,000 trips with almost near-maximum shareability.Days with fewer trips are rare and occur mostly during special events.
- Shareability versus trip density: The fitted saturation curve uses f(x) = Kx^n/(1+Kx^n), with n = 1.39 reported as the best fit for shared-trip maximization.The fast, hyperbolic saturation is used to characterize how sharing opportunities change with taxi density.
- Computational constraints: Triple-sharing computation is at least 15 times slower than graph computation for double sharing, and hyper-network matching is NP-hard.The method therefore uses a greedy polynomial-time heuristic for the hyper-network matching problem and evaluates shared-trip savings in the Online model for selected days.
- Increasing the number of shared trips: 60% of taxi trips were saved with k = 3 at Δ = 300 sec, compared with about 50% for k = 2 and a 66.6% all-trip-triples benchmark.Triple sharing becomes advantageous only when the quality-of-service parameter is approximately Δ ≥ 150 sec.
- Increasing the number of shared trips: Increasing shared-trip size from 2 to 3 produced an additional saving of about 10% in total travel time at Δ = 300 sec.The difference between double and triple sharing becomes perceivable only for Δ ≥ 150 sec.
- Passenger tolerance: Triple sharing achieved up to 45% total-travel-time savings, but only for relatively patient customers accepting longer waiting or travel times.At δ = 120 sec, double sharing is near ideal; triple sharing approaches near-ideal performance at δ = 180 sec with Δ = 5 min.
- Demand dependence: Double sharing remains near ideal on lower-demand days, whereas fully exploiting triple sharing requires more taxi requests.Total travel-time savings for both sharing sizes consistently benefit from higher request volumes.