IITA — Integer (Iterative) Traffic Assignment

Version iita-1.4a · C++17 · CMake · Windows / Linux

A research implementation of Integer Traffic Assignment on standard TNTP benchmark networks. The algorithm distributes OD demand as discrete integer vehicles via K-Trees path generation, Logit / Path-Size-Logit route choice, and multinomial sampling. Assignment runs in two stages: an expected-loading MSA phase (fractional) to locate the stochastic equilibrium, then a final integer-loading phase that MSA-averages several integer multinomial realizations (seeded from the relaxed equilibrium) to keep the reported flow free of single-realization Jensen bias on congested links.

---

Repository layout

IITA/
├── Datasets/               TNTP benchmark networks
│   ├── Anaheim/            416 nodes / 914 links / 38 zones
│   ├── Chicago-Sketch/     mid-size
│   ├── Philadelphia/       mid-size (no _flow.tntp)
│   └── chicago-regional/   ~13k nodes / 39k links / 1790 zones
├── include/iita/           Public C++ headers
├── src/                    Library source files
├── apps/                   Executable entry points
│   ├── run_chicago_sketch.cpp   Main assignment driver (→ iita.exe)
│   ├── integerize_only.cpp      OD integerization tool
│   └── eval_only.cpp            Evaluation-only tool
├── tests/                  Unit tests
├── output/                 Run outputs (gitignored)
├── ref/                    Reference material (read-only)
├── CMakeLists.txt
└── workplan.md

---

Build

Requires CMake ≥ 3.16, a C++17 compiler, and optionally OpenMP.

Two build trees coexist (both use MinGW GCC via msys64/mingw64):

Directory	Build Type	Purpose
build/	Debug	Development / step-through debugging
build-release/	Release	Benchmarking (-O3 -march=native)

# Debug
cmake -S . -B build -G "MinGW Makefiles" -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j4

# Release
cmake -S . -B build-release -G "MinGW Makefiles" -DCMAKE_BUILD_TYPE=Release
cmake --build build-release -j4

Outputs (in whichever build directory):

• iita.exe — main assignment executable
• integerize_only.exe — OD integerization tool
• eval_only.exe — evaluation tool
• iita_tests.exe — unit test suite

---

Usage

Main assignment (iita.exe)

iita.exe --dataset <path> [options]

Flag	Default	Description
--dataset <path>	Datasets/Chicago-Sketch	Path to TNTP dataset directory
--out <path>	output/chicago_sketch	Output directory
--theta <value|auto>	0.5	Logit dispersion parameter; auto samples ODs to calibrate, clamped to [0.1, 20.0]
--theta-sample <n>	50	OD sample size for auto-theta calibration
--adaptive-theta	off	Enable per-OD adaptive theta scaling
--max-k <n>	19	Max candidate paths per OD
--max-iters <n>	200	Max expected-loading (MSA) iterations
--vht-gap <v>	1e-4	VHT convergence threshold
--final-smooth <n>	8	Integer multinomial realizations MSA-averaged in the final loading phase; 1 reproduces the legacy single-realization behaviour
--integerize <S1|S2|S2B|S3>	S2B	OD integerization strategy
--demand-scale <f>	1.0	Multiply every OD entry by f before integerization
--seed <n>	42	RNG seed
--capture-paths	off	Write path_records.csv (large on big networks)

Examples:

# Anaheim with auto theta
./build/iita.exe --dataset Datasets/Anaheim --theta auto --out output/anaheim

# Chicago-Regional (large, ~13 min)
./build/iita.exe --dataset Datasets/chicago-regional --theta auto \
    --max-iters 200 --final-smooth 8 --out output/chicago_regional

---

Outputs

Each run writes to the specified --out directory:

