Seite - (000420) - in Autonomes Fahren - Technische, rechtliche und gesellschaftliche Aspekte
Bild der Seite - (000420) -
Text der Seite - (000420) -
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.
Autonomes Fahren
Technische, rechtliche und gesellschaftliche Aspekte
Gefördert durch die Daimler und Benz Stiftung