Individual mobility prediction holds significant importance in urban computing, supporting various applications such as place recommendations. Current studies primarily focus on frequent mobility patterns including commuting trips to residential and workplaces. However, such studies do not accurately forecast irregular trips, which incorporate journeys that end at locations other than residences and workplaces. Despite their usefulness in recommendations and advertising, the stochastic, infrequent, and spontaneous nature of irregular trips makes them challenging to predict. To address the difficulty, this study proposes a web search-driven bipartite graph neural network, namely WS-BiGNN, for the individual irregular mobility prediction (IIMP) problem. Specifically, we construct bipartite graphs to represent mobility and web search records, formulating the IIMP problem as a link prediction task. First, WS-BiGNN employs user-user edges and POI-POI edges (POI: point-of-interest) to bolster information propagation within sparse bipartite graphs. Second, the temporal weighting module is created to discern the influence of past mobility and web searches on future mobility. Lastly, WS-BiGNN incorporates the search-mobility memory module, which classifies four interpretable web search-mobility patterns and harnesses them to improve prediction accuracy. We perform experiments utilizing real-world data in Tokyo from October 2019 to March 2020. The results showcase the superior performance of WS-BiGNN compared to baseline models, as supported by higher scores in Recall and NDCG. The exceptional performance and additional analysis reveal that infrequent behavior may be effectively predicted by learning search-mobility patterns at the individual level.

Mean-Field Control (MFC) has recently been proven to be a scalable tool to approximately solve large-scale multi-agent reinforcement learning (MARL) problems. However, these studies are typically limited to unconstrained cumulative reward maximization framework. In this paper, we show that one can use the MFC approach to approximate the MARL problem even in the presence of constraints. Specifically, we prove that, an $N$-agent constrained MARL problem, with state, and action spaces of each individual agents being of sizes $|\mathcal{X}|$, and $|\mathcal{U}|$ respectively, can be approximated by an associated constrained MFC problem with an error, $e\triangleq \mathcal{O}\left([\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}]/\sqrt{N}\right)$. In a special case where the reward, cost, and state transition functions are independent of the action distribution of the population, we prove that the error can be improved to $e=\mathcal{O}(\sqrt{|\mathcal{X}|}/\sqrt{N})$. Also, we provide a Natural Policy Gradient based algorithm, and prove that it can solve the constrained MARL problem within an error of $\mathcal{O}(e)$ with a sample complexity of $\mathcal{O}(e^{-6})$.

This study explores the vaccine prioritization strategy to reduce the overall burden of the pandemic when the supply is limited. Existing vaccine distribution methods focus on macro-level or simplified micro-level assuming homogeneous behavior within populations without considering mobility patterns. Directly applying these models for micro-level vaccine allocation leads to sub-optimal solutions. To address the issue, we first proposed a Trans-vaccine-SEIR model to incorporate mobility heterogeneity in disease propagation. Then we develop a novel deep reinforcement learning to seek the optimal vaccine allocation strategy for the disease evolution system. The graph neural network is used to effectively capture the structural properties of the mobility network and extract disease features. In our evaluation, the proposed framework reduces 7%-10% of infections and deaths compared to the baseline strategies. Extensive evaluation shows that the proposed framework is robust to seek the optimal vaccine allocation with diverse mobility patterns. In particular, we find transit usage restriction is significantly more effective than restricting cross-zone mobility for the top 10% age-based and income-based zones under optimal vaccine allocation strategy. These results provide valuable insights for areas with limited vaccines and low logistic efficacy.

