Logit-SUE

A Python solver for path-based stochastic user equilibrium (SUE) traffic assignment under the Logit route-choice model. Supported step-size rules include a Newton-GMRES method with superlinear convergence and constant step-size MSA with linear convergence. Benchmarked on standard Transportation Network Test Problems (TNTP).

Associated paper: to be added soon. Please contact the author for a copy in the meantime.

Collaborators: @debojjalb, @sboyles

Supported Step Rules

Rule	Description
Newton	Matrix-free Newton-GMRES
MSA-HS	Method of Successive Averages with harmonic step
MSA-ACS	MSA with adaptive constant step
BB1 / BB2	Barzilai-Borwein step sizes
BB1-ACS / BB2-ACS	BB with adaptive constant step
BB-Newton	BB warm-start followed by Newton

Project Structure

.
├── main.py                         # Single-run driver (start here)
├── SUEPath.py                      # Assignment module (StochasticUE class)
├── readNetwork.py                  # Network / demand parsers
├── helper.py                       # TNTP → DAT conversion utilities
├── generate_assignment_results.py  # Paper: all assignemnt results
├── generate_convergence_results.py # Paper: all convergence results
├── generate_eigenvalue_results.py  # Paper: K-matrix eigenvalue analysis
├── genPlots.py                     # All plots and LaTeX tables for the paper
├── requirements.txt
├── testNetworks/                   # TNTP benchmark networks
├── Paths/                          # Precomputed k-shortest path caches (.pkl)
├── logResults/                     # Per-iteration logs written during a run
├── optimalSolutions/               # Pickled converged path-flow arrays
├── eigenValueResults/              # Eigenvalue tables
└── Plots/                          # Generated figures and all_tables.tex

Installation

pip install -r requirements.txt

Dependencies: numpy, scipy, networkx, pandas, matplotlib, tqdm

Gneerate path sets using modules in pathGenerator/

Tested with Python 3.12.5.

Quick Start

Edit the parameters at the bottom of main.py and run:

python main.py

Key parameters:

inputLocation     = "testNetworks/Sioux Falls/"  # network folder
k                 = 20       # number of pre-computed shortest paths per OD
theta             = 1.0      # logit dispersion parameter
demand_multiplier = 1.0      # scale OD demands
stepRule          = "Newton" # step-size rule (see table above)
I_s               = 10       # MSA-ACS switch iteration
time_limit        = 60       # wall-clock limit in seconds
optSolAccuracy    = 1e-10    # RGAP convergence threshold
save_log          = True     # write per-iteration log to logResults/

Test Instances

TNTP network files are sourced from bstabler/TransportationNetworks.

Network	Category	K (paths per OD)	Path cache available
Sioux Falls	Small	20	Yes
BMC	Small	20	Yes
EMA	Small	20	Yes
Anaheim	Small	20	Yes
Berlin Center	Medium	20	No — generate with pathGenerator/
Chicago Sketch	Medium	20	No — generate with pathGenerator/
Winnipeg (Asymmetric)	Medium	20	Yes
Chicago Regional	Large	5	No — generate with pathGenerator/
Philadelphia	Large	5	No — generate with pathGenerator/

Path caches are stored as Paths/allPathsODCache_{k}_{NetworkName}.pkl. If no cache exists for a given network and k, generate one using the utilities in pathGenerator/ before running the solver.

The pathGenerator/ folder contains four scripts. Before running, edit the first_thru_node_dict at the bottom of each generator to include the networks you want.

• Generate path sets with either pathSetGenerator_yen.py (Yen's k shortest paths, exact) or pathSetGenerator_fast.py (link-penalization heuristic, faster on large networks). Outputs go to Paths/ and metadata to path_cache_metadata.txt.
• Fix node ID types across all caches in Paths/ with fix_pikles.py (converts IDs to strings in place).
• Analyze path diversity across networks with analyzePaths.py, which reports edge Jaccard, overlap ratios, and cost dispersion per OD pair. Outputs path_diversity_summary.csv, path_diversity_per_od.csv, and path_diversity_log.txt.

python pathGenerator/pathSetGenerator_fast.py
python pathGenerator/fix_pikles.py
python pathGenerator/analyzePaths.py

Network Format

Networks are stored as TNTP files (net.tntp, trips.tntp) or pre-converted DAT files (network.dat, demand.dat). Conversion happens automatically on first run via helper.convert_network_tntp_to_dat / convert_demand_tntp_to_dat.

Reproducing Paper Results

Note on reproducibility. The results in the paper use path sets that are stored as Paths/allPathsODCache_{k}_{NetworkName}.pkl. The path sets marked "Yes" above are included in this repository. All path sets used in the paper can be downloaded from Texas Data Repository. Regenerating path sets with pathGenerator/ can take a long time on large networks, and results obtained on a different path set may not match the paper exactly (particularly those using the link-penalty heuristic rather than Yen's k shortest paths). Hence, we recommend using the same path sets, either those provided with this repository or those that can be downloaded from the link above.

The three batch scripts each reproduce a specific part of the paper's experiments:

Script	Paper role
generate_convergence_results.py	Runs different I_s and theta values to generate the data for Tables 3–4 (MSA-ACS convergence rate analysis)
generate_eigenvalue_results.py	Computes eigenvalues for reduced Jacobian and step-size bounds at the converged equilibrium (Table 5)
generate_assignment_results.py	Runs every network × demand multiplier × step-rule combination and writes log files used for Tables 7–10 and the convergence/runtime plots

Once the log files exist (after running the batch scripts above), run:

python genPlots.py

This writes all five paper tables as LaTeX to Plots/all_tables.tex and saves all convergence and runtime-vs-gap PDF figures to Plots/.

Output File Structure

Log files — logResults/<NetworkName>/

One file per run, named:

{NetworkName}_theta{θ}_d{demand}x_K{k}_{StepRule}.txt

Example: Sioux Falls_theta1.0_d1.0x_K20_Newton.txt

Each line after the header records one iteration:

Iteration: N, Gap: G, TSTT: T, Alpha: α, Time elapsed: t, Newton taken?: Bool

Field	Description
Iteration	Iteration number
Gap	Relative gap (RGAP)
TSTT	Total system travel time
Alpha	Step size used
Time elapsed	Wall-clock seconds for this iteration
Newton taken?	Whether a Newton-GMRES step was accepted

Plot files — Plots/

Pattern	Description
convergence_plot_{Network}_theta{θ}_k{k}_demand{d}x.pdf	RGAP vs iterations for all step rules
runtime_vs_gap_{Network}_theta{θ}_k{k}_demand{d}x.pdf	RGAP vs wall-clock time for all step rules
all_tables.tex	All five paper tables as ready-to-include LaTeX
{network}/	Per-network subdirectory with additional convergence figures from plotAll

Contact

For questions, collaborations, or further discussions, feel free to reach out:

• Email: debojjalb@utexas.edu
• Website: https://debojjalb.github.io

Acknowledgements

The SUE assignment code was adapted from Traffic-Assignment.