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

Kai Zhang (), Yu Dong (), Lin Cheng (), Xinyuan Chen (), Qixiu Cheng () and Zhiyuan Liu ()
Additional contact information
Kai Zhang: The Hong Kong Polytechnic University
Yu Dong: Southeast University, Jiulonghu Campus
Lin Cheng: Southeast University, Jiulonghu Campus
Xinyuan Chen: Nanjing University of Aeronautics and Astronautics
Qixiu Cheng: University of Bristol
Zhiyuan Liu: Southeast University, Jiulonghu Campus

Networks and Spatial Economics, 2025, vol. 25, issue 1, No 9, 219-248

Abstract: Abstract 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.

Keywords: Transportation network; Edge-coloring; Backtracking algorithm; Traffic assignment; Link-based subproblems (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-024-09661-z Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:25:y:2025:i:1:d:10.1007_s11067-024-09661-z

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-024-09661-z

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().