Dynamic Graph Convolutional Network-Based Prediction of the Urban Grid-Level Taxi Demand–Supply Imbalance Using GPS Trajectories

Abstract

The objective imbalance between the taxi supply and demand exists in various areas of the city. Accurately predicting this imbalance helps taxi companies with dispatching, thereby increasing their profits and meeting the travel needs of residents. The application of Graph Convolutional Networks (GCNs) in traffic forecasting has inspired the development of a spatial–temporal model for grid-level prediction of the taxi demand–supply imbalance. However, spatial–temporal GCN prediction models conventionally capture only static inter-grid correlation features. This research aims to address the dynamic influences caused by taxi mobility and the variations of other transportation modes on the demand–supply dynamics between grids. To achieve this, we employ taxi trajectory data and develop a model that incorporates dynamic GCN and Gated Recurrent Units (GRUs) to predict grid-level imbalances. This model captures the dynamic inter-grid influences between neighboring grids in the spatial dimension. It also identifies trends and periodic changes in the temporal dimension. The validation of this model, using taxi trajectory data from Shenzhen city, indicates superior performance compared to classical time-series models and spatial–temporal GCN models. An ablation study is conducted to analyze the impact of various factors on the predictive accuracy. This study demonstrates the precision and applicability of the proposed model.

1. Introduction

The optimal state for urban taxi services is to attain a balance between supply and demand [1]. However, due to the mobility of taxis and the randomness of travel demands, many areas within a city are in an imbalanced state most of the time [2]. For instance, some areas have an excessive taxi demand, while in other areas, the taxi supply far exceeds the demand, causing inefficiency. In order to rectify this situation, taxi companies are increasingly using intelligent algorithms for taxi dispatching [3,4]. These algorithms require precise forecasting of the demand–supply imbalance in specific areas. So, grid-level taxi demand–supply prediction [5,6,7], especially the prediction of said imbalance [8,9], has become a focal point of research. The accurate prediction of the demand–supply imbalance in specific areas is a critical consideration when it comes to making taxi dispatching decisions. It also facilitates research in various areas, such as the formulation and forecasting of taxi-based mobility [6], cruising route recommendation for vacant taxis [10], and ride-hailing services [11], among others.

The demand and supply of transportation for urban residents, including taxi services, have traditionally relied on surveys or numerical simulations [12,13]. Nonetheless, these methods present issues with reliability and timeliness. With the widespread use of GPS devices, a significant number of taxis outfitted with GPS systems traverse the city’s road networks, gathering trajectory data that depict aspects of urban traffic operations, such as the traffic flow, speed, and density [14]. The GPS systems of most city taxis can trace information such as the vehicle ID, location coordinates, and time, as well as whether the vehicle is occupied [15,16,17]. This presents opportunities for analyzing demand and supply in terms of taxi travel, offering potential solutions to the accuracy and timeliness issues previously faced.

Grid-level taxi demand and supply demonstrate unique characteristics in the temporal and spatial dimensions, similar to traffic flow parameters like the volume and speed [18]. On the one hand, temporal trend features are present in traffic flow parameters, making them predictable via time-series models, and the same does hold true for grid-level taxi demand and supply. Various modeling approaches exist for traffic forecasting, such as early methods like AR (Autoregressive Models) [19], MA (Moving Average Models) [20], and ARIMA (Auto-Regressive Integrated Moving Average Models) [21]. These models convert time-series data into stationary sequences and then establish a mathematical model to predict future values. However, these models perform poorly when modeling data that exhibit pronounced periodicity, and the intricate periodicity of traffic flows limits the applicability of these models in the domain of traffic prediction. In recent years, numerous machine-learning models have emerged that have shown improved performance in predicting time-series data. RNN (Recurrent Neural Network) [22], LSTM (Long Short-Term Memory) [23], GRU (Gated Recurrent Unit) [24], and Transformer [25] are some such models. These models effectively capture the trend and periodicity characteristics of the traffic flow in the time dimension, resulting in excellent predictive performance.

On the other hand, traffic flow displays detectable spatial correlations in the spatial dimension due to geographical and road connectivity features. This implies that time-series models alone cannot predict the traffic flow with precision. A significant number of deep-learning prediction models have been developed based on the GCN (Graph Convolutional Network) model [26], capable of capturing the spatiotemporal characteristics of traffic flow. For instance, several models have arisen within this context, including T-GCN [27], GAMCN [28], DDP-GCN [29], KST-GCN [30], and TPP-GCN [31]. These models generally take into account only the fixed correlations between vertices while executing spatial convolution operations, such as adjacency relationships [27], distance [30], and attribute correlations between vertices [31]. However, even in adjacent grids, the connections between them can be intricate due to variances in taxi trip origins and destinations. As an illustration, in Figure 1, Grid A and Grid B both belong to residential areas. When the subway operates during its hours of operation, the taxi demand in Grid B surpasses that in Grid A. Nevertheless, when the subway service concludes at night, the taxi demand in both areas tends to equalize. Moreover, Grid C and Grid D exhibit comparable taxi demand on weekdays owing to the presence of schools and hospitals. However, on weekends, when the schools are off, the demand for taxis in Grid C notably decreases in contrast to Grid D.

To tackle these issues, a model for forecasting the taxi demand–supply imbalances at the level of the grid is proposed. A dynamic graph convolutional network is designed to capture the dynamic spatial characteristics between grids. The correlations between the grids can be dynamically computed to form a graph by sliding a window of T time periods along the temporal dimension, as illustrated in Figure 2. The edges of graph $G^t$ during time period $t$ are determined by the attribution correlations between the grids from time period $t-T$ to $t$, and so on. Subsequently, we employ a GRU to uncover the temporal characteristics of the taxi supply and demand. We then establish a correlation between the taxi supply and demand, and the mismatch within the grids to predict the current mismatch. We validate our model utilizing taxi trajectory data from Shenzhen city and examine the effect of involved hyperparameters. The key contributions of this paper are summarized below:

