Webinar Files
Autonomous Vehicle Assignment and Routing in Congested Transportation Networks
(October 25, 2018)
Presenter: Xuesong Zhou
Presenter’s Org: Arizona State University
Presenter: Jiangtao Liu
Presenter’s Org: Arizona State University
HTML version of the presentation
Image descriptions are contained in brackets. [ ]
<< Return to Webinar Files
T3e webinars are brought to you by the Intelligent Transportation Systems (ITS) Professional Capacity Building (PCB) Program of the U.S. Department of Transportation’s (U.S. DOT) ITS Joint Program Office (JPO). References in this webinar to any specific commercial products, processes, or services, or the use of any trade, firm, or corporation name is for the information and convenience of the public, and does not constitute endorsement, recommendation, or favoring by the U.S. DOT.
Most of the slides in this presentation contain the Arizona State University Ira A. Fulton Schools of Engineering logo.
Slide 1: Autonomous Vehicle Assignment and Routing in Congested Networks
 Arizona State University
 School of Sustainable Engineering and the Built Environment
 School of Computing, Informatics, and Decision Systems Engineering (CIDSE)
T3 Webinars are sponsored by ITS Professional Capacity Building Program, ITS Joint Program Office, U.S. Department of Transportation
Slide 2: Outline
 Introduction
 Problem Statement
 SpaceTimeState Network Flow Models
 DantzigWolfe Decomposition Algorithm
 Preliminary Experiments
Slide 3: 1. Introduction
 Ride Sharing Companies
 Informationsharing technology
[This slide contains three images: (1) the Uber logo, (2) the Lyft logo, and (3) a graphic showing the relationship among many informationsharing technologies.]
Slide 4: 1. Introduction
 The “three revolutions” in the future transportation systems
 Automation
 Shared Use
 Electrification
[This slide contains three images: (1) a graphic of a car with wireless waves emanating from it, representing connected vehicle automation, (2) a graphic of five people, representing shared use of future transportation systems, and (3) a graphic of a smartphone that has an electrical cord attached to it, representing vehicle electrification systems.]
Slide 5: (No title)
Future urban transportation systems: integrated multimodal scheduled transportation system
 Mobility as a shared service via an integrated platform
 Mass public transit forms the backbone of the mobility system
 Feet of shared AVs fulfills first and last mile needs
 V2V and V2I communications
 No traffic control at intersections
 Low emission zones
 Parking spaces converted into public green, walking, and cycling
 Fast public charging
[This slide contains a graphic representation of a multifaceted connected urban transportation system, whose various elements are labeled. The labels are reproduced in the above lists.]
Picture source: McKinsey & Company, 2016. An integrated perspective on the future of mobility.
Slide 6: (No title)
How to optimize demand, supply and infrastructure?
 Trip Demand
 Pickup/dropoff location
 Time windows
 Origin/destination
 Vehicle Supply
 Vehicletopassenger assignment
 Routing and Congestion
 Infrastructure Design
 Capacity: Road/transit line/Signal/Depot/Parking
[This slide contains a threecircle Venn Diagram whose elements are reproduced in the list above. The intersection of Trip Demand and Vehicle Supply is Vehicletopassenger assignment. The intersection of Vehicle Supply and Infrastructure Design is Routing and Congestion.]
Slide 7: 1. Introduction
Key questions:
 How many autonomous vehicles do we need?
 How many passengers can we serve?
 How to capture the new traffic congestion?
 What is the best vehicle routing and vehicletopassenger assignment solution?
[This slide contains a map that represents one scenario for potential demand for autonomous vehicles and how many passengers might need to be served.]
Slide 8: 2. Problem Statement
Traffic Assignment Problem:
 Network: Physical traffic network
 Objective function: System Optimal or User Equilibrium
 Road capacity: considered to capture road congestions
 Vehicletopassenger assignment: given in advance
 Passenger trip request: has the same origin and destination as that of the assigned vehicles
 Vehicle carrying capacity: not explicitly considered
 Variable: usually continuous vehicle flow
[This slide contains a graphic that represents one scenario containing potential gridlock issues between zones in an area in Phoenix and how it might affect autonomous/passenger pickup.]
Slide 9: 2. Problem Statement
Vehicle Routing Problem:
 Network: Virtual pointtopoint network
 Objective function: System Optimal
 Traffic congestion: not explicitly considered
 Vehicletopassenger assignment: will be found
 Passenger trip request: has specific pickup and dropoff location with time windows
 Vehicle carrying capacity: considered
 Variable: discrete vehicle routing and scheduling
