A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration

This paper presents a novel user-equilibrium (UE) traffic assignment algorithm, which under conventional assumptions, promises to compute UE arc flows to acceptable precision, regardless of the network’s topology, size or congestion:
• The algorithm takes the simple approach of shifting flow from a costliest path to a cheapest path until the costs of all used paths are within a given ϵ of the cheapest.
• Because of being path-based, it avoids tailing.
• In spite of being path-based, it neither stores nor enumerates paths.
• These efficiencies derive from decomposing the problem into a sequence of easy single-origin problems on acyclic sub-networks.Solutions to this sequence of sub-network flows converge rapidly to a sharp practical estimate of UE arc flows—as is amply demonstrated by tests using the Chicago region’s 40,000-arc network model.