User Equilibrium Traffic Assignment — Chicago-Regional (C++ 0.1)

Wardrop User Equilibrium (UE) link-flow assignment for the Chicago-Regional TNTP benchmark network. Current implementation is a C++ program:

• source: src/oba_assignment.cpp
• binary: oba_assignment.exe

Solver: Frank–Wolfe family — choose FW, CFW, BFW, or 3FW (tri-conjugate Frank–Wolfe) via OBA_ALGO. When OBA_ENABLE_PATHS=1, solver automatically uses FW to preserve convex path-flow decomposition for multi-path outputs.

Performance: OpenMP parallel Dijkstra + AON, CSR row-scan edge lookup, Newton-bisection line search.

---

Requirements

• Windows + MSYS2 MinGW64 g++ (or any C++17 compiler with OpenMP support)

---

Data layout

Place the Chicago-Regional TNTP files under chicago-regional/ next to the executable:

File	Role
chicago-regional/ChicagoRegional_net.tntp	Links, BPR parameters, capacities
chicago-regional/ChicagoRegional_trips.tntp	OD demand
chicago-regional/ChicagoRegional_node.tntp	Node coordinates

Typical scale: on the order of 13k nodes, ~1.8k zones, ~39k links, ~1.36M trips — see TransportationNetworks for metadata.

Shapefile CRS: NAD83 / Illinois State Plane East (US survey feet), WKT embedded as *.prj.

---

Build & Run

Build (Makefile)

make

Build (PowerShell)

.\build.ps1

or

$env:PATH="C:\msys64\mingw64\bin;$env:PATH"
g++ -std=c++17 -O3 -fopenmp -march=native src\oba_assignment.cpp -o oba_assignment.exe

Run

.\oba_assignment.exe

.\oba_assignment.exe --data-dir .\chicago-regional --out-dir .\output --conv 1e-4

Outputs go to output/ (created if missing).

Fast solver-only run (skip large outputs)

paths.csv can be very large. For timing the assignment only:

PowerShell (Windows):

$env:OBA_ENABLE_PATHS="0"; $env:OBA_ENABLE_TURNS="0"; .\oba_assignment.exe

3FW (often fewer iterations at tight gaps)

PowerShell (Windows):

$env:OBA_ALGO="3FW"; .\oba_assignment.exe

---

Configuration (environment variables)

Variable	Default	Meaning
OBA_ALGO	BFW	FW, CFW, BFW, or 3FW
OBA_CONV	1e-4	Stop when relative gap RelGap < this value
OBA_MAX_ITER	500	Maximum iterations
OBA_THREADS	max_threads	Worker threads for chunked Dijkstra + AON
OBA_ENABLE_PATHS	1	0 skips paths.csv (and uses accelerated algos)
OBA_MULTIPATH	0	1 enables iterative multi-path tracking (slower, forces FW)
OBA_ENABLE_TURNS	1	0 skips turning movements
OBA_ENABLE_SHP	0	Reserved (current C++ version does not export shapefiles)
OBA_PATH_FLOW_EPS	1e-3	Prune tiny path flows when tracking paths

Runtime CLI parameters

Argument	Meaning
--data-dir <path>	Dataset directory containing TNTP files
--out-dir <path>	Output directory
--conv <value>	Convergence threshold (overrides OBA_CONV)

Generalized link cost: BPR time plus fixed terms 0.04 min/mile length and 0.02 min/cent toll.

Relative gap:

[ \text{RelGap} = \frac{\text{TSTT} - \text{SPTT}}{\text{SPTT}} ]

where TSTT is total system travel time at current flows and SPTT is the sum of minimum OD costs from the AON pass at current costs.

---

What's in 0.1 (summary)

1. Parallel AON — each thread finishes Dijkstra for origin chunks and performs subtree-flow loading.
2. CSR row scan for predecessor edge → link id mapping.
3. Newton-bisection line search for step length on Beckmann slope.
4. 3FW/BFW/CFW/FW with fallback chain for singular small systems.

---

Outputs

Path	Description
output/convergence.csv	Per iteration: iter, vkt_gap, beckmann_gap, tstt, sptt, vkt, alpha, iter_time_s, cumulative_s
output/iteration_metrics.csv	Detailed per-iteration metrics: convergence gaps, flow stats, V/C ratios, timing breakdowns (AON, direction, line search, update)
output/paths.csv	If enabled: default single-path (fast); with OBA_MULTIPATH=1 outputs multi-path per OD
output/turning_movements.csv	If enabled: junction_node, from_node, to_node, volume
output/link_metrics.csv	Link-level metrics: flow, V/C, travel time, generalized cost and base attributes
output/network.*, output/nodes.*	Not generated in current C++ version

---

Program structure (src/oba_assignment.cpp)

Function	Line	Role
Config::from_env	~68	Read env vars into config
parse_network	~153	TNTP link file parser
parse_trips	~196	TNTP OD demand parser
parse_nodes	~238	TNTP node coordinate parser
build_network	~262	Construct Network struct from raw parsed data
build_csr / update_csr_costs	~348 / ~392	CSR adjacency graph for Dijkstra
dijkstra_single	~400	Single-origin shortest path
aon_parallel	~434	OpenMP parallel Dijkstra + subtree AON loading
line_search	~652	Newton-bisection on Beckmann objective
compute_direction	~757	FW/CFW/BFW/3FW conjugate direction
run_solver	~1013	Main iteration loop
extract_final_paths	~1157	Post-convergence path reconstruction
save_convergence_csv	~1396	Convergence history export
save_iteration_metrics_csv	~1417	Detailed iteration metrics export
save_turning_movements	~1291	Turning volume computation and CSV export
save_link_metrics_csv	~1514	Per-link metrics export
decompose_and_save_paths	~1555	Multi-path decomposition and export
main	~1800	Entry point, CLI parsing, orchestration

---

References

1. Wardrop, J.G. (1952). Some theoretical aspects of road traffic research. Proc. ICE, 1(3), 325–362.
2. Beckmann, M., McGuire, C.B., & Winsten, C.B. (1956). Studies in the Economics of Transportation.
3. Frank, M. & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Res. Logist. Q., 3(1–2), 95–110.
4. Mitradjieva, M. & Lindberg, P.O. (2013). The stiff is moving — conjugate direction Frank–Wolfe methods with applications to traffic assignment. Transportation Science, 47(2), 280–293.
5. Ignashin, I.N. & Yarmoshik, D.V. (2024). Modifications of the Frank–Wolfe algorithm in the problem of finding an equilibrium distribution of traffic flows. arXiv:2403.04863
6. TNTP networks: bstabler/TransportationNetworks