• A spatial–temporal graph convolution model that integrates GCN and GRU is proposed, which can accurately forecast the taxi demand–supply imbalance at the grid level. It not only reflects the temporal trends and periodicity of the taxi demand–supply in the time dimension but also captures the interplay of the taxi demand–supply imbalance among different grids.
• A dynamic graph convolutional network is developed to capture the dynamic spatial features between grids. The correlations between grids are evident and vary substantially in different time periods, such as daytime and nighttime, weekdays and weekends, and so on. By capturing these variable influences, the taxi demand–supply can be predicted more accurately.
• Experiments are carried out utilizing real taxi trajectory data from Shenzhen city to validate the feasibility and accuracy of the proposed model. The experiments contrast the suggested model with other existing spatial–temporal graph convolutional models. In addition, the impact of the hyperparameters involved in the model on real-world scenarios are also discussed, providing a reference for the practical application of the model.

The structure of this paper is as follows. Section 2 provides a comprehensive review of the research related to this paper. Section 3 introduces the relevant definitions and explanations, while Section 4 presents the forecasting model of the grid-level taxi demand-supply imbalance, including a breakdown of each component and its overall structure. Section 5 presents the experimental data required for validating the model alongside a comparison of the obtained results with those from other models. Following this, a discussion is provided. Lastly, a comprehensive summary is presented.

2. Related Studies

In this section, we firstly review the related works concerning urban taxi services, and then we review the related work from two perspectives: deep-learning neural network-based methods and complex deformable graph convolutional network-based methods.

2.1. Related Works Concerning Urban Taxi Services

The increasing use of GPS devices in modern cities has led to the emergence of intelligent applications aimed at improving or transforming taxi services [32]. For instance, modeling the location choice of taxi drivers for passenger pickup using GPS data [33], discussing how informal transport can be better understood using GPS tracking data [34], modeling the spatial–temporal of yellow taxi demands in New York City using generalized STAR models [35], etc. With the support of data, this sentence highlights the potential for data-driven methodologies in the field of taxi services. For instance, forecasting residents’ taxi travel demand can be achieved using traditional time-series models such as ARMA and Linear Regression [36], using deep-learning methods such as reinforcement learning to minimize taxi idle times [37], etc. The use of these technologies is leading research in urban taxi services toward data-driven approaches and the ongoing development and application of deep learning.

2.2. Deep-Learning Neural Network-Based Methods

Taxi demand–supply data are a specific type of traffic flow data. Therefore, most methods suitable for traffic flow prediction can also be used for predicting taxi demand–supply data. As traffic flow data are a type of time-series data, researchers have long been using traditional time-series models for prediction, such as HA (Historical Average Model) [38], Kalman Filters [39], ARIMA [15] and its variants [40]. These models convert time-series data into stationary sequences and then build mathematical models to predict future values, which have proven to perform well.

The early time-series models mentioned above have limited suitability for data with strong periodic and trending patterns. Traffic flow data exhibit strong trending and periodic patterns, making these models increasingly less appropriate. With the application of deep learning, models such as RNN [16], LSTM [17], GRU [18] and their variants [41,42] have proven to better capture the changing characteristics of traffic flow data in the time dimension, leading to improved prediction results.

In recent years, an increasing number of studies have focused not only on capturing the changing characteristics of traffic flow data in the time dimension but also on considering the mutual influences between adjacent roads and neighboring areas in the spatial dimension. Some of the earliest attempts have used CNN (Convolutional Neural Network) models [43,44,45] to capture the spatial characteristics of traffic flow. However, urban road networks and regions within the city have unique connectivity and uneven distribution, so the CNN model, which excels at exploring spatial features based on Euclidean distances [46,47], faces limitations in the field of grid-level traffic flow prediction. The GCN model, on the other hand, is better at extracting spatial features from non-Euclidean distance data [27,48]. This has led to a considerable amount of research focusing on combining GCN models with temporal models for traffic prediction. For example, there are models such as the ride-hailing demand forecasting model [49], which combines GCN and LSTM, and the T-GCN model [27], which integrates GCN and GRU. These models have been widely researched and applied due to their outstanding predictive performance.

2.3. Complex Deformable Graph Convolutional Network-Based Methods

However, traditional graph convolutional neural networks, which focus primarily on considering the influence between adjacent nodes (such as road segments, networks, or regions), quickly become inadequate for predicting some complex traffic flows, such as predicting traffic speed in non-grid road networks [29], predicting traffic propagation flow [31], predicting road network traffic density [50], and so on. Consequently, many methods based on complex deformable graph convolutional networks have emerged [43]. These methods can be broadly categorized into static graph-based approaches and dynamic graph-based approaches.

A static graph means that its structure does not change over time. The early graph convolutional neural network-based traffic prediction models considered only the influence between adjacent vertices. Later, various spatial–temporal prediction models with more complex graph structures were developed. These graphs include those that consider the upstream–downstream relationships of road segments [31], angles between adjacent roads [29], attribute correlations between adjacent regions [48], and geographic features within regions [30]. These complex deformable graphs are calculated based on the historical attribute or geographic information associated with the vertices and do not change over time. Furthermore, these graphs are used in conjunction with the original adjacency graph for either sequential or parallel convolutions that enrich the spatial feature extraction. The results have shown that these prediction models outperform models that only perform convolution operations on the adjacency graph.

A dynamic graph means that its structure changes over time. As outlined in the introduction, adjacent grids display dynamic correlations in their taxi demand. It is probable that the correlation is strong during particular time periods on the same day, but weak during others. Additionally, the correlation can fluctuate greatly from one day to the next. Therefore, a number of scholars have initiated investigations into traffic flow prediction models using dynamic graph convolutional networks. Such investigations have resulted in various models, including a reinforced dynamic graph convolutional network model for network-wide traffic flow prediction [51], an attention-based spatial–temporal graph neural network for long-term traffic prediction [52], a new dynamic correlation graph construction method for specific location traffic flow prediction [53], etc. However, these studies primarily use dynamic graph convolution to capture dynamic spatial features at a single-point level or link level [51,52,53,54], with limited focus on grid-level research. Moreover, these studies are geared toward predicting general traffic flow, while the grid-level taxi demand exhibits higher randomness and variability, making it challenging to apply these models.