[This slide contains a graphic that displays one scenario of potential gridlock issues between depots in an area in Phoenix and how it might affect autonomous vehicles/passengers.]
Slide 10: 2. Problem Statement
Keywords:
 Physical traffic network to consider traffic congestion
 Trip requests with Pickup and delivery with time windows
 Autonomous vehicles with carrying capacity for ride sharing
 Central control (System optimal)
[This slide contains a graphic representation of a Transportation Management and Control Center involved in managing the pickup of passengers by an autonomous vehicle.]
Slide 11: Link Capacity
Without link capacity: Total cost is 6
With link capacity: Total cost is 15
[This slide contains two pairs of images: (1) One pair represents autonomous vehicles without Transportation Management and Control Center management and the path they would take to pick up passengers 1 and 2. (2) The other pair represents autonomous vehicles with Transportation Management and Control Center connection and the alternate path one blue car would take to avoid gridlock and reach the destination faster.]
Slide 12: System Optimal Coordination
Without coordination (selfish routing): Total cost is 15
With coordination: Total cost is 9
[This slide contains three images: (1) representation showing the optimal coordination between vehicles and Transportation Command Center, reducing time for passenger pickup, (2) representation showing passenger pickup without coordination, which takes more time and additional resources, and 3) representation showing passenger pickup with coordination between vehicles and command center, which results in more efficient routes and reduced time and cost.]
Slide 13: Time windows
The red vehicle can wait until time 3 to pick up passenger 2, so the blue vehicle can pick up passenger 1 at exact time 3.
The optimal result doesn’t only optimize the vehicle routing, but also the departure time of picked up passengers.
[This slide contains two images: (1) a graphic representation that shows efficient time windows when autonomous vehicles are connected with a command center, and (2) a graphic representation showing vehicle routing and passenger departure time being enhanced as a result.]
Slide 14: Ridesharing (vehicle carrying capacity)
When the red vehicle’s carrying capacity is increased to 2, the total cost is reduced to 4 from 9;
Only the red vehicle is required to serve the trip requests.
[This slide contains two images that represent time windows and reduced cost when ridesharing is introduced.]
Slide 15: The Challenge of solving system optimal vehicle routing with pickup and dropoff location and time windows in congested physical traffic networks:
 Systemimpact of adjusting one vehicle routing:
 System marginal travel time
 System marginal passenger service benefit/cost
 In this queuing system:
 Waiting time for individual: 4 min
 After adding one more person in the queue:
 Societal travel time: additional 4 min for each person behind: +16 min, and the waiting time of added person is 4 min, so the system marginal waiting time is 20 min.
 Societal service benefit: some persons may not be served in their preferred time window and it decreases the service benefit.
[This slide contains an image that represents added waittime for passengers when a new passenger is added to the queue.]
Slide 16: (No title)
Marginal cost calculation in system optimal dynamic traffic assignment (SODTA)
Ghali, M.O. and Smith, M.J., 1995. A model for the dynamic system optimum traffic assignment problem. Transportation Research Part B: Methodological, 29(3), pp.155170.
[This slide contains a cost calculation graph in a system of optimal dynamic traffic assignment.]
Slide 17: Our Approach 1: Marginal Cost Calculation
 Step 1: Build virtual pickup and dropoff links in physical traffic networks, and its service pricing is converted to generalized link travel cost
 Step 2: find one initial solution as the input
 Step 3: Perform network loading within a spacetimestate network
 3.1 use cumulative arrival and departure counts to derive the link marginal travel cost.
 3.2 update the marginal service link benefit of passengers (not served or served by multiple vehicles)
 Step 4: find the new leastmarginalcost route for each vehicles, and go to step 3; otherwise, stop.
Slide 18: Our Approach 2: DantzigWolfe Decomposition
 Solved by standard solvers
 Restricted master problem
 Road capacity constraint
 Passenger service constraint
 Solved by the beamsearch algorithm in spacetimestate networks
 Subproblems (Timedependent State dependent shortest path problem for each vehicle)
[This slide contains a rudimentary flow chart that is reproduced above. There is an arrow from Restricted master problem to Subproblems that is labeled “Marginal costs from the solver.” There is an arrow from Subproblems to Restricted master problem titled “Vehicle routing solution.”]
Slide 19: 3. Spacetimestate network and model formulation
[This slide contains two images: (1) a graphic representation of a physical transportation network and (2) a modified physical transportation network with virtual pickup/delivery nodes and links.]
Slide 20: 3. Spacetimestate network and model formulation
Timeextended Spacetime network construction for physical path 1→2→4→6
 Arc (i,j,t,s) with capacity
 Vertex (i,t), (j,s)
 Passenger pickup and dropoff time windows and locations are embedded in this network