Recurring outbreaks of COVID-19 have posed enduring effects on global society, which calls for a predictor of pandemic waves using various data with early availability. Existing prediction models that forecast the first outbreak wave using mobility data may not be applicable to the multiwave prediction, because the evidence in the USA and Japan has shown that mobility patterns across different waves exhibit varying relationships with fluctuations in infection cases. Therefore, to predict the multiwave pandemic, we propose a Social Awareness-Based Graph Neural Network (SAB-GNN) that considers the decay of symptom-related web search frequency to capture the changes in public awareness across multiple waves. Our model combines GNN and LSTM to model the complex relationships among urban districts, inter-district mobility patterns, web search history, and future COVID-19 infections. We train our model to predict future pandemic outbreaks in the Tokyo area using its mobility and web search data from April 2020 to May 2021 across four pandemic waves collected by Yahoo Japan Corporation under strict privacy protection rules. Results demonstrate our model outperforms state-of-the-art baselines such as ST-GNN, MPNN, and GraphLSTM. Though our model is not computationally expensive (only 3 layers and 10 hidden neurons), the proposed model enables public agencies to anticipate and prepare for future pandemic outbreaks.

Mean-Field Control (MFC) is a powerful tool to solve Multi-Agent Reinforcement Learning (MARL) problems. Recent studies have shown that MFC can well-approximate MARL when the population size is large and the agents are exchangeable. Unfortunately, the presumption of exchangeability implies that all agents uniformly interact with one another which is not true in many practical scenarios. In this article, we relax the assumption of exchangeability and model the interaction between agents via an arbitrary doubly stochastic matrix. As a result, in our framework, the mean-field ‘seen’ by different agents are different. We prove that, if the reward of each agent is an affine function of the mean-field seen by that agent, then one can approximate such a non-uniform MARL problem via its associated MFC problem within an error of $e=\mathcal{O}(\frac{1}{\sqrt{N}}[\sqrt{|\mathcal{X}|} + \sqrt{|\mathcal{U}|}])$ where $N$ is the population size and $|\mathcal{X}|$, $|\mathcal{U}|$ are the sizes of state and action spaces respectively. Finally, we develop a Natural Policy Gradient (NPG) algorithm that can provide a solution to the non-uniform MARL with an error $\mathcal{O}(\max\{e,\epsilon\})$ and a sample complexity of $\mathcal{O}(\epsilon^{-3})$ for any $\epsilon >0$.

Mean field control (MFC) is an effective way to mitigate the curse of dimensionality of cooperative multi-agent reinforcement learning (MARL) problems. This work considers a collection of $N_{\mathrm{pop}}$ heterogeneous agents that can be segregated into $K$ classes such that the $k$-th class contains $N_k$ homogeneous agents. We aim to prove approximation guarantees of the MARL problem for this heterogeneous system by its corresponding MFC problem. We consider three scenarios where the reward and transition dynamics of all agents are respectively taken to be functions of $(1)$ joint state and action distributions across all classes, $(2)$ individual distributions of each class, and $(3)$ marginal distributions of the entire population. We show that, in these cases, the $K$-class MARL problem can be approximated by MFC with errors given as $e_1=\mathcal{O}(\frac{\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}}{N_{\mathrm{pop}}}\sum_{k}\sqrt{N_k})$, $e_2=\mathcal{O}(\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]\sum_{k}\frac{1}{\sqrt{N_k}})$ and $e_3=\mathcal{O}\left(\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]\left[\frac{A}{N_{\mathrm{pop}}}\sum_{k\in[K]}\sqrt{N_k}+\frac{B}{\sqrt{N_{\mathrm{pop}}}}\right]\right)$, respectively, where $A, B$ are some constants and $|\mathcal{X}|,|\mathcal{U}|$ are the sizes of state and action spaces of each agent. Finally, we design a Natural Policy Gradient (NPG) based algorithm that, in the three cases stated above, can converge to an optimal MARL policy within $\mathcal{O}(e_j)$ error with a sample complexity of $\mathcal{O}(e_j^{-3})$, $j\in\{1,2,3\}$, respectively.

To improve the mymargin efficiency of urban on-demand mobility services (OMS) (e.g., taxi and for-hire vehicles such as Uber, Lyft, and Didi), it is important to frame proactive operation strategies before the actual demand is revealed. The task is challenging since the effectiveness depends on the knowledge of passenger demand distribution in immediate future and is prone to prediction errors. In this study, we develop the boosting Gaussian conditional random field (boosting-GCRF) model to accurately forecast the distribution of short-term future OMS demand using historical OMS demand data. Comprehensive numerical experiments are conducted to evaluate the performance of boosting-GCRF as compared to four other benchmark algorithms. The results suggest that the boosting-GCRF is superior with the best mean absolute percentage error being 14%. In addition, the model is found to be robust under demand anomalies, and the density functions generated by the boosting-GCRF model are found to well capture the actual distribution of the short-term taxi demand.

