An improved ant colony optimization strategy for dual-objective high-speed train scheduling

Hui Zhao, Jiahuan Zhang, Haixing Li, Dong LiJournal of King Saud University - Computer and Information Sciences 2025 · DOI

TL;DR

Researchers have developed an improved Ant Colony Optimization (ACO) algorithm to tackle the complex task of rescheduling high-speed trains after a delay. By balancing the conflicting goals of minimizing passenger delay and reducing traction energy consumption, the new strategy finds a "Pareto optimal" suite of schedules that outperform standard optimization methods in both efficiency and convergence speed.

What Problem Does This Paper Address?

High-speed rail networks are marvels of precision, but a single delay can trigger a "ripple effect," propagating through the schedule and causing massive economic losses. When a train is late, dispatchers face a difficult choice: should they push the train to its limits to recover the schedule (which spikes energy consumption) or accept the delay to save on power?

This is a dual-objective optimization problem characterized by being non-linear, multi-constraint, and NP-hard. Traditional mathematical programming struggles as the number of stations and trains grows. While machine learning (like Reinforcement Learning) shows promise, it often requires extensive retraining for every new scenario. The authors aim to provide a more robust, "intelligent heuristic" approach that can handle real-time rescheduling constraints.

Methods

The authors propose an Improved Ant Colony Optimization (ACO) strategy. Standard ACO mimics how ants find the shortest path to food using pheromone trails. This paper introduces three specific enhancements:

  1. Dual-Objective Heuristic Information: The "ants" (software agents) don't just look for the fastest path. Their movement is guided by a state transition mechanism that calculates the probability of selecting a time point based on both the inverse of departure delay and a specific energy consumption metric.
  2. Positive and Negative Feedback Pheromones: In traditional ACO, good paths get more pheromones (positive feedback). This paper adds negative feedback: paths that result in delays worse than the iteration average have their pheromone levels actively weakened. This prevents the algorithm from getting stuck in "local optima" (mediocre solutions).
  3. Dynamic Pheromone Evaporation: Instead of a fixed decay rate, the algorithm uses a dynamic evaporation factor that adjusts as iterations progress. This maintains search diversity in early stages and accelerates convergence toward the end.

The model accounts for ten distinct real-world constraints, including "skylight" periods (reserved maintenance time), station track capacity, and minimum tracking intervals between adjacent trains.

Datasets

The study evaluates the algorithm using a simulation based on a segment of the Beijing-Shanghai high-speed railway line.

  • Scope: 8 stations and 7 sections.
  • Traffic: 20 trains.
  • Scenario: A 20-minute delay is introduced to a specific train (G445) at Taian station to test the rescheduling response.
  • Comparison: The results are benchmarked against standard ACO, Particle Swarm Optimization (PSO), Genetic Algorithms (GA), Reinforcement Learning (RL), and First-Come-First-Service (FCFS) methods.

Key Insights and Ideas

  • The Energy-Delay Trade-off: The paper quantifies the "sweet spot" in train scheduling. For example, one solution showed that by accepting a 15% increase in total delay time, the operator could reduce total energy consumption by a staggering 50%.
  • Escaping the Trap: The inclusion of negative feedback is the "aha moment" for the algorithm's performance. By actively punishing bad paths, the algorithm explores the solution space more effectively than standard heuristics, which often converge too quickly on a sub-optimal schedule.
  • Pareto Efficiency: Rather than giving a single "best" answer, the algorithm produces a Pareto front—a set of solutions where you cannot improve one objective (delay) without degrading the other (energy). This gives dispatchers a menu of options based on current priorities.

Key Results

  • Convergence Superiority: In head-to-head tests (Figure 9), the Improved ACO reached a lower objective function value faster than GA, PSO, and RL. While RL and standard ACO eventually stabilized, they did so at significantly higher "cost" levels.
  • Quantitative Gains: In a multi-train delay scenario, the proposed method reduced energy consumption by 47.5% compared to a single-objective (delay-only) optimization, with only a marginal increase in total delay.
  • Feasibility: The algorithm consistently generated feasible solutions that respected all ten operational constraints, proving its potential for real-world dispatching systems.

Limitations and Future Work

While the results are impressive for a single line segment, the authors acknowledge that real-world networks are far more complex.

  • Network Complexity: The current model focuses on a single line. Future work will need to address multi-line or interactive line scenarios where delays on one line affect intersecting routes.
  • Real-time Computation: While faster than many methods, the computational overhead for massive, nation-wide networks remains a challenge for true real-time, second-by-second rescheduling.
  • Stochastic Factors: The model uses deterministic constraints; incorporating stochastic variables (like fluctuating passenger loads or weather-related speed restrictions) would further improve its robustness.

Summary updated

Abstract

In this paper, for the high-speed train scheduling problem with operation delay of trains, a dual-objective high-speed train scheduling model with the objective function of minimizing the total delay time and total energy consumption is established by considering multiple operation constraints. Then, an improved ant colony optimization algorithm is proposed to solve the model. The heuristic information of algorithm is improved and a state transition mechanism is investigated to comprehensively consider delay time and energy consumption. In addition, the positive and negative feedback pheromone updating rules are utilized to solve train scheduling problem. The Pareto optimal solution set satisfying the dual-objective is obtained through simulation experiments. Finally, the typical solutions are selected as the scheduling scheme to analyze the scheduling results and effectiveness of the proposed scheduling strategy.
BibTeX
@article{zhao2025improved,
  author = {Hui Zhao and Jiahuan Zhang and Haixing Li and Dong Li},
  title = {{An improved ant colony optimization strategy for dual-objective high-speed train scheduling}},
  journal = {Journal of King Saud University - Computer and Information Sciences},
  year = {2025},
  doi = {10.1007/s44443-025-00226-9},
}
Figure