Seminar reports related to Electrical Engineering and Computer Science

S15-MarcoPavone-AutonomousMobility-on-DemandSystemsforFutureUrbanMobility.pdf

Home >Engineering homework help >Electrical Engineering homework help >Seminar reports related to Electrical Engineering and Computer Science

Autonomous Mobility-on-Demand Systems for Future Urban Mobility

Marco Pavone Autonomous Systems Laboratory Department of Aeronautics and Astronautics Stanford University

Seminar@ University of Southern California April 18, 2019

Charging demand Energy storage

Electricity prices Energy provision

Power network

Transportation network

Research portfolio

Trajectory optimization

Interplay with perception Safe and robust decision making

and learning

Safe interactions with humans

System-level coordina>onTrustworthy autonomy

Full decision-making and control stack [Leung, Schmerling, Chen, Talbot, Gerdes, Pavone, ISER ’18]

Potential benefits of autonomous vehicles

Safety (economic cost)1 $242B

Safety (societal harm)1 $594B

Productivity4 $1,315B

Congestion2 $160B

Vehicle sharing4 $402B

Health3 $15B

1 [Blincoe et al., NHTSA Report, 2015] 2 [Schrank et al., Texas A&M Transportation Institute, 2015] 3 [Levy et al., Environmental Health, 2010] 4 [Spieser, et al., Road Vehicle Automation, 2014]

A new paradigm for personal urban mobility Car SharingVehicle Autonomy

+" Autonomous Mobility-On-Demand (AMoD)

How to control a fleet of autonomous vehicles? Problem falls under the general class of networked, heterogeneous, stochastic decision problems with uncertain information: • Problem data / model: travel demand, road network • Control inputs: vehicle routing, passenger loading/unloading • Outputs: customer waiting times, customer queue lengths, externalities, etc.

SystemController

Static version NP-hard

Closed system: cascade feedback effects

Dynamics add queueing phenomena

Closed-loop control policies aimed at optimal throughput

Research program at a glance

A. Recent Research

here comes the literature, bla bla bla - somebody has to do it

B. Aims and Scope

As can be seen, no study on centrally operated intermodal passenger transportation exists so far, especially with respect to AMoD systems. Against this background, we provide the first study that analyzes the benefit of such an inter- modal transportation system from a mesoscopic point of view. We develop an optimization approach that finds the optimal control policy for this system under steady state conditions. Herein, we incorporate different objectives that consider either the total transportation time, or the generated emissions, or both by incorporating a convexly combined objective as well as a generalized cost function. We provide a case study based on real-world data from Manhattan. Based on the results for this study, we derive managerial insights for both fleet operators and municipalities.

The contribution of our study is fourfold: First, we pro- vide the first optimization framework for an intermodal autonomous mobility-on-demand (I-AMoD) system, which handles real-world data sets in short computational times and delivers global optimality. Second, we provide a sound case that is based on real-world data for Manhattan, an urban area in which the need for a sustainable transportation concept is more than urgent. Third, we present results that are not limited to a single objective but include different perspectives: i) the social welfare in monetary terms of value of time and operational costs, and ii) the social welfare in both monetary and environmental terms. Fourth, we derive

[MaS]:Update managerial insights that, besides providing dedicated intu- itions for single stakeholders, analyse the social optimum that can be reached.

The remainder of this paper is structured as follows: Section II presents the methodological background for our studies. Section III derives a pricing scheme to steer self- interested agents to the social optimum. Then, Section IV details our case study and discusses our experiments and results. Finally, Section V concludes the paper with a short summary and an outlook on future research.

II. METHODOLOGY This section presents the methodological background for

our studies. We aim at analyzing the benefit of AMoD systems in an intermodal setting. Herein, we use a fluidic optimization approach to determine the optimal equilibrium for such a system. Within this approach, we consider

• the assignment of transportation requests to transport flows,

• different modes of transportation, • capacity limits which are specific to the transportation

mode, such as congestion and seats availability per unit time on public transportation lines,

