PaperlayerView exact revision on arXiv

Source-linked AI summary

Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas: A Receding Horizon Control Approach

Fei Miao, Shuo Han, Shan Lin, John A. Stankovic, Hua Huang, Desheng Zhang, Sirajum Munir, Tian He, George J. Pappas

arXiv:1603.04418v1eess.SY

TL;DR

Traditional taxi service is uncoordinated, causing idle driving, while historical models alone cannot account for taxis’ changing real-time positions. The paper develops a receding horizon control framework using historical models and real-time sensing to dispatch taxis, reducing average total idle distance by 52% and supply-demand ratio error by 45% in San Francisco trace-driven analysis.

  • Problem

    Traditional taxi service remains uncoordinated, with drivers sometimes traveling idly while seeking nearby requests.

  • Method

    The receding horizon control framework combines historical demand and mobility models with real-time GPS and occupancy feedback to dispatch vacant taxis under multiple objectives.

  • Results

    The approach reduces average total taxi network idle distance by 52% and local-global supply-demand ratio error by 45% compared with historical taxi system performance.

  • Takeaways & Limitations

    The framework computes suboptimal dispatch solutions that seek globally balanced supply-demand ratios with least associated cruising distance and supports robust formulations for demand uncertainty.

  • Takeaways & Limitations

    Longer prediction horizons may amplify errors when demand and mobility predictions are imperfect, making real-time adjustment necessary.

Abstract

from arXiv · show

Traditional taxi systems in metropolitan areas often suffer from inefficiencies due to uncoordinated actions as system capacity and customer demand change. With the pervasive deployment of networked sensors in modern vehicles, large amounts of information regarding customer demand and system status can be collected in real time. This information provides opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this paper, we present a receding horizon control (RHC) framework to dispatch taxis, which incorporates highly spatiotemporally correlated demand/supply models and real-time GPS location and occupancy information. The objectives include matching spatiotemporal ratio between demand and supply for service quality with minimum current and anticipated future taxi idle driving distance. Extensive trace-driven analysis with a data set containing taxi operational records in San Francisco shows that our solution reduces the average total idle distance by 52%, and reduces the supply demand ratio error across the city during one experimental time slot by 45%. Moreover, our RHC framework is compatible with a wide variety of predictive models and optimization problem formulations. This compatibility property allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event information.

I. INTRODUCTION

The paper addresses city-scale taxi coordination by combining historical models with real-time sensing in a receding horizon control framework. It targets fairer supply-demand balance while reducing current and anticipated idle driving, with trace-driven San Francisco results supporting the approach.

  • Motivation: Uncoordinated driver behavior and locality-based dispatch create spatiotemporal mismatches between taxi supply and passenger demand.Local greedy methods prioritize immediate satisfaction rather than future network-wide resource utilization and service fairness.
  • Approach: The method combines historical system models with real-time taxi data in a taxi network control framework.Sensing data supports predictive passenger-demand and taxi-mobility models and provides real-time feedback for control.
  • Approach: The framework uses receding horizon control to coordinate taxis across large-scale networks using predicted future demand and current system information.Future demand may come from historical taxi datasets or streaming data, while GPS and occupancy data update supply-demand information.
  • Evaluation: 52% lower average total taxi network idle distance and 45% lower local-global supply-demand ratio error were reported on San Francisco taxi records.Both comparisons use actual historical taxi system performance as the baseline.
  • Robustness: The framework extends to robust dispatch formulations by representing disruptive passenger demand as uncertainty sets.The robust formulation reduced local-global supply-demand ratio error by 25% relative to solutions without demand uncertainties.
  • Related work: Prior work addressed taxi dispatch, transportation modeling, and coordination, but did not combine real-time sensing, historical mobility patterns, and RHC for taxi supply rebalancing.The paper positions this combination as the missing integration in related mobility-control work.

III. TAXI DISPATCH PROBLEM FORMULATION