In summary, there is presently no predictive model that can effectively capture the spatial and dynamic characteristics of the taxi demand–supply imbalances at a grid level, which are caused by the unpredictability and variability of taxis. This study proposes a forecasting model for grid-level taxi demand–supply imbalances that employs dynamic graph convolutional networks to address these challenges.

3. Preliminaries

Table 1. Notations.

Notation	Description
${\mathcal{T}}^a$	A type a trajectory where the vehicle consistently remains in a “vacant” state.
${\mathcal{T}}^b$	A type b trajectory where the vehicle consistently remains in an “occupied” state.
${\mathcal{T}}^c$	A type c trajectory where the vehicle transitions from a “vacant” state to an “occupied” state.
${\mathcal{T}}^d$	A type d trajectory where the vehicle transitions from an “occupied” state to a “vacant” state.
$I_t^g$	The grid-level taxi demand–supply imbalance $I_t^g$ within grid $g$ in time period $t$.
${\widetilde{{\mathcal{T}}^a}}_t^g$	The sum of the type a trajectories crossing the grid $g$ in time period $t$.
${\widetilde{{\mathcal{T}}^c}}_t^g$	The sum of the type c trajectories crossing the grid $g$ in time period $t$.
${\widetilde{{\mathcal{T}}^d}}_t^g$	The sum of the type d trajectories crossing the grid $g$ in time period $t$.
$G〈V,E〉$	A general graph, where $V$ represents the nodes in the graph, and $E$ represents the relationships between the nodes.
$\mathcal{G}〈G,R〉$	The taxi demand–supply graph.
$G$	The set of the grids $\left\{g1,g2,\dots ,gn\right\}$.
$R$	The set of the relationships $\left\{r1,r2,\dots ,rm\right\}$ between grids in the graph.
$X_{t~t+T}^g$	The feature vector of grid $g$.
$X_{ }^g$	The traffic demand $D^g$ or the traffic supply $S^g$ of grid $g$.
${\overline{X}}_t$	The spatial features within the grid $g$ in time period $t$.
${\overline{D}}_t$	The spatial features of the travel demand within the grid $g$ in time period $t$.
${\overline{S}}_t$	The spatial features of the travel supply within the grid $g$ in time period $t$.
$gc(\cdot )$	The graph convolution.
$gru(\cdot )$	The processing using the GRU model.
${\widehat{D}}_t$	The temporal features of the travel demand within the grid $g$ in time period $t$.
${\widehat{S}}_t$	The temporal features of the travel supply within the grid $g$ in time period $t$.
${\widehat{I}}_t^G$	The predicted taxi demand–supply imbalance within the grid $g$ in time period $t$.
${\mathcal{I}}_{t+1~t+T}^G$	The taxi demand–supply imbalance of all the grids in all the time periods.

lists all the symbols used in this paper.

3.1. Taxi Demand–Supply Information within a Grid

Taxi trajectories are typically categorized into four types, as shown in Figure 3: (a) type a trajectory ${\mathcal{T}}^a$ where the vehicle consistently remains in a “vacant” state; (b) type b trajectory ${\mathcal{T}}^b$ where the vehicle consistently remains in an “occupied” state; (c) type c trajectory ${\mathcal{T}}^c$ where the vehicle transitions from a “vacant” state to an “occupied” state, and the initial appearance of an “occupied point” signifies passengers boarding the taxi; and (d) type d trajectory ${\mathcal{T}}^d$ where the vehicle transitions from an “occupied” state to a “vacant” state and the first appearance of a “vacant point” represents passengers disembarking.

The trajectories of these four types of taxis crossing the grid can reflect the traffic demand–supply information within the grid. As shown in Figure 3e, a type a trajectory ${\mathcal{T}}^a$ crossing the grid can be considered a traffic supply within the grid. A type c trajectory ${\mathcal{T}}^c$ crossing the grid represents not only a taxi demand but also a taxi supply in the grid, as in Figure 3g. A type d trajectory ${\mathcal{T}}^d$ crossing the grid can be considered an added traffic supply in the grid, as in Figure 3h.

Therefore, the taxi demand within the grid can be defined as the quantity of type c trajectories crossing the grid. Meanwhile, the taxi supply within the grid can be defined as the sum of the type a trajectories, type c trajectories, and type d trajectories crossing the grid. The grid-level taxi demand–supply imbalance $I_t^g$ within grid $g$ in time period $t$ can be defined as

$$I_t^g=\frac{{\widetilde{{\mathcal{T}}^c}}_t^g}{{\widetilde{{\mathcal{T}}^a}}_t^g+{\widetilde{{\mathcal{T}}^c}}_t^g+{\widetilde{{\mathcal{T}}^d}}_t^g}$$

(1)

in which ${\widetilde{{\mathcal{T}}^a}}_t^g$, ${\widetilde{{\mathcal{T}}^c}}_t^g$ and ${\widetilde{{\mathcal{T}}^d}}_t^g$ are the sum of the type a trajectories, type c trajectories, and type d trajectories crossing the grid $g$ in time period $t$, respectively, and $I_t^g$ ranges from 0 to 1. When the taxi demand-supply imbalance is equal to 0, it implies that the number of type c trajectories is 0, while there are a significant number of type a trajectories and type d trajectories. This means that during this time period, there is minimal taxi demand within the grid, and taxis should be dispatched to other areas.

When the taxi demand–supply imbalance approaches 1, it means that the proportion of type c trajectories is increasing, while the proportion of type a and type d trajectories is decreasing. This indicates that during this time period, the taxi demand within the grid is becoming increasingly challenging to meet, and taxis need to be dispatched to this area.

3.2. Graph of the Taxi Demand–Supply Based on Divided Grids

$G〈V,E〉$ can be defined as a general graph, where V represents the nodes in the graph, and E represents the relationships between the nodes. In this paper, we define the taxi demand–supply graph as $\mathcal{G}〈G,R〉$, where $G$ represents the set of the grids $\left\{g1,g2,\dots ,gn\right\}$, and $R$ is the set of the relationships $\left\{r1,r2,\dots ,rm\right\}$ between grids in the graph.

