Route choice models predict which path a traveler takes through a road network. Their central obstacle is counting: between two points in a city there are more possible paths than can ever be listed, so researchers estimate models on a small sampled subset of paths. The sampling has to be corrected afterwards, and that correction needs the exact probability that the sampler would produce each path. The correction is known to work. It recovers true behavioral parameters on a 38-node test network where every path can be listed. It has not been shown to work on realistic networks, because the smart samplers used there make those probabilities expensive or ill-defined. A second family of models, recursive logit, avoids sampling entirely by treating route choice as a sequence of link-by-link decisions. It can only express preferences that add up link by link, so it cannot capture effects such as "overlapping routes are partly the same option."
This note proposes to use the second family as the sampler for the first. We solve a recursive logit model, which is a single sparse linear system over links. We then draw paths from it as a Markov chain. Each path's sampling probability is an exact product of link transition probabilities, available at any network size. These draws feed a path-based model that keeps the non-additive attributes recursive logit cannot represent. The same machinery also supports a reproducible way to test whether synthetic trajectory benchmarks can stand in for private GPS data. Instead of trusting one generator, we check whether conclusions about estimators stay the same across several generators with different built-in assumptions.
Core Claim
The importance sampling correction for sampled choice sets adds $\ln(k_i/q_i)$ to the utility of each sampled path $i$. Here $q_i$ is the probability the sampler draws $i$, and $k_i$ is how often it was drawn. Frejinger, Bierlaire and Ben-Akiva (Sampling of alternatives for route choice modeling) supply this correction. They pair it with a biased random walk tuned by two Kumaraswamy shape parameters and with an "extended" path set used for the path-overlap attribute. Their validation used a network with exactly 170 paths between the tested origin and destination. Without correction, the estimated scale parameter fell from its true value 1.0 to as low as 0.14. With correction, estimates were statistically indistinguishable from the truth.
We claim that a recursive logit model makes a better sampler, for two reasons. The first is exactness at scale. If $P(a \mid s)$ is the recursive logit probability of taking link $a$ from state $s$, a sampled path $i = (a_1,\dots,a_L)$ has
$$q_i = \prod_{l=1}^{L} P(a_l \mid a_{l-1}),$$
and each transition probability comes from value functions computed by one linear solve (A tutorial on recursive models for analyzing and predicting path choice behavior).
The second reason is that it handles cycles cleanly. Recursive logit can generate looping paths, which the tutorial lists as an open nuisance. We discard them and keep only simple paths. Every retained path's probability then rescales by the same factor, the probability of drawing a simple path. That common constant appears in every alternative's correction term, so it cancels in the logit ratio. Rejecting cycles therefore costs efficiency but not correctness. The corrected estimator is
$$P(i \mid C_n) = \frac{\exp\big(\mu V_i + \ln(k_i/q_i)\big)}{\sum_{j \in C_n} \exp\big(\mu V_j + \ln(k_j/q_j)\big)}.$$
In this estimator, $C_n$ is the sampled set for traveler $n$ with the observed path added, $\mu$ is the scale parameter, and $V_i$ is the systematic utility. $V_i$ may include non-additive terms such as a Path Size overlap penalty.
A third point makes the sampler efficient rather than merely valid. We refit the link-additive part of $V$ at each estimation round and re-solve the recursive model with those parameters. The proposal then tracks the target model, which should raise the effective sample size. The biased random walk has no such self-tuning; the original paper leaves the choice of its shape parameters open for arbitrary topologies.
Research Program
The first component is the estimator itself. It has three parts: the recursive logit proposal, rejection of cyclic draws, and adaptive refitting of the proposal. We will derive its consistency, and give an effective-sample-size diagnostic computed from the $\ln(k_i/q_i)$ weights, so practitioners can tell when a sampled set is too small. Path Size will be computed on the sampled set and on a larger extended set, following Frejinger et al. We will measure how much the approximation to the universal-set value matters on large networks.
The second component uses exact enumeration as ground truth. Hop-constrained s-t Simple Path Enumeration introduces BC-DFS and JOIN, which list every simple path under a hop limit on graphs up to 1.46 billion edges. JOIN finished $k=6$ queries on Twitter-WWW in about 5.7 hours, where prior methods exceeded 24 hours. That work is purely deterministic. We use it to build a hop-limited universal set on mid-sized road networks. There, the full-enumeration logit is computable and serves as an exact reference that the sampled estimator should approach. This bridge between deterministic path listing and stochastic correction is absent in both literatures.
The third component is a stress test drawn from inverse reinforcement learning. Choice Set Misspecification in Reward Inference shows that when the observed choice is the worst option in the assumed set, inferred preferences invert, with mean regret 2.059 in 20x20 gridworlds. A sampler concentrated on attractive paths is exactly the setting that places an unusual observed route beside many better ones. The correction is unbiased in expectation, but its finite-sample behavior in this regime is unknown. We will build populations of travelers whose chosen routes are deliberately poor. On them we measure whether corrected estimates degrade gracefully or flip sign, and whether the effective-sample-size diagnostic flags the problem.
The fourth component addresses the reproducibility problem. Real trajectories are private, so parameter recovery can only be checked on synthetic choices. The danger is that a benchmark rewards whichever estimator matches its generator. Efficacy of Synthetic Data as a Benchmark motivates this concern. It finds synthetic test sets rank models well on simple tasks: Spearman rank correlation with real rankings was 0.94 on SNIPS intent detection. Ranking collapsed on complex extraction, to 0.20 on political named entity recognition. We will generate choices on the same networks from four generator families. The first is a path-based logit with strong overlap effects. The second is a pure recursive logit. The third mixes travelers with different cost sensitivities. The fourth consists of LLM agents with memory and personas in the style of AI-Driven Day-to-Day Route Choice. That paper simulated 1,700 agents on the Ortuzar and Willumsen network but never calibrated them against real GPS data and never used large choice sets.
For each generator we rank the estimators and then compute rank correlation across generators. A benchmark conclusion counts as trustworthy only if it holds across generators. This does not replace real data. It is a publishable, auditable check on whether a synthetic benchmark measures the estimator or its own generator. We will release the networks, generators, seeds and evaluation code so every number can be rerun.
Baselines
The naive reference is the practice most planners use. They generate an attractive path set with the same sampler and fit a standard logit without the $\ln(k_i/q_i)$ term. The file reports this failure mode as the scale parameter collapsing from 1.0 to 0.14 on the 38-node network (Sampling of alternatives for route choice modeling; see also Choice set generation for route choice models using a sampling approach). We should beat it by a wide margin everywhere. This comparison mainly confirms that our pipeline reproduces the known failure.
The strongest existing method is Frejinger et al.'s biased random walk with importance correction and extended-set Path Size. Its reported result is recovery of all true parameters, with t-tests showing no significant difference from true values, on 3,000 simulated observations over a 170-path universal set. No numeric parameter errors or t-statistics are reported in the file. To keep the comparison fair, both samplers get the same number of draws per observation, the same wall-clock budget, and the same extended set for Path Size. The random walk also gets a grid search over its two shape parameters on a held-out validation split. We are not claiming to beat it on the 38-node network, where both should recover the truth. On Sioux Falls (24 nodes, 76 links) and larger hop-limited networks, beating it means lower parameter root-mean-square error and closer-to-nominal confidence-interval coverage at equal compute, or equal accuracy at clearly lower compute.
The third baseline is recursive logit estimated directly with no sampling, which is the natural "why sample at all" competitor. It is correctly specified when the generator is purely link-additive, so it should win there. It is misspecified whenever overlap effects are present.
The exact reference is full-enumeration logit on BC-DFS hop-limited universal sets. The sampled estimators should converge toward it as draws increase.
Two ablations isolate what matters. One uses the recursive logit proposal with parameters frozen at an initial guess, which tests whether adaptation carries the gain. The other uses the recursive proposal without the correction term, which tests whether a good proposal alone suffices.
Why not just…?
Why not just sample paths uniformly? Uniform sampling removes the need to track attractiveness bias. On spatial networks, however, it draws winding routes almost exclusively. The effective number of realistic alternatives approaches zero, which is why the route choice literature abandoned it. We include uniform sampling of hop-limited paths, drawn from the BC-DFS enumeration, on mid-sized networks. We expect its effective sample size to be far lower at equal draws. We will report that result rather than assume it.
Why not just use recursive logit and skip path sets? This is a real threat. If overlap effects in real travel are weak, recursive logit alone is simpler and exact. The tutorial itself notes that adding non-additive attributes forces state-space expansion (A tutorial on recursive models for analyzing and predicting path choice behavior). That limitation matters only if such attributes matter. We settle this by sweeping the Path Size coefficient in the generator from zero upward. Our proposal should tie recursive logit at zero and pull ahead as overlap grows. If it never pulls ahead at realistic magnitudes, we will report that the extra machinery is unwarranted.
Why not just tune the biased random walk better? On small networks a well-tuned random walk may be as good as our method, and we expect a tie on the 38-node network. Our argument is that tuning its shape parameters is topology-specific, whereas the recursive proposal adapts through the estimated parameters themselves. The equal-budget comparison on larger networks, with a tuning grid given to the random walk, decides this. If the tuned walk matches us there, the contribution shrinks to the exact-enumeration validation and the synthetic-benchmark protocol, and we will say so.
Why not just validate on one realistic synthetic generator? A single generator cannot distinguish an estimator's accuracy from its agreement with the generator's assumptions. The rank collapse from 0.94 to 0.20 on harder tasks in Efficacy of Synthetic Data as a Benchmark warns that synthetic rankings can fail silently. The cross-generator rank correlation directly measures whether this happens in route choice.
Proposed Experiments
The first check is replication on the 38-node, 64-link network with 3,000 observations. We must reproduce both the uncorrected collapse of the scale parameter and the recovery by Frejinger et al.'s method before any new claim is made. Next we move to Sioux Falls and a series of progressively larger hop-limited road graphs. On each we report four quantities: parameter root-mean-square error, 95% confidence-interval coverage, effective sample size per second, and held-out log-likelihood of observed paths. Held-out likelihood speaks to the open question of whether sampled sets support prediction and not just estimation. On Sioux Falls we also compute predicted link flows as a forecasting check. For context, a graph-network surrogate reached $R^2 = 0.952$ on synthetic equilibrium flows in Learning traffic flows. That task differs from ours, so we use it only to calibrate expectations for flow accuracy.
Three results would decide the proposal. First, as overlap strength rises, our estimator must keep coverage near 95% while recursive logit's coverage falls. Second, at matched compute it must beat the tuned random walk on the largest networks. Third, the rank of estimators must stay stable across the four generator families, including the LLM-agent generator. If the third fails, that is still a result: it shows synthetic route benchmarks cannot substitute for private GPS data without multi-generator checks, and we would publish it as such. The adversarial "poor choice" populations are reported separately. They show whether the correction has a finite-sample failure mode the transportation literature has not examined.
References
- Sampling of alternatives for route choice modeling
- A tutorial on recursive models for analyzing and predicting path choice behavior
- Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice
- Choice Set Misspecification in Reward Inference
- Efficacy of Synthetic Data as a Benchmark
- AI-Driven Day-to-Day Route Choice
- Choice set generation for route choice models using a sampling approach
- Learning traffic flows: Graph Neural Networks for Metamodelling Traffic Assignment