The formulation represents regional passenger demand and vacant-taxi supply using real-time information, then seeks dispatch assignments that balance service while respecting operational constraints. The system repeatedly updates information and dispatch decisions.

  • A. Supply and demand in taxi dispatch: The dispatch system schedules vacant taxis toward predicted passengers across regions and time slots while minimizing total idle mileage.Supply-demand ratio is used as the service-quality measure.
  • A. Supply and demand in taxi dispatch: The dispatch center periodically processes GPS and occupancy streams, computes a new real-time dispatch solution, and sends destination regions to vacant taxis.A new decision is made after sensing information is updated in the next period.
  • A. Supply and demand in taxi dispatch: The city is divided into n regions, with r^k_j denoting passenger requests in region j during time slot k.The request vector contains regional demands to be met over the dispatch horizon.
  • A. Supply and demand in taxi dispatch: The system dispatches N vacant taxis identified through real-time GPS positions, while occupied-taxi information affects predicted demand served by vacant taxis.The algorithm directly makes decisions for vacant taxis.
  • A. Supply and demand in taxi dispatch: Each region contains predicted requests and vacant-taxi locations, and dispatch solutions send selected taxis toward regions according to predicted demand.Figure 2 represents regions as circles, adjacent regions with black dashed edges, and dispatches with red taxi-labeled edges.
  • B. Optimal dispatch under operational constraints: Table I lists the parameters and variables used in the RHC problem formulation.The formulation can use a standard relaxation when mixed-integer programming is inefficient for large problem sizes.
  • B. Optimal dispatch under operational constraints: The binary matrix X^k ∈ {0,1}^{N×n} assigns each vacant taxi to a region, with X^k_ij = 1 exactly when taxi i is sent to region j.Every taxi must be dispatched to one region during each time slot.

1) Two objectives:

The dispatch objective balances regional supply-demand ratios against current and anticipated future idle driving distance. The formulation softens potentially infeasible fairness constraints and uses Manhattan distance as a tractable regional approximation.

  • 1) Two objectives:: Supply-demand ratio measures whether vacant taxis are allocated across regions in proportion to predicted passenger requests.Equal regional and citywide ratios represent the desired fairness condition.
  • 1) Two objectives:: The fairness requirement is converted into a soft constraint with a supply-demand mismatch penalty because integer assignments and limited taxi speeds may make exact balance infeasible.The resulting objective minimizes the mismatch penalty rather than requiring exact equality.
  • 1) Two objectives:: The second objective minimizes idle cruising distance introduced when vacant taxis travel to dispatched regions.Large future idle distance can reduce long-run taxi-network profits after current demand is served.
  • 1) Two objectives:: Regional destinations are mapped to specific longitude-latitude positions for each taxi before distance costs are computed.The matrix W_i stores the taxi-specific dispatch positions associated with candidate regions.
  • 1) Two objectives:: Current idle distance is estimated from each taxi’s GPS position to its assigned location using the Manhattan norm on a grid-road approximation.This is a closed-form regional heuristic that avoids requiring exact traffic conditions or travel times.
  • 1) Two objectives:: Anticipated future idle distance is estimated from predicted taxi ending positions based on a convex mobility pattern function.The estimate accounts for the next slot beginning at the prior slot’s predicted ending location.
  • 1) Two objectives:: Each taxi’s travel distance is bounded by α^k, and total idle distance is accumulated across taxis and time slots.The distance estimate is nonzero only when a vacant taxi is dispatched to a different region.

2) An RHC problem formulation:

