A Fast Lax–Hopf Algorithm to Solve the Lighthill–Whitham–Richards Traffic Flow Model on Networks

Efficient and exact algorithms are important for performing fast and accurate traffic network simulations with macroscopic traffic models. In this paper, we extend the semianalytical Lax–Hopf algorithm in order to compute link inflows and outflows with the Lighthill–Whitham–Richards (LWR) model. Our proposed fast Lax–Hopf algorithm has a very low computational complexity. We demonstrate that some of the original algorithm’s operations (associated with the initial conditions) can be discarded, leading to a faster computation of boundary demands/supplies in network simulation problems for general concave fundamental diagrams (FDs). Moreover, the computational cost can be further reduced for triangular FDs and specific space–time discretizations. The resulting formulation has a performance comparable to the link transmission model and because it solves the original LWR model for a wide range of FD shapes, with any initial configuration, it is suitable to solve a broad range of traffic operations problems. As part of the analysis, we compare the performance of the proposed scheme with that of other well-known computational methods.