Source-linked AI summary
Large Scale Real-time Ridesharing with Service Guarantee on Road Networks
Yan Huang, Ruoming Jin, Favyen Bastani, Xiaoyang Sean Wang
TL;DR
The paper addresses large-scale real-time ridesharing with service guarantees, where dynamic requests must be matched to servers under waiting-time and detour constraints. It proposes a kinetic tree approach for incremental scheduling and reports faster performance than branch-and-bound and integer-programming approaches on a large Shanghai taxi dataset.
Problem
Existing branch-and-bound and integer-programming approaches reschedule unfinished trips and new requests without reusing prior computations, requiring minutes or hours instead of millisecond responses.
Method
The paper proposes a kinetic tree approach that incrementally maintains valid trip schedules so new requests can be accommodated without recomputing schedules from scratch.
Results
The kinetic tree algorithm outperforms branch-and-bound and mixed-integer programming in experiments on a large Shanghai taxi dataset; slack-time optimization saves over 32% versus the basic tree algorithm under the tightest constraints.
Takeaways & Limitations
The kinetic tree structure supports dynamically matching real-time trip requests to road-network servers while adjusting routes on-the-fly.
Takeaways & Limitations
The authors identify uncertainty in scheduling as an important future issue and a potential major roadblock to large-scale ridesharing.
Abstract
from arXiv · showhide
The mean occupancy rates of personal vehicle trips in the United States is only 1.6 persons per vehicle mile. Urban traffic gridlock is a familiar scene. Ridesharing has the potential to solve many environmental, congestion, and energy problems. In this paper, we introduce the problem of large scale real-time ridesharing with service guarantee on road networks. Servers and trip requests are dynamically matched while waiting time and service time constraints of trips are satisfied. We first propose two basic algorithms: a branch-and-bound algorithm and an integer programing algorithm. However, these algorithm structures do not adapt well to the dynamic nature of the ridesharing problem. Thus, we then propose a kinetic tree algorithm capable of better scheduling dynamic requests and adjusting routes on-the-fly. We perform experiments on a large real taxi dataset from Shanghai. The results show that the kinetic tree algorithm is faster than other algorithms in response time.
I. INTRODUCTION
The paper formulates large-scale real-time ridesharing on road networks as dynamically matching servers with trip requests while satisfying waiting-time and service constraints. It targets fast scheduling of incoming requests and minimizes servers’ travel costs for committed services.
- Motivation: 1.6 persons per vehicle mile is the mean occupancy rate of personal vehicle trips in the United States.The paper presents ridesharing as a response to empty seats, congestion, pollution, and energy concerns.
- Problem setting: Real-time ridesharing dynamically matches cruising or passenger-carrying servers with incoming requests specifying sources, destinations, waiting limits, and detour constraints.A server must satisfy the new request’s constraints and those of already assigned trips.
- Motivation: Large-scale urban ridesharing must handle approximately 120,000 Shanghai road intersections, 40,000 taxis, and more than 400,000 daily taxi trips.These figures illustrate the scale of the motivating urban setting.
- Problem definition: A trip request tr = <s, e, w, ϵ> specifies a source, destination, maximal waiting time, and extra-detour service constraint.The service constraint bounds overall travel distance by (1 + ϵ)d(s, e).
- Problem definition: A valid schedule preserves request-point, pickup, and dropoff order while satisfying waiting-time and service constraints.Schedules represent request, source, and destination points in sequence, with servers traveling along shortest paths between consecutive points.
- Problem definition: The real-time objective is to choose a vehicle minimizing the augmented schedule’s overall trip cost for an incoming request.Only the unfinished portion can be changed because the finished schedule has already been executed.
B. Challenges
Urban-scale real-time ridesharing requires fast matching and rescheduling despite many en-route servers and dynamically arriving requests. Existing branch-and-bound and integer-programming approaches are poorly suited to millisecond response times.
- Matching challenge: A new request may require reshuffling an executing server schedule while preserving service guarantees for existing and incoming trips.The system must determine quickly whether a server can accommodate the request.
- Matching challenge: Servers farther than the request’s waiting limit from its pickup location can be filtered out, but many nearby candidates may remain.The customer is assigned to the server offering the shortest total trip time among viable candidates.
- Algorithmic limitation: Existing branch-and-bound and integer-programming methods reschedule unfinished trips from scratch and do not reuse prior-round computations.Their calculation times were measured in minutes or hours, whereas the application requires millisecond response time.
C. Contributions
The paper proposes a kinetic-tree formulation for incremental real-time matching and a hotspot approximation for controlling schedule explosion. Experiments compare the approach with traditional methods and evaluate optimization performance on large Shanghai taxi data.
- C. Contributions: Materializing valid schedules incrementally can reuse prior schedules when new requests arrive instead of recomputing them from scratch.The approach must address storage, maintenance as servers move, and rapid feasibility testing.
- C. Contributions: The kinetic tree represents the dynamic matching problem in a structure suited to real-time request and route updates.The paper formulates the ridesharing scenario around current locating and communication technology.
- C. Contributions: When nearby pickup or dropoff locations permit many valid permutations, hotspot clustering removes near-duplicate schedules while bounding solution error under stated conditions.The method targets cases where proximity makes service constraints ineffective and valid schedules numerous.
- C. Contributions: Experiments compare the tree approach with branch-and-bound and mixed-integer programming on a large Shanghai taxi dataset.Additional tests examine larger problems and the effectiveness of the proposed optimizations.
II. BRANCH-AND-BOUND AND MIXED INTEGER PROGRAMMING ALGORITHMS
The baseline methods search for a minimum-cost augmented schedule while enforcing route order, timing, and service constraints. Branch-and-bound prunes partial schedules using lower bounds, whereas mixed-integer programming encodes the schedule with binary and timing constraints.
- Baseline approaches: The brute-force baseline enumerates permutations of augmented schedule points and checks their validity constraints.Branch-and-bound and integer programming are introduced to accelerate this search.
- Branch-and-bound: Branch-and-bound expands the partial schedule with the lowest lower bound and prunes invalid candidates or candidates whose bounds exceed the best complete solution.Its bound combines current partial cost with minimum-cost incident edges for unscheduled nodes.
- Branch-and-bound: The rescheduling set contains unfinished existing points plus the incoming request’s request, pickup, and dropoff points, starting from the request point.The search finds a path through each node once without returning to the first node.
- Mixed-integer programming: The mixed-integer formulation partitions nodes into already-active dropoffs, new pickups, and new-trip dropoffs on a complete directed graph.Traditional solvers are then applied to find the schedule.
- Mixed-integer programming: Binary variables and timing constraints enforce one-time node visitation, schedule start, earliest arrival, waiting limits, and service constraints.The nonlinear timing constraint is linearized with constants Mij using a Miller-Tucker-Zemlin-style construction.
- Mixed-integer programming: v = O(m^2) and c = O(m) for the mixed-integer program, where m is the number of optimized requests.These counts refer respectively to variables and constraints.
IV. KINETIC TREE APPROACH
The kinetic tree maintains prior scheduling computations for dynamic requests, but closely located pickup or dropoff points can cause exponential schedule growth. A hotspot-based approach reduces this search space while approximating solutions with bounds.
- The kinetic tree maintains and updates calculations performed so far when new requests arrive, unlike algorithms that reschedule unfinished trips from scratch.
- Multiple nearby pickup or dropoff locations can make the number of valid schedules increase exponentially.
- The hotspot-based approach reduces the search space and approximates the solution with bounds.
A. Basic Tree Structure
The kinetic tree represents valid schedules from a server’s current location and updates them as movement and new requests make portions obsolete. Pruning preserves only schedules that remain feasible and share the executed prefix.
- The tree root tracks the server’s current location, while the remaining tree records valid schedules from that location onward.
- The selected schedule is executed along the darkened path, while completed nodes are marked as finished.
- When new requests arrive, the tree represents multiple valid insertion and service-order options subject to waiting and service constraints.
- Once the server reaches a new pickup or dropoff location, schedules without the same unfinished-trip prefix can be pruned.
- Eager invalidation prunes during movement, whereas lazy invalidation waits until a new request makes pruning necessary.
B. Handling a New Request
A new request is inserted into every feasible active schedule by testing pickup and dropoff positions, copying viable branches, and pruning infeasible subtrees. Slack-time bounds accelerate these feasibility checks, after which the shortest resulting route is selected.
- The insertion procedure extends every valid active schedule to include the new request, processing its pickup before its dropoff.
- Inserting Pickup Location: Pickup insertion requires satisfying the waiting-distance bound and limiting the additional detour introduced on a tree edge.
- Inserting Pickup Location: A traversal stops expanding descendants once the distance from the current location exceeds the waiting limit.
- Tree Insertion: The recursive insertion algorithm creates nodes, copies feasible child branches, and deletes branches when feasibility checks fail.
- Tree Insertion: Inserting s3 illustrates that infeasible routes are pruned while alternate feasible orderings remain in the generated tree.
- Min-max Filtering using Slack time: Slack time summarizes the minimum detour tolerated by a subtree, enabling a fast edge test and pruning when the detour exceeds the bound.
- Updating ∆and Tree: Among the resulting trees, the algorithm chooses the one with the shortest route; only that tree’s slack values require updating.
V. HOTSPOT BASED OPTIMIZATION
Hotspot clustering groups nearby locations and treats them as a single tree point with an arbitrary internal order, reducing schedule enumeration. Under stated slack or unconstrained conditions, the resulting cost has an additive bound.
- The basic tree can contain 8! = 40,320 pickup permutations when eight nearby pickups are feasible, before considering dropoffs.
- Hotspot clustering combines locations within θ and stops trying other insertion edges, thereby reducing the number of schedules considered.
- Without service constraints, a hotspot schedule visits its m points consecutively and satisfies cost(Ths) ≤ cost(Sbest) + 2(m + 1) × θ.
- The bound is obtained by connecting hotspot points consecutively and threading the remaining locations through the original optimal schedule.
- Arbitrary hotspot ordering adds at most (m + 1)θ relative to another hotspot ordering, according to the stated comparison.
- Combining the two comparisons yields cost(Shs) ≤ cost(Sbest) + (2m + 1) × θ for the illustrated m = 3 case.
- With service constraints, the corresponding hotspot schedule may not exist unless the constraints on the optimal schedule’s points are relaxed.
- When θ is sufficiently small, the method is expected to find a schedule with a small additional time relative to the best schedule.
VI. EXPERIMENTAL DESIGN
The experiments simulate real-time taxi requests on a large Shanghai road-network dataset and evaluate algorithm response times under controlled computational settings.
- The dataset contains 432,327 trips from 17,000 Shanghai taxis recorded on May 29, 2009.
- Trip requests are initialized from taxi pickup and destination coordinates and submitted to the simulator at their recorded pickup times.
- Each new request is tested with every vehicle, then assigned to the vehicle producing the minimum return time.
- The simulator uses an undirected weighted Shanghai road-network graph with 122,319 vertices and 188,426 edges.
- Performance experiments run in single-threaded C++ processes on Intel Xeon X5550 nodes with a three-gigabyte memory limit.
- The implementation uses separate LRU caches for up to ten million shortest distances and ten thousand shortest paths to reduce repeated shortest-path computation.
A. Four Algorithm Comparison
The study compares four algorithms across request loads, service constraints, and fleet sizes, measuring route-calculation and assignment response times. The tree algorithm is consistently fastest, while performance varies with problem size and constraints.
- Experimental setup: The evaluation varies capacity, waiting-time and tolerance constraints, and the number of taxis or servers using one-parameter-at-a-time tests.
- Metrics: ACRT measures the average search time to select a vehicle for a new request, while ART measures average route-calculation time for a taxi’s current state.
- Four Algorithm Comparison: The tree algorithm outperforms brute-force, branch-and-bound, and mixed-integer programming in all Figure 6 test cases through its incremental approach.
- Four Algorithm Comparison: Branch-and-bound outperforms brute-force with few taxis and many requests already scheduled, whereas brute-force benefits from faster initialization on smaller problems.
- Four Algorithm Comparison: For default parameters, mixed-integer programming is approximately 20 times slower, while the tree algorithm is almost two times faster than branch-and-bound.
- Sensitivity analysis: For four requests, ART increases as constraints loosen, while increasing servers has little effect on the tree algorithm but decreases ART for the other algorithms.
B. Comparing Tree Algorithms
The study evaluates tree-algorithm variants across constraints, fleet sizes, and capacities. Slack time improves runtime under tight constraints, while hotspot clustering extends scalability to higher and unlimited capacities.
- Slack-time achieves over 32% maximum time savings versus the basic tree algorithm at the tightest tested constraints, and approximately 18% under default parameters.
- Basic and slack-time tree algorithms show steep ART increases for tight constraints and large capacities when servers reach six passengers.
- ART increases gradually with looser constraints because they permit more feasible combinations.
- Hotspot clustering is the only tree variant that finishes simulations above capacity seven and at unlimited capacity.
- At unlimited capacity, a server carries at most 17 passengers and averages 1.7 under default parameters, while the top 20% filled servers average slightly above 3.9.
VII. RELATED WORK
Related work spans static and dynamic dial-a-ride, nearest-neighbor filtering, heuristic trip grouping, and exact optimization. The paper addresses multiple servers, real-time requests, deadlines, and large-scale scheduling constraints.
- Nearest-neighbor search on road networks is used only as a preliminary filter for candidate taxis within ridesharing systems.
- Trip grouping methods use heuristics such as expiration grouping, pairwise combination savings, greedy grouping, space partitioning, and parallelization.
- Earlier dial-a-ride research commonly targets one vehicle or static request sets known in advance, unlike large-scale ad-hoc taxi services.
- Dynamic single-vehicle DARP considers online decisions and objectives including makespan or average completion time, with competitive ratio as a standard measure.
- This paper's multiple-server dynamic DARP setting with deadlines targets real-time response, average completion time, and maximizing served requests.
VIII. CONCLUSION
The paper proposes an optimized kinetic tree algorithm for dynamically matching real-time trip requests to servers on road networks. Experiments on a large Shanghai taxi dataset show it outperforms branch-and-bound and mixed-integer programming, while uncertainty remains future work.
- The optimized kinetic tree algorithm dynamically matches real-time trip requests to servers on road networks for ridesharing.
- Experiments on a large taxi dataset show that the proposed algorithm outperforms branch-and-bound and mixed-integer programming.
- The authors identify uncertainty in scheduling as important future work and a possible major obstacle to large-scale ridesharing.