Abstract Understanding how information use contributes to uncertainties surrounding evacuation decisions is crucial during disasters. While literature increasingly establishes that people consult multiple information sources in disaster situations, little is known about the patterns in which multiple media and personal network sources are combined simultaneously and sequentially across decision‐making phases. We address this gap using survey data collected from households in Jacksonville, Florida affected by 2016's Hurricane Matthew. Results direct attention to perceived consistency of information as a key predictor of uncertainty regarding hurricane impact and evacuation logistics. Frequently utilizing National Weather Service, national and local TV channels, and personal network contacts contributed to higher perceived consistency of information, while the use of other local and online sources was associated with lower perceived consistency. Furthermore, combining a larger number of media and official sources predicted higher levels of perceived information consistency. One's perception of information amount did not significantly explain uncertainty. This study contributes to the theorizing of individuals' information environment from the perspective of media and network multiplexity and provides practical implications regarding the need of information coordination for improved evacuation decision‐making.

Unsupervised translation has become a popular task in natural language processing (NLP) due to difficulties in collecting large scale parallel datasets. In the urban computing field, place embeddings generated using human mobility patterns via recurrent neural networks are used to understand the functionality of urban areas. Translating place embeddings across cities allow us to transfer knowledge across cities, which may be used for various downstream tasks such as planning new store locations. Despite such advances, current methods fail to translate place embeddings across domains with different scales (e.g. Tokyo to Niigata), due to the straightforward adoption of neural machine translation (NMT) methods from NLP, where vocabulary sizes are similar across languages. We refer to this issue as the domain imbalance problem in unsupervised translation tasks. We address this problem by proposing an unsupervised translation method that translates embeddings by exploiting common hierarchical structures that exist across imbalanced domains. The effectiveness of our method is tested using place embeddings generated from mobile phone data in 6 Japanese cities of heterogeneous sizes. Validation using landuse data clarify that using hierarchical anchors improves the translation accuracy across imbalanced domains. Our method is agnostic to input data type, thus could be applied to unsupervised translation tasks in various fields in addition to linguistics and urban computing.

Large mobility datasets collected from various sources have allowed us to observe, analyze, predict and solve a wide range of important urban challenges. In particular, studies have generated place representations (or embeddings) from mobility patterns in a similar manner to word embeddings to better understand the functionality of different places within a city. However, studies have been limited to generating such representations of cities in an individual manner and has lacked an inter-city perspective, which has made it difficult to transfer the insights gained from the place representations across different cities. In this study, we attempt to bridge this research gap by treating cities and languages analogously. We apply methods developed for unsupervised machine language translation tasks to translate place representations across different cities. Real world mobility data collected from mobile phone users in 2 cities in Japan are used to test our place representation translation methods. Translated place representations are validated using landuse data, and results show that our methods were able to accurately translate place representations from one city to another.

Predicting the evacuation decisions of individuals before the disaster strikes is crucial for planning first response strategies. In addition to the studies on post-disaster analysis of evacuation behavior, there are various works that attempt to predict the evacuation decisions beforehand. Most of these predictive methods, however, require real time location data for calibration, which are becoming much harder to obtain due to the rising privacy concerns. Meanwhile, web search queries of anonymous users have been collected by web companies. Although such data raise less privacy concerns, they have been under-utilized for various applications. In this study, we investigate whether web search data observed prior to the disaster can be used to predict the evacuation decisions. More specifically, we utilize a session-based query encoder that learns the representations of each user's web search behavior prior to evacuation. Our proposed approach is empirically tested using web search data collected from users affected by a major flood in Japan. Results are validated using location data collected from mobile phones of the same set of users as ground truth. We show that evacuation decisions can be accurately predicted (84%) using only the users' pre-disaster web search data as input. This study proposes an alternative method for evacuation prediction that does not require highly sensitive location data, which can assist local governments to prepare effective first response strategies.