For each grid $g$,we can obtain its feature vector $X_{t~t+T}^g=\left[X_t^g,X_{t+1}^g,\dots ,X_{t+T}^g\right]$, where the feature $X_{ }^g$ can be the traffic demand $D^g$ or the traffic supply $S^g$ within the grid. And the feature matrix ${\mathcal{X}}_{t~t+T}^G=\left\{X^{g1},X^{g2},\dots ,X^{gn}\right\}$ can be obtained for all the grids.

In addition, for each pair of girds $g_i$ and $g_j$ ($i,j\le n$), the relationship between them falls into two categories in most studies [30,31]. The first category involves considering the spatial topology between grids, typically measured using distance. The second category measures the similarity between features within two grids. As shown in Figure 4a, for a 3× grid region, it is possible to construct graphs based on the effective grids A, B, E, F, and G.

The first kind of graph formed is illustrated in Figure 4b, where the distances between A and B, B and E, and E and F are all equal to the length of the grid, while the remaining distances are greater than this value. For grid pairs with smaller distances, wider edges are assigned to represent a higher likelihood of mutual influence between them. The second kind of graph formed is illustrated in Figure 4c, where A, E, and G exhibit high feature correlations, and B and F also display high feature correlations. Grid pairs with greater feature correlations are assigned wider edges to represent their high likelihood of changing simultaneously. We will discuss in detail how to quantify these two types of relationships in Section 4.2 to better predict the grid-level taxi demand–supply imbalance.

3.3. Prediction of the Grid-Level Taxi Demand–Supply Imbalance

In this article, we use predictions of the future traffic demand and supply to predict the taxi demand–supply imbalance within the grid. This mainly consists of three steps:

Step 1 in the spatial dimension, spatial features within the grid ${\overline{X}}_{t-T’},{\overline{X}}_{t-T’+1},\dots ,{\overline{X}}_t$ are computed using graph convolution, as shown in the following equation.

$${\overline{X}}_{t-T’},{\overline{X}}_{t-T’+1},\dots ,{\overline{X}}_t=gc\left(X_{t-T’},X_{t-T’+1},\dots ,X_t\right)$$

(2)

where $gc(\cdot )$ represents the graph convolution. The features within the grid discussed in this article mainly refer to the traffic demand and supply, which are represented by the following two equations.

$${\overline{D}}_{t-T’},{\overline{D}}_{t-T’+1},\dots ,{\overline{D}}_t=gc\left(D_{t-T’},D_{t-T’+1},\dots ,D_t\right)$$

(3)

$${\overline{S}}_{t-T’},{\overline{S}}_{t-T’+1},\dots ,{\overline{S}}_t=gc\left(S_{t-T’},S_{t-T’+1},\dots ,S_t\right)$$

(4)

Step 2 in the temporal dimension, we use the GRU model to predict the future traffic demand ${\widehat{D}}_{t+1},{\widehat{D}}_{t+2},\dots ,{\widehat{D}}_{t+T}$ and supply ${\widehat{S}}_{t+1},{\widehat{S}}_{t+2},\dots ,{\widehat{S}}_{t+T}$ from time period $t+1$ to $t+T$ based on the spatial features, as represented by the following two equations.

$${\widehat{D}}_{t+1},{\widehat{D}}_{t+2},\dots ,{\widehat{D}}_{t+T}=gru\left({\overline{D}}_{t-T’},{\overline{D}}_{t-T’+1},\dots ,{\overline{D}}_t\right)$$

(5)

$${\widehat{S}}_{t+1},{\widehat{S}}_{t+2},\dots ,{\widehat{S}}_{t+T}=gru\left({\overline{S}}_{t-T’},{\overline{S}}_{t-T’+1},\dots ,{\overline{S}}_t\right)$$

(6)

Step 3 Using the predicted demand and supply, along with the historical demand and supply, the predicted taxi demand–supply imbalance within the grid ${\widehat{I}}_{t+1}^g$ can be obtained, as indicated by the following equation.

$${\widehat{I}}_{t+1}=f\left({\widehat{D}}_{t+1},{\widehat{S}}_{t+1},\left(D_{t-T’},D_{t-T’+1},\dots ,D_t\right),\left(S_{t-T’},S_{t-T’+1},\dots ,S_t\right)\right)$$

(7)

and then, the taxi demand–supply imbalance of all the grids in all the time periods can be obtained as follows:

$${\mathcal{I}}_{t+1~t+T}^G=\left\{\left\{{\widehat{I}}_{t+1}^{g1},\dots ,{\widehat{I}}_{t+T}^{g1}\right\},\left\{{\widehat{I}}_{t+1}^{g2},\dots ,{\widehat{I}}_{t+T}^{g2}\right\},\dots ,\left\{{\widehat{I}}_{t+1}^{gn},\dots ,{\widehat{I}}_{t+T}^{gn}\right\}\right\}$$

(8)

4. Methodology

4.1. Overall Structure

Figure 5 depicts the spatial–temporal prediction network introduced in this paper. The left side of the diagram shows the prediction of the grid-level features using graph convolution and time-series forecasting. This process involves two rounds of graph convolution and one round of GRU prediction. The initial graph convolution utilizes the static grid relationships, which are the distances between grids. The second graph convolution exploits the dynamic grid relationships and considers the correlations of grid features during previous time periods. A GRU model predicts the future attribute values within the grid for the following T time periods. On the right side of Figure 5, a forecast of the grid-level taxi demand–supply imbalance for time period $t+1$ is presented. This part first predicts the taxi demand ${\widehat{D}}_{t+1}$ and supply ${\widehat{S}}_{t+1}$, and then combined them with historical data $D_{t-1},D_t$ and $S_{t-1},S_t$ to forecast the demand–supply imbalance $I_{t+1}$ for time period $t+1$.

4.2. Graph Convolutional Network Part

4.2.1. Geographic Graph

According to Tobler’s First Law of Geography [55], grids that are closer in geographical location exhibit stronger spatial correlations. Additionally, traffic flow naturally exhibits a propensity to propagate more readily between adjacent grids [31]. Therefore, the primary consideration when mining spatial correlations between grids is the distance between them. Hence, we define the geographical adjacency matrix as $A^{Geo}$, and each element $a_{ij}^{Geo}$ can be calculated as follows:

