Efficient numerical computation of traveler states in explicit mobility-based metapopulation models: Mathematical theory and application to epidemics

Metapopulation models are powerful tools for capturing the spatio-temporal spread of infectious diseases. Models that explicitly account for traveler origins and destinations, such as Lagrangian metapopulation models, enable a detailed representation of mobility and traveling subpopulations. However, tracking these subpopulations requires a separate set of ordinary differential equations (ODEs) for each traveler group, leading to quadratic growth in system size with the number of spatial patches in densely connected networks. While specific approaches reducing the effort of traveler state estimation have been proposed, these approaches are either model-specific or heuristic and lack sufficient numerical accuracy. For Lagrangian formulations with discrete mobility events, we here introduce a stage-aligned Runge–Kutta (RK) scheme for computing traveler states under compartment-level homogeneity that leverages the precomputed intermediate stage values of explicit RK methods. We prove that the resulting numerical solution is identical to that of the standard Lagrangian formulation when solved with the corresponding RK method. For compartments without inflows, we further show that the exact same results can be obtained using a simple algebraic scaling based on the initial traveler share. When embedded in a recently proposed metapopulation framework that combines local ODE dynamics on nodes with discrete mobility events along network edges, the stage-aligned approach eliminates the need for heuristic traveler approximations. In contrast to the standard Lagrangian formulation, the resulting method enables efficient simulations by reducing the global ODE system to linear scaling in the number of patches, while the remaining quadratic interactions are handled through simple and highly efficient algebraic updates for traveler estimation. Numerical experiments confirm the theoretical results, demonstrating optimal convergence order and good scalability with respect to the number of patches. Benchmarks on fully connected networks with up to 1025 patches, 1024 local travel connections, and six age groups achieve speedups of up to 76 and 50 for first- and fourth-order Runge–Kutta methods, respectively.