A Time Flow Neural Network for Solving Time-Varying Steady-State Maximum Flow Problem
摘要
Effective processing of large-scale spatio-temporal data is crucial in collaborative systems such as intelligent transportation and distributed logistics. In such time-varying networks, traversal times vary with departure moments, and changes can lead to significant delays on paths considered optimal under static analysis, making the results ineffective in practice. This paper introduces the Time-Varying Steady-State Maximum Flow Problem (TSMFP), which differs from traditional formulations by considering not only fixed edge capacities but also the dynamic variations in arc traversal times. In TSMFP, only flows that can reach the destination within a predefined stable time threshold are valid. To tackle this, we propose the Time Flow Neural Network (TFNN), which comprises six components: input, flow receptor, neuron state, time window selector, flow generator, and output. Unlike traditional neural networks, TFNN operates without requiring training. Its mechanism dynamically propagates time flows through neurons to identify feasible time-varying shortest paths that meet the constraint, iteratively updating the network. The final output represents the maximum flow that satisfies steady-state time requirements. We provide a theoretical analysis of TFNN’s correctness and time complexity, and experimental results on the New York road network dataset confirm that TFNN achieves the global optimum, demonstrating its effectiveness in solving the TSMFP.