In static networks, finding the shortest path is a solved problem. But when edge weights change over time—such as traffic congestion during rush hour—routing becomes dynamic. In these time-dependent networks, a single property dictates whether a routing problem is computationally trivial or fiercely NP-hard: the First-In, First-Out (FIFO) property.
Intuitively, the FIFO property states that departing earlier along a path always guarantees arriving earlier (or at the same time) at the destination. It forbids overtaking. If you leave Node A at 1:00 PM and your friend leaves Node A at 1:05 PM along the same route, you will always reach Node B before or alongside them.
Understanding how to exploit this property when it holds, how to manage the complexity when it is violated, and how to strictly enforce it in simulations forms the core of modern time-dependent network analysis.
Why FIFO Makes Routing Easy
The mathematical power of the FIFO property lies in monotonicity. If the arrival time function of every link in a network is monotonically increasing with respect to the departure time, the network satisfies FIFO.
This monotonicity preserves Bellman’s principle of optimality, which states that an optimal path is composed of optimal subpaths. If arriving earlier at an intermediate node $V$ always allows you to arrive earlier at your final destination, you can safely discard any subpath to $V$ that arrives later.
As Yuan et al., 2019 note in their survey of time-dependent graphs, this property is the exact boundary condition that determines the applicability of greedy routing algorithms. When FIFO holds, standard shortest-path frameworks like Dijkstra's algorithm can be extended to time-dependent networks with minimal overhead.
FIFO Network (Monotonic):
Departure: 1:00 PM ------> Arrival: 1:15 PM
Departure: 1:05 PM ------> Arrival: 1:22 PM (Order preserved)
Non-FIFO Network (Overtaking):
Departure: 1:00 PM ------> Arrival: 1:30 PM (Stuck in bottleneck)
Departure: 1:05 PM ------> Arrival: 1:25 PM (Bottleneck cleared, overtakes)
Engineers exploit this simplification to build highly efficient, real-time systems. For example, Gao 0001 et al., 2014 rely on the FIFO assumption to design algorithms that find cost-optimal paths under strict arrival deadlines. Because departure and arrival times scale monotonically, the search space remains constrained.
Similarly, in the domain of shared mobility (such as ride-hailing and on-demand delivery), Gong et al., 2024 demonstrate that exploiting the FIFO property allows algorithms to rapidly evaluate where to insert a new passenger request into an existing vehicle route. By leveraging FIFO monotonicity, their insertion operator prunes suboptimal routes instantly, reducing computational overhead to linear time and enabling real-time dispatching.
The Complexity of Non-FIFO Networks
When a network violates the FIFO property, a later departure can result in an earlier arrival. This occurs naturally in multi-modal transportation (e.g., waiting for a fast express train that overtakes a slow local bus) or in financial networks with time-varying transaction delays.
Without FIFO, greedy pathfinding heuristics collapse. You can no longer throw away a path that arrives later at an intermediate node, because that specific arrival time might perfectly align with a massive drop in downstream congestion, allowing it to overtake the currently "optimal" path.
The theoretical consequences of losing FIFO are severe. Gajjar et al., 2021 map out the computational boundaries of these parametric path problems. They demonstrate that while simple linear routing remains tractable, introducing non-FIFO dynamics—such as piecewise linear travel functions or multiple cost parameters—instantly pushes the problem into the realm of NP-hardness. Without monotonic constraints, pathfinding transforms from a sequence of local decisions into a massive combinatorial explosion.
Strategic Waiting as an Intentional Violation
While non-FIFO dynamics complicate algorithms, they also open the door to a powerful optimization strategy: intentional waiting. If a network is non-FIFO, an agent can choose to sit idle at a node to achieve a better outcome.
Consider a vehicle navigating a highly congested city. Li et al., 2017 study the Minimal On-Road Time (MORT) problem, where the goal is to minimize the time a vehicle spends actively driving, rather than its total elapsed journey time. The authors introduce "parking vertices" where vehicles can strategically wait out a rush-hour traffic wave. By pausing, the vehicle deliberately violates FIFO relative to its continuous journey, trading a longer total duration for significantly reduced fuel consumption and active driving stress.
Standard Routing (FIFO-constrained):
[Start] -> (Drive through heavy traffic) -> [Destination]
Total Drive Time: 60 mins. Total Journey: 60 mins.
MORT Routing (Strategic Non-FIFO Waiting):
[Start] -> (Drive 10m) -> [Park & Wait 20m] -> (Drive 20m through clear roads) -> [Destination]
Total Drive Time: 30 mins. Total Journey: 50 mins.
Strategic waiting is equally vital in fleet logistics. Branke et al., 2005 analyze dynamic vehicle routing where new customer requests appear unpredictably over time. They prove that while a single isolated vehicle should never wait, a multi-vehicle fleet benefits immensely from strategic pausing. By intentionally waiting at a customer location rather than rushing to the next destination, vehicles remain centrally positioned to absorb incoming, unknown requests, minimizing future detours.
Enforcing FIFO for Realistic Simulations
While computer scientists struggle with the complexity of non-FIFO networks, transport engineers face the opposite problem: ensuring that macroscopic traffic simulations do not accidentally violate FIFO.
In continuous-time traffic models, vehicles are often treated as a fluid flow rather than discrete entities. Without explicit mathematical safeguards, these models can suffer from "non-physical overtaking," where vehicles entering a long road segment late in a time step mathematically bypass vehicles that entered earlier.
Friesz et al., 2006 highlight this issue in the context of Dynamic User Equilibrium (DUE). They frame traffic flow as a non-cooperative game in infinite-dimensional space, noting that maintaining the FIFO queue discipline within continuous-time differential variational inequalities is notoriously difficult but mathematically mandatory for realistic models.
To prevent these non-physical anomalies, simulation frameworks must build explicit FIFO tracking mechanisms:
- Node Prioritization: Nie et al., 2008 introduce the Polymorphic Dynamic Network Loading (PDNL) model, which enforces the FIFO principle at complex diverge nodes by tracking exact vehicle arrival times and prioritizing flows that have been waiting the longest.
- Time-Aggregated Constraints: In safety-critical applications like urban evacuation planning, Zhou et al., 2010 utilize time-aggregated graphs that explicitly constrain flow logic. Their capacity-constrained routing ensures that evacuees entering a network segment at an earlier time step are guaranteed to exit before those who enter later, preventing dangerous, unrealistic bottlenecks in emergency simulations.
Key Foundational Work
Waiting Strategies for Dynamic Vehicle Routing (2005) — contributed 3 concept elements to this direction.
Dynamic Non-Cooperative Games as a Foundation for Modeling Dynamic User Equilibrium (2006) — contributed 1 concept elements to this direction.