Catering to the humanitarian needs of hurricane-affected residents is the most challenging part for the emergency management agencies. These agencies typically follow a centralized help disbursement model by collecting donations and disbursing them to the needful through their employees or registered volunteers. The time required to move goods and volunteers to the place of need poses a survival challenge to emergency hit residents especially during the initial few days after the emergency. We propose and design a social-media (specifically Twitter) aided hyperlocal help-network by utilizing the tweets to identify users who require help and those who are willing to provide it. We also analyze tweets related to road damage, traffic jam, etc. to sense the current state of road infrastructure. We propose to match the help seekers and those who are willing to help, taking into consideration their spatial proximity and then provide the fastest working route for the help-provider to reach the matched help-seeker. Numerical experiments performed on hurricane Sandy Twitter dataset shows the effectiveness of the proposed approach as we are able to satisfy the need of more than 80% of help-seekers by matching them to appropriate help-offerer within a 24-hour duration after posting the request for help tweet with a maximum travel distance of 10 km.

Geo-location data from the check-ins made in online social media offers us information, in new ways, to understand activity-location choices of a large number of people. However, one of the major challenges of using check-in data is that it has missing activities, since users share their activities voluntarily. In this paper, we present a probabilistic modeling approach to reconstruct user activity-location sequences from this incomplete activity participation information. Specifically, we answer the question of how to predict an individual's next activity, its duration and location given the incomplete trajectory data. The model describes the dynamics of individual activity participation behavior evolving over continuous time. A semi-Markov modeling approach is used to capture the stochastic processes involved in the activity generation mechanism. We present a particle-based Markov chain Monte Carlo sampler to run inference over the model. We further develop an expectation-maximization algorithm to learn the unknown parameters of the model from incomplete trajectory data. Finally, the method is applied to synthetically generated activity-location sequences and a data set of Foursquare check-ins of the users from New York City. Our experiments show that this method can successfully extract the true transition and duration distributions given the incomplete trajectory information. The proposed approach can help building many intelligent transportation applications using check-in data.

Dynamic pricing implemented in the form of a surge price multiplier (SPM) by mobility-on-demand services such as Uber, Lyft, etc. have significantly altered the demand-supply dynamics of the fixed fare rate traditional taxi market. However, it bears a fair share of criticism for being opaque, opportunistic, and socially insensitive, especially during large public events and emergency situations. In this paper, we collect and mine the operational data of one of the largest mobility service provider: Uber in the New York City (NYC) to understand the underlying mechanism behind the dynamic pricing generation. We find the common spatiotemporal patterns in the SPM and identify the cost-effectiveness of its most popular service, UberX as compared to UberBlack and street hailing taxis. We model the underlying phenomenon behind the SPM generation as a function of demand, supply, the time of the day, the day of the week, and expected time to arrival (ETA) using various machine learning classifiers. Support vector machines, k-nearest neighbor, and decision tree classifiers are found to model the SPM the best with the average classification loss for the 10-fold cross validation being as low as 0.001 for the rapidly changing SPM for UberX.

For a regular weekday in New York City, the number of taxi trips at 8 P.M. may be 10 times greater than that at 5 A.M., while passengers are charged under the same pricing scheme. Motivated by temporally non-stationary demand and supply in the taxi market, the time-of-day (TOD) pricing scheme for taxi industry is framed to vary trip cost dynamically over time, so that total market revenue is maximized. Temporal market dynamics is modeled as a semi-Markov process, which captures leftover of drivers, spillover of passengers, and restoration of drivers in service along the time horizon. The TOD pricing scheme is therefore formulated as discrete time stochastic dynamic programming with the goal to find the optimal sequence of price multipliers. The approximate dynamic programming (ADP) approach is introduced to solve the curse of dimensionality. Numerical experiments are conducted using New York City taxi trip data to illustrate the effectiveness of TOD price in real-world taxi market. The results suggest that TOD price may increase daily market revenue by over 10% using the ADP approach. Our experiments also show that TOD price may be even more effective if sudden surges in demand take place in the market.

