PaperlayerView exact revision on arXiv

Source-linked AI summary

Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspective

Rick Zhang, Marco Pavone

arXiv:1404.4391v1cs.ROcs.MA

TL;DR

Autonomous MOD systems need network-wide vehicle coordination because demand can create station imbalances and existing fluid models omit stochastic availability and waiting-time metrics. The paper models these systems as closed Jackson networks, derives linear-program rebalancing, and evaluates the approach in Manhattan, where 7,000–8,000 vehicles provide adequate service under current demand while congestion remains a concern in already-congested settings.

  • Problem

    Existing fluid models do not capture stochastic fluctuations or provide vehicle-availability and customer-waiting-time metrics needed to assess autonomous MOD systems.

  • Method

    The paper models autonomous MOD systems as closed Jackson networks with passenger loss, optimizes rebalancing through a linear program, and develops a real-time policy.

  • Results

    7,000–8,000 robotic vehicles can provide adequate service with current Manhattan taxi demand, with 8,000 vehicles producing an average wait time of 2.5 minutes.

  • Takeaways & Limitations

    Autonomous rebalancing can balance vehicle availability and generally follows less congested roads, though it can worsen congestion in already-congested systems.

Abstract

from arXiv · show

In this paper we present and analyze a queueing-theoretical model for autonomous mobility-on-demand (MOD) systems where robotic, self-driving vehicles transport customers within an urban environment and rebalance themselves to ensure acceptable quality of service throughout the entire network. We cast an autonomous MOD system within a closed Jackson network model with passenger loss. It is shown that an optimal rebalancing algorithm minimizing the number of (autonomously) rebalancing vehicles and keeping vehicles availabilities balanced throughout the network can be found by solving a linear program. The theoretical insights are used to design a robust, real-time rebalancing algorithm, which is applied to a case study of New York City. The case study shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 60% of the size of the current taxi fleet). Finally, we extend our queueing-theoretical setup to include congestion effects, and we study the impact of autonomously rebalancing vehicles on overall congestion. Collectively, this paper provides a rigorous approach to the problem of system-wide coordination of autonomously driving vehicles, and provides one of the first characterizations of the sustainability benefits of robotic transportation networks.

I. INTRODUCTION

The paper addresses how autonomous MOD systems can coordinate vehicles across urban networks while maintaining service quality. It develops a stochastic queueing approach to model, optimize, and evaluate such systems.

  • Urban population is projected to double within 30 years, while limited road and parking capacity makes private automobiles appear unsustainable for future urban mobility.
  • One-way vehicle sharing can target parking, pollution, and low vehicle-utilization problems, but human-driven systems develop imbalances between stations.
  • Driverless electric cars can rebalance themselves and enable system-wide coordination, yet little is known about designing and operating robotic transportation networks.
  • Fluid models provide operational insight but cannot capture stochastic fluctuations or compute vehicle availability and customer waiting times.
  • The paper proposes a Jackson-network model, studies rebalancing algorithms, evaluates autonomous MOD benefits, and analyzes congestion effects.
  • The approach extends queueing-network analysis to autonomous vehicle coordination, building on prior work modeling traditional shared vehicles with Jackson networks.

III. MODEL DESCRIPTION AND PROBLEM FORMULATION

The model represents an autonomous MOD system with stations, vehicles, stochastic customer arrivals, destination choices, travel times, and passenger loss when vehicles are unavailable. Its availability criterion is suited to impatient customers requiring immediate service.

  • A. Model of autonomous MOD system: The system contains N stations and m autonomous vehicles, with customers arriving at station i through a time-invariant Poisson process of rate λi.
  • A. Model of autonomous MOD system: Each arriving customer chooses destination j with probability pij, where the destination probabilities form an irreducible Markov chain.
  • A. Model of autonomous MOD system: Customers take an available vehicle; if the station is empty, they immediately leave, defining a passenger-loss model rather than a waiting-queue model.
  • A. Model of autonomous MOD system: Travel times from station i to station j are independent and identically distributed exponential random variables with mean Tij.
  • A. Model of autonomous MOD system: Vehicles may autonomously travel through the network to rebalance themselves and anticipate future demand.
  • A. Model of autonomous MOD system: The principal performance criterion is vehicle availability at each station, equivalently the probability that an arriving customer is lost.
  • A. Model of autonomous MOD system: The loss model captures impatient customers unwilling to wait and simplifies analysis by representing immediate departures when vehicles are unavailable.

