Skip to content

README.md

Latest commit

 

History

History
178 lines (125 loc) · 6.68 KB

README.md

File metadata and controls

178 lines (125 loc) · 6.68 KB
Raw

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