In the test bed of connected vehicles, detailed trajectory data are collected for connected vehicles only. It brings challenges to study the car-following behavior of connected vehicles following nonconnected vehicles. This paper proposes an optimal estimation approach to calibrate connected vehicles' car-following behavior in a mixed traffic environment. Particularly, the state-space system dynamics is captured by the simplified car-following model with disturbances, where the trajectory of nonconnected vehicles are considered as unknown states, and the trajectory of connected vehicles are considered as measurements with errors. The objective of the reformulation is to obtain an optimal estimation of states and model parameters simultaneously. It is shown that the customized state-space model is identifiable with the mild assumption that the disturbance covariance of the state update process is diagonal. Then, a modified expectation-maximization (EM) algorithm based on the Kalman smoother is developed to solve the optimal estimation problem. The performance of the EM algorithm is validated through simulation data. The second part of this paper applies the empirical data of connected vehicles from the Michigan test bed and analyzes the mobility impact of connected vehicles with different penetration rates and demand scenarios.

Traffic volume estimation at the city scale is an important problem useful to many transportation operations and urban applications. This paper proposes a hybrid framework that integrates both state-of-art machine learning techniques and well-established traffic flow theory to estimate citywide traffic volume. In addition to typical urban context features extracted from multiple sources, we extract a special set of features from GPS trajectories based on the implications of traffic flow theory, which provide extra information on the speed-flow relationship. Using the network-wide speed information estimated from a travel speed estimation model, a volume related high level feature is first learned using an unsupervised graphical model. A volume re-interpretation model is then introduced to map the volume related high level feature to the predicted volume using a small amount of ground truth data for training. The framework is evaluated using a GPS trajectory dataset from 33,000 Beijing taxis and volume ground truth data obtained from 4,980 video clips. The results demonstrate effectiveness and potential of the proposed framework in citywide traffic volume estimation.

Taxi service systems in big cities are immensely complex due to the interaction and self-organization between taxi drivers and passengers. An inefficient taxi service system leads to more empty trips for drivers and longer waiting time for passengers and introduces unnecessary congestion on the road network. In this paper, we investigate the efficiency level of the taxi service system using real-world large-scale taxi trip data. By assuming a hypothetical system-wide recommendation system, two approaches are proposed to find the theoretical optimal strategies that minimize the cost of empty trips and the number of taxis required to satisfy all the observed trips. The optimization problems are transformed into equivalent graph problems and solved using polynomial time algorithms. The taxi trip data in New York City are used to quantitatively examine the gap between the current system performance and the theoretically optimal system. The numerical results indicate that, if system-wide information between taxi drivers and passengers was shared, it is possible to reduce 60%-90% of the total empty trip cost depending on different objectives, and one-third of all taxis required to serve all observed trips. The existence of destructive competition among taxi drivers is also uncovered in the actual taxi service system. The huge performance gap suggests an urgent need for a system reconsideration in designing taxi recommendation systems.

Abstract Designing and optimizing traffic behavior and animation is a challenging problem of interest to virtual environment content generation and to urban planning and design. While some traffic simulation methods have appeared in computer graphics, most related systems focus on the design of buildings, roads, or cities but without explicitly considering urban traffic. To our knowledge, our work provides the first interactive approach which enables a designer to specify a desired vehicular traffic behavior (e.g., road occupancy, travel time, emissions, etc.) and the system will automatically compute what realistic 3D urban model (e.g., an interconnected network of roads, parcels, and buildings) yields the specified behavior. Our system both altered and improved traffic behavior in novel procedurally‐generated cities and in road networks of existing cities. Our urban models contain up to 360 km of roads, 300,000 vehicles, and typically cover four hours of simulated peak traffic time. The typical editing session time to “paint” a new traffic pattern and to compute the new/changed urban model is two to five minutes.

The 12 papers in this special issue focus on exploiting wireless communication technologies in vehicular traffic networks.