B. Casting an autonomous MOD system into a Jackson model

The paper maps stations and roads to single-server and infinite-server nodes, respectively, producing a closed Jackson network for vehicle movements. Rebalancing is incorporated through virtual passenger flows that preserve tractability.

  • Stations are modeled as single-server nodes where vehicles wait for customers, while roads are modeled as infinite-server nodes representing vehicle travel.
  • The abstract network contains N^2 nodes: N station nodes and N(N−1) road nodes.
  • Vehicles move from station nodes to road nodes according to customer destinations, then from each road node to its destination station.
  • Station service rates are λi, while a road connecting j to k has service rate n · µjk, with µjk = 1/Tjk.
  • The resulting abstract queueing network is closed and can therefore be analyzed using Jackson-network tools.
  • Rebalancing is represented by independent Poisson virtual passengers generated at station i at rate ψi and routed to station j with probability αij.
  • Virtual passengers are lost at empty stations, and the policy class promotes rebalancing without enforcing a fixed rebalancing rate, preserving tractability.
  • Real and virtual passenger processes are superposed and Bernoulli-split into generalized passenger flows, yielding modified routing probabilities for the Jackson model.

C. Problem formulation

The formulation uses rebalancing to equalize station availability while minimizing rebalancing vehicles. Without rebalancing, some stations remain persistently undersupplied regardless of fleet size.

  • Without rebalancing, station availability converges to γi/γmax_S as fleet size grows, based on each station’s relative utilization.
  • Stations with maximal relative utilization can approach full availability, while other stations remain below full availability regardless of the number of vehicles.
  • The paper therefore seeks rebalancing that equalizes station availabilities, providing service fairness and making availability approach one as fleet size increases.
  • The optimization adjusts rebalancing rates and routing probabilities so station relative utilizations are equalized while minimizing rebalancing vehicles on the roads.
  • The Optimal Rebalancing Problem determines rebalancing controls for a closed Jackson-network model.
  • Direct solution is difficult because relative throughputs require a large null-space computation and the objective and balance constraints are nonlinear.

IV. OPTIMAL REBALANCING

The paper reduces optimal rebalancing in an autonomous MOD Jackson network to a lower-dimensional optimization problem. The resulting solution supports balanced vehicle availability while minimizing rebalancing effort.

  • Traffic-equation reduction: The SS-node traffic equations can be folded into reduced equations, after which IS-node throughputs are recovered separately.This isolates the station-to-station nodes when computing relative throughputs.
  • Optimal rebalancing formulation: The optimal rebalancing problem can always be solved through a low-dimensional linear optimization problem.The theorem identifies a linear optimization formulation whose solution is optimal for ORP.
  • Optimal rebalancing formulation: The reduced optimization has the form of an uncapacitated minimum cost flow problem and is therefore always feasible.This provides the computational structure used to obtain an optimal rebalancing solution.
  • Optimality conditions: The equal-throughput constraint γ_i = γ_j follows from an irreducible row-stochastic transition matrix and its unique stationary solution.The Perron-Frobenius argument yields γ = (1, ..., 1)^T.
  • Relation to prior models: Problem (13) has the same form as the linear optimization problem used previously for fluidic autonomous MOD models.The queueing analysis supplies a theoretical foundation for that fluidic approximation.
  • Implications: Theorem IV.3 enables efficient computation of an optimal open-loop rebalancing policy and vehicle-availability metrics.These metrics are used to evaluate autonomous MOD system quality of service.

B. Computation of performance metrics