[This slide contains a graph showing a modified physical transportation network with virtual pickup/delivery nodes and links, with the X axis representing time and the Y axis representing space.]
Slide 21: 3. Spacetimestate network and model formulation
Challenge: how to model the logit of passenger pickup and delivery with vehicle carrying capacity
One more dimension→ Vehicle Carrying States: which passengers are being carried by this vehicle:
To record the passenger service status:
 0: the passenger is not served;
 1: under served (picked up but not delivered);
 2: finished (delivered)
Example: In the case: if vehicle capacity is 1 and 2 passengers trip requests,
All possible states: [ ], [1[1]], [1[2]], [2[1]] or [2[2]]
[This slide contains two images (1) a graphic of a vehicle and two passengers, and (2) a graphic of a passenger watching a clock, waiting for a ride.]
Slide 22: 3. Spacetimestate network and model formulation
Vehicle carrying state transition logit: focusing on specific passenger 1
 0→0: vehicle departs at the origin depot
 0→1[1]: passenger 1 is picked up at his location within time window.
 1[1]→1[2]: passenger 1 is dropped off at his location within time window
 1[2]→0: vehicle arrives at the destination depot.
 Once one passenger is picked up, he/she will always be dropped off, because 1[1]→0 is not a feasible state transition.
 No passenger will be served if the vehicle carrying capacity is fully used.
[This slide contains Image a graphic of three gears, which represent how a spacetimestate network runs.]
Slide 23: 3. Spacetimestate network and model formulation
Vehicle State Transition with specific locations and time intervals
Vehicle carrying state transition graph
 [ ] Before serving any passengers
 [1[1]] After passenger 1 is picked up at node 7 at the allowed time, this state keeps unchanged until passenger 1 is delivered
 [1[2]] After passenger 1 is delivered at node 10 at the allowed time, the state keeps unchanged and the vehicle capacity is reduced by 1
 [2[1]] After passenger 2 is picked up at node 8 at the allowed time, this state keeps unchanged until passenger 2 is delivered
 [2[2]] After passenger 2 is delivered at node 10 at the allowed time, the state keeps unchanged and the vehicle capacity is reduced by 1
 [F] Virtual ending state connecting those feasible ending states at the destination depot
[This slide contains a Vehicle carrying state transition graph that displays states at various nodes and how it affects the state after various passenger pickups. The details of the graph are listed above.]
Slide 24: 3. Spacetimestate network and model formulation
One possible vehicle trajectory in a spacetimestate network
[This slide contains a graph that plots vehicle trajectory in a spacetimestate network.]
Slide 25: 3. Spacetimestate network and model formulation
Mathematical formulation:
 (1) Flow balance constraint for each vehicle
 (2) Passenger p pickup request at (o,d,τ)
 (3) Tight road capacity constraint (point queue model)
 (4) Binary variables
[This slide contains four mathematical formulas for flow balance constraint for each vehicle, passenger pickup request, tight road capacity constraint, and binary variable.]
Slide 26: 3. Spacetimestate network and model formulation
Capture queue spillback:
 Inflow arc capacity constraint
 Outflow arc capacity constraint
 Link storage capacity constraint
Newell’s simplified kinematic wave model (Newell, 1993)
[This slide contains four mathematical formulas for inflow arc capacity constraint, outflow arc capacity constraint, link storage capacity constraint, and Newell’s simplified kinematic wave.]
Slide 27: 4. DantzigWolfe Decomposition Algorithm
Objective function, subject to:
 Flow balance for each vehicle
 Passenger p’s pickup request constraint
 Tight road capacity constraint (point queue model)
 Binary definitional constraint
Special block: timedependent statedependent shortest path problem
 A special block can be solved by our VRP solution engine
 can be the subproblem in DantzigWolfe decomposition
[This slide contains four mathematical formulas: flow balance constraint for each vehicle, passenger pickup request constraint, tight road capacity constraint, and binary definitional constraint.]
Slide 28: 4. DantzigWolfe Decomposition Algorithm
Restricted master problem
 (9)
 Pickup constraint (10)
 Capacity constraint (11)
 Column selection (12), (13)
[This slide contains three mathematical formulas: pickup constraint, capacity constraint, and column selection.]
Slide 29: 4. DantzigWolfe Decomposition Algorithm
Subproblems (TDSDSP)
 Dual variable/marginal cost of passenger pickup constraints
 Dual variable/marginal cost of congestion restraints
 Dual variable/marginal cost of path weight constraints
[This slide contains two mathematical formulas with three variables highlighted. The variables are listed above.]
Slide 30: 4. DantzigWolfe Decomposition Algorithm
 1. Initialization
 Feasible solution finding (paths)
 2. Restricted Master Problem: Integer linear programming
 Dual price of side constraints
 3. Subproblems: Timedependent state dependent least cost path finding
 Nonnegative
 No: New extreme points (loop back to Step 2)
 Yes: Optimal solution