The RHC problem combines fairness mismatch and idle-distance costs under assignment and travel constraints. Continuous relaxation can be rounded into executable binary dispatch decisions with a bounded constraint violation.

  • 2) An RHC problem formulation:: A weight parameter β^k controls the trade-off between supply-demand fairness and total idle driving distance.The optimization formulation can be relaxed when mixed-integer programming is inefficient for large taxi networks.
  • 2) An RHC problem formulation:: Problem (8) formulates the dispatch optimization from the defined variables, parameters, constraints, and objective function.The formulation is the computational problem solved to obtain dispatch decisions.
  • 2) An RHC problem formulation:: The relaxed assignment variables satisfy 0 ≤ X^k_ij ≤ 1 for every taxi, region, and time slot.This replaces binary assignment values with bounded continuous variables during relaxation.
  • 2) An RHC problem formulation:: Rounding may violate the original distance bound, but the resulting solution satisfies d^k_i ≤ α^k_i + ϵ with bounded ϵ.A conservative upper bound keeps the rounded dispatch executable during the time slot.
  • 2) An RHC problem formulation:: Figure 3 traces the estimate of a taxi’s idle distance to its dispatched location through a predicted prior-slot ending position.The illustration uses the i-th taxi at k = 2 and the predicted ending location for k = 1.

C. Discussions on the optimal dispatch formulation

The formulation uses supply-demand ratio error to assess regional fairness, while constraining dispatch timing through the reachable distance α_k.

  • 1) Why use supply demand ratio as a metric:: The supply-demand ratio measures differences between vacant taxis and predicted requests across regions.
  • 1) Why use supply demand ratio as a metric:: A citywide vacancy-request error can be large even when taxis are preferentially allocated to busier regions.
  • 1) Why use supply demand ratio as a metric:: The error alone cannot establish whether supply has been fairly allocated according to varying regional demand.
  • 2) The meaning of α_k:: When a time slot lasts one hour, α_k represents the distance a taxi can travel during 20 minutes of that hour.
  • 2) The meaning of α_k:: The dispatch constraint requires taxis to reach their assigned positions within 20 minutes to fulfill predicted requests.
  • 2) The meaning of α_k:: Traffic monitoring and speed prediction can adjust α_k using available travel-time and travel-speed information.

3) One example of mobility pattern function f k:

The mobility-pattern model represents probabilistic taxi movements between regions and uses expected ending positions to estimate future idle driving distances within the dispatch horizon.

  • The mobility pattern matrix C^k describes taxi movement between regions during time slot k.
  • Each entry [C^k]_ij is the probability that a vacant taxi starting in region i ends in region j during time k.
  • Given a taxi’s current assignment and the mobility matrix, the model computes its probability of ending in each region.
  • To avoid the high complexity of stochastic optimization, the formulation uses the taxi’s expected ending position.
  • The predicted ending location is used to form a lower bound on idle distance to a future dispatch position.
  • The first idle-distance term uses real-time GPS location, while later terms estimate future idle distances for meeting requests.
  • Mobility-pattern accuracy affects future idle-distance choices, but updated GPS positions enable replanning from actual taxi locations.

4) Information on road congestion and passenger destination:

The framework incorporates congestion, destination assumptions, fairness objectives, and demand uncertainty, including computationally tractable robust formulations for disruptive events.

  • 4) Information on road congestion and passenger destination:: Congestion information can generalize the mobility model; under congestion, taxis may have high probability of remaining in the same region.
  • 4) Information on road congestion and passenger destination:: Passenger destinations are not assumed available, but known destinations and travel times can be incorporated into the ending-position function.
  • 4) Information on road congestion and passenger destination:: The dispatch objective targets global service fairness through balanced supply-demand ratios rather than minimizing each individual waiting time.
  • D. Robust RHC formulations: Historical demand and mobility predictions are imperfect, and disruptive events can cause actual spatiotemporal demand to deviate from predictions.
  • D. Robust RHC formulations: The nominal formulation is computationally tractable and flexible enough to adjust constraints and objectives for different conditions.
  • D. Robust RHC formulations: Uncertain regional demand can be modeled with interval uncertainty while fixing approximated total city demand in the denominator.
  • D. Robust RHC formulations: The resulting robust optimization problem remains computationally tractable and is equivalent to a computationally efficient convex optimization problem.
  • D. Robust RHC formulations: The uncertainty set can incorporate empirical confidence regions or external information about future disruptive events.

IV. RHC FRAMEWORK DESIGN

