[PDF] A BCMP Network Approach to Modeling and Controlling

View - Download A BCMP Network Approach to Modeling and Controlling

Previous PDF

Next PDF

A BCMP Network Approach

to Modeling and Controlling

Autonomous Mobility-on-Demand Systems

Ramon Iglesias

1, Federico Rossi1, Rick Zhang1, and Marco Pavone1

Stanford University, Stanford CA 94305, USA,

frdit, frossi2, rickz, pavoneg@stanford.edu Abstract.In this paper we present a queuing network approach to the problem of routing and rebalancing a eet of self-driving vehicles pro- viding on-demand mobility within acapacitatedroad network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We rst cast an AMoD system into a closed, multi-class BCMP queuing network model. Second, we present analysis tools that allow the char- acterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities, and rst and second order moments of vehi- cle throughput. Third, we propose a scalable method for the synthesis of routing policies, with performance guarantees in the limit of large eet sizes. Finally, we validate the theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which subsumes earlier Jackson and network ow models, provides a quite large set of modeling options (e.g., the inclusion of road capacities and general travel time distribu- tions), and allows the analysis of second and higher-order moments for the performance metrics. Keywords:queuing networks, autonomous vehicles, self-driving cars, transportation. 1

In troduction

Personal mobility in the form of privately owned automobiles contributes to in- creasing levels of trac congestion, pollution, and under-utilization of vehicles (on average 5% in the US [17]) { clearly unsustainable trends for the future. The pressing need to reverse these trends has spurred the creation of cost compet- itive, on-demand personal mobility solutions such as car-sharing (e.g. Car2Go, ZipCar) and ride-sharing (e.g. Uber, Lyft). However, without proper eet man- agement, car-sharing and, to some extent, ride-sharing systems lead to vehicle imbalances: vehicles aggregate in some areas while becoming depleted in others, due to the asymmetry between trip origins and destinations [24]. This issue has been addressed in a variety of ways in the literature. For example, in the context of bike-sharing, [5] proposes rearranging the stock of bicycles between stations using trucks. The works in [18], [4], and [1] investigate using paid drivers to move vehicles between car-sharing stations where cars are parked, while [2] studies the merits of dynamic pricing for incentivizing drivers to move to underserved areas. Self-driving vehicles oer the distinctive advantage of being able to rebalance themselves, in addition to the convenience, cost savings, and possibly safety of not requiring a driver. Indeed, it has been shown that one-way vehicle shar- ing systems with self-driving vehicles (referred to as autonomous mobility-on- demand systems, or AMoD) have the potential to signicantly reduce passenger cost-per-mile-traveled, while keeping the advantages and convenience of personal mobility [22]. Accordingly, a number of works have recently investigated the po- tential of AMoD systems, with a specic focus on the synthesis and analysis of coordination algorithms. Within this context, the goal of this paper is to pro- vide a principled framework for the analysis and synthesis of routing policies for

AMoD systems.

Literature Review: Previous work on AMoD systems can be categorized into two main classes: heuristic methods and analytical methods. Heuristic routing strategies are extensively investigated in [7,8,16] by leveraging a trac sim- ulator and, in [25], by leveraging a model predictive control framework. Ana- lytical models of AMoD systems are proposed in [20], [24], and [26], by using uidic, Jackson queuing network, and capacitated ow frameworks, respectively. Analytical methods have the advantage of providing structural insights (e.g., [26]), and provide guidelines for the synthesis of control policies. The problem of controlling AMoD systems is similar to the System Optimal Dynamic Trac Assignment (SO-DTA) problem (see, e.g., [6,19]) where the objective is to nd optimal routes for all vehicles within congested or capacitated networks such that the total cost is minimized. The main dierences between the AMoD con- trol problem and the SO-DTA problem is that SO-DTA only optimizes customer routes, andnotrebalancing routes. This paper aims at devising a general, unifying analytical framework for anal- ysis and control of AMoD systems, which subsumes many of the analytical mod- els recently presented in the literature, chie y, [20], [24], and [26]. Specically, this paper extends our earlier Jackson network approach in [24] by adopting a BCMP queuing-theoretical framework [3,15]. BCMP networks signicantly ex- tend Jackson networks by allowing almost arbitrary customer routing and service time distributions, while still admitting a convenient product-form distribution solution for the equilibrium distribution [15]. Such generality allows one to take into account several real-world constraints, in particular road capacities (that is, congestion). Indeed, the impact of AMoD systems on congestion has been a hot topic of debate. For example, [16] notes that empty-traveling rebalancing vehicles may increase congestion and total in-vehicle travel time for customers, but [26] shows that, with congestion-aware routing and rebalancing, the increase in congestion can be avoided. The proposed BCMP model recovers the results in [26], with the additional benets of taking into account the stochasticity of transportation networks and providing estimates for performance metrics. Statement of Contributions: The contribution of this paper is fourfold. First, we show how an AMoD system can be cast within the framework of closed, multi- class BCMP queuing networks. The framework captures stochastic passenger arrivals, vehicle routing on a road network, and congestion eects. Second, we present analysis tools that allow the characterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities and second- order moments of vehicle throughput. Third, we propose a scalable method for the synthesis of routing policies: namely, we show that, for large eet sizes, the stochastic optimal routing strategy can be found by solving a linear program. Finally, we validate the theoretical results on a case study of New York City. Organization: The rest of the paper is organized as follows. In Section 2, we cover the basic properties of BCMP networks and, in Section 3, we describe the AMoD model, cast it into a BCMP network, and formally present the routing and rebalancing problem. Section 4 presents the mathematical foundations and assumptions required to reach our proposed solution. We validate our approach in Section 5 using a model of Manhattan. Finally, in Section 6, we state our concluding remarks and discuss potential avenues for future research. 2

Bac kgroundMaterial

In this section we review some basic denitions and properties of BCMP net- works, on which we will rely extensively later in the paper. 2.1

Closed, Multi-Class BCMP Net works

LetZbe a network consisting ofNindependent queues (or nodes). A set of agents move within the network according to a stochastic process, i.e. after receiving service at queueithey proceed to queuejwith a given probability. No agent enters or leaves the network from the outside, so the number of agents is xed and equal tom. Such a network is also referred to as aclosedqueuing network. Agents belong to one ofK2N>0classes, and they can switch between classes upon leaving a node. Letxi;kdenote the number of agents of classk2 f1;:::;Kgat nodei2 f1;:::;Ng. The state of nodei, denoted byxi, is given byxi= (xi;1;:::;xi;K)2 N

K. The state space of the network is [10]:

m:=f(x1;:::;xN) :xi2NK;NX i=1kxik1=mg; wherek k1denotes the standard 1-norm (i.e.,kxk1=P ijxij). The relative frequency of visits (also known as relative throughput) to nodeiby agents of classk, denoted asi;k, is given by the trac equations [10]: i;k=KX k 0=1N X j=1 j;k0pj;k0;i;k;for alli2 f1;:::;Ng;(1) wherepj;k0;i;kis the probability that upon leaving nodej, an agent of classk0 goes to nodeiand becomes an agent of classk. Equation (1) does not have a unique solution (a typical feature of closed networks), and=fi;kgi;konly determines frequencies up to a constant factor (hence the name \relative" fre- quency). It is customary to express frequencies in terms of a chosen reference node, e.g., so that1;1= 1. Queues are allowed to be one of four types: First Come First Serve (FCFS), Processor Sharing, Innite Server, and Last Arrived, First Served. FCFS nodes have exponentially distributed service times, while the other three queue types may follow any Cox distribution [10]. Such a queuing network model is referred to as a closed, multi-class BCMP queuing network [10]. LetNrepresent the set of nodes in the network andNits cardinality. For the remainder of the paper, we will restrict networks to have only two types of nodes: FCFS queues with a single server (for short, SS queues), forming a set S N, and innite server queues (for short, IS queues), forming a setI N. Furthermore, we consider class-independent and load-independent nodes, whereby at each nodei2 f1;:::;Ngthe service rate is given by: i(xi) =ci(xi)oi; wherexi:=kxik1is the number of agents at nodei,oiis the (class-independent) base service rate, andci(xi) is the (load-independent)capacityfunction c i(xi) =x iifxicoi; c

0iifxi> coi;

which depends on the number of serverscoiat the queue. In the case considered in this paper,coi= 1 for alli2 Sandcoi=1for alli2 I. Under the assumption of class-independent service rates, the multi-class net- workZcan be \compressed" into a single-class networkZwith state-space m:=f(x1;:::;xN) :xi2N;PN i=1xi=mg[14]. Performance metrics for the original, multi-class networkZcan be found by rst analyzing the compressed networkZ, and then applying suitable scalings for each class. Specically, let i=PK k=1i;kand i=PK k=1 i;k oi, be the total relative throughput and rela- tive utilization at a nodei, respectively. Then, the stationary distribution of the compressed, single-class networkZis given by

P(x1;:::;xN) =1G(m)N

Y i=1 xiiQ xi a=1ci(a);whereG(m) =X mN Y i=1 xiiQ xi a=1ci(a) is a normalizing constant. Remarkably, the stationary distribution has a product form, a key feature of BCMP networks. Three performance metrics that are of interest at each node are throughput, expected queue length, and availability. First, the throughput at a node (i.e., the number of agents processed by a node per unit of time) is given by i(m) =iG(m1)G(m):(2) Second, letPi(xi;m) be the probability of ndingxiagents at nodei; then the expected queue length at nodeiis given byLi(m) =Pm x i=1xiPi(xi;m): In the case of IS nodes (i.e., nodes inI), the expected queue length can be more easily derived via Little's Law as [11] L i(m) =i(m)=oifor alli2 I:(3) Finally, the availability of single-server, FCFS nodes (i.e., nodes inS) is dened as the probability that the node has at least 1 agent, and is given by [11] A i(m) = iG(m1)G(m)for alli2 S: The throughputs and the expected queue lengths for the original, multi-class networkZcan be found via scaling [14], specically,i;k(m) = (i;k=i)i(m) andLi;k(m) = (i;k=i)Li(m): It is worth noting that evaluating the three performance metrics above re- quires computation of the normalization constantG(m), which is computation- ally expensive. However, several techniques are available to avoid the direct com- putation ofG(m). In particular, in this paper we use the Mean Value Analysis method, which, remarkably, can be also used to compute higher moments (e.g., variance) [23]. Details are provided in the Appendix. 2.2

Asymptotic B ehaviorof Closed BCM PNet works

In this section we describe the asymptotic behavior of closed BCMP networks as the number of agentsmgoes to innity. The results described in this section are taken from [11], and are detailed for a single-class network; however, as stated in the previous section, results found for a single-class network can easily be ported to the multi-class equivalent in the case of class-independent service rates.

Leti:=

i=coibe the utilization factor of nodei2 N, wherecoiis the number of servers at nodei. Assume that the relative throughputsfigiare normalized so that max i2Si= 1; furthermore, assume that nodes are ordered by their utilization factors so that 1 =12:::N, and dene the set of bottleneck nodes asB:=fi2 S:i= 1g. It can be shown [11, p. 14] that, as the number of agentsmin the system approaches innity, the availability at all bottleneck nodes converges to 1 while the availability at non-bottleneck nodes is strictly less than 1, that is lim m!1Ai(m)( = 18i2 B: <18i =2 B:(4) Additionally, the queue lengths at the non-bottleneck nodes have a limiting distribution given by lim m!1Pi(xi;m) =((1i)xiii2S;i =2 B; e i xiix i!i2I:(5) Together, (4) and (5) have strong implications for the operation of queuing net- works with a large number of agents, and in particular for the operation of AMoD systems. Intuitively, (4) shows that as we increase the number of agents in the network, they will be increasingly queued at bottleneck nodes, driving availabil- ity in those queues to one. Alternatively, non-bottleneck nodes will converge to an availability strictly less than one, implying that there is always a non-zero probability of having an empty queue. In other words, agents will aggregate at the bottlenecks and become depleted elsewhere. Additionally, (5) shows that, as the number of agents goes to innity, non-bottleneck nodes tend to behave like queues in an equivalent open BCMP network with the bottleneck nodes removed, i.e., individual performance metrics can be calculated in isolation. 3

Mo delDescription and Problem F ormulation

In this section, we introduce a BCMP network model for AMoD systems, and formalize the problem of routing and rebalancing such systems under stochastic conditions. Casting an AMoD system as a queuing network allows us to char- acterize and compute key performance metrics including the distribution of the number of vehicles on each road link (a key metric to characterize trac con- gestion) and the probability of servicing a passenger request. To emphasize the relationship with the theory presented in the previous section, we reuse the same notation whenever concepts are equivalent. 3.1

Autonomous Mobilit y-on-DemandMo del

Consider a set of stations

1Sdistributed within an urban area connected by a

network of individual road linksI, andmautonomous vehicles providing one- way transportation between these stations for incoming customers. Customers arrive to a stations2 Swith a target destinationt2 Saccording to a time- invariant Poisson process with rate2R>0. The arrival process for all origin- destination pairs is summarized by the set of tuplesQ=f(s(q);t(q);(q))gq.quotesdbs_dbs26.pdfusesText_32

[PDF] bcmr 2016 participation 955 dont bcmr 2016 - Anciens Et Réunions

[PDF] BCMRD Release Notes

[PDF] BCN, prix culture, communiqué presse jd

[PDF] Bcom POSTE These CONDOR-SET

[PDF] BCP - Bourse en ligne CDM

[PDF] BCP-AwArd GOLDPREISTRäGER DES BEST OF CORPORATE

[PDF] BCPST - Lycée Saint - France

[PDF] bcpst - SCEI - Anciens Et Réunions

[PDF] BCPST 1.2 Lycée Pierre de Fermat Année 2010

[PDF] BCPST 2 - Anciens Et Réunions

[PDF] BCPST Manipulation d`images 2016-2017 Ce TP est en tr`es grande

[PDF] BCQS – Formation Qualité « La pratique de l`audit interne »

[PDF] BCR FISH DNA Probe, Split Signal Code Y5403

[PDF] bcr-1 wireless controller user manual bedienungsanleitung

[PDF] BCR-ABL - Santé Et Remise En Forme