Optimization of two-passenger ride-pooling orders based on ST-GNN and path optimization

Abstract

Urban dynamic ride-pooling faces significant challenges in achieving efficient real-time order matching and path planning, primarily due to the complex spatio-temporal coupling of passenger demand and traffic conditions. Traditional algorithms often struggle to dynamically integrate these features and adapt to multi-objective optimization under real-world constraints. To address these limitations, this study proposes a novel dual-optimization framework that synergizes a Spatio-Temporal Graph Neural Network (ST-GNN) with a multi-objective path planning algorithm. Our approach begins by constructing a demand-adaptive urban spatial structure using Voronoi polygons. A spatio-temporal graph is then built upon this structure, where a graph neural network model, incorporating multi-head attention and Transformer mechanisms, is employed to learn node embeddings that capture complex urban dynamics. These embeddings inform the matching of suitable ride-pooling pairs and guide an improved Dijkstra algorithm to generate optimal paths that co-optimize travel distance, passenger detour, and carbon emissions while strictly adhering to passenger time windows. Validated on a large-scale real-world dataset from Chengdu (Didi Chuxing), our method achieves a matching success rate of 86.6%, reduces carbon emissions by 0.34 kg CO 2 per order on average, and maintains a low average detour rate of 0.1202. The results demonstrate that the proposed model enhances spatio-temporal collaboration in complex scenarios and offers a practical and efficient solution for the intelligent upgrade of shared mobility systems, contributing to optimized urban traffic resources and low-carbon travel practices.

Affiliated Institutions

• Jilin University of Chemical Technology CN

Related Publications