Graph Coloring for Parallel User-Equilibrium Traffic Assignment with Reduced Path Overlap

Path overlapping is a well-recognized limitation in user-equilibrium traffic assignment models, often leading to unrealistic route choices and biased flow estimates especially in parallel computation of traffic assignment. This paper proposes a parallelizable preprocessing framework based on graph vertex coloring to explicitly mitigate path overlap prior to parallel assignment and fasten the solution process. To this end, new path overlapping measures are proposed. An origin–destination (OD) conflict graph is constructed in which vertices represent OD pairs and edges denote significant overlap between their shortest or candidate paths, measured by shared links or nodes exceeding a predefined threshold. A greedy vertex-coloring algorithm partitions the OD set into independent color classes, ensuring minimal intra-group path overlap. Traffic assignment is then performed independently and in parallel for each class, enabling efficient exploitation of multi-core architectures while reducing route competition. Computational experiments on real-world networks show that the proposed method reduces path overlap ratios by up to improves convergence stability, and yields more behaviorally realistic route choice patterns. These improvements are achieved without increasing computational cost, with yields ۴.۸× speedup runtime due to parallel execution. The proposed graph-theoretic framework offers a scalable and effective solution for overlap-aware and parallel traffic assignment in large-scale networks.

کلیدواژه ها:

traffic assignment ، path overlapping ، graph coloring ، parallel computation