Page - (000420) - in Autonomes Fahren - Technische, rechtliche und gesellschaftliche Aspekte

40519.2 Modeling and controlling AMoD systems 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 [19], 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 [13], transportation requests are modeled by assuming that customers arrive at a set of stations located within a given environment1, similar to the hypercube model [19]. The arrival process at each station is Poisson with a rate Ȝi , where i  {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 [19].) 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 sta- tions with single-server queues and the roads with infinite-server queues. (Jackson net- works 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 identifi- cation, an AMoD system becomes a closed Jackson network with respect to the vehicles, which is amenable to analytical treatment [13] (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 [13]. Specifically, one assumes that each station i generates “virtual customers” according to a Poisson process with rate ȥi , and routes these virtual customers to station j with prob- ability Įi j . The problem of controlling an AMoD system becomes one of optimizing over the rates {ȥi} and probabilities {Įi j} which, by exploiting the theory of Jackson networks, 1 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.