XGBoost-Based Heuristic Path Planning Algorithm for Large Scale Air–Rail Intermodal Networks

Shengyuan Weng, X. Y. Shan, Guangdong Bai, Jinfei Wu, Nan ZhaoInventions 2025 · DOI

TL;DR

This paper introduces an XGBoost-based heuristic path planning algorithm (XGB-HPPA) to tackle the computational challenge of finding optimal routes in large-scale air-rail intermodal networks. By using XGBoost to predict promising transfer stations, the algorithm significantly accelerates pathfinding while maintaining a high quality of solutions.

What Problem Does This Paper Address?

Planning efficient travel routes in complex intermodal transportation systems, like the air-rail network in China, is a significant challenge. While Time-Expanded Graphs (TEGs) are effective for modeling schedules and transfers, they can lead to massive networks with millions of nodes and edges. This scale makes traditional pathfinding algorithms computationally prohibitive, especially when passengers need multiple route options. The core problem is how to find good air-rail routes quickly in these vast networks without sacrificing too much solution quality.

Methods

The proposed XGB-HPPA algorithm has two main components:

  1. XGBoost for Transfer Station Prediction: Instead of exploring all possible transfers, the algorithm first uses a trained XGBoost model to predict likely transfer cities (to manage complexity) and then identifies relevant transfer stations within those cities. This prediction is based on historical passenger travel data.
  2. Heuristic Path Planning: The XGBoost predictions are used to create a heuristic factor for transfer edges. This factor helps to quickly prune "unreasonable" transfer edges, effectively reducing the network's effective size. A bidirectional Dijkstra algorithm is then used to find the K shortest paths on this refined network.

Datasets

  • Air-Rail Intermodal Network Dataset: Constructed from real-world train and civil aviation flight data from October to December 2023. This dataset includes 3174 railway stations, 259 airports, 23,748 train services, and 5800 civil aviation flights, resulting in a TEG with over 2.3 million nodes and 23 million edges.
  • XGBoost Model Training Dataset: Derived from passenger air and train ticket purchase data from October to December 2023. This dataset, containing 450,000 valid entries, captures start/terminal station information and transfer locations, used to train the XGBoost model to predict transfer cities.

Key Insights and Ideas

  • Leveraging Predictive Models for Graph Pruning: The core innovation is using a machine learning model (XGBoost) not just for prediction but as a crucial component in reducing the search space for graph algorithms. This is a powerful paradigm shift from traditional graph traversal.
  • City-Level Prediction as a Scalability Tactic: Predicting transfer cities instead of individual stations is a smart way to manage the multi-class classification problem in XGBoost, especially when dealing with a vast number of potential transfer points.
  • Heuristic Factor for Edge Pruning: The introduction of a heuristic factor derived from XGBoost predictions allows for dynamic pruning of the graph, directly addressing the computational bottleneck of large networks.
  • Trade-off Between Speed and Solution Diversity: The study highlights that while XGBoost significantly speeds up pathfinding, there's a nuanced trade-off. Using too few transfer cities can slightly degrade path quality (longer travel times, fewer options), while using too many can increase computation time.

Key Results

  • Computational Speedup: The XGB-HPPA algorithm reduced the average path planning calculation time by approximately 50% (from 673 ms to 337 ms) compared to the baseline without XGBoost. The maximum calculation time was reduced by about 65% (from 4772 ms to 1657 ms).
  • Path Quality:
    • When using only one predicted transfer city, the median travel time for optimal paths slightly increased.
  • However, when using two or more transfer cities, the travel time distribution remained similar to the baseline.
  • The average number of available routes decreased slightly with XGBoost (from ~10 to ~8), but this stabilized.
  • The proportion of solvable OD pairs remained high, reaching ~98% when selecting more than nine cities.
  • The proportion of samples achieving the optimal solution increased with the number of selected transfer cities, reaching ~83% when selecting more than ten cities.
  • Feature Importance: Coordinate features (latitude and longitude) of start and terminal stations were found to be more influential than unique identification labels for predicting transfer cities.

Limitations and Future Work

  • Parameter Tuning Complexity: XGBoost requires meticulous parameter tuning, which can be computationally expensive and time-consuming.
  • Interpretability: The XGBoost model's interpretability is relatively weak, making it harder to understand why certain transfers are predicted.
  • Imbalanced Data: The model may struggle with imbalanced datasets, potentially leading to poor performance for minority classes (e.g., less frequent transfer cities).
  • Future Work: The authors suggest exploring combinations of XGBoost with deep learning or ensemble methods, and investigating techniques for handling imbalanced data to improve performance and robustness. They also propose finding an optimal balance for the number of selected transfer cities (suggesting 7-10 cities) to harmonize speed and solution quality.

Summary updated

Abstract

It is particularly important to develop efficient air–rail intermodal path planning methods for making full use of the advantages of air–rail intermodal networks and providing passengers with richer and more reasonable travel options. A Time-Expanded Graph (TEG) is used to model the timetable information of public transportation providing a theoretical basis for public transportation path planning. However, if the TEG includes a large amount of data such as train stations, airports, train and air schedules, the network scale will become very large, making path planning extremely time-consuming. This study proposes an XGBoost-based heuristic path planning algorithm (XGB-HPPA) for large scale air–rail intermodal networks, which use the XGBoost model to predict transfer stations before path planning, and quickly eliminate unreasonable transfer edges by adding a heuristic factor, reducing the network scale, thus accelerating the computation speed. Comparative results indicate that XGB-HPPA can markedly enhance computational speed within large-scale networks, while obtaining as many valid solutions as possible and approximating the optimal solution.
BibTeX
@inproceedings{weng2025xgboost,
  author = {Shengyuan Weng and X. Y. Shan and Guangdong Bai and Jinfei Wu and Nan Zhao},
  title = {{XGBoost-Based Heuristic Path Planning Algorithm for Large Scale Air–Rail Intermodal Networks}},
  booktitle = {Inventions},
  year = {2025},
  doi = {10.3390/inventions10020027},
}
Figure