A Backtracking Algorithm for Solving the Nearly Equitable Strong Edge-coloring Problem on Transportation Network

Faced with the challenges of continuously expanding traffic network scales and increasing travel demands in practical engineering problems, the computation required by traditional algorithms for solving large-scale traffic assignment problem (TAP) is expanding, making it increasingly difficult to balance computational efficiency and accuracy. The search for effective decomposition methods suitable for large-scale TAP has been a prominent focus. However, the complexity of the transportation network topology makes it challenging for existing traffic assignment algorithms to decompose the network. This paper utilizes the edge color theory from graph theory, the topology of transportation networks is deeply analyzed, and the characteristics of two-way edge coloring are defined in transportation networks. To further decompose the network at the level of link variables, a backtracking algorithm is presented for solving the nearly equitable strong edge-coloring (NESEC) problem. The proposed algorithm provides a theoretical foundation for modeling parallel traffic assignment based on the alternative direction method of multipliers (ADMM). The backtracking algorithm makes NESEC results easier for the ADMM-based traffic assignment model to perform parallel computation and enables the parallel calculation on thousands of link-based subproblems on large-scale TAP. The proposed algorithm was validated by conducting numerical experiments.