 19.2.2 Approaches for controlling AMoD systems

This section presents two recent, yet promising approaches for the control of spatial queueing systems as models for AMoD systems, namely the lumped approach and the distributed approach. Both approaches employ a number of relaxations and approximations to overcome the difficulties in directly applying results from queueing (network) theory to spatial queueing models. A remarkable feature of these approaches is that they yield formal performance bounds for the control policies (i.e., factor of sub-optimality) and scaling laws for the quality of service in terms of model data, which can provide useful guidelines for selecting system parameters (e.g., number of vehicles). These approaches take their origin from seminal works on hypercube models for spatial queues , on the Dynamic Traveling Repairman problem [20, 21, 22, 23], and on the Dynamic Traffic

Assignment problem [24, 25].

Alternative approaches could be developed by leveraging worst-case (as opposed to stochastic) techniques for dynamic vehicle routing, e.g., competitive (online) analysis [26, 27, 28]. This is an interesting direction for future research.

19.2.2.1 Lumped approach

Within the lumped approach , transportation requests are modeled by assuming that customers arrive at a set of stations located within a given environment similar to the hypercube model . The arrival process at each station is Poisson with a rate di , where i E {1, … , N} and N denotes the number of stations. (Reasonable deviations from the assumption of Poisson arrivals have been found not to substantially alter the predictive accuracy of these models .) Upon arrival, a customer at station i selects a destination j according to a probability mass function {pi j} (Figure 19.3, left). If vehicles are parked at station i, the customer takes a vehicle and is driven to the intended destination, with a travel time modeled as a random variable Ti j. However, if the station is empty of vehicles, the customer immediately leaves the system. Under the assumptions of Poisson arrivals and exponentially-distributed travel times, an AMoD system is then translated into a Jackson network model through an abstraction procedure [13, 29], whereby one identifies the stations with single-server queues and the roads with infinite-server queues. (Jackson networks are a class of queueing networks where the equilibrium distribution is particularly simple to compute as the network has a product-form solution [30, 31]). With this identification, an AMoD system becomes a closed Jackson network with respect to the vehicles, which is amenable to analytical treatment  (Figure 19.3, left).

To control the network, for example, to (autonomously) rebalance the vehicles to ensure even vehicle availability, the strategy is to add virtual customer streams . Specifically, one assumes that each station i generates “virtual customers” according to a Poisson process with rate lf!i , and routes these virtual customers to station j with probability ai j . The problem of controlling an AMoD system becomes one of optimizing over the rates {lf!i} and probabilities {ai j} which, by exploiting the theory of Jackson networks, Fig. 19.3 Left figure: In the lumped model, an AMoD system is modeled as a Jackson network, where stations are identified with single-server queues and roads are identified with infinite-server queues. (Customers are denoted with yellow dots and servicing vehicles are represented by small car icons.) Some vehicles travel without passengers to rebalance the fleet. Right figure: In a distributed model of an AMoD system, a stochastic process with rate d generates origin-destination pairs, distributed over a continuous domain Q.

can be cast as a linear program (hence, this approach extends well to large transportation networks). This method encourages coordination but does not enforce it, which is the key to maintaining tractability of the model . The rates {lf!i} and probabilities {ai j} are then used as feedforward reference signals in a receding horizon control scheme to control in real-time an entire AMoD system , as done for case studies of New York City and Singapore presented in Section 19.3.

19.2.2.2 Distributed approach

The key idea behind the distributed approach [14, 15, 16, 17] is that the number of stations represents a continuum (i.e., N --oo), similar to the Dynamic Traveling Repairman problem [20, 21, 22, 23]. In other words, customers arrive at any point in a given bounded environment [15, 16], or at any point along the segments of a road map . In the simplest scenario, a dynamical process generates spatially-localized origin-destination pairs (representing the transportation requests) in a geographical region Q c R2 . The process that generates origin-destination pairs is modeled as a spatio-temporal Poisson process, namely, (i) the time between consecutive generation instants has an exponential distribution with intensity d , and (ii) origins and destinations are random variables with probability density functions, respectively, rpO and rpD , supported over Q, see Figure 19.3 (right). The objective is to design a routing policy that minimizes the average steady-state time delay between the generation of an origin-destination pair and the time the trip is completed. By removing the constraint that customers' origin-destination pairs are localized at a finite set of points in an environment, one transforms the problem of controlling N different queues into one of controlling a single "spatially-averaged" queue This considerably simplifies analysis and control, and allows one to derive analytical expressions for important design parame-ters. For example, one can show that a necessary and sufficient condition for stability is that the load factor is strictly less than one, where m is the number of servicing vehicles, v is the average speed of the vehicles, ErpO rpD [Y X ] is the expected distance between origin and destination locations, and EMD(rpO , rpD) is the earth mover's distance between densities rpO and rpD , representing the minimum distance, on average, a vehicle must travel to realign itself with an asymmetrical travel demand . Intuitively, if distributions rpO and rpD are imagined as describing two piles each consisting of a unit of “dirt” (i.e., earth), then EMD(rpO , rpD) can be thought of as the minimum work (dirt × distance) required to reshape rpO into rpD (see  for a formal definition) One can use the above formula to estimate the required fleet size to ensure stability an example application to a case study of Singapore is presented in Section 19.3. With this approach, it is also possible to obtain formal performance bounds (i.e., factors of sub-optimality) for receding horizon control policies, in the asymptotic regimes p --](heavy-load, system saturated) and p --0+ (light-load, system empty of customers) [33, 17].

19.2.3 Comparison

The lumped approach and the distributed approach are complementary in a number of ways. Both models provide formal guarantees for stability and performance. The former is more realistic (a road topology can be readily mapped into this model) and provides a natural pathway to synthesize control policies. The latter provides significant mathematical simplifications (as one only needs to study a spatially-averaged queue) and enables the determination of analytical scaling laws that can be used to select system parameters (e.g., fleet sizing). In the next section we exploit the interplay between these two approaches to characterize AMoD systems for case studies of New York City and Singapore.

Both approaches appear to be promising tools to systematically tackle the problem of system-wide control of AMoD systems. Several research questions, however, still need to be addressed to fulfill this objective, particularly with respect to inclusion of congestion effects (in Section 19.2.2.1, roads are modeled as infinite server queues, so the travel time for each vehicle is independent of all other vehicles), predictive accuracy, and control synthesis for complex scenarios, as detailed in Section 19.4.

•  Alternatively, to model an AMoD system where the vehicles directly pick up the customers, one would decompose a city into N disjoint regions Q1, Q2, … , QN . Such regions would replace the notion of stations. When a customer arrives in region Qi , destined for Qj , a free vehicle in Qi is sent to pick up and drop off the customer before parking at the median of Qj . The two models are then formally identical and follow the same mathematical treatment