The RHC framework combines learned models with real-time sensing and repeatedly solves a finite-horizon optimization, executing only the current dispatch decision.

  • Historical models alone cannot determine dispatch solutions when taxi positions change dynamically in real time.
  • Real-time GPS and occupancy data provide feedback for updating taxi locations and demand information.
  • At each iteration, solving the nominal or robust optimization problem produces the dispatch solution for the RHC framework.
  • RHC optimizes over a horizon [1,T], but sends vacant taxis only the first decision X_1 before replanning.

A. RHC Algorithm

Algorithm 1 repeatedly updates real-time taxi and demand information, estimates current and future service conditions, and solves a receding-horizon dispatch problem. It can use predicted demand intervals for robust dispatch when disruptive-event uncertainty is known.

  • A. RHC Algorithm: At each t2-minute iteration, the RHC algorithm updates taxi GPS, occupancy, vacant-taxi counts, and preferred dispatch locations.The loop then refreshes demand, mobility functions, idle-distance thresholds, and objective weights before optimization.
  • A. RHC Algorithm: The dispatch center solves an optimization problem and sends orders to vacant taxis according to the optimal first-step dispatch matrix.The algorithm stores sensor data and dispatch solutions after each iteration.
  • A. RHC Algorithm: The framework deducts estimated service from occupied taxis using real-time occupancy counts and predicted drop-off probabilities before forming remaining demand.For region j, the predicted drop-off count is based on pdj(h1) and the current number of occupied taxis.
  • A. RHC Algorithm: Future demand rk is estimated by averaging predicted requests across t2 intervals within the current and subsequent t1 time slots.The number of t2 intervals per t1 slot is H = t1/t2.
  • A. RHC Algorithm: When predicted demand is represented as an interval, the algorithm constructs an uncertain set for rk to formulate a computationally efficient robust dispatch problem.This supports dispatch under disruptive-event demand uncertainty.

4) Spatial and temporal granularity of Algorithm 1:

The algorithm’s granularity and parameter settings balance prediction accuracy, future-cost coverage, and computational resources. Evaluation uses trace-driven San Francisco taxi data, bootstrapped demand estimates, and mobility and drop-off models across selected regions and time periods.

  • 4) Spatial and temporal granularity of Algorithm 1:: The main computational cost is solving the optimization problem, so t2 must be no shorter than the required computation time.The authors regulate parameters empirically because no closed-form equations determine their optimal values.
  • 4) Spatial and temporal granularity of Algorithm 1:: A large prediction horizon captures longer-term idle-distance costs but may amplify prediction errors, whereas a small horizon may omit future idle-distance costs.Real-time information is used to adjust taxi supply as predictions are revised.
  • 5) Selection process of parameters βk, αk, and T:: Parameter selection is trial-and-adjustment, including βk for fairness versus idle distance, αk for idle-distance thresholds, and T for look-ahead effects.A formal parameter-selection method is identified as future work.
  • 4) Spatial and temporal granularity of Algorithm 1:: The framework accepts predicted demand or reservation records and can combine forecast-based dispatch with real-time demand updates.A multi-level framework first dispatches using predicted demand, then applies current-demand dispatch when taxis reach assigned locations.
  • 4) Spatial and temporal granularity of Algorithm 1:: San Francisco trace-driven simulations learn average requests and taxi mobility patterns from GPS position, occupancy status, and Unix epoch time records.Vacant taxis are assumed to follow dispatch orders and pick up the nearest recorded request in target regions for simulated idle-mileage calculation.
  • 4) Spatial and temporal granularity of Algorithm 1:: Weekday results average data across the dataset, while the results in Subsection V-C use weekend data; the study also evaluates a baseball game as a disruptive event.The Giant baseball game at AT&T Park on May 31, 2008 is used to evaluate the robust optimization formulation.
  • 4) Spatial and temporal granularity of Algorithm 1:: Figure 4 compares request patterns across hours for weekdays and weekends in four selected regions, motivating region- and time-dependent taxi dispatch.The study also estimates drop-off-event vectors using a similar process and displays them for selected regions.
  • 4) Spatial and temporal granularity of Algorithm 1:: Demand and drop-off events are inferred from occupancy transitions and assigned to spatial regions and time slots using taxi locations and timestamps.Equal-area regions are used for evaluation, with vacant-taxi station positions sampled uniformly within the city.

