A heuristic algorithm for the earliest arrival flow with multiple sources

This paper presents a heuristic algorithm for the earliest arrival flow problem. Existing exact algorithms, even polynomial in the output size, contain submodular function optimization as a frequently called subroutine, and thus are not practical in real-life applications. In this paper we propose an algorithm that does not involve the submodular function optimization. Although solving an EAF nearoptimal, the algorithm is remarkably simple and efficient as it only involves shortest path computations on a static network. A numerical example illustrates how the algorithm works. As an application, we demonstrate the algorithm’s solution quality and computational performance by solving a real-size network.