Deep Learning Algorithms For Short-term Ride-hailing Demand Forecasting

In recent years,ride-hailing has become more and more popular and profoundly altered the travel behavior of passengers.The ride-hailing services have various advantages compared to taxis but still suffer from the spatial and temporal imbalance between supply and demand.Online ride-hailing service platforms,such as Didi,Uber,and Lyft,provide convenient ride service via smartphone apps and accumulated a massive amount of spatial-temporal data.These data can facilitate intelligent operation and management of not only the ride-hailing service platforms but also the whole traffic system of a city.The passenger demand prediction problem is a fundamental issue for ride-hailing service platforms.By knowing ride-hailing demand in advance,the platforms can dispatch orders with more effective strategies to reduce both customer waiting time and empty vehicle cruising time.Moreover,accurate demand prediction also enables efficient dynamic pricing schemes for achieving higher platform profit.With the rapid development of electronic sensors and wireless communication technology,real-time demand prediction using the spatial and temporal data collected by internet and mobile terminals has become a research hotspot in the field of transportation.Basically,the passenger demand prediction problem,as a typical spatial-temporal prediction problem,can be divided into two sub-problems:the region-level demand prediction and the origin-destination(OD)demand prediction.The region-level demand prediction aims to predict the demand generations/attractions of each region,while the OD demand prediction attempts to forecast the demand transactions of each OD pair.For the considering of the temporal dependencies among data,traditional statistics-based methods were developed to address traffic prediction problems within certain regions(or at certain stations).However,these statistics-based methods treat each region independently and thus are not capable of capturing the spatial dependencies.In recent years,deep learning methods are increasingly being applied in transportation research and significantly improve the accuracy of many traffic prediction tasks.To date,neural network based algorithms have become the model of choice in traffic prediction problems.To model the complex spatial and temporal dependencies of the ride-hailing demand or other spatio-temporal data,various deep neural network architectures are designed by researchers.Generally,among these works,convolutional neural networks are widely adopted to extract the spatial dependencies.However,models that extract spatial dependencies rely on CNNs can only apply on regular Euclidean data,which restricts their accuracy and generalizability on the demand prediction task.To this end,some efforts have recently been made to research the application of graph neural networks(GNNs)in the traffic domain.In this paper,we develop several research works to address the unique challenges of the ride-hailing demand prediction problem in both regionlevel and OD-level based on spatial-temporal data.Firstly,to collectively forecast the ride-hailing demand in all regions of a city,many existing studies focus on the capturing of spatial and temporal correlations among regions but ignore the local statistical differences throughout the geographical layout of a city.This limits the further improvement of prediction accuracy.In this paper,we propose a new deep learning framework called Locallyconnected Spatial-Temporal Fully Convolutional Neural Network(LST-FCN)to learn the spatial-temporal correlations and capture the local statistical differences among regions.In the LST-FCN model,the 3D convolutional operations are used to extract features from the spatial and temporal dimensions simultaneously.And the locally connected convolutional layers are adopted to deal with the local statistical differences among regions.Due to the fully convolutional architecture of the LST-FCN,the spatial coordinates of regions are maintained throughout the process and no spatial information is lost between layers.Hence,the prediction error of each region can be delivered to the previous layers independently during the backpropagation training stage and optimize the corresponding training parameters of the region.We evaluate the proposed model on a real dataset from a ride-hailing service platform(DiDi Chuxing)and observe significant improvements compared with a bunch of baseline models.Besides,we further explore the working mechanism of the proposed model by visualizing its feature extraction process.The visualization results showed that our approach can better localize and capture useful features from spatial-related regions.Secondly,from the aspect of research purpose,the OD demand prediction problem is a natural extension of the region-level demand prediction problem.Despite its wider applicability,real-time OD-level prediction is much more challenging than the region-level prediction.The reasons include:(1)NonEuclidean spatial-temporal dependencies:The spatial and temporal correlations among the OD demand data cannot be straightforwardly drawn from the OD matrices.In other words,it is hard to learn meaningful correlations among the OD matrices without their graph structure;(2)Dynamic and bidirectional graph structure:The region-level demand prediction task only focuses on the dynamic attributes of nodes(e.g.demand volume)but ignores the directionality and dynamics of edges(both attributes and connections).However,in the OD demand prediction task,the demand transactions between regions are bidirectional at each time interval and dynamic change over time.This requires the learned model not only to capture the structure information of each OD graph,but also has the ability to model the evolutionary patterns of timing-varying OD graphs;(3)High sparsity:The OD demand prediction aims to forecast the demand transactions between regions,thus,given N regions of a city,there are N2 possibilities of demand transactions(OD demand matrix)that need to be predicted at each time interval.However,among the N2 demand transactions,the number of zero elements is far more than the non-zero elements.Therefore,models that only utilize the very limited observed links are not enough to reach a satisfactory performance and may be sensitive to noise.Partly due to the above difficulties inherent in the OD demand prediction problem,existing studies by-and-large focus on the region-level demand prediction.In this paper,from the graph aspects,we construct dynamic OD graphs to describe the ride-hailing demand data.We propose a novel neural architecture named the Dynamic NodeEdge Attention Network(DNEAT)to address the unique challenges of OD demand prediction from the demand generation and attraction perspectives.Different from previous studies,in DNEAT,we develop a new neural layer,named k-hop temporal node-edge attention layer(k-TNEAT),to capture the temporal evolution of node topologies in dynamic OD graphs instead of the pre-defined relationships among regions.We evaluate our model on two real-world ride-hailing demand datasets(from Chengdu,China,and New York City).The experiment results show that the proposed model outperforms six baseline models and is more robust to demand data with high sparsity.Finally,for the OD demand prediction problem,we further attempt to bridge the gaps between the graph representation learning issue and graph structure construction issue.In the past few years,to overcome the shortcomings of Convolutional Neural Network(CNN)based models in capturing non-Euclidean dependencies,several spatial-temporal graph learning approaches have been proposed to address the OD demand prediction problem.However,due to the requirements and restrictions of GNNs on graph structures,the majority of previous OD demand prediction methods have to make a compromise between the complexity of the OD transportation network and applicability of the GNN approaches.To date,the learning of graph structured data in dynamic scenarios is still challenging.Previous spatial-temporal graph-based methods are built on predefined and inflexible graph structures which can hardly reveal the instinct and dynamic dependencies of the ride-hailing demand data.In this paper,we propose a general end-to-end deep learning framework,named Dynamic Auto-structuring Graph Neural Network(DAGNN),to address the origin-destination demand prediction problem.A Dynamic Graph Decomposition and Reconstruction layer(DGDR)is developed to jointly handle both the graph structure construction and the graph representation learning problems,in which the graph representations are obtained based on a group of trainable and time-aware edge-induced subgraphs.Experimental results show that our proposed model outperforms ten baseline models on two real-world ride-hailing demand datasets and is more robust to demand data with high sparsity.Moreover,the visualization results illustrate the effectiveness of our method in terms of graph structure construction.