Grids Versus Graphs: Partitioning Space for Improved Taxi Demand-Supply Forecasts

Accurate taxi demand-supply forecasting is a challenging application of ITS (Intelligent Transportation Systems), due to the complex spatial and temporal patterns involved. We investigate the impact of different spatial partitioning techniques on the prediction performance of an LSTM (Long Short-Term Memory) network, in the context of taxi demand-supply forecasting. We consider two tessellation schemes: (i) the variable-sized Voronoi tessellation, and (ii) the fixed-sized Geohash tessellation. While the widely employed ConvLSTM (Convolutional LSTM) method can model fixed-sized Geohash partitions, the standard convolutional filters cannot be applied on variable-sized Voronoi partitions. To explore the impact of the Voronoi strategy, we propose the use of a GraphLSTM (Graph-based LSTM) model, by representing the Voronoi spatial partitions as nodes on an arbitrarily structured graph. The GraphLSTM model offers competitive performance against the ConvLSTM model, at a lower computational complexity, across three real-world large-scale taxi demand-supply data sets, with different performance metrics. To ensure superior performance across diverse settings, a HEDGE based ensemble learning algorithm is applied over the ConvLSTM and the GraphLSTM networks.