B. RHC with real-time sensor information

The RHC dispatch framework combines estimated mobility patterns with real-time taxi positions and occupancy data to reduce idle driving while balancing regional supply and demand. In San Francisco experiments, real-time sensing improved both idle-distance and supply-demand matching outcomes.

  • Mobility-pattern estimation: The mobility pattern matrix estimates transitions between origin and destination regions using passenger trajectories and bootstrap estimation.For weekday 5:00–6:00 pm data, the estimated matrix had a 34.8% average cross-validation error.
  • Idle-distance results: 17.6% lower total idle distance was achieved using estimated mobility patterns than in the original no-dispatch record.Using the true mobility matrix reduced idle distance by 68%, while real-time sensing compensated for errors in estimated mobility patterns.
  • Idle-distance results: 52% lower idle distance was achieved with dispatch using real-time GPS and occupancy information than without dispatch.Real-time initial positions let the optimization use current taxi locations rather than estimated positions from mobility patterns.
  • Supply-demand balance: Real-time dispatch made each region’s supply-demand ratio closest to the whole-city ratio and reduced mismatch error by 45%.The comparison evaluates regional balance across the city during one time slot.

C. Robust taxi dispatch

The robust dispatch formulation incorporates uncertain and disruptive demand into RHC, while parameter studies show that performance depends on prediction horizons, update intervals, regional partitioning, and objective weights. These experiments expose trade-offs between regional balance, idle distance, prediction accuracy, and computation time.

  • Robust dispatch: A baseball game near AT&T Park increased customer requests in nearby Region 7 by about 40% above average near the game’s end.This event was used to evaluate robust optimization formulation (12).
  • Robust dispatch: 46% lower supply-demand mismatch error was obtained with robust dispatch than with historical data without dispatch during a disruptive event.The robust formulation also reduced mismatch error by 25% relative to the standard formulation (8).
  • Objective weighting: Increasing βk lowers idle-distance cost but increases supply-demand ratio error, exposing the objective’s balance between the two terms.The total cost is defined as s/d error + βk × idle distance.
  • Distance threshold: Increasing αk reduces local-global supply-demand error by allowing vacant taxis to travel farther toward demand.A 0.1 difference in GPS coordinates corresponds to almost 7 miles on the ground.
  • Region partitioning: Larger region-division numbers reduced idle distance until the reduction slowed and distance became nearly steady.Smaller regions can improve dispatch accuracy, but prediction and mobility-model considerations also constrain the choice.
  • Prediction horizon: For prediction horizons T = 2 and T = 4, idle distance decreased at most hours as T increased, whereas T = 8 produced the largest driving distance.Prediction error can offset the benefit of considering farther future costs when the horizon becomes too large.
  • Sensor-update interval: Shorter update intervals can reduce idle distance, but t2 must exceed the computation time required for one dispatch iteration.When t2 = 1 minute, supply-demand ratios were worse in some regions because an iteration could not finish.

VI. CONCLUSION

The paper concludes that RHC can combine historical models, real-time sensing, and robust demand formulations to dispatch taxis toward citywide balance with lower cruising distance. San Francisco evaluations support system-level performance improvements, while future work targets privacy-preserving control.

  • Conclusion: The RHC framework uses historical and real-time GPS and occupancy data to compute suboptimal dispatches balancing citywide supply-demand ratios and cruising distance.The framework incorporates demand uncertainty from disruptive events through robust dispatch formulations.
  • Conclusion: San Francisco evaluation results support system-level performance improvements from the proposed RHC framework.The paper also examines how objective weights, idle-distance thresholds, and prediction horizons affect dispatch design.
  • Conclusion: Future research will develop privacy-preserving control when some taxis do not share data with the dispatch center.This identifies a scope boundary for the current sensing-based framework.
Loading 1603.04418v1…