• and rebalancing flows for the AMoD system. Section II-A describes such an optimization approach, as- suming a globally controlled mobility system. Understanding

the unlikelihood of an intermodal system being globally controlled, we derive a (Pigovian) pricing scheme that would influence selfish actors to behave according to the social optimum in Section III-B.

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the (in)complete layered graph

[FR]:? G = (V ,A ) shown in Fig. 1 with a set of vertices V and a set of arcs A ✓ V ⇥ V , comprising a road network layer GR = (VR,AR), a subway layer GS = (VS,AS), and a pedestrian layer GP = (VP,AP). The road layer represents intersections i 2 VR and road links (i, j) 2 AR. The subway layer comprises subway stops i 2 VS and the respective lines (i, j) 2 AS, while the pedestrian layer represents walkable streets (i, j) 2 AP in between intersections i 2 VP. Finally, arcs out of set AC ✓ VR ⇥VP [VS ⇥VP connect the pedestrian layer to the road and to the subway layer, respectively, such that V = VP [ VR [ VS, A = AP [ AR [ AS [ AC and VR \ VS = /0 holds.

We use the following notation to describe characteristics of G and define our optimization problem: Each arc has a capacity ci j which denotes either the capacity of a certain transportation mean (AR,AS) or remains as ci j = •, 8(i, j) 2 AC,AP for transportation means without capacity limits, i.e., walking. The travel time ti j denotes the average time needed to traverse an arc (i, j). Times on arcs (i, j) 2 AC represent switching times between or to reach a certain mean of transportation. Let R be the set of all travel requests. A request rm = (om,dm,am) 2 R is a triple composed by an origin node om, a destination node dm and a request rate am that denotes the amount of customers per unit time. Since we identify different transportation modes by different arc sets, we use only a single type of flow variables fm (i, j) that denotes the flow on an arc (i, j) for a certain travel request m 2 M = [1,M] ✓ N. Furthermore, f0 (i, j) denotes the rebalancing flow of empty AMoD vehicles on the road arcs (i, j) 2 AR.

With this notation, the I-AMoD optimization problem holds as follows: For a given set of transportation demands (om,dm,am) 2 R, we want to find the optimal customer and rebalancing flows, fm (i, j),(i, j) 2 A and f0 (i, j), (i, j) 2 AR, such that the objective costs (1a) are minimized. Herein, customer flow conservation constraints (1b), conservation of vehicles (1c), capacity constraints on road (1d), and public transportation links (1e) must hold.

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the digraph G = (V ,A ) shown in Fig. 1, which has a set of vertices V and a set of arcs A ✓ V ⇥ V . The graph contains a road network layer GR = (VR,AR), a subway layer GP = (VP,AP), and[MaS]:public

trans- porta- tion?

a pedestrian layer GW = (VW,AW). Herein, the road layer represents intersections i 2 VR and road links (i, j) 2 AR. The subway layer comprises subway stops i 2 VP connected by arcs (i, j) 2 AP, while the pedestrian layer represents walkable streets (i, j) 2 AW between intersections i 2 VW. Finally, arcs out of set AC ✓ VR ⇥ VW [ VP ⇥ VW connect the pedestrian layer to the road and to the subway layer, respectively. These arcs model the customer’s ability to switch transportation modes, such that V = VW [ VR [ VP, A = AW [ AR [ AP [ AC and VR \ VP = /0 holds.

To consider congestion we use a simplified threshold model: Each arc (i, j) has a capacity ci j which denotes the maximum flow of passengers or vehicles that the arc can accommodate without encountering traffic congestion ((i, j) 2 AR) or overcrowding ((i, j) 2 AP). The capacity of walking arcs remains as ci j = •, 8(i, j) 2 AC,AW. Travers- ing an arc (i, j) takes on average ti j time units. Note herein, that ti j8(i, j) 2 AC denotes the time necessary to switch between two means of transportation. Given the threshold modeling approach, we assume ti j to be constant if an arc’s capacity constraint holds.

Let R be the set of all travel requests. A request rm = (om,dm,am) 2 R is a triple of an origin node om 2 VW, a destination node dm 2 VW, and a request rate am that denotes the amount of customers per unit time for each request. Note that om and dm lie on the pedestrian digraph. Accounting for different transportation modes by separate arc sets, fm (i, j) denotes the flow on arc (i, j) 2 A for a certain travel request m 2 M = [1,M] ✓ N. To account for rebalancing flows between a customer’s destination and the next customer’s origin, f0 (i, j) denotes the flow of empty vehicles on road arcs (i, j) 2 AR.

Given this notation, the I-AMoD optimization problem holds as follows:

min fm(i, j), f0(i, j)

C ( fm (i, j), f0 (i, j)) (1a)

s.t.

Â i:(i, j)2A

fm(i, j)+1 j=om · am = Â k:( j,k)2A

fm( j,k)+1 j=dm · am

8m 2 M , j 2 V (1b)

Â i:(i, j)2AR

f0 (i, j)+ Â

m2M fm(i, j)

! =

Â k:( j,k)2AR

( f0 ( j,k)+ Â

m2M fm( j,k)

! 8 j 2 VR (1c)

f0 (i, j)+ Â m2M

fm (i, j)  cRi j 8(i, j) 2 AR (1d)

Â m2M

fm (i, j)  cPi j 8(i, j) 2 AP. (1e)

For a given set of transportation demands (om,dm,am) 2 R, we minimize the objective cost C with the customer flows

fm (i, j) and rebalancing flows f0 (i, j) in Eq. (1a). The constraint (1b) guarantees flow conservation for customers, whereby 1 j=x is a boolean indicator function. We secure further flow conservation for vehicles in Eq. (1c), and enforce capacity limits for roads in Eq. (1d) and public transportation links in Eq. (1e).

B. I-AMoD Objective

The generalized cost function (1a) can be used to address different objectives. In our studies, we optimize the social welfare by minimizing overall costs. Specifically, we define commuting costs that depend on the customers’ value of time VT and on operational costs for the AMoD fleet and the subway. Herein, costs for the AMoD fleet comprise mileage dependent ownership costs VD,R to account for maintenance and depreciation as well as energy costs VE. For the subway system, VD,P comprises all operational costs per passenger kilometer. This way, we define the social cost as

CM ( fm (i, j), f0 (i, j)) = VT · Â m2M ,(i, j)2A

ti j · fm (i, j)

+Â (i, j)2AR

(VD,R · di j +VE · eR,i j) ·

f0 (i, j)+ Â m2M

fm (i, j)

+VD,P · Â (i, j)2AP

di j · Â m2M

fm (i, j).

(2)

Given the mesoscopic nature of our study, we estimate the energy consumption of a single vehicle eR,i j > 0, (i, j) 2 AR assuming that road arcs are traversed at the constant speed vi j =

di j

ti j . Considering electric vehicles with full recuperation

capabilities and an overall tank-to-wheel efficiency hEV, the energy consumption for a road arc is

eR,i j = ⇣ra

2 · Af · cd · v2i j + cr · mv · g

⌘ ·

di j

hEV 8(i, j) 2 AR. (3)

The first term in (3) represents the aerodynamic drag com- posed by the air density ra, the frontal area Af, and the drag coefficient cd, and the rolling friction computed combining its coefficient cr with the mass of the vehicle mv and the gravity g [22].

C. Discussion

A few comments are in order. First, we consider time- invariant travel requests. This assumption is valid if requests change slowly compared to the average travel time of an individual trip, as is often the case in densely populated urban environments [23]. Second, we adopt a threshold model for congestion. The model is consistent with classical traffic flow theory [24] and it is adequate for the goal of efficiently optimizing customer and vehicle routes. Congestion models offering higher accuracy can be used for the analysis of specific control policies. Third, the model in this paper represents customer and vehicle routes as fractional flows and does not capture the stochastic nature of the customer arrival process. These approximations are in line with the

Research objectives: 1. Modeling: mathematical

models for tractable analyses

2. Control: real-time routing of autonomous vehicles at a city-wide scale

3. Applications: case studies and technology infusion

Objectives

1. Mesoscopic modeling of AMoD

2. On the interaction between AMoD and other infrastructures

Flow optimization model (basic) [Rossi, Zhang, Hindy, and Pavone, Auro ‘18]

• Trip requests represented by set of origins/destinations/rates:

• Road : network represented by a graph with road capacities:

Flow optimization model (basic) [Rossi, Zhang, Hindy, and Pavone, Auro ‘18]

Vehicles’ motion represented as flows on edges:

• Customer flows

Flow optimization model (basic) [Rossi, Zhang, Hindy, and Pavone, Auro ‘18]

Vehicles’ motion represented as flows on edges:

• Customer flows

• Rebalancing flows

Control strategies for flow model [Rossi, Zhang, Hindy, and Pavone, Auro ‘18]

Congestion-free Routing and Rebalancing Problem (CRRP): Given an autonomous MOD system described via a flow model, solve

Fractional multi-commodity flow problem

Does AMoD increase congestion? [Rossi, Zhang, Hindy, and Pavone, Auro ‘18]

Would rebalancing vehicles contribute to an increase in congestion? [Templeton, ’15], [Barnard, ’16], [Levin, Li, Boyles, Kockelman, TRB ‘16]

Capacity-symmetric (C-S) networks: For all network cuts

Capacity-symmetric network Feasible customer flows

Feasible rebalancing flows

Feasibility of rebalancing

1. Theory: In C-S networks rebalancing does not increase congestion

2. Practice: Customer flows and rebalancing flows are decoupled and can be computed separately

Network flow model - assumptions

• Demand is time-invariant • Generalized models with time expanded graphs

[Rossi et al., TCNS ‘19, Tsao et al., ICRA ’19, Zgraggen et al., ITSC ‘19]

• Congestion as a threshold • Extensions to BPR model, Davidson’s model, etc.

[Salazar et al., ECC ‘19; Solovey et al., RSS ‘19]

• Model is deterministic • Connection to queueing-theoretical models [Zhang

and Pavone, IJRR ‘16; Iglesias et al., IJRR ‘18]

0 5 10 15 20 Time of the day

A vg

. n um

be r o

f p ic

ku ps

# 104

Average trip duration

Number of vehicles

S pe

BPR model Threshold model

Network Flow Model - Assumptions

• Congestion as a threshold

0 5 10 15 20 Time of the day

A vg

. n um

be r o

f p ic

ku ps

# 104

Average trip duration

Number of vehicles

S pe

BPR model Threshold model

Average trip duration

0 5 10 15 20 Time of the day

A vg

. n um

be r o

f p ic

ku ps

# 104

Average trip duration

Number of vehicles

S pe

BPR model Threshold model

• Demand is time-invariant

[Salazar, Rossi, Schiffer, Onder, Pavone, ITSC18]

2/28/2019 2-Dice-Icon.svg

file:///Users/pavone/Downloads/2-Dice-Icon.svg 1/1

Network flow model - assumptions

• Continuum approximation • Control via sampling [Rossi et al., TCNS ‘19] or

hybrid approximations [Tsao et al., ICRA ‘19]

• Model is large-scale • Special-purpose solver that leverages

reduction to TAP and Frank-Wolfe optimization [Solovey et al., RSS ‘19]

• Model considers one passenger per car • Extension to ride-sharing [Tsao et al., ICRA ‘19]

Queueing-theoretical models [Zhang and Pavone, IJRR ’16; Iglesias, Rossi, Zhang, and Pavone, IJRR ’18]

Jackson model BCMP model

Takeaway: stochastic queueing network model reduces to a (deterministic) network flow model in the limit of large fleet sizes

Evaluation: case study of Singapore [Spieser, Treleaven, Zhang, Frazzoli, Morton, Pavone, RVA ‘14]

• Three complementary data sources: HITS survey, Singapore taxi data, Singapore road network • 779,890 passenger vehicles operating in Singapore • 100 stations for robotic MoD

Key result: total mobility cost cut in half!

COS COT TMC

Traditional 0.96 0.76 1.72

AMoD 0.66 0.26 0.92

Mobility-related costs (USD/km)

Ride-sharing AMoD [Tsao, Milojevic, Ruch, Salazar, Frazzoli, and Pavone, ICRA ‘19]

Zero Occupants Single Occupant Double Occupants• Features: • Multiple sub-fleets • Time-expanded model • MILP formulation for control

Performance of R-AMoD

R-AMoD MPC achieves more than 40% lower mean waiting times

Real-time control of Ha:Mo system

Rebalancing tasks

TakumiPrior knowledge

Real-time information from Ha:Mo app

Rebalancing tasks

TakumiRebalancing suggestions

Historical information

MUI Back end:

model-based controller

NN-based forecasting

model

Real-time information via TMC API

Forecasted demand

Optimal actions

Real-time control of Ha:Mo system • Deployed vehicle rebalancing algorithms in Ha:Mo system in Dec. 2018

App developed by Prof. Pavone’s group to optimize vehicle

rebalancing and availability

Prof. Pavone’s group spent one week in Toyota city to assess

functionality and performance

Future research will address upgrading Ha:Mo system to

autonomous rebalancing vehicles

Objectives

1. Mesoscopic modeling and control of AMoD

2. On the interaction between AMoD and other infrastructures

Power-in-the-loop AMoD [Rossi, Iglesias, Alizadeh, Pavone, RSS 2018]

Uncoordinated

Uncoordinated charging of AMoD fleets can yield • Overload of local distribution network and local blackouts • Two-fold increase in electricity prices [Hadley and Tsvetkova, ‘09] • Increased emissions due to polluting peaker power plants

Excessive local power load High electricity prices Power network instability

Charging demand Energy storage

Electricity prices Energy provision

Power network

Transportation network

Power-in-the-loop AMoD [Rossi, Iglesias, Alizadeh, Pavone, RSS 2018]

Coordinated

Coordination of charging and discharging with the power network can yield • lower electricity prices • new revenue streams for AMoD operator • increased adoption of renewables

Lower loads Vehicle-to-grid (V2G) power injection

Low electricity prices Payment for vehicle-to-grid

Charging demand Energy storage

Electricity prices Energy provision

Power network

Transportation network

In c re

a s in

g c

h a rg

e l e v e l

Power networkTransportation networkTransportation network

In c re

a s in

g c

h a rg

e l e v e l

Optimizing social welfare [Rossi, Iglesias, Alizadeh, Pavone, RSS 2018]

minimize customer discomfort (travel times) + vehicle wear and tear + cost of power generation

Goal:

Constraints: road congestion, charger parking space, power network stability

Formulation: linear program

Flow optimization model [Rossi, Iglesias, Alizadeh, Pavone, RSS 2018]

minimize fm,�

c,in m ,�

c,t,out m ,NF ,✓,p

˝ ÿ

pv,wqPE tv,w

Mÿ

m“1 fmpv, wq

‚` VD

˝ ÿ

pv,wqPE dvv,vw

Mÿ

m“0 fmpv, wq

‚` Tÿ

t“1

gPG ogptqppg, tq

u:pu,vqPE fmpu, vq ` 1vv“vm1tv“tm�cv,inm “

w:pv,wqPE fmpv, wq ` 1vv“wm�tv,cv,outm ,

@v P V, m P t1, . . . , Mu, Cÿ

c“1 �c,inm “ �m, @m P t1, . . . , Mu,

Tÿ

t“1

Cÿ

c“1 �t,c,outm “ �m, @m P t1, . . . , Mu,

u:pu,vqPE f0pu, vq `

Mÿ

m“1 1vv“wm�

tv,cv,out m ` NI pvq

“ ÿ

w:pv,wqPE f0pv, wq `

Mÿ

m“1 1vv“vm1tv“tm�

cv,in m ` NF pvq, @v P V,

Mÿ

cv“1

˜ Mÿ

m“0 fmpv, wq

¸ § f pvv,vwq , @pvv, vwq P ER, @tv P t1 . . . , T u,

pv,wqPES: vv“vw“s, tv§t†tw

˜ Mÿ

m“0 fmpv, wq

¸ § Ss, @s P S, t P t1, . . . , T u,

pu,vqPEP

✓pu, tq ´ ✓pv, tq xu,v

` 1vPGppv, tq “ 1vPLdvptq ` ÿ

pv,wqPEP

✓pv, tq ´ ✓pw, tq xv,w

@v P B, t P t1, . . . , T u,

´ pb1,b2 § ✓pb1, tq ´ ✓pb2, tq

xb1,b2 § pb1,b2, @pb1, b2q P EP , t P t1, . . . , T u,

p g ptq § ppg, tq § pgptq, @g P G, t P t1, . . . , T u,

´ p´g ptq § ppg, t ` 1q ´ ppg, tq § p`g ptq, @g P G, t P t1, . . . , T ´ 1u, dlptqptq § dlptq, @l P L, t P t1, . . . , T u,

dlptq “ dl,eptq ` JC�c`MP,Rplq ÿ

pv,wqPM `P,Gpl,tq

Mÿ

m“0 fmpv, wq

` JC�c´MP,Rplq ÿ

pv,wqPM ´P,Gpl,tq

Mÿ

m“1 fmpv, wq, @l P L, t P t1, . . . , T u.

subject to

Case study: Dallas-Fort Worth [Rossi, Iglesias, Alizadeh, Pavone, RSS 2018]

Road network 25 nodes 173 road links 30 charge levels

Power network 282 generators 2007 buses 2481 transmission lines

Key takeaways: • No coordination: +$500M/yr electricity bill across TX, blackouts in DFW • P-AMoD: - $64M/yr electricity bill (incl. EV charging!); -44% EV charging bill • Coordination reduces total price of electricity w.r.t. baseline, despite extra demand!

Ongoing work: coupling with distribution

Operation of intermodal AMoD systems [Salazar, Rossi, Schiffer, Onder, and Pavone, ITCS ’18 – Best Student Paper Award]

Optimal Operation of Intermodal AMoD Systems

+ Vehicle Autonomy Car Sharing

Public Transit

+ ? [Salazar, Rossi, Schiffer, Onder, Pavone, ITSC18]

Optimal Operation of Intermodal AMoD Systems

+ Vehicle Autonomy Car Sharing

Public Transit

+ ? [Salazar, Rossi, Schiffer, Onder, Pavone, ITSC18]

Literature review

Congestion Pricing Intermodal TransitAMoD

Queuing-theoretical Models [Zhang et al. 2016, Calafiore et al. 2017, Iglesias et al. 2018]

Simulation-based Models [Levin et al. 2017, Maciejewski et al. 2017, Hörl et al. 2018]

Network Flow Optimization [Pavone et al. 2012, Spieser et al. 2014, Rossi et al. 2018,]

Pigovian Taxes for Congestion [Mayeres et al. 1996]

Pricing for AMoD Vehicles [Chen et al. 2016, Simoni et al. 2018]

Simulation-based Models [Seaborn et al. 2009, Gentile et al. 2016, Maciejewski et al. 2017, Bischoff et al. 2017]

No Intermodal No Joint Optimization No Optimization

Pricing for Multimodal Systems [Hamdouch et al. 2007, Wu et al. 2012, Tirachini et al. 2014]

Optimal Control of Intermodal AMoD Systems

Intermodal AMoD

Road

Public  Transit

Intermodal Autonomous Mobility-on-Demand

A. Recent Research

here comes the literature, bla bla bla - somebody has to do it

B. Aims and Scope

[MaS]:Update managerial insights that, besides providing dedicated intu- itions for single stakeholders, analyse the social optimum that can be reached.

II. METHODOLOGY This section presents the methodological background for

• the assignment of transportation requests to transport flows,

• different modes of transportation, • capacity limits which are specific to the transportation

mode, such as congestion and seats availability per unit time on public transportation lines,

• and rebalancing flows for the AMoD system. Section II-A describes such an optimization approach, as- suming a globally controlled mobility system. Understanding

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the (in)complete layered graph

A. Recent Research

here comes the literature, bla bla bla - somebody has to do it

B. Aims and Scope

[MaS]:Update managerial insights that, besides providing dedicated intu- itions for single stakeholders, analyse the social optimum that can be reached.

II. METHODOLOGY This section presents the methodological background for

• the assignment of transportation requests to transport flows,

• different modes of transportation, • capacity limits which are specific to the transportation

mode, such as congestion and seats availability per unit time on public transportation lines,

• and rebalancing flows for the AMoD system. Section II-A describes such an optimization approach, as- suming a globally controlled mobility system. Understanding

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the (in)complete layered graph

8 [Salazar, Rossi, Schiffer, Onder, Pavone, ITSC18]

Intermodal AMoD

Road

Public  Transit

Walk

Intermodal Autonomous Mobility-on-Demand

A. Recent Research

here comes the literature, bla bla bla - somebody has to do it

B. Aims and Scope

[MaS]:Update managerial insights that, besides providing dedicated intu- itions for single stakeholders, analyse the social optimum that can be reached.

II. METHODOLOGY This section presents the methodological background for

• the assignment of transportation requests to transport flows,

• different modes of transportation, • capacity limits which are specific to the transportation

mode, such as congestion and seats availability per unit time on public transportation lines,

• and rebalancing flows for the AMoD system. Section II-A describes such an optimization approach, as- suming a globally controlled mobility system. Understanding

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the (in)complete layered graph

A. Recent Research

here comes the literature, bla bla bla - somebody has to do it

B. Aims and Scope

[MaS]:Update managerial insights that, besides providing dedicated intu- itions for single stakeholders, analyse the social optimum that can be reached.

II. METHODOLOGY This section presents the methodological background for

• the assignment of transportation requests to transport flows,

• different modes of transportation, • capacity limits which are specific to the transportation

mode, such as congestion and seats availability per unit time on public transportation lines,

• and rebalancing flows for the AMoD system. Section II-A describes such an optimization approach, as- suming a globally controlled mobility system. Understanding

A. Multi Commodity Flow Based Optimization Approach

To represent the transportation system and its different transportation modes, we use the (in)complete layered graph

A. Multi Commodity Flow Based Optimization Approach

trans- porta- tion?

Given this notation, the I-AMoD optimization problem holds as follows:

min fm(i, j), f0(i, j)

C ( fm (i, j), f0 (i, j)) (1a)

s.t.

Â i:(i, j)2A

fm(i, j)+1 j=om · am = Â k:( j,k)2A

fm( j,k)+1 j=dm · am

8m 2 M , j 2 V (1b)

Â i:(i, j)2AR

f0 (i, j)+ Â

m2M fm(i, j)

! =

Â k:( j,k)2AR

( f0 ( j,k)+ Â

m2M fm( j,k)

! 8 j 2 VR (1c)

f0 (i, j)+ Â m2M

fm (i, j)  cRi j 8(i, j) 2 AR (1d)

Â m2M

fm (i, j)  cPi j 8(i, j) 2 AP. (1e)

For a given set of transportation demands (om,dm,am) 2 R, we minimize the objective cost C with the customer flows

B. I-AMoD Objective

CM ( fm (i, j), f0 (i, j)) = VT · Â m2M ,(i, j)2A

ti j · fm (i, j)

+Â (i, j)2AR

(VD,R · di j +VE · eR,i j) ·

f0 (i, j)+ Â m2M

fm (i, j)

+VD,P · Â (i, j)2AP

di j · Â m2M

fm (i, j).

(2)

Given the mesoscopic nature of our study, we estimate the energy consumption of a single vehicle eR,i j > 0, (i, j) 2 AR assuming that road arcs are traversed at the constant speed vi j =

di j

ti j . Considering electric vehicles with full recuperation

capabilities and an overall tank-to-wheel efficiency hEV, the energy consumption for a road arc is

eR,i j = ⇣ra

2 · Af · cd · v2i j + cr · mv · g

⌘ ·

di j

hEV 8(i, j) 2 AR. (3)

C. Discussion

8 [Salazar, Rossi, Schiffer, Onder, Pavone, ITSC18]

Network flow model [Salazar, Rossi, Schiffer, Onder, and Pavone, ITCS ’18]

Extended Graph

Conservation of Customers

Conservation of Vehicles

G = (V, A), V = VR � VP � VW, A = AR � AP � AW � ARW � APW

�

i�V fm(i, j) + 1j=om · �m =

�

k�V fm(j, k) + 1j=dm · �m �m � M, �j � V

�

i�VR

� f0(i, j) +

�

m�M fm(i, j)

� =

�

k�VR

� f0(j, k) +

�

m�M fm(j, k)

� �j � VR

Network flow model [Salazar, Rossi, Schiffer, Onder, and Pavone, ITCS ’18]

Capacity of Road and Public Transportation

Optimize Social Welfare: minimize time, operational costs and energy consumption

min {fm(·,·)}m,f0(·,·)

�

(i,j)�A

�

m�M VT · tij · fm(i, j)

+ �

(i,j)�AR

(VD,R · dij + VE · eR,ij ) · �

f0(i, j) + �

m�M fm(i, j)

�

+ �

(i,j)�AP

VD,P · dij · �

m�M fm(i, j)

f0(i, j) + �

m�M fm(i, j) � cR(i, j), �(i, j) � AR

�

m�M fm(i, j) � cP(i, j), �(i, j) � AP

Intermodal AMoD – Manhattan case study

• 54,000 taxi rides during rush hour, distributed in 7000 origin-destination pairs • Computed the socially optimal control strategies to maximize social welfare

Longitude

L a ti tu d e

Longitude

L a ti tu d e

Case Study NYC The optimal solution for different levels of road usage

Baseline Road Usage [%]

M o d a l S h a re , T im

e, E m is si o n s a n d C o st

90 92 94 96 98 100 0

100

Case study of NYC – sample optimal path

—Line M

Longitude

L a ti tu d e

—Line 3

Case study of NYC – pure AMoD vs. I-AMoD

—Line M

Longitude L a ti tu d e

Longitude

L a ti tu d e

—Line 3

Case study of NYC – pure AMoD vs. I-AMoD

Coordination with public transit significantly reduces travel time, number of cars, emissions and cost!

Baseline Road Usage [%]

R el a ti v e D iff er en ce s [%

]

90 92 94 96 98 100

Conclusions

• Autonomous driving might lead to a transformational paradigm for personal urban mobility • Integration of autonomous driving with transportation infrastructure

gives rise to an entirely new class of problems (and opportunities) • Value of (autonomous) EVs supporting renewables integration? • Co-optimization of AMoD systems? • Ensuring equity in transportation?

[email protected]

http://asl.stanford.edu/

https://twitter.com/StanfordASL

mailto:[email protected]?subject=

http://asl.stanford.edu/

Collaborators

• Stephen Zoepf, exec Director of CARS: demand modeling • Mauro Salazar, post-doc: intermodal mobility • Yang Kaidi, post-doc: vehicle routing • Kiril Solovey , post-doc: combinatorial optimization • Ramon Iglesias, Ph.D.: AI, Ha:Mo, mobility marketplace • Matt Tsao, Ph.D.: statistical learning, demand prediction

• Ram Rajagopal, faculty: data analytics for PG • Ashley Pilipiszyn, Ph.D.: charging infrastructure • Justin Luke, Ph.D.: charging optimization • Ryder Ross: software engineer • Masanori Yamato, Toyota/TRI: PM • Stephen Hughes, Toyota/TRI: PM