Manuscript Introduction: Improved heuristic to reduce oscillations in transit assignment on refined networks

The source code for the implementation, along with the data used in experiments, is publicly available at Github

1. The Challenge: Instability in Transit Network Modeling

Transit assignment is a foundational tool for planning and operating efficient public transportation systems. A common approach, known as frequency-based assignment, models passenger choices based on the frequency of transit lines. However, these models face a critical challenge when networks become congested.

To account for congestion, models use an effective frequency, which decreases as a vehicle fills with passengers. This creates a complex feedback loop: more passengers lead to lower effective frequency, which in turn alters waiting times and redistributes passenger flows. While realistic, this mechanism often causes the solution process to become unstable. Instead of converging to a single, stable solution, the calculated passenger flows begin to oscillate—bouncing between two or more distinct states without ever settling down.

This paper addresses two fundamental issues:

1. The Oscillation Problem: Why do these oscillations occur, and how can they be mitigated to ensure stable and rapid convergence?
2. The Modeling Problem: Many existing network representations are unrealistic, for example by allowing passengers to alight from a bus and then re-board the very same line at the same stop, a behavior rarely seen in practice.

2. Contribution 1: Diagnosing the Problem and a More Realistic Model

The first major contribution of this work is a rigorous analysis of the oscillation phenomenon and the development of a more behaviorally sound transit assignment model.

Diagnosing the Oscillation

The authors demonstrate that the iterative algorithms used to solve these problems effectively become a high-dimensional fixed-point iteration. The convergence of this process is not guaranteed, especially when the effective frequency function has a steep gradient (i.e., when the network is near capacity). The paper formally proves a crucial insight:

Theorem 2.3 (Paraphrased): When line flows fall into a period-2 oscillation (bouncing between state vk and vk+1), the true, convergent flow v* is guaranteed to lie between them: min(vk, vk+1) < v* < max(vk, vk+1).

This theorem provides the theoretical key to resolving the oscillations: instead of letting the solution bounce, an algorithm should aim for the middle ground.

The Pre-Line Marked (PLM) Model

To address the modeling problem, the paper introduces the Pre-Line Marked (PLM) model. Unlike traditional “expanded network” approaches that aggregate all transferring passengers at a stop, the PLM model differentiates passengers based on their preceding line.

This simple but powerful refinement has significant implications:

• It prevents unrealistic transfer behaviors, such as re-boarding the same line.
• It provides a more accurate and detailed calculation of passenger flows within stations.
• It eliminates the need for unrealistic assumptions (like infinite effective frequency for certain movements), simplifying the model.

The difference is illustrated in Figure 2. The traditional expanded approach (b) merges all flows at a stop node, allowing for unrealistic “re-boarding.” The PLM approach (c) keeps the flows distinct based on their origin, leading to a more faithful representation of reality.

a

b

c

3. Contribution 2: The Oscillation Detection Algorithm (ODA)

Building on the theoretical analysis of oscillations, the paper’s second major contribution is a novel heuristic algorithm designed to detect and mitigate these instabilities in real-time.

The Oscillation Detection Algorithm (ODA) is an intelligent component that can be embedded within standard iterative solvers. Its mechanism is as follows:

1. Monitor: The algorithm maintains a queue of the effective frequency vectors from recent iterations.
2. Detect: It uses the Autocorrelation Function (ACF) to analyze this sequence. A high autocorrelation coefficient for a lag of 2 is a strong statistical signal that the system is trapped in a period-2 oscillation.
3. Intervene: If a significant oscillation is detected, the algorithm dynamically adjusts the effective frequency of the unstable lines—for example, by averaging the two oscillating values. This intervention is a direct, practical application of the insight from Theorem 2.3, guiding the solution back toward the stable point between the oscillating extremes.

By actively detecting and dampening oscillations, the ODA prevents the solution from diverging and dramatically enhances the stability and convergence rate of the entire process.

4. The Improved Algorithm in Action: MSAD and SRAD

The ODA is not a standalone solver; its power lies in enhancing existing heuristic methods. The paper integrates the ODA into two widely used algorithms: the Method of Successive Averages (MSA) and the Self-Regulated Averaging (SRA) algorithm. This creates two improved versions:

• MSAD (MSA with Detection)
• SRAD (SRA with Detection)

The flowchart in Figure 3 illustrates how the new detection and update steps are integrated into the standard iterative loop. After calculating flows and frequencies, the algorithm runs the ODA (Algorithm 1) to check for and correct instabilities before proceeding to the next iteration. This proactive approach ensures a much smoother and more direct path to the equilibrium solution.

5. Numerical Validation: Superior Performance on Large-Scale Networks

The effectiveness of the proposed model and algorithms is validated through extensive numerical experiments on both a small network and the large-scale, real-world Winnipeg transit network. The improved algorithms (MSAD and SRAD) are compared against their original counterparts across low, medium, and high demand scenarios.

The results are conclusive. The improved algorithms consistently outperform the original versions, demonstrating significantly faster and more stable convergence, especially under congested conditions where oscillations are most severe.

As shown in the performance graphs below for the 40-line Winnipeg network, the original MSA and SRA algorithms struggle to converge under high demand, with their relative gap oscillating wildly. In contrast, the improved MSAD and SRAD algorithms converge smoothly and rapidly to a high degree of precision.

The performance gain is quantified by the headline result from the study: for the same convergence precision, the improved SRAD algorithm reduces the required computation time by 63% compared to the original SRA algorithm that fails to converge.

6. Conclusion and Impact

This paper successfully tackles the long-standing problem of oscillations in frequency-based transit assignment. It provides a trio of core contributions:

1. A Theoretical Diagnosis: It formally analyzes the implicit functions that cause oscillations and proves that the true solution lies between the oscillating states.
2. A More Realistic Model: It introduces the Pre-Line Marked (PLM) model, which offers a more granular and behaviorally sound representation of passenger transfers.
3. An Effective Solution Algorithm: It develops the Oscillation Detection Algorithm (ODA), a practical heuristic that, when embedded in existing solvers, dramatically improves their convergence speed and stability.

The research provides a robust and computationally efficient framework for analyzing congested transit networks. By ensuring that assignment models converge reliably, this work enables transportation planners and engineers to more accurately evaluate and optimize public transport systems, ultimately leading to better service quality and operational efficiency in large urban areas.