Add to Chrome
Add to Firefox
Add to EdgeJoseph Y. J. Chow
A sequential transit network design algorithm with optimal learning under correlated beliefs
May 16, 2023
Mobility service route design requires potential demand information to well accommodate travel demand within the service region. Transit planners and operators can access various data sources including household travel survey data and mobile device location logs. However, when implementing a mobility system with emerging technologies, estimating demand level becomes harder because of more uncertainties with user behaviors. Therefore, this study proposes an artificial intelligence-driven algorithm that combines sequential transit network design with optimal learning. An operator gradually expands its route system to avoid risks from inconsistency between designed routes and actual travel demand. At the same time, observed information is archived to update the knowledge that the operator currently uses. Three learning policies are compared within the algorithm: multi-armed bandit, knowledge gradient, and knowledge gradient with correlated beliefs. For validation, a new route system is designed on an artificial network based on public use microdata areas in New York City. Prior knowledge is reproduced from the regional household travel survey data. The results suggest that exploration considering correlations can achieve better performance compared to greedy choices in general. In future work, the problem may incorporate more complexities such as demand elasticity to travel time, no limitations to the number of transfers, and costs for expansion.
A deep real options policy for sequential service region design and timing
Dec 30, 2022
As various city agencies and mobility operators navigate toward innovative mobility solutions, there is a need for strategic flexibility in well-timed investment decisions in the design and timing of mobility service regions, i.e. cast as "real options" (RO). This problem becomes increasingly challenging with multiple interacting RO in such investments. We propose a scalable machine learning based RO framework for multi-period sequential service region design & timing problem for mobility-on-demand services, framed as a Markov decision process with non-stationary stochastic variables. A value function approximation policy from literature uses multi-option least squares Monte Carlo simulation to get a policy value for a set of interdependent investment decisions as deferral options (CR policy). The goal is to determine the optimal selection and timing of a set of zones to include in a service region. However, prior work required explicit enumeration of all possible sequences of investments. To address the combinatorial complexity of such enumeration, we propose a new variant "deep" RO policy using an efficient recurrent neural network (RNN) based ML method (CR-RNN policy) to sample sequences to forego the need for enumeration, making network design & timing policy tractable for large scale implementation. Experiments on multiple service region scenarios in New York City (NYC) shows the proposed policy substantially reduces the overall computational cost (time reduction for RO evaluation of > 90% of total investment sequences is achieved), with zero to near-zero gap compared to the benchmark. A case study of sequential service region design for expansion of MoD services in Brooklyn, NYC show that using the CR-RNN policy to determine optimal RO investment strategy yields a similar performance (0.5% within CR policy value) with significantly reduced computation time (about 5.4 times faster).
EMVLight: a Multi-agent Reinforcement Learning Framework for an Emergency Vehicle Decentralized Routing and Traffic Signal Control System
Jun 29, 2022
Emergency vehicles (EMVs) play a crucial role in responding to time-critical calls such as medical emergencies and fire outbreaks in urban areas. Existing methods for EMV dispatch typically optimize routes based on historical traffic-flow data and design traffic signal pre-emption accordingly; however, we still lack a systematic methodology to address the coupling between EMV routing and traffic signal control. In this paper, we propose EMVLight, a decentralized reinforcement learning (RL) framework for joint dynamic EMV routing and traffic signal pre-emption. We adopt the multi-agent advantage actor-critic method with policy sharing and spatial discounted factor. This framework addresses the coupling between EMV navigation and traffic signal control via an innovative design of multi-class RL agents and a novel pressure-based reward function. The proposed methodology enables EMVLight to learn network-level cooperative traffic signal phasing strategies that not only reduce EMV travel time but also shortens the travel time of non-EMVs. Simulation-based experiments indicate that EMVLight enables up to a $42.6\%$ reduction in EMV travel time as well as an $23.5\%$ shorter average travel time compared with existing approaches.
Worldwide city transport typology prediction with sentence-BERT based supervised learning via Wikipedia
Mar 29, 2022
An overwhelming majority of the world's human population lives in urban areas and cities. Understanding a city's transportation typology is immensely valuable for planners and policy makers whose decisions can potentially impact millions of city residents. Despite the value of understanding a city's typology, labeled data (city and it's typology) is scarce, and spans at most a few hundred cities in the current transportation literature. To break this barrier, we propose a supervised machine learning approach to predict a city's typology given the information in its Wikipedia page. Our method leverages recent breakthroughs in natural language processing, namely sentence-BERT, and shows how the text-based information from Wikipedia can be effectively used as a data source for city typology prediction tasks that can be applied to over 2000 cities worldwide. We propose a novel method for low-dimensional city representation using a city's Wikipedia page, which makes supervised learning of city typology labels tractable even with a few hundred labeled samples. These features are used with labeled city samples to train binary classifiers (logistic regression) for four different city typologies: (i) congestion, (ii) auto-heavy, (iii) transit-heavy, and (iv) bike-friendly cities resulting in reasonably high AUC scores of 0.87, 0.86, 0.61 and 0.94 respectively. Our approach provides sufficient flexibility for incorporating additional variables in the city typology models and can be applied to study other city typologies as well. Our findings can assist a diverse group of stakeholders in transportation and urban planning fields, and opens up new opportunities for using text-based information from Wikipedia (or similar platforms) as data sources in such fields.
Agent-based Simulation Model and Deep Learning Techniques to Evaluate and Predict Transportation Trends around COVID-19
Sep 23, 2020
The COVID-19 pandemic has affected travel behaviors and transportation system operations, and cities are grappling with what policies can be effective for a phased reopening shaped by social distancing. This edition of the white paper updates travel trends and highlights an agent-based simulation model's results to predict the impact of proposed phased reopening strategies. It also introduces a real-time video processing method to measure social distancing through cameras on city streets.
V2I Connectivity-Based Dynamic Queue-Jump Lane for Emergency Vehicles: A Deep Reinforcement Learning Approach
Aug 01, 2020
Emergency vehicle (EMV) service is a key function of cities and is exceedingly challenging due to urban traffic congestion. A main reason behind EMV service delay is the lack of communication and cooperation between vehicles blocking EMVs. In this paper, we study the improvement of EMV service under V2I connectivity. We consider the establishment of dynamic queue jump lanes (DQJLs) based on real-time coordination of connected vehicles. We develop a novel Markov decision process formulation for the DQJL problem, which explicitly accounts for the uncertainty of drivers' reaction to approaching EMVs. We propose a deep neural network-based reinforcement learning algorithm that efficiently computes the optimal coordination instructions. We also validate our approach on a micro-simulation testbed using Simulation of Urban Mobility (SUMO). Validation results show that with our proposed methodology, the centralized control system saves approximately 15\% EMV passing time than the benchmark system.
V2I Connectivity-Based Dynamic Queue-Jumper Lane for Emergency Vehicles: An Approximate Dynamic Programming Approach
Mar 06, 2020
Emergency vehicle (EV) service is a key function of cities and is exceedingly challenging due to urban traffic congestion. A key contributor to EV service delay is the lack of communication and cooperation between vehicles blocking EVs. In this paper, we study the improvement of EV service using vehicle-to-vehicle connectivity. We consider the establishment of dynamic queue jumper lanes (DQJLs) based on real-time coordination of connected vehicles. We develop a novel stochastic dynamic programming formulation for the DQJL problem, which explicitly account for the uncertainty of drivers' reaction to approaching EVs. We propose a deep neural network-based approximate dynamic programming (ADP) algorithm that efficiently computes the optimal coordination instructions. We also validate our approach on a micro-simulation testbed using Simulation On Urban Mobility (SUMO).
Empirical validation of network learning with taxi GPS data from Wuhan, China
Nov 09, 2019
In prior research, a statistically cheap method was developed to monitor transportation network performance by using only a few groups of agents without having to forecast the population flows. The current study validates this "multi-agent inverse optimization" method using taxi GPS probe data from the city of Wuhan, China. Using a controlled 2062-link network environment and different GPS data processing algorithms, an online monitoring environment is simulated using the real data over a 4-hour period. Results show that using only samples from one OD pair, the multi-agent inverse optimization method can learn network parameters such that forecasted travel times have a 0.23 correlation with the observed travel times. By increasing to monitoring from just two OD pairs, the correlation improves further to 0.56.
Air Taxi Skyport Location Problem for Airport Access
Apr 03, 2019
Air taxis are poised to be an additional mode of transportation in major cities suffering from ground transportation congestion. Among several potential applications of air taxis, we focus on their use within a city to transport passengers to nearby airports. Specifically, we consider the problem of determining optimal locations for skyports (enabling pick-up of passengers to airport) within a city. Our approach is inspired from hub location problems, and our proposed method optimizes for aggregate travel time to multiple airports while satisfying the demand (trips to airports) either via (i) ground transportation to skyport followed by an air taxi to the airport, or (ii) direct ground transportation to the airport. The number of skyports is a constraint, and the decision to go via the skyport versus direct ground transportation is a variable in the optimization problem. Extensive experiments on publicly available airport trips data from New York City (NYC) show the efficacy of our optimization method implemented using Gurobi. In addition, we share insightful results based on the NYC data set on how ground transportation congestion can impact the demand and service efficiency in such skyports; this emerges as yet another factor in deciding the optimal number of skyports and their locations for a given city.
Network learning via multi-agent inverse transportation problems
Sep 07, 2017
Despite the ubiquity of transportation data, methods to infer the state parameters of a network either ignore sensitivity of route decisions, require route enumeration for parameterizing descriptive models of route selection, or require complex bilevel models of route assignment behavior. These limitations prevent modelers from fully exploiting ubiquitous data in monitoring transportation networks. Inverse optimization methods that capture network route choice behavior can address this gap, but they are designed to take observations of the same model to learn the parameters of that model, which is statistically inefficient (e.g. requires estimating population route and link flows). New inverse optimization models and supporting algorithms are proposed to learn the parameters of heterogeneous travelers' route behavior to infer shared network state parameters (e.g. link capacity dual prices). The inferred values are consistent with observations of each agent's optimization behavior. We prove that the method can obtain unique dual prices for a network shared by these agents in polynomial time. Four experiments are conducted. The first one, conducted on a 4-node network, verifies the methodology to obtain heterogeneous link cost parameters even when multinomial or mixed logit models would not be meaningfully estimated. The second is a parameter recovery test on the Nguyen-Dupuis network that shows that unique latent link capacity dual prices can be inferred using the proposed method. The third test on the same network demonstrates how a monitoring system in an online learning environment can be designed using this method. The last test demonstrates this learning on real data obtained from a freeway network in Queens, New York, using only real-time Google Maps queries.