Two Modifications of MinSum Algorithm for Efficient System-Optimal Traffic Assignment

Traffic assignment in large urban areas is an old but increasingly important problem because of the rapid growth of the world population and traffic demands. Many algorithms have been developed but their convergence rates and complexities are still prohibitive for real-time applications. The recently developed MinSum algorithm introduces a new approach. It is a highly efficient discrete-domain optimization algorithm for system-optimized route assignment between two city zones. Its complexity (the number of critical operations) is O(R3), where R is the number of routes. Nonetheless, there is still room for improvements, and this paper presents two modified MinSum variants, heuristic and approximate, that are significantly faster and of lower complexity, while retaining MinSum’s prominent features. Heuristic variant MinSumH is up to five times faster than MinSum and its complexity theoretically remains O(R3), though experiments indicate that it is closer to O(R2). Approximate variant MinSumA is faster by up to over 100 times and reduces the complexity to O(R). Both proposed variants are progressively faster as R grows. Due to their high convergence rate and exceptionally low complexity, along with other prominent features, the proposed algorithms are ready for real-time system-optimal traffic assignment in a real urban environment.