$$a_{ij}^{Geo}=\left\{\begin{array}{cc}1& d_{eu}\left(gi,gj\right)\le \mu \\ 0& otherwise\end{array}\right.$$

(9)

where $d_{eu}\left(gi,gj\right)$ is the Euclidean distance between grid $gi$ and grid $gj$, and $\mu$ is the distance threshold to pick out the closer grids. In this paper, we only consider the influence between adjacent grids, and thus the value of $\mu$ is set to $\sqrt{2}\cdot l$, where $l$ represents the side length of a grid. As shown in Figure 3, to calculate the spatial features of grid E, only the influences of the eight adjacent grids, A, B, C, D, F, G, H, and I, are considered, while other grids that are farther away are not within the scope of consideration.

4.2.2. Dynamic Feature Correlation Graph

Considering the correlation of vertex features in graph construction has become one of the hot topics in graph convolution research [43]. In this paper, we investigate the travel features within a grid, which exhibit certain distribution patterns over time. For example, residential areas have a high taxi demand during the morning rush hour but a lower demand during the evening rush hour, whereas commercial areas show the opposite pattern. Setting larger connection weights for grids with similar traffic travel patterns enables them to mutually complement information during the convolution process.

Furthermore, traditional research has only considered the static correlations of features within the grids, which is not accurate enough [56,57]. This is because the geographical features within the grids are complex, and travel patterns exhibit strong randomness, such that two grids with high daytime correlation may have different patterns at night. Thus, it is necessary to consider the dynamic correlations and establish a dynamic feature correlation graph. Based on this, the present paper defines the dynamic feature correlation matrix as $A_{ij}^{Dyn.t},A_{ij}^{Dyn.t+1},\dots ,A_{ij}^{Dyn.t+T}$. Taking the matrix $A_{ij}^{Dyn.t}$ for time period $t$ as an example, each element is defined as follows:

$$a_{ij}^t=\left\{\begin{array}{cc}\frac{\rho \left(X_{gi}^{t-T~t},X_{gj}^{t-T~t}\right)+1}{2}& a_{ij}^{Geo}\ne 0\\ 0& otherwise\end{array}\right.$$

(10)

where $\rho \left(X_{gi}^{t-T~t},X_{gj}^{t-T~t}\right)$ represents the Pearson correlation coefficient between the feature vector $\left[X_{gi}^{t-T},X_{gi}^{t-T+1},\dots ,X_{gi}^t\right]$ of grid $gi$ and the feature vector $\left[X_{gj}^{t-T},X_{gj}^{t-T+1},\dots ,X_{gj}^t\right]$ of grid $gj$, which is calculated as follows:

$${\rho }_{ij}^{t-T~t}=\frac{{\displaystyle \sum _{t^{\prime }=1}^T\left(X_i^{t^{\prime }}-{\overline{X}}_i^{t-T~t}\right)\left(X_j^{t^{\prime }}-{\overline{X}}_j^{t-T~t}\right)}}{\sqrt{{\displaystyle \sum _{t^{\prime }=1}^T{\left(X_i^{t^{\prime }}-{\overline{X}}_i^{t-T~t}\right)}^2\times {\displaystyle \sum _{t^{\prime }=1}^T{\left(X_j^{t^{\prime }}-{\overline{X}}_j^{t-T~t}\right)}^2}}}}$$

(11)

$${\overline{X}}_i^{t-T~t}=\frac{X_i^{t-T}+X_i^{t-T+1}+\dots +X_i^t}{T+1}$$

(12)

$${\overline{X}}_j^{t-T~t}=\frac{X_j^{t-T}+X_j^{t-T+1}+\dots +X_j^t}{T+1}$$

(13)

It is important to note that the value of $a_{ij}^t$ falls within the range [0, 1], and the higher its value, the more it signifies that feature predictions between two grids can be mutually influential, leading to a greater impact during the graph convolution process. Additionally, $a_{ij}^t$ is a dynamic variable, signifying that the feature correlation graph is subject to dynamic changes.

4.2.3. Graph Convolution Layer

For the travel features within the grids, two graph convolution layers are designed to perform spatial feature extraction operations twice. In the first convolution, it is based on the geographic graph, and it filters the influence between adjacent grids. The output of this convolution layer $H^{\left(Geo\right)}$ is defined as follows:

$$H^{\left(Geo\right)}=\tau \left({\widetilde{D^{Geo}}}^{-1/2}\widehat{A^{Geo}}{\widetilde{D^{Geo}}}^{-1/2}X{\theta }^{\left(Geo\right)}\right)$$

(14)

where $\tau \left(\cdot \right)$ is the activation function, $\widetilde{D^{Geo}}$ is the degree matrix of the geographic graph, and $\widehat{A^{Geo}}$ is the sum of geographical adjacency matrix $A^{Geo}$ (defined as Equation (8)) and identity matrix. $X$ is the input travel feature matrix, which can be either the traffic demand $D$ or traffic supply $S$. ${\theta }^{\left(Geo\right)}$ is the set of all the parameters of this convolution layer.

The second convolution layer is based on the dynamic feature correlation graph, with its input being the output from the first convolutional layer $H^{\left(Geo\right)}$. Its output $H^{\left(t\right)}$ is defined as follows:

$$H^{\left(t\right)}=\tau \left({\widetilde{D^t}}^{-1/2}\widehat{A^t}{\widetilde{D^t}}^{-1/2}{H}^{\left(Geo\right)}{\theta }^{\left(t\right)}\right)$$

(15)

where $H^{\left(t\right)}$ represents the output of the second convolution layer during time period $t$, $\widetilde{D^t}$ is the degree matrix of the feature correlation graph during $t$, $\widehat{A^t}$ is the sum of feature correlation matrix $A^t$ during t (defined as equation 9) and identity matrix, and ${\theta }^{\left(t\right)}$ represents all the parameters of the second convolution layer.

4.3. Gated Recurrent Unit Part

After extracting the spatial features of the taxi demand and supply within the grids, it is also necessary to capture the features in the temporal dimension. The Gated Recurrent Unit model is applied to accomplish this task. The GRU model is widely used and has been proven to have significant advantages in terms of predictive accuracy [42], mitigating gradient disappearance and explosion problems [58].

Given the feature sequence $H^{\left(t-T’\right)},\dots ,H^{\left(t-1\right)},H^{\left(t\right)}$ after 2 rounds of graph convolution operations, it is possible to recursively predict future the taxi demand and supply using Equations (12)–(15).

$$r_t=\sigma \left(W_r\left[H^{\left(t\right)},h_{\left(t-1\right)}\right]+b_r\right)$$

(16)

$$z_t=\sigma \left(W_u\left[H^{\left(t\right)},h_{\left(t-1\right)}\right]+b_u\right)$$

(17)

$${\tilde{h}}_t=tanh\left(W_{\tilde{h}}\left[H^{\left(t\right)},(r_t\odot h_{\left(t-1\right)})\right]+b_{\tilde{h}}\right)$$

(18)

$$h_t=z_t\odot h_{\left(t-1\right)}+\left(1-z_t\right)\odot {\tilde{h}}_t$$

(19)

where $\sigma \left(\cdot \right)$ is the sigmoid activation function, $h_{\left(t-1\right)}$ is the outer hidden state during $t-1$, ${\tilde{h}}_t$ is the inner hidden state during $t$, $W_r$, $W_u$ and $W_{\tilde{h}}$ are the weight sets, $b_r$, $b_u$ and $b_{\tilde{h}}$ are the biases, $\odot$ represents the dot product between two tensors, and all the the weights and biases are learnable.

4.4. Full Connected Layer

After two rounds of graph convolution operations and one round of prediction using the GRU model, we can obtain the taxi demand ${\widehat{D}}_{t+1}$ and supply ${\widehat{S}}_{t+1}$ for time period $t+1$, respectively. This allows us to calculate the taxi demand–supply imbalance for this time period, i.e., ${\widehat{D}}_{t+1}/{\widehat{S}}_{t+1}$, as described in Section 3.1. However, to mitigate the short-term random fluctuations in urban traffic, we apply smoothing to it using the values from the past two time periods.

In the final part of the model, as shown in Figure 4, we establish a fully connected layer to map the taxi demand–supply imbalance ${\widehat{I}}_{t+1}$ to the taxi demand vector $\left({\widehat{D}}_{t+1},D_t,D_{t-1}\right)$ and taxi supply vector $\left({\widehat{S}}_{t+1},S_t,S_{t-1}\right)$, i.e., ${\widehat{I}}_{t+1}\sim fc\left(\left({\widehat{D}}_{t+1},D_t,D_{t-1}\right),\left({\widehat{S}}_{t+1},S_t,S_{t-1}\right)\right)$, to facilitate training and forecasting.

5. Experiment

5.1. Data Description

The dataset used in this article is the real taxi GPS data from Shenzhen, China, including the date, time, taxi ID, longitude, latitude, and passenger status (vacant or occupied). The data were collected in January 2019 and processed to obtain nearly 88.62 million taxi trajectories. Furthermore, we opted for Futian District in Shenzhen city as the experimental area. Futian District lies in the heart of Shenzhen, stretching 10 km in a north–south direction and 12 km in an east–west direction. It spans nearly 80 square kilometers, as depicted in Figure 6.

We perform the following data preprocessing to meet the experimental requirements. (1) Based on the longitude, latitude, and passenger occupancy information contained in the taxi GPS data, we compute four types of trajectories, as illustrated in Figure 3, namely, type a trajectory ${\mathcal{T}}^a$, type b trajectory ${\mathcal{T}}^b$, type c trajectory ${\mathcal{T}}^c$, and type d trajectory ${\mathcal{T}}^d$. (2) We grid the entire experimental area according to the 1 km × 1 km standard, and then select 10 min as the minimum statistical time period. Therefore, a total of 102 grids and 4464 periods can be obtained. (3) Based on this, we count the type a trajectory ${\mathcal{T}}^a$, type b trajectory ${\mathcal{T}}^b$, and type d trajectory ${\mathcal{T}}^d$ in each grid in each period. Further statistical analysis reveals that the average number of valid taxi trajectories in each grid within a single period is 215, and the number of type a, type c, and type d trajectories is 118, 50, and 47, respectively. (4) According to Formula 1, we compute the dataset of the imbalance index for taxi demand–supply across all the grids and all the time periods. (5) In the end, the data from the first 21 days of January 2019 are utilized as the training set, while the remaining 10 days’ data serve as the testing set.

5.2. Baseline Methods

We select several classic prediction models to compare with our model, including the Historical Average (HA), Auto-Regressive Moving Average (ARIMA), Graph Convolutional Network (GCN), Gated Recurrent Unit model (GRU), Temporal Graph Convolutional Network (T-GCN), Temporal Multi-Spatial Dependence Graph Convolutional Network (TmS-GCN) [48], and Multi-Attribute Graph Convolutional Network (MAGCN) [59].

5.3. Results

To evaluate the predictive performance of our model and the baseline models, we use metrics such as the Mean Absolute Error (MAE), Mean Absolute Percentage Error (MAPE) and Root Mean Square Error (RMSE):

$$MAE\left(I,\widehat{I}\right)=\frac{1}{\mathcal{N}}{\displaystyle \sum _i^{\mathcal{N}}\left|I_i-{\widehat{I}}_i\right|}$$

(20)

$$MAPE\left(I,\widehat{I}\right)=\frac{1}{\mathcal{N}}{\displaystyle \sum _i^{\mathcal{N}}\frac{\left|I_i-{\widehat{I}}_i\right|}{I_i}}$$

(21)

$$RMSE\left(I,\widehat{I}\right)=\sqrt{\frac{1}{\mathcal{N}}{\displaystyle \sum _i^{\mathcal{N}}{\left(I_i-{\widehat{I}}_i\right)}^2}}$$

(22)

where $I$ and $\widehat{I}$ are the actual and predicted values of the taxi supply–demand imbalance, respectively, and $\mathcal{N}$ is the number of predictions.

Table 2. Comparison of the performance of the different models across temporal scales.

Models	Metrics
	10 min			20 min			30 min
	MAE	MAPE	RMSE	MAE	MAPE	RMSE	MAE	MAPE	RMSE
HA	0.0476	1.5375	0.0769	0.0476	1.5375	0.0769	0.0476	1.5375	0.0769
ARIMA	0.0902	0.5552	0.1108	0.0928	0.7627	0.1066	0.0980	1.3971	0.1225
GCN	0.0462	0.3286	0.0728	0.0473	0.3373	0.0736	0.0483	0.3463	0.0745
GRU	0.0439	0.2902	0.0678	0.0443	0.3072	0.0743	0.0446	0.3159	0.0853
T-GCN	0.0428	0.2826	0.0669	0.0439	0.2792	0.0684	0.0441	0.2867	0.0684
TmS-GCN	0.0431	0.2845	0.0680	0.0433	0.2880	0.0695	0.0441	0.2865	0.0692
MAGCN	0.0421	0.2812	0.0653	0.0453	0.2881	0.0702	0.0462	0.2907	0.0713
our model	0.0413	0.2716	0.0643	0.0425	0.2855	0.0659	0.0438	0.2932	0.0672

presents the results of evaluating our model and the baseline models on the dataset described in Section 5.1. We can draw the following conclusions:

• The overall predictive performance of deep-learning models is much better than traditional time-series models, which aligns with our expectations. This indicates that the grid-level taxi demand–supply exhibits nonlinear periodicity over time, a feature that traditional time-series models are unable to capture.
• Predictive models that comprehensively consider the spatial correlation of the taxi demand–supply and temporal variation features, including T-GCN and our model, outperform time-series models such as HA, ARIMA, and GRU. They also outperform models that only consider spatial correlation features, such as GCN. This indicates that the grid-level taxi demand–supply imbalance is also a typical spatial correlation data, with neighboring grids influencing each other.
• Our model, which considers the dynamic correlation features between grids, outperforms T-GCN, TmS-GCN and MAGCN, which only consider static spatial features. This confirms our hypothesis stated in the introduction that the influences on the taxi demand and supply vary over time, even among adjacent grids. The impact is sometimes significant and at other times minimal.

We carry out the comparison between the actual and predicted taxi demand–supply imbalance during specific time periods on January 23rd, including the morning peak hours (7:30–9:30 am), daytime (9:30 am–4:30 pm), and evening peak hours (4:30–7:30 pm). The results are shown in Figure 7. The figure shows that the majority of the grid cells have an imbalance value of 0.6 or less, which means that the demand for taxi rides is less than half of the available supply of taxis. This is due to the use of only taxi GPS data to estimate both the demand and supply. If separate data sources were available to track taxi demand, such as order data from DiDi or Uber, this imbalance information could be more accurately determined. However, this does not affect our evaluation of the model. From this, we can draw the following conclusions:

• Based on the imbalance index, it is divided into five categories, namely [0, 0.2], [0.2, 0.4], [0.4, 0.6], [0.6, 0.8], and [0.8, 1.0], where the closer the value is to 1, the more difficult the demand is to meet. Based on this, the number of grid cells with prediction errors during the morning peak, daytime, and evening peak is 7, 7, and 10, respectively, accounting for only 6.86%, 6.86%, and 9.8%.
• From the figure, it is noticeable that within certain areas, the imbalance between the taxi demand and supply changes from morning to evening. For example, within the area highlighted by the solid red ellipse in the figure, there is a pronounced imbalance during the morning peak hours, while it tends to stabilize during the midday and evening peak hours.
• We further analyze the grid cells with prediction errors, particularly those within the green dashed box during the morning peak hours. In this particular grid, there is a significant discrepancy between the predicted results and the ground truth. The grid corresponds to the area of Meilin Mountain Park, which is characterized by few roads and a low traffic volume, resulting in an average number of taxi trajectories within the grid mostly below 10 during most periods. Grids with a low number of trajectories are bound to affect the predictive accuracy. We will specifically discuss this issue in Section 6.2.

Taxi companies or other city traffic management authorities can use the model’s predicted results to proactively conduct taxi dispatching, which includes short-term scheduling and long-term allocation strategies:

• For short-term scheduling, when taxi companies or other city traffic management authorities become aware of an expected demand–supply imbalance in a specific grid, they can proactively dispatch information to available taxis in the surrounding grids, urging them to support that particular grid. This approach aims to address the upcoming imbalance within the grid. Based on our model, we predict the specific travel demand and supply within each grid in addition to the imbalance index. This information can help taxi companies and city traffic management authorities determine the number of taxis needing to be redirected, preventing an excess supply over demand within the grid and avoiding wastage of resources.
• For long-term allocation, when a particular area is expected to have an imbalance between the taxi demand and supply in the next half-hour, or even within an hour, it means that residents attempting to hail a taxi within this area during this time may face difficulties and delays. Upon receiving this predictive information, taxi companies or other city traffic management authorities can use platforms such as Uber or Didi to disseminate this information to potential users. This can encourage users to avoid hailing a taxi within this area during the specified time frame. Furthermore, for specific events such as concerts, school dismissal times, or other occasions causing severe imbalances, taxi companies or other city traffic management authorities may designate particular taxis to wait in advance to meet the anticipated high demand for travel in the future.

6. Discussion

This section begins by discussing whether the assumptions presented in the introduction have been validated. Then, we focus on discussing several factors that influence the prediction of taxi demand and supply imbalances, including the number of trajectories within a grid, the size of the grid, and the number of GRU units.

6.1. Verification of the Hypothesis

In the introduction section of this paper, we postulated that the dynamic variations in the taxi demand and supply within a grid are crucial factors influencing the prediction of the grid-level equilibrium indices. Based on this premise, we proposed our model. Based on the experimental results, as shown in Table 2, we can discuss the following aspects:

• Overall, solely exploring the static feature correlations between grids, such as the grid adjacency (T-GCN) and static intra-grid feature correlations (TmS-GCN, MAGCN), performs worse in terms of predictive accuracy compared to considering the dynamic intra-grid feature correlations (our model). According to Table 2, particularly at the optimal prediction scale of 10 min, our model shows an improvement of approximately 3.5%, 4.2%, and 1.9% over T-GCN, TmS-GCN, and MAGCN, respectively.
• As the prediction scale increases, the performance of the model considering the dynamic intra-grid feature correlations (our model) deteriorates. This pattern is similar to other models, indicating that long-term predictions are more challenging compared to short-term predictions.

However, compared to the T-GCN model, the improvement of our model diminishes. Specifically, at the 10 min scale, the improvement is 3.5%, reducing to 3.2% at the 20 min scale and further down to 0.7% at the 30 min scale. This is because, in our model, predicting the demand and supply separately from the rolling forecast introduces an additional unknown compared to T-GCN, which predicts traffic flow directly from the rolling forecast. The accumulation of errors in predicting more values leads to a decrease in the overall prediction quality. Therefore, the model proposed in this paper exhibits a limitation in its predictive performance on long-term scales.

6.2. Effect of the Number of Trajectories within a Grid

The effect of three types of trajectory counts on the prediction performance is analyzed, as shown in Figure 8. It is obvious that as the number of taxi trajectories within a grid increases, the overall prediction performance improves. When the number of trajectories is less than 10, the predictive performance is the worst, which can explain the worse prediction results for certain grid mentioned in Section 5.3. In addition, compared to type c and type d trajectories, increasing the number of type a trajectories significantly improves the predictive performance. In other words, a higher number of vacant taxis within a grid leads to better predictive performance in terms of the imbalance index. This indirectly highlights the feasibility of using taxi GPS data for prediction, as information about vacant or occupied states is a fundamental aspect of most urban taxi GPS datasets.

Based on the analysis presented above, it is possible to achieve relatively high predictive accuracy in practical applications of this model, as long as the number of taxi trajectories within a grid exceeds 10. To ensure that the prediction results are applicable across most areas of the city, the prediction time scale can be extended or the grid’s range can be expanded. Alternatively, a specific analysis for each scenario can be conducted in practical applications. Prediction results from grids with a higher number of trajectories can be used directly. However, for remote areas with fewer internal taxi trajectories, the prediction results may need to be selectively adopted.

6.3. Effect of the Grid Size

In fact, we can expect that as the grid size increases, the number of taxi trajectories within the grid will also increase, resulting in an improvement in predictive accuracy. However, grid sizes that are too large become meaningless for taxi dispatching by taxi companies, because drivers would not be assigned a specific destination. Therefore, finding an appropriate grid size is crucial to ensuring both effective prediction models and clear destinations for taxi drivers. We conducted an analysis on this issue, and the results are shown in Figure 9. It is obvious that as the grid size increases, metrics such as the MAE, MAPE, and RMSE gradually decrease, indicating better predictive performance. However, when the grid size is around 1 km, the prediction performance is comparatively better, and the improvement becomes less significant. Therefore, we recommend using a grid size of 1 km × 1 km for regional partitioning in model applications.

The grid size is a crucial factor in the practical application of this model. If the grid size is too small, it may provide more precise but unreliable prediction results due to fewer trajectories within the grid. On the other hand, if the grid size is too large, it may offer accurate predictions but may result in overly generalized predictions, making it challenging for taxi companies or other city traffic management authorities to devise precise taxi dispatching strategies.

Therefore, we suggest that for most cities, considering cost-effectiveness, the adoption of a 1 km × 1 km grid division method could be suitable. However, if possible, it may be beneficial to conduct a customized analysis of the density across different regions of the city. In densely trafficked areas, smaller grid sizes, such as 250 m × 250 m or 500 m × 500 m, may be more suitable, while larger grid sizes, such as 1 km × 1 km or 1.5 km × 1.5 km, may be more appropriate for sparsely trafficked areas.

6.4. Effect of the Number of Units of GRU

Based on previous research, we know that the number of hidden units in the GRU can affect the effectiveness of traffic prediction. Therefore, we conducted a detailed analysis of this factor, and the results are shown in Figure 10. We observed that as the number of hidden units increases, the predictive performance gradually improves. However, when the number of hidden units reaches 120, the improvement in predictive performance becomes less significant. Therefore, considering these results, we recommend that using 120 hidden units in the model is the optimal choice.

This is likely to improve the predictive accuracy, although it may impact the computational efficiency and speed. Based on the analysis above, it is recommended to increase the number of hidden units in the GRU to 160 or more, if economic conditions allow and sufficient computational power is available. For scenarios with average economic conditions, it is recommended to set the number of hidden units in the GRU to at least 120. Having fewer than 120 units could significantly reduce the predictive performance.

7. Conclusions

The purpose of this paper is to predict imbalances between the taxi supply and demand at a grid level. To achieve this, a prediction model is proposed that utilizes dynamic Graph Convolutional Neural Networks (GCNs) and Gated Recurrent Units (GRUs). The model is designed to capture the dynamic influence of the taxi demand–supply between adjacent grids, which is affected by the mobility of taxis and changes in other transportation modes. The study utilized the GRU model to capture the temporal trends and cyclical characteristics of the supply and demand for taxis. Experiments were conducted using taxi trajectory data from Futian District in Shenzhen city starting in January 2019 to compare the model against several baseline models, including HA, ARIMA, GCN, GRU, and T-GCN. The data indicate that our model performs better than the baseline models in predicting at different scales (10, 20, and 30 min) based on metrics such as the MAE, MAPE, and RMSE. To improve the practical application of our model, we conducted an ablation study to examine the impact of various factors on the predictive performance. The study findings indicate that better performance in real-world applications is associated with an increased volume of taxi trajectories, a larger grid size of 1 km × 1 km, and more than 120 hidden units in the GRU.

The method proposed in this paper has certain limitations that need to be improved in future research. Firstly, due to the difficulty of data acquisition, we only utilized taxi GPS data from Shenzhen city to validate our method, which itself is a limitation. It would be beneficial to include data from other cities, such as those in North America or Europe, if the opportunity arises, to demonstrate the universality of the method we have proposed. Second, after discussion, it has been observed that as the prediction scale increases in our model, the involvement of more unknowns in the intermediate calculations leads to an increase in errors. This poses a limitation in the application of our model. In the future, we intend to address this issue and make improvements accordingly.