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

  1. Introduction
  2. Problem Statement
  3. Space-Time-State Network Flow Models
  4. Dantzig-Wolfe Decomposition Algorithm
  5. Preliminary Experiments

Slide 3: 1. Introduction

  • Ride Sharing Companies
    • Uber
    • Lyft
  • Information-sharing technology

[This slide contains three images: (1) the Uber logo, (2) the Lyft logo, and (3) a graphic showing the relationship among many information-sharing 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 multi-modal scheduled transportation system

  1. Mobility as a shared service via an integrated platform
  2. Mass public transit forms the backbone of the mobility system
  3. 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 multi-faceted 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/drop-off location
    • Time windows
    • Origin/destination
  • Vehicle Supply
    • Vehicle-to-passenger assignment
    • Routing and Congestion
  • Infrastructure Design
    • Capacity: Road/transit line/Signal/Depot/Parking

[This slide contains a three-circle Venn Diagram whose elements are reproduced in the list above. The intersection of Trip Demand and Vehicle Supply is Vehicle-to-passenger 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 vehicle-to-passenger 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
  • Vehicle-to-passenger 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 point-to-point network
  • Objective function: System Optimal
  • Traffic congestion: not explicitly considered
  • Vehicle-to-passenger assignment: will be found
  • Passenger trip request: has specific pick-up and drop-off 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 drop-off location and time windows in congested physical traffic networks:

  • System-impact 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 wait-time 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.155-170.

[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 drop-off 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 space-time-state 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 least-marginal-cost route for each vehicles, and go to step 3; otherwise, stop.

Slide 18: Our Approach 2: Dantzig-Wolfe Decomposition

  • Solved by standard solvers
    • Restricted master problem
      • Road capacity constraint
      • Passenger service constraint
  • Solved by the beam-search algorithm in space-time-state networks
    • Subproblems (Time-dependent 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. Space-time-state 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. Space-time-state network and model formulation

Time-extended Space-time network construction for physical path 1→2→4→6

  • Arc (i,j,t,s) with capacity
  • Vertex (i,t), (j,s)
  • Passenger pickup and drop-off 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. Space-time-state 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. Space-time-state 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 space-time-state network runs.]

Slide 23: 3. Space-time-state 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. Space-time-state network and model formulation

One possible vehicle trajectory in a space-time-state network

[This slide contains a graph that plots vehicle trajectory in a space-time-state network.]

Slide 25: 3. Space-time-state network and model formulation

Mathematical formulation:

  • (1) Flow balance constraint for each vehicle
  • (2) Passenger p pick-up 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 pick-up request, tight road capacity constraint, and binary variable.]

Slide 26: 3. Space-time-state 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. Dantzig-Wolfe Decomposition Algorithm

Objective function, subject to:

  1. Flow balance for each vehicle
  2. Passenger p’s pick-up request constraint
  3. Tight road capacity constraint (point queue model)
  4. Binary definitional constraint

Special block: time-dependent state-dependent shortest path problem

  • A special block can be solved by our VRP solution engine
  • can be the subproblem in Dantzig-Wolfe decomposition

[This slide contains four mathematical formulas: flow balance constraint for each vehicle, passenger pick-up request constraint, tight road capacity constraint, and binary definitional constraint.]

Slide 28: 4. Dantzig-Wolfe Decomposition Algorithm

Restricted master problem

  • (9)
  • Pick-up constraint (10)
  • Capacity constraint (11)
  • Column selection (12), (13)

[This slide contains three mathematical formulas: pick-up constraint, capacity constraint, and column selection.]

Slide 29: 4. Dantzig-Wolfe 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. Dantzig-Wolfe Decomposition Algorithm

  • 1. Initialization
    • Feasible solution finding (paths)
  • 2. Restricted Master Problem: Integer linear programming
    • Dual price of side constraints
  • 3. Sub-problems: Time-dependent state dependent least cost path finding
    • Reduced cost
  • Non-negative
    • No: New extreme points (loop back to Step 2)
    • Yes: Optimal solution

[This slide contains a flowchart that is reproduced above.]

Slide 31: 4. Dantzig-Wolfe Decomposition Algorithm

A tree-based path representation

  • One-to-all 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 tree-based path representation of the Dantzig-Wolfe Decomposition Algorithm.]

Slide 32: 5. Preliminary Experiments

# of nodes 24
# of links 84
# of trip requests (pickup and drop-off 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 space-time-state 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

Danzig-Wolfe decomposition algorithm solution:

  • Each passenger has specific pickup and drop-off 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 system-level travel cost, including vehicle travel time and service benefits
  • Satisfy passengers’ trip requests with pickup and drop-off location and time windows
  • Consider the road congestion incurred by assigned vehicles

Future Extension: multi-modal scheduled transportation system: human-driven vehicles, autonomous vehicles, and public transit systems.

Slide 36: 6. Summary

Required knowledge:

  • Dynamic Traffic Assignment and Vehicle Routing Problem
  • Space-time-state network construction and network flow model
  • Time-dependent, Space-dependent, shortest path problem
  • Dantzig-Wolfe 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

Space-time-state network flow models and vehicle routing problem:

  1. 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 state-space-time network representations. Transportation Research Part B: Methodological, 89, 19-42.
  2. Liu, J., Kang, J., Zhou, X., Pendyala, R., 2018. Network-oriented household activity pattern problem for system optimization. Transportation Research Part C 94, 250-269
  3. Zhou, X., Tong, L., Mahmoudi, M., Zhuge, L., Yao, Y., Zhang, Y., Shang, P., Liu, J. and Shi, T., 2018. Open-source VRPLite Package for Vehicle Routing with Pickup and Delivery: A Path Finding Engine for Scheduled Transportation Systems. Urban Rail Transit, 4(2), 68-85.

Dynamic Traffic Assignment and Traffic flow model:

  1. Lu, C.C., Liu, J., Qu, Y., Peeta, S., Rouphail, N.M. and Zhou, X., 2016. Eco-system optimal time-dependent flow assignment in a congested network. Transportation Research Part B: Methodological, 94, pp.217-239.
  2. Zhou, X. and Taylor, J., 2014. DTALite: A queue-based mesoscopic traffic simulator for fast model evaluation and calibration. Cogent Engineering, 1(1), p.961345.

Dantzig-Wolfe Decomposition algorithm

  1. https://en.wikipedia.org/wiki/Dantzig%E2%80%93Wolfe_decomposition

Slide 38: Thank You

↑ Return to top

SUPPORT

Get technical support

Technical Assistance is available to Federal, State and local transportation agencies through:

ITS Peer Program - The ITS Peer-to-Peer Program puts you in touch with technical experts or experienced peers.
ITS Help Line - The ITS Help Line provides technical support by email or telephone at 866-367-7487.

STAY CONNECTED

go to twittergo to email