The paper computes autonomous MOD performance metrics by combining the optimal rebalancing solution, reduced traffic equations, and mean value analysis. The procedure is designed for large systems with many stations and vehicles.

  • Evaluation procedure: Performance evaluation first solves ORP using Theorem IV.3 and then computes relative throughputs using Lemma IV.1.The ORP formulation contains N^2 variables.
  • Evaluation procedure: Mean value analysis avoids explicitly computing the normalization constant, which is prohibitively expensive for large vehicle and station counts.MVA iteratively calculates mean waiting times and queue lengths in the closed queueing system.
  • Mean value analysis: MVA iterates over vehicle counts n = 1, 2, ..., m to calculate mean waiting times and queue lengths at each node.In this model, the abstract queueing-system customers are vehicles.
  • Performance metrics: Station throughput is obtained with Little’s theorem, and availability is then calculated as A_i(m) = Λ_i(m)/λ̃_i.The throughput is Λ_i(m) = L_i(m)/W_i(m).
  • Scalability and application: The procedure scales to hundreds of stations and thousands of vehicles and is applied to real-world New York City settings.The application assesses autonomous MOD performance in a large urban network.
  • Scalability and application: The preceding rebalancing-promoting policy is open-loop and has limited applicability, motivating a closed-loop policy for practical operation.The next section uses insights from ORP to formulate that policy.

C. Real-time rebalancing policy

The real-time policy uses current system information to estimate station ownership and excess vehicles, then solves an integer optimization to distribute rebalancing vehicles evenly.

  • State representation: Station-owned vehicles include vehicles at the station, en route to it, or scheduled to travel there.This definition incorporates vehicles that are not physically present but are allocated to the station.
  • Excess-vehicle calculation: The policy computes excess vehicles by comparing station-owned vehicles with the number of customers at each station.The total excess is expressed using the positive part of the vehicle-customer difference.
  • Excess-vehicle calculation: Rebalancing aims to distribute excess vehicles evenly so every station reaches a target vehicle level.The target is defined as a station-specific desired number of vehicles.
  • Real-time optimization: Every τ_hor > 0 time periods, the policy computes station-to-station rebalancing counts by solving a linear integer optimization problem.The optimization determines num_ij, the number of vehicles rebalanced from station i to station j.
  • Real-time optimization: The policy uses all currently known system information and sets rebalancing rates to distribute excess vehicles evenly across stations.Its design is partly inspired by the optimal rebalancing formulation in Theorem IV.3.
  • Evaluation: The policy is used to validate vehicle availability as a performance criterion.It is applied in the subsequent case study.

V. CASE STUDY: AUTONOMOUS MOD IN MANHATTAN

The Manhattan case study estimates the robotic fleet needed to match current taxi demand and evaluates resulting customer waiting times using taxi data and simulation. Results indicate that 7,000–8,000 vehicles can provide adequate service, with 8,000 vehicles achieving high availability and short waits.

  • Data and setup: 439,950 taxi trips from March 1, 2012, were used to estimate hourly Manhattan demand and system parameters.The data represent current taxi activity used for the case study.
  • Availability analysis: Vehicle availability was evaluated at peak, low, and average demand for fleets of different sizes using mean value analysis.The demand cases were 29,485, 1,982, and 16,930 demands per hour, respectively.
  • Availability analysis: 8,000 vehicles provide about 95% availability at peak demand, while 6,000 vehicles provide the same availability at average demand.The 8,000-vehicle fleet is roughly 60% of the current taxi fleet size.
  • Waiting-time simulation: Simulations use 100 stations, 8,000 vehicles, 2-second time steps, 24 hours, hourly demand variation, and rebalancing every 15 minutes.Travel times use Manhattan distance and hourly average speeds estimated from taxi data.
  • Waiting-time simulation: 7,000 vehicles produce a peak average wait below 5 minutes, while 8,000 vehicles reduce the average wait to 2.5 minutes.The peak wait for the 7,000-vehicle fleet occurs from 9–10am.

VI. A MEAN VALUE ANALYSIS APPROACH TO THE ANALYSIS OF CONGESTION EFFECTS