File	Contents
flows.csv	MSA-averaged link flows from the final integer-loading phase (fractional when --final-smooth > 1) + BPR travel times and v/c ratios
relaxed_flows.csv	Fractional link flows from the expected-loading MSA phase
turn_movements.csv	Integer turn volumes from the last integer realization of the final-loading phase
metrics.json	RMSE / MAPE vs SUE and UE, timing, iteration count, resolved theta
report.md	Human-readable summary with iteration table
path_records.csv	Per-path audit records from the last integer realization (only with --capture-paths)

---

Benchmark results

Results at current default settings (--theta auto, --max-k 19, --max-iters 200, --vht-gap 1e-4, --final-smooth 8, Release build, seed = 42), using the output/v14a runs:

Dataset	Vehicles	Theta	Iters	SUE RMSE	UE RMSE	UE MAPE	Time
Anaheim	104,697	1.467	5	346	1,742	66.2%	0.14 s
Chicago-Sketch	1,137,495	1.075	23	805	296	2.38%	3.44 s
Philadelphia	14,336,062	0.916	60	1,378	773	18.2%	786.9 s
chicago-regional	1,316,341	1.125	65	421	320	5.19%	815.8 s

Notes:

• theta is the resolved network-level auto-theta written to metrics.json.
• Philadelphia and chicago-regional still have unrouted demand in the current dataset / validation state, so Vehicles reflects final assigned vehicles rather than total integerized demand.

---

Algorithm summary

1. OD integerization — round continuous OD demands to integers (strategies S1–S3, S2B).
2. Auto-theta calibration — when --theta auto, sample OD shortest-path costs and set θ = 0.5772 · median / std, clamped to [0.1, 20.0] to keep the perturbation scale bounded while preserving network-to-network variation.
3. K-Trees generation — per origin: tree 0 = Dijkstra on current costs; trees 1..K-1 = Dijkstra on Gumbel-perturbed costs with σ = 1/θ. Centroid nodes excluded from through-routing. K trees built in parallel.
4. Cost filter — candidate paths with cost exceeding a piecewise threshold of the shortest-path cost are dropped (tighter for long trips, looser for short ones).
5. Saturation-aware theta — mean v/c on the shortest path scales θ per OD: low saturation concentrates flow on the fastest route; high saturation spreads it across alternatives.
6. Path-Size Logit — utility V_k = −θ·c_k + ln(PS_k) where PS_k corrects for path overlap. Overlap-index filter enforces diversity.
7. Expected loading iteration (fractional MSA) — load expected flows y_n = demand · probability per OD; update f_{n+1} = f_n + (1/(n+1))·(y_n − f_n); update BPR. Cached OD path sets avoid repeated rebuilds on stable iterations, and a plateau detector trims low-yield tail iterations.
8. Final integer loading (integer MSA) — seeded from the relaxed fractional equilibrium, run final_smoothing_iters integer multinomial samplings; MSA-average them (step 1/(iter+2), treating the seed as a 0th observation). The averaged flow is reported as the final solution; the last realization's integer counts feed turn_movements.csv and path_records.csv. MSA averaging cancels the convex-BPR (Jensen) bias that a single integer realization otherwise induces on congested links.

See CLAUDE.md for full algorithmic context.

---

Running tests

./build/iita_tests.exe

Covers: TNTP parsing, OD integerization, Logit / PSL, Dijkstra / centroid constraints, flow conservation, path count limits, RNG / multinomial correctness (26 core tests).

---

Datasets

All networks follow the Bar-Gera TNTP format. Ground-truth reference files per dataset:

• UE.csv — User Equilibrium link flows (deterministic reference)
• SUE.csv — Stochastic UE link flows (stochastic reference)
• *_flow.tntp — Bar-Gera canonical flows (where available)

Chicago-Sketch notes:

• ChicagoSketch_net.tntp has been normalised so centroid connectors use positive free-flow time from ChicagoSketch_flow.tntp, and <FIRST THRU NODE> is set to 388.
• ChicagoSketch_trips.tntp has intrazonal (origin == destination) demand zeroed so total demand matches the assignment model, which routes only interzonal trips.

See Datasets/chicago-regional/README.md for known data issues in the large network.