[This slide contains a flowchart that is reproduced above.]
Slide 31: 4. DantzigWolfe Decomposition Algorithm
A treebased path representation
 Onetoall shortest path tree is generated for one vehicle
 Directly obtain the shortest path for vehicles with the same depot and departure time but different destination depot
 Does not need to run the shortest path algorithm again to improve the computation efficiency.
[This slide contains a treebased path representation of the DantzigWolfe Decomposition Algorithm.]
Slide 32: 5. Preliminary Experiments
# of nodes 
24 
# of links 
84 
# of trip requests (pickup and dropoff with time windows) 
30 
# of available autonomous vehicles 
30 
# of depots 
5 
optimization time horizon (time unit) 
110 
Vehicle capacity (person) 
1 
[This slide contains a representation of the Sioux Falls spacetimestate network.]
Slide 33: 5. Preliminary Experiments
Initial feasible solution
Vehicle_No 
Passenger_No 
Vehicle_No 
Passenger_No 
Vehicle_No 
Passenger_No 
1 
[15] 
11 
[20] 
21 
[23] 
2 
[8] 
12 
[26] 
22 
[25] 
3 
[1] 
13 
[16] 
23 
[22] 
4 
[7] 
14 
[18] 
24 
[19] 
5 
[9] 
15 
[2] 
25 
[4] 
6 
[11] 
16 
[10] 
26 
[5] 
7 
[29] 
17 
[3] 
27 
[24] 
8 
[28] 
18 
[12] 
28 
[14] 
9 
[17] 
19 
[27] 
29 
[13] 
10 
[21] 
20 
[30] 
30 
[6] 
Slide 34: 5. Preliminary Experiments
DanzigWolfe decomposition algorithm solution:
 Each passenger has specific pickup and dropoff location and time windows
 The vehicle benefit of serving one passenger is 20
 The vehicle waiting cost is the half of the waiting time

Number of required vehicles 
Total travel cost 
Initial solution 
30 
1096 
vehicle carrying capacity is 1 
27 
967.5 
vehicle carrying capacity is 2 
25 
869.5 
Take vehicle 9 as an example:
 In initial solution: picks up passenger 17 → drops off passenger 17;
 Vehicle carrying capacity is 1: picks up passenger 17 → drops off passenger 17 → picks up passenger 29 → drops off passenger 29
 Vehicle carrying capacity is 2: picks up passenger 17 → drops off passenger 17 → picks up passenger 30 → picks up passenger 29 → drops off passenger 29 → drops off passenger 30
Slide 35: 6. Summary
Our goals:
 Minimize the systemlevel travel cost, including vehicle travel time and service benefits
 Satisfy passengers’ trip requests with pickup and dropoff location and time windows
 Consider the road congestion incurred by assigned vehicles
Future Extension: multimodal scheduled transportation system: humandriven vehicles, autonomous vehicles, and public transit systems.
Slide 36: 6. Summary
Required knowledge:
 Dynamic Traffic Assignment and Vehicle Routing Problem
 Spacetimestate network construction and network flow model
 Timedependent, Spacedependent, shortest path problem
 DantzigWolfe decomposition algorithm
[This slide contains a graphic image of a puzzle with four interlocking pieces which represents how topics of presentation fit together. Each of the puzzle pieces is labeled with one of the four items listed above.]
Slide 37: Reference
Spacetimestate network flow models and vehicle routing problem:
 Mahmoudi, M. and Zhou, X., 2016. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on statespacetime network representations. Transportation Research Part B: Methodological, 89, 1942.
 Liu, J., Kang, J., Zhou, X., Pendyala, R., 2018. Networkoriented household activity pattern problem for system optimization. Transportation Research Part C 94, 250269
 Zhou, X., Tong, L., Mahmoudi, M., Zhuge, L., Yao, Y., Zhang, Y., Shang, P., Liu, J. and Shi, T., 2018. Opensource VRPLite Package for Vehicle Routing with Pickup and Delivery: A Path Finding Engine for Scheduled Transportation Systems. Urban Rail Transit, 4(2), 6885.
Dynamic Traffic Assignment and Traffic flow model:
 Lu, C.C., Liu, J., Qu, Y., Peeta, S., Rouphail, N.M. and Zhou, X., 2016. Ecosystem optimal timedependent flow assignment in a congested network. Transportation Research Part B: Methodological, 94, pp.217239.
 Zhou, X. and Taylor, J., 2014. DTALite: A queuebased mesoscopic traffic simulator for fast model evaluation and calibration. Cogent Engineering, 1(1), p.961345.
DantzigWolfe Decomposition algorithm
 https://en.wikipedia.org/wiki/Dantzig%E2%80%93Wolfe_decomposition
Slide 38: Thank You
↑ Return to top