The paper extends its queueing framework to represent road congestion by replacing infinite-server road queues with finite-server queues whose capacities correspond to physical road capacities. It develops a mapping from shared physical roads to virtual queue capacities and retains the Jackson-network analysis, while leaving optimal congested rebalancing policies for future work.

  • Congestion model: Congestion is modeled by replacing infinite-server road queues with finite-server queues, where server counts represent road capacities.The approach is based on an abstract queueing network and an extended mean value analysis algorithm.
  • Model implications: The extended Jackson model preserves earlier results, but congestion-dependent travel times complicate optimal rebalancing-policy formulation.Given a rebalancing policy, the framework can still compute metrics such as vehicle availability.
  • Road-capacity mapping: The main mapping difficulty is that trips with different origins and destinations may share the same physical road.Virtual capacities must therefore represent overlapping route usage rather than isolated station-to-station links.
  • Road-capacity mapping: For a three-station example, virtual server counts are constrained by route consistency, while physical road capacities determine the number of vehicles that can travel without significant congestion.The example defines q_ij as a physical capacity and m_ij as the corresponding virtual server count.
  • Road-capacity mapping: A quadratic objective minimizes the difference between real road capacities and summed virtual road capacities, but does not yield a unique solution without relative usage rates.Known relative throughput can assign virtual capacities proportionally to traffic using each road.

B. Numerical study of congestion effects

A nine-station grid experiment examines how rebalancing vehicles affect road utilization and congestion under finite road capacities. Rebalancing generally increases average utilization but usually avoids increasing congestion on the most congested segment, with rare cases reaching a 10% increase.

  • Network and assumptions: The experiment uses a nine-station square grid with 0.5-km, two-way road segments, each having capacity for 40 vehicles.Vehicles travel at 30 km/h in free flow, corresponding to one minute per road segment.
  • Simulation design: The study generates 500 random systems with different demand imbalances and computes passenger and rebalancing vehicle loads on each road.Uniform routing distributes vehicles from each station pair across its possible paths.
  • Results: Rebalancing increases average road utilization linearly with the number of rebalancing vehicles, but maximum congestion increases are usually zero.Rebalancing vehicles mostly use less congested routes and generally avoid the most congested segment.
  • Results: The most congested road segment can remain unchanged even when rebalancing increases vehicle counts on many other roads.The example identifies the segment from station 6 to station 5 as the most congested road.
  • Limitations and future work: In rare cases, rebalancing increases maximum congestion by up to 10%, particularly when congestion is already above 90%.The paper identifies congestion-aware routing or limiting rebalancing as a future direction for these cases.

VII. CONCLUSIONS

The paper presents a queueing-theoretical model and linear-program-based open-loop policy for autonomous MOD rebalancing, then develops a real-time policy and evaluates congestion effects. It concludes that rebalancing can worsen congestion in already-congested systems, although rebalancing vehicles usually use less congested roads.

  • The paper presents a queueing-theoretical model for autonomous MOD systems and derives an optimal open-loop rebalancing policy using a linear program.The policy is used as the basis for subsequent control design.
  • A closed-loop, real-time rebalancing policy based on the linear-program solution is applied to a New York City case study.
  • The paper identifies policies balancing less-congested routing with limits on rebalancing vehicles under excessive congestion as an open research direction.Other proposed extensions include additional performance metrics, intermodal coordination, more case studies, and real-vehicle demonstrations.

SUPPLEMENTAL MATERIAL

The supplemental material proves lemmas about the network’s separated SS and IS node structure, transition probabilities, steady-state distribution, and relative utilizations.

  • The proof of Lemma IV.1 separates equation (1) into SS and IS nodes.
  • For SS nodes, the proof uses their exclusive connection through IS nodes and the routing relation for an IS node’s child.
  • For IS nodes, the proof uses their SS-node connections and the probability that a single SS node feeds each IS node.
  • Lemma IV.2 establishes positivity of the steady-state vector π using irreducibility of the transition chain and the Perron-Frobenius theorem.The proof states that π_i > 0 for all i ∈ S.
  • The supplemental proof then invokes Lemma IV.1 under pii = 0 and αii = 0 to address the second part of Lemma IV.2.
  • Lemma IV.1’s intermediate equalities are derived from equations (8), (9), (3), (6), and (7), completing the proof.
Loading 1404.4391v1…