Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
100,840 characters · 21 sections · 36 citation commands
Constrained Recursive Logit for Route Choice Analysis
\newcolumntype{C}{>{\arraybackslash}p{4em}}
\affil[1]{\it School of Computing and Information Systems, Singapore Management University} \affil[2]{\it SLSCM and CADA, Faculty of Data Science and Artificial Intelligence, College of Technology, National Economics University, Hanoi, Vietnam} \affil[*]{\it Corresponding author, [email removed]}
{\bf Keywords:} Constrained Recursive Logit; Route choice modeling; State-space extension; Transportation networks.
Route choice modeling is a central component of travel demand analysis, providing the basis for applications ranging from network design and traffic management to policy evaluation and infrastructure pricing. Among the existing frameworks, the recursive logit (RL) model FosgFrejKarl13 has become particularly popular due to its computational advantages: it avoids sampling of alternative routes, can be consistently estimated using maximum likelihood methods, and offers a tractable structure for prediction through dynamic programming.
Despite these strengths, a fundamental limitation of the RL model lies in its assumption of a universal choice set, where all possible paths between an origin and a destination are included in the consideration choice sets. This assumption often results in the assignment of positive probabilities to paths that are clearly unrealistic, such as those with excessively long travel times or those that violate natural feasibility conditions (e.g., exceeding an energy budget or ignoring temporal deadlines). As a consequence, the RL model may produce biased parameter estimates and misleading behavioral predictions in contexts where constraints play a defining role. To date, this limitation has not been satisfactorily addressed in the literature, leaving a gap between theory and practical travel behavior.
In this paper, we propose a novel Constrained Recursive Logit (CRL) model that explicitly incorporates feasibility constraints into the recursive logit framework. The proposed CRL model retains the computational advantages of the classical RL formulation---it requires no sampling of path alternatives and remains straightforward to predict---while systematically eliminating infeasible paths from the universal choice set. By doing so, the CRL model ensures that estimated choice probabilities reflect only realistic and feasible route choices. Specifically, we make the following contributions:
Our CRL model might have wide-ranging applications in constrained travel settings. Examples include trip planning under deadlines, electric vehicle routing where battery capacity limits the feasible path set, and shared mobility systems such as bike-sharing, where trip duration or rental constraints restrict traveler decisions. More generally, the CRL model bridges the gap between the theoretical elegance of recursive logit and the practical realities of constrained travel behavior, offering a robust and versatile tool for both empirical estimation and policy analysis in modern transportation systems.
Although our discussions in this paper focus on the route choice problems, the proposed CRL framework has broader applicability. In particular, it provides a general approach for incorporating feasibility constraints into dynamic discrete choice settings, which are widely used in fields such as activity-based travel demand modeling and sequential decision processes. For example, activity-based models often require capturing temporal or resource constraints in daily activity schedules BowmanBenAkiva2001. Similarly, in dynamic discrete choice models (DDCMs), feasibility conditions such as budget limits, time windows, or capacity restrictions play an important role in determining choice behavior Rust1987, AguirregabiriaMira2010. By systematically excluding infeasible alternatives from the universal choice set, CRL can offer a unified and tractable way to enhance behavioral realism across these domains.
The remainder of the paper is structured as follows. Section (ref) provides a brief review of the related literature. Section (ref) presents the standard RL model, which serves as the foundation for our proposed CRL framework. Section (ref) introduces the CRL formulation together with illustrative examples, while Section (ref) explores the fundamental properties of the model. Estimation methods based on the extended state-space representation are discussed in Section (ref). Section (ref) reports the results of numerical experiments, and Section (ref) concludes the paper. The Appendix provides further details, including extensions of CRL to handle multiple constraints and nested RL.
The literature on route choice modeling can broadly be categorized into path-based and link-based recursive approaches. Path-based models Prat09 rely on sampling of paths, which makes the resulting parameter estimates sensitive to the sampling procedure. Even when correction terms are introduced to ensure consistent estimation, prediction remains computationally challenging, particularly in large networks.
In contrast, link-based recursive models FosgFrejKarl13,MaiFosFre15,mai2021RL_STD,oyama2017discounted build on the dynamic discrete choice framework of Rust87 and are essentially equivalent to discrete choice models defined over the set of all feasible paths. These models have several attractive advantages: they can be consistently estimated without requiring path sampling, and they allow efficient prediction through dynamic programming. The first RL model was introduced by FosgFrejKarl13, and has since been extended in various directions, such as accounting for correlations between path utilities MaiFosFre15,Mai_RNMEV,MaiBasFre15_DeC, handling dynamic networks de2020RL_dynamic, incorporating stochastic time-dependent link costs mai2021RL_STD, or modeling discounted behavior oyama2017discounted. Applications of recursive models can be found in traffic management BailComi08,Melo12, network pricing zimmermann2021strategic, network interdiction mai2024stackelberg, and beyond. A comprehensive review is provided in zimmermann2020tutorial.
Despite their many strengths, most existing RL models share two fundamental limitations. First, they do not impose feasibility constraints, which implies that any path in the network is assigned a non-zero probability, even if it is clearly unrealistic (e.g., excessively long travel times or violations of energy or temporal constraints). Second, RL is known to suffer from instability in estimation when applied to highly cyclic networks, which is typically the case in real-world transportation systems MaiFrejinger22. These issues limit the behavioral realism and empirical robustness of RL models. Our proposed CRL framework retains the computational and estimation advantages of the classical RL model, but introduces feasibility constraints directly into the recursive formulation. In doing so, CRL ensures that infeasible routes are systematically excluded from the universal choice set, thereby resolving both the issue of unrealistic path probabilities and the instability of estimation in cyclic networks. This makes CRL a more robust and behaviorally consistent foundation for route choice modeling in constrained transportation systems.
It is worth noting that our CRL model is closely related to prism-based approaches, which also extend RL models by restricting the universal path set. Specifically, OyaHat19 introduced a prism-based path set restriction for Markovian traffic assignment, pruning paths outside a feasible travel-time prism and thereby avoiding the assignment of positive probabilities to unrealistically long routes. Building on this idea, oyama2023prism_estimation applied prism constraints to RL estimation, showing that they improve stability and better capture positive network attributes by excluding infeasible alternatives. While prism-based methods incorporate path feasibility, they are limited to unit-value constraints (i.e., assigning a cost of one per transition). In contrast, our CRL framework generalizes this idea by accommodating a broader class of constraints---such as travel-time deadlines, energy budgets, or rental duration limits---directly within the recursive structure. This generalization yields a unified and flexible framework for modeling constrained route choice behavior.
Our CRL framework is also related to the literature on constrained discrete choice models, which has primarily focused on introducing feasibility restrictions within classical static frameworks. For example, the constrained nested logit model constrained_nested_logit incorporates both hard constraints, which eliminate infeasible alternatives, and soft constraints, which reduce the attractiveness of certain options. Likewise, spatially constrained destination choice models constrained_destination_choice impose restrictions based on land use and trip distribution, thereby yielding more behaviorally realistic predictions. While these approaches highlight the value of incorporating constraints into discrete choice models, they remain static and path-based, and therefore differ fundamentally from link-based recursive formulations such as CRL in both their estimation strategies and predictive capabilities.
The RL and CRL models also share a strong connection with the literature on dynamic discrete choice models (DDCMs) Rust87,aguirregabiria2010ddcm,mai2020relation. Recent extensions of DDCMs bruneel2025dynamic,Chen2025ModelAdaptive have advanced computational techniques for handling large state spaces and, in some cases, allow for implicit incorporation of constraints. However, these models are predominantly applied in economics and industrial organization rather than in transportation networks. By contrast, our work focuses specifically on transportation networks, and establishes a direct connection between the link-based RL framework and the path-based MNL model under both universal and restricted universal choice sets. In this sense, the CRL model bridges the gap between the constrained discrete choice literature and recursive route choice modeling, providing both behavioral realism and computational tractability.
Consider a set of states ${\mathcal{S}}$, where each state $s \in {\mathcal{S}}$ represents a link or node in the transportation network. Let $N(s) \subseteq {\mathcal{S}}$ denote the set of states that are directly reachable from state $s$. Here, $N(s)$ can represent the set of outgoing nodes (or links) from state $s$. For each trip with destination $d$, we introduce $d$ as an absorbing state into the system, making the set of all states $\widetilde{{\mathcal{S}}} = {\mathcal{S}} \cup \{d\}$.
In the context of the recursive logit (RL) model, each path choice is modeled as a sequence of state choices, which could correspond to a sequence of link or node choices in the transportation network. Under the random utility maximization framework, each pair of states $(s, s')$, where $s' \in N(s)$, is associated with an instantaneous random utility: \[ u(s'|s) = v(s'|s) + \mu \epsilon(s'), \] where:
At each state, the traveler is assumed to choose the next state to maximize their expected utility: \[ \mathbb{E}_{\epsilon} \left[ \max_{s' \in N(s)} \{ v(s'|s) + V(s') + \mu \epsilon(s') \} \right], \] where $V(s)$ is the expected maximum utility from state $s$ to the destination $d$. This expected utility function can be recursively calculated as: \[ V(s) =
\]
Here we note that the value function $V(s)$ could be dependent of both the destination $d$ and the traveler's characteristics, but these indicators are omitted here for notational simplicity.
Given the value function $V$, the probability that a traveler chooses state $s'$ from state $s$ can be computed as: \[ P(s'|s) =
\] The probability of observing a path $\sigma = \{s_0, \ldots, s_n\}$ can then be calculated as: \[ P(\sigma) = \prod_{t=0}^{n-1} P(s_{t+1}|s_t) = \exp(v(\sigma) - V(s_0)), \] where $v(\sigma)$ is the total deterministic utility of the path $\sigma$, defined as: $v(\sigma) = \sum_{t=0}^{n-1} v(s_{t+1}|s_t)$.
For model estimation, each deterministic utility function \(v(s'|s)\) can be specified as a (linear) function of various link or node attributes, such as travel time and cost, along with parameters to be estimated. Given a set of observed paths, the model parameters can be estimated using Maximum Likelihood Estimation (MLE) by maximizing the log-likelihood of these observations Mcfadden2001economicNobel,FosgFrejKarl13.
It is important to note that the RL model can be considered a specific case of the logit-based dynamic discrete choice model aguirregabiria2010ddcm,mai2020relation,Rust87. To elaborate, let \(\phi_t(s_t | {\pmb{\epsilon}}_t): {\mathcal{S}} \rightarrow {\mathcal{S}}\) represent a decision rule at time step \(t = 0, 1, \ldots\), determining the next state \(s_{t+1}\) based on the current state \(s_t\) and the realization of the random terms \({\pmb{\epsilon}}_t\). The RL model can then be framed as a logit-based discrete choice model, where the objective is to select a set of decision rules that maximize the expected long-term utility: \[ \max_{\phi_0,\phi_1,\ldots} \mathbb{E}_{{\pmb{\epsilon}}}\left[\sum_{t = 0}^\infty v(s_{t+1}|s_t) +\mu \epsilon(s_{t+1})\right]. \]
In the following, we present the formal formulation of the CRL model and provide illustrative examples that demonstrate how it captures constrained route choice behavior in networks.
The CRL model extends the standard RL framework by explicitly incorporating constraints into travelers’ route choice behavior. Specifically, we assume that each movement from state \(s_t\) to state \(s_{t+1}\) is associated with a cost function \(c(s_{t+1} \mid s_t)\), reflecting the cost incurred by travelers when transitioning from \(s_t\) to \(s_{t+1}\). These cost values can take either positive or negative values. Travelers are assumed to make route choice decisions by maximizing their expected accumulated random utility while ensuring that the total accumulated cost at every point in time does not exceed a given threshold $\alpha$.
For example, in the context of electric vehicles (EVs), drivers must ensure that, at any point in time, the total consumed energy does not exceed the remaining battery charge before reaching a charging station or their destination. Here, \(c(s_{t+1}|s_t)\) represents the energy consumed on the path from \(s_t\) to \(s_{t+1}\), which depends on factors like travel time and road conditions, while \(\alpha\) corresponds to the initial battery charge at the start of the trip. The cost function \(c(s_{t+1}|s_t)\) typically takes positive values, reflecting energy consumption. However, it can take negative values if the vehicle visits a charging station, where it can partially recharge or replace the battery. This flexibility allows the model to realistically capture travel scenarios involving resource constraints. Another example is the context of bike-sharing systems, where companies often impose a time limit on each rental session. For instance, a bike may need to be returned to a designated station within a specific duration, such as 30 minutes, to avoid additional fees or penalties. For example, in Singapore, Anywheel's daily pass allows users unlimited rides per day, but each trip cannot exceed 30 minutes or they incur a surcharge of S\$0.50 per 30 minutes (\url{https://www.sharedmobility.news/bike-sharing-time-crack-free-riding}). Such a requirement forces travelers to plan their routes carefully to ensure they can return the bike within the allowed time frame. If the total trip exceeds the time budget, the traveler may need to return the bike to a station, complete the current rental session, and start a new one to continue their journey.
\paragraph{Non-Markovian Property.} It can be observed that a policy solving the above constrained modeling problem would be non-Markovian (and therefore not stationary). This means that the choice probability at a state $s_t$ would depend not only on the state $s_t$ itself but also on the entire historical trajectory $\{s_0, \ldots, s_t\}$. To illustrate this, consider the simple example shown in Figure (ref). The network contains four nodes, where $a$ is the origin and $d$ is the destination. Each edge is labeled with its associated cost. Let $\alpha = 12$, which implies that we need to seek a policy assigning zero probability to paths whose cost exceeds 12. In this scenario, from node $c$, if the traveler takes the edge $[a,c]$, both outgoing edges from $c$ to $d$ will form paths with a total cost less than 12. Thus, both edges $[c,4,d]$ and $[c,1,d]$ are feasible choices. On the other hand, if the traveler takes the path $[a,b,c]$, they cannot take the edge $[c,4,d]$ because the total cost would exceed $\alpha$. In this case, $[c,1,d]$ becomes the only feasible path to reach the destination.
From this example, it is evident that the policy at state $c$ depends on the historical path the traveler took to arrive at $c$. This demonstrates the non-Markovian property of the constrained policy. This phenomenon can also be observed in a more general context. For instance, in an EV scenario, at a state, if the driver chooses a path that helps conserve energy, they might be able to reach the destination directly without stopping at a charging station. In contrast, if the driver has depleted energy due to a historically long or energy-intensive route, they will need to stop at a charging station to ensure they can reach their destination.
\paragraph{Mathematical Formulation. } To model such a non-Markovian behavior, let \(\pi(s_{t+1} \mid S_t)\) denote the probability that the traveler chooses the next state \(s_{t+1}\) conditional on a joint state \(S_t = \{s_0, \ldots, s_t\}\), which represents the historical path from the origin to state \(s_t\). Due to the incorporation of constraints, the resulting decision process is no longer Markovian—the policy at state \(s_t\) may depend on the entire trajectory up to \(s_t\). We will discuss the non-Markovian property in more detail in the next section.
At each state \(s_t\), the traveler chooses the next state \(s_{t+1}\) by maximizing the following expected utility: \[ \mathbb{E}_{\epsilon} \left[ \max_{s_{t+1} \in N(s_t)} \left\{ v(s_{t+1} \mid s_t) + V(S_{t+1}) + \mu \epsilon(s_{t+1}) \right\} \right], \] where \(v(s_{t+1} \mid s_t)\) denotes the immediate deterministic utility of moving from \(s_t\) to \(s_{t+1}\), \(V(S_{t+1})\) is the expected utility from the joint state \(S_{t+1} = S_t \cup \{s_{t+1}\}\) to the destination, and \(\epsilon(s_{t+1})\) are i.i.d. Gumbel (Type I extreme value) distributed random utilities.
Under this assumption, the value function \(V(S_t)\) from the joint state \(S_t\) is computed as:
where \(C(S_t)\) is the accumulated cost along the path \(S_t\), given by \[ C(S_t) = \sum_{i=0}^{t-1} c(s_{i+1} \mid s_i), \] and \(\alpha\) is the upper bound on the allowable accumulated cost. Intuitively, when the cost exceeds this threshold, the value function becomes \(-\infty\), ensuring that the corresponding choice probability becomes zero.
Given the value function, the choice probability is given by a MNL model: \[ \pi(s_{t+1} \mid S_t) =
\] Finally, given an observed path \(\sigma = \{s_0, \ldots, s_T\}\), the path probability under the constrained RL model is given by: \[ P(\sigma) = \prod_{t=0}^{T-1} \pi(s_{t+1} \mid S_t). \]
It can be seen that, under the value function defined above, at any state \( S_t \), if there exist two candidate next states \( s \) and \( s' \) such that the accumulated cost of transitioning to \( s \) remains below the threshold \(\alpha\), while the accumulated cost of transitioning to \( s' \) exceeds \(\alpha\), then—as expected—the probability of choosing state \( s' \) will be zero. We formalize this observation in the following proposition:
The above proposition highlights an important implication of the model: for any path, if at any point along that path the accumulated cost exceeds the specified upper bound \( \alpha \), then the probability of taking that path is exactly zero. This result is consistent with the real-world constraints observed in several application domains. For instance, in the EV routing example, a driver must ensure that the battery never depletes entirely along the journey. As such, the driver would never consider a path that would result in the energy level dropping to zero at any point along the way, which corresponds to a constraint violation and thus leads to zero path probability. Similarly, in the context of bike-sharing or bike rental systems, consider a policy where users are required to return the bike within 30 minutes before initiating a new rental; otherwise, they incur a substantial penalty Tsushima2023timelimit. In this case, a traveler (or renter) would not consider any path that violates this time constraint at any moment along the route. The model naturally encodes such behavior: any path that violates the constraint, even temporarily, will be assigned zero probability and effectively ruled out from the consideration choice set of paths.
We present some simple examples to illustrate the implications of the modeling framework discussed above.
\paragraph{Example 1: Route choice with travel time upper-bounds} The first scenario considers a route choice problem in which we assume that travelers will not consider invalid route whose travel times exceed a travel time upper-bound $\alpha$. This is a common case in real world: A taxi driver chooses a route to pick up customer on time, or a shipper plans to deliver packages before a deadline.
We consider a toy network shown in Figure (ref), where node \( k_0 \) is the origin and node \( d \) is the destination. The number on each edge represents its travel time. The utility associated with each transition from node \( s \) to node \( s' \) is computed as \( v(s' \mid s) = -2 \times TT(s' \mid s) \), where \( TT(s' \mid s) \) denotes the travel time from \( s \) to \( s' \). The cost is also defined as the travel time on each edge, and we impose an upper bound \( \alpha = 2.5 \), meaning that any path with a total travel time exceeding 2.5 hours will be assigned zero probability under the constrained model.
In Table (ref), we report the path probabilities computed under both the original (unconstrained) RL model and the constrained RL model with \( \alpha = 2.5 \). The values in parentheses represent the total travel time for each path. As observed, in the unconstrained setting, all paths have non-zero probabilities. In contrast, when the constraint is enforced, the probabilities of paths \([1,2]\) and \([1,3,4,6,2]\) become zero due to violation of the travel time limit.
In the previous example, the costs represent travel times, which are always non-negative. In this section, we present a scenario where the cost can take both negative and positive values. Specifically, we consider a route choice problem for rechargeable vehicles that consume some form of energy (e.g., fuel or electricity) to operate. During long trips, such vehicles must periodically refuel or recharge at gas stations or charging stations.
In this scenario, certain locations in the network represent charging stations where a vehicle can replenish its energy up to a specified level in order to continue the trip. The cost function \( c(s' \mid s) \) represents the net energy change when transitioning from state \( s \) to state \( s' \). Specifically, this cost takes a positive value when the vehicle travels along a road segment—corresponding to energy consumption—and a negative value when the vehicle visits a charging station—corresponding to energy replenishment. At the origin, the initial negative cost reflects the vehicle's starting energy level. The energy constraint imposes that the accumulated cost at any point in time must remain less than or equal to the vehicle's maximum energy capacity, denoted by \( \alpha \). Formally, this is expressed as \( C(S_t) \leq \alpha \) for all time steps \( t \). This condition ensures that the vehicle does not exceed its energy capacity and has sufficient energy to complete its journey.
We consider the toy network illustrated in Figure (ref), which comprises 7 nodes and 10 links. The driver seeks to travel from the origin node \( k_0 \) to the destination node \( d \). Each link is annotated with its travel time, and for simplicity, we assume that the travel time on a link is equal to the amount of energy consumed when traversing it. In this setting, Nodes 4 and 7 are designated as recharging stations. When the vehicle visits either of these nodes, the accumulated cost—representing the total energy consumed—is reset to zero, simulating a full recharge. We model the energy constraint by setting the initial energy level to zero, representing a fully charged vehicle at the start of the trip. Each traversal of a road link increases the accumulated cost (i.e., depletes energy), while visits to recharging stations reset this cost to zero, thereby allowing the vehicle to continue its journey without violating the energy constraint.
Different values of the constraint parameter \( \alpha \) lead to different sets of feasible paths. Intuitively, when \( \alpha \) is high—corresponding to a vehicle with greater energy capacity—more paths become feasible and are included in the route choice set. In contrast, when \( \alpha \) is low, the vehicle must visit charging stations more frequently to ensure it has sufficient energy to complete the trip. In the following, we illustrate how path choice probabilities vary with different values of \( \alpha \), specifically \( \alpha \in \{3, 4, 5\} \).
In Table (ref), we report the path choice probabilities computed using the constrained Recursive Logit (RL) model under different energy thresholds \( \alpha \). As observed, when \( \alpha = 5 \), all candidate paths satisfy the energy constraint and are therefore feasible, resulting in strictly positive choice probabilities for all paths. However, as the threshold \( \alpha \) decreases, some paths become infeasible due to excessive energy consumption without sufficient opportunity for recharging. Consequently, these paths receive zero probability under the constrained model. In particular, when \( \alpha = 3 \), only a single path—namely \([1,3,4,5,6,7,2]\)—remains feasible. This path includes both designated charging stations at Nodes 4 and 7, allowing the vehicle to replenish its energy and continue the trip under the energy constraint.
For visualization purposes, Figure (ref) illustrates the path choice probabilities under three different values of the energy constraint parameter \( \alpha \). The link utilities \( v(s' \mid s) \) are defined as \( -2 \times TT(s' \mid s) \), where \( TT(s' \mid s) \) is the travel time between nodes \( s \) and \( s' \). In the figure, dashed links represent transitions with zero probabilities under the constrained model, while the thickness of each solid link reflects the magnitude of its corresponding choice probability. For example, when \( \alpha = 5 \), all links are feasible and thus have positive probabilities. Among them, the link \( (1,3) \) has the highest probability of being chosen. Furthermore, at Node 3, the probability of transitioning to Node 4 (a charging station) is higher than the probability of transitioning to Node 6. In contrast, when \( \alpha = 3 \), several links—including \( (1,2) \), \( (3,6) \), and \( (5,2) \)—have zero probability of being selected, as they lead to infeasible paths that violate the energy constraint. This visualization highlights how stricter energy constraints restrict the set of viable routes and alter the structure of the route choice probabilities accordingly.
It is important to highlight that \([1,3,4,5,6,7,2]\) is also the longest path in terms of travel time. This outcome underscores a critical insight: when energy constraints are in place, travelers may be forced to take longer routes in order to ensure sufficient energy availability, particularly through visits to charging stations. In contrast, in the unconstrained setting, this longest path receives the lowest choice probability due to its higher travel cost. This comparison demonstrates that ignoring operational constraints—such as energy limits—can result in significantly biased or incorrect predictions of route choice behavior. Incorporating such constraints into the modeling framework is therefore essential for producing realistic and reliable results.
We now present a larger illustrative example to highlight the impact of feasibility constraints in route choice modeling for rechargeable vehicles. The network, shown in Figure (ref), is a $5 \times 5$ grid consisting of $25$ nodes, among which $4$ are designated as charging stations. A vehicle travels from node $1$ (bottom left) to node $25$ (top right). Each edge is associated with a travel time, and the instantaneous utility of traversing an edge is set to the negative of its travel time.
For the CRL model, we assume that the energy consumed on each link is equal to its travel time. The vehicle has a finite energy capacity of $\alpha = 7$, meaning it must recharge at a station before the remaining energy is exhausted. This setting naturally enforces feasibility constraints: any route that exceeds the energy capacity without visiting a station is considered infeasible and is excluded from the consideration choice set.
We compute link choice probabilities under both the RL and CRL models using the specified link utilities. The resulting choice probability distributions are visualized by varying the thickness of the links in (ref) and (ref). In the RL model with an unrestricted choice set, links closer to the diagonal from node $1$ to node $25$ dominate, as they correspond to shorter travel times, whereas links farther away from the diagonal have lower probabilities.
In contrast, the CRL model with the energy upper-bound $\alpha=7$ yields drastically different probability patterns. Routes near the diagonal, which appear optimal under the RL model, become infeasible due to the absence of charging stations in that region and therefore disappear from the choice set. Instead, feasible routes that include detours to charging stations, often located near the corners, retain non-negligible probability mass. This result demonstrates how the CRL model successfully captures feasibility constraints that fundamentally alter the set of available alternatives, leading to more realistic modeling of traveler behavior in energy-constrained settings.
In this section we delve into the main properties of the CRL model described above.
First, to better understand the modeling formulation of the CRL model, let us connect it with a logit-based path choice model. It is well-known that the standard RL model is equivalent to the MNL model over the universal choice set of paths. That is, let $\Omega$ be the set of all possible paths reaching the destination $d$. The path choice probability given by the RL model can be expressed as:
where $v(\tau)$ is the accumulated utility of path $\tau$. Similarly, the proposition below shows that, if the cost $c(s'|s)$ are non-negative, the CRL formulation gives path choice probabilities equivalent to an MNL model over a restricted universal choice set:
We note that Proposition (ref) no longer holds if the cost function is allowed to take both positive and negative values. The reason is that when \( c(s' \mid s) \) can be either positive or negative, the condition \( C(\tau) \leq \alpha \) is not sufficient to guarantee the feasibility of a path \( \tau \). In particular, even if the total accumulated cost along a path satisfies the constraint, the path may still be infeasible if, at any intermediate state \( s_t \), the accumulated cost \( C(S_t) \) exceeds \( \alpha \). This violates the per-step feasibility condition imposed by the constraint.
To extend Proposition (ref) to the case where the cost function can take both positive and negative values, we refine the definition of the restricted choice set as follows:
Under this definition, we can show that the CRL model is also equivalent to a MNL model over the restricted choice set $\overline{\Omega}^\alpha$.
A direct implication of Proposition (ref) is that, for any given path \( \tau \in \overline{\Omega}^\alpha \), the path choice probability assigned by the original RL model is less than or equal to that assigned by the CRL model. As a result, the in-sample log-likelihood under the CRL model is always greater than or equal to that under the standard RL model. We formally state this result in the following corollary.
The corollary follows directly from the fact that the restricted choice set \( \overline{\Omega}^\alpha \) is a subset of the universal choice set \( \Omega \), which immediately implies: \[ \sum_{\tau \in \overline{\Omega}^\alpha} \exp\left( \frac{1}{\mu} v(\tau) \right) \leq \sum_{\tau \in \Omega} \exp\left( \frac{1}{\mu} v(\tau) \right). \] This inequality directly leads to the result \( P^{\text{RL}}(\tau) \leq P^{\text{CRL}}(\tau) \) for any feasible path \( \tau \in \overline{\Omega}^\alpha \). Equality holds, i.e., \( P^{\text{RL}}(\tau) = P^{\text{CRL}}(\tau) \) for all \( \tau \), if and only if the restricted and universal choice sets are identical, that is, \( \overline{\Omega}^\alpha = \Omega \). In this case, all paths are feasible with respect to the constraint, and the CRL model reduces to the standard RL model. In fact, we can see that the inequality above is strict if the universal choice set $\Omega$ strictly contains the feasible set $\overline{\Omega}^{\alpha}$, i.e., $\mathcal{L}^{\text{CRL}}(\mathcal{D}) > \mathcal{L}^{\text{RL}}(\mathcal{D}),$ whenever there exists a path $\tau \in \Omega$ that is not feasible with respect to the constraint ($\tau \notin \overline{\Omega}^{\alpha}$).
As discussed above, the CRL model is inherently non-Markovian, since the choice probabilities at a given state (i.e., a node in the network) depend not only on the current state but also on the sequence of historical states visited. This violation of the Markov property renders the model impractical for estimation and prediction. To address this issue, in the following section we propose an approach based on state-space expansion. The key idea is to augment the state representation with the information regarding the accumulated cost, thereby transforming the CRL model into an equivalent Markovian model. Once the Markov property is restored, the problem can be reformulated as a standard RL model, enabling efficient estimation through classical methods such as value iteration. We begin by presenting our approach to transform the model into a Markovian form, followed by a discussion of the associated estimation methods.
To achieve Markovian choice probabilities, we leverage the observation that the expected utility at a state $s_t$ depends only on the accumulated cost at that state, rather than on the entire history of previously visited states. This motivates us to incorporate the accumulated cost into the state representation, thereby ensuring that the value function is independent of the historical trajectory.
Formally, we define an extended state space $\widetilde{\mathcal{S}}$, where each extended state $\widetilde{s} \in \widetilde{\mathcal{S}}$ is a pair $\widetilde{s} = (s,z),$ with $s \in \mathcal{S}$ denoting the original state and $z \in \mathbb{R}$ the accumulated cost up to that state. Similarly, we define the set of feasible next states in the extended space as \[ \widetilde{N}(\widetilde{s}) = \bigl\{ (s',z') \;\big|\; s' \in N(s), \; z' = z + c(s' \mid s) \bigr\}, \] that is, each successor in the extended state space consists of a next state $s'$ from the original state space together with the updated accumulated cost $z' = z+c(s'|s)$.
We now formulate a RL model on this extended state space. At each extended state $\widetilde{s}_t = (s_t,z_t)$, the decision-maker selects the next state $\widetilde{s}_{t+1} = (s_{t+1},z_{t+1})$ by maximizing the expected utility \[ \mathbb{E}_{\epsilon} \left[ \max_{\widetilde{s}_{t+1} \in \widetilde{N}(\widetilde{s}_t)} \Bigl\{ \widetilde{v}(\widetilde{s}_{t+1} \mid \widetilde{s}_t) + \widetilde{V}(\widetilde{s}_{t+1}) + \mu \, \epsilon(\widetilde{s}_{t+1}) \Bigr\} \right], \] where $\widetilde{v}(\widetilde{s}_{t+1} \mid \widetilde{s}_t)$ denotes the deterministic immediate utility of moving from $\widetilde{s}_t$ to $\widetilde{s}_{t+1}$, given by \[ \widetilde{v}(\widetilde{s}_{t+1} \mid \widetilde{s}_t) = v(s_{t+1} \mid s_t), \] $\widetilde{V}(\widetilde{s}_{t+1})$ is the expected utility value from the extended state $\widetilde{s}_{t+1}$ to the destination, and $\epsilon(\widetilde{s}_{t+1})$ are i.i.d.\ Gumbel-distributed (Type I extreme value) random components.
The value function $\widetilde{V}(\widetilde{s}_t)$ associated with state $\widetilde{s}_t = (s_t,z_t)$ is defined recursively as
In other words, the value function is assigned $-\infty$ whenever the accumulated cost at the current state exceeds the upper bound $\alpha$. In all other cases, it takes the standard log-sum-exp form of the RL model. This construction ensures that any path whose cumulative cost violates the constraint is rendered infeasible and, consequently, is assigned zero probability of being chosen in the decision process. In effect, the extended state-space formulation enforces the feasibility constraints directly within the recursive structure of the value function, thereby integrating the constraint into the Markovian dynamics of the model.
The choice probability at each state is given by the standard MNL model:
For notational convenience, we denote the recursive logit model defined on the extended state space by ERL. We are now ready to state the main result, which establishes the equivalence between the ERL and the CRL model.
Theorem (ref) establishes the equivalence between the non-Markovian CRL model and the Markovian ERL model. This equivalence is crucial, as it implies that estimation can be carried out on the extended state space using standard recursive logit estimation techniques, such as the NFXP algorithm Rust87. In the following, we provide a detailed discussion of the estimation procedure for the ERL model. In particular, we highlight an important property: under certain conditions, estimation based on the ERL formulation exhibits greater numerical stability compared to estimation of an unconstrained RL model. This stability arises because the ERL representation naturally enforces feasibility constraints through the extended state space, thereby eliminating infeasible paths and reducing irregularities in the likelihood function.
Since the ERL model takes the standard form of the RL model, its estimation can be carried out using the NFXP algorithm. In this approach, value iteration is employed to compute both the value function $\widetilde{V}(\widetilde{s})$ and the corresponding likelihood function. To make estimation computationally feasible, we impose an additional assumption on the cost structure. Specifically, we assume that the cost $c(s' \mid s)$ takes values in a discrete set. This assumption guarantees that the extended state space $\widetilde{\mathcal{S}}$ is finite and discrete, thereby enabling practical implementation of the NFXP algorithm on the ERL model.
The recursive definition of $\widetilde{V}(\widetilde{s})$ in (ref) allows us to define \[ \widetilde{Z}(\widetilde{s}) \;=\; \exp\!\left(\tfrac{1}{\mu}\widetilde{V}(\widetilde{s})\right), \] and rewrite the Bellman recursion in terms of $\widetilde{Z}(\cdot)$ as \[ \widetilde{Z}(\widetilde{s}) =
\] where $\mathcal{N}(\widetilde{s})$ denotes the original state $s \in \mathcal{S}$ corresponding to the extended state $\widetilde{s}$.
Equivalently, we may encode this system in matrix form. First, for any state $\widetilde{s}$ such that $\mathcal{C}(\widetilde{s})>\alpha$, we set $\widetilde{N}(\widetilde{s})=\emptyset$, effectively removing infeasible states from the recursion. Then we define a vector $B \in \mathbb{R}^{|\widetilde{\mathcal{S}}|}$ with entries \[ B(\widetilde{s}) =
\] and a nonnegative matrix $M \in \mathbb{R}^{|\widetilde{\mathcal{S}}|\times|\widetilde{\mathcal{S}}|}$ with elements \[ M(\widetilde{s},\widetilde{s}') =
\] With these definitions, the Bellman recursion can be written compactly as \[ \widetilde{Z} \;=\; M \widetilde{Z} + B, \] which is a linear system of equations. This form can be solved efficiently via value iteration or directly through matrix inversion. Importantly, the system admits a unique solution under some certain conditions, as stated in the following proposition.
An important implication of Proposition (ref) is that the estimation of the CRL and ERL models can be carried out more conveniently compared to the original recursive logit (RL) model. Specifically, prior work has shown that the estimation of the RL model may suffer from instability when the utility function takes large values, which can render the associated Bellman equations infeasible MaiFrejinger22. By contrast, Proposition (ref) establishes that if the cost associated with each transition between states is strictly positive---a condition that is generally satisfied in practical applications---then the Bellman equations of the ERL model always admit a unique solution, regardless of the scale of the utility function $v(s' \mid s)$. This property ensures that the ERL formulation avoids the degeneracies that may arise in the standard RL setting and thereby provides a stable foundation for consistent estimation.
In this section, we present a series of experiments to evaluate the effectiveness of the proposed CRL model in comparison with the standard RL model. The evaluation is carried out on both synthetic and real-world datasets. All experiments are conducted on a Google Cloud TPU v2-8 server equipped with a 96-core Intel Xeon 2.00 GHz CPU.
We first conduct experiments on synthetic datasets in order to evaluate the performance of the proposed CRL model, compared to the standard RL model. Two problem settings of particular interest are considered:
\paragraph{Network generation.} For computational tractability, we construct synthetic networks in the form of directed acyclic graphs (DAGs). The DAGs are generated as random geometric graphs Penrose2003RandomGeom, a topology frequently employed for benchmarking graph algorithms. In this setting, node locations are sampled uniformly at random within a unit square $[0,1]\times[0,1]$, and edges are created by connecting nodes whose Euclidean distance falls below a prescribed threshold. For each successive link, we associate four attributes---travel time, left turn, right turn, and U-turn---derived from the geometric positions of the incident nodes and their relative orientations. The travel time is proportional to the Euclidean length of the link, while turn indicators are determined from the angular relationship between consecutive links. This setup provides a controlled, yet flexible, framework for simulating route choice scenarios with heterogeneous link characteristics while maintaining a mathematically tractable network structure. To generate the observational data, we fix a ground-truth parameter vector $\beta = [-4, \; -0.1, \; -0.05, \; -0.3]^{\top}.$ We then simulate path choices according to the RL formulation.
\paragraph{Experimental setup.} The number of observations used for parameter estimation and in-sample prediction is set to $3000$, while an additional $1000$ observations are generated for out-of-sample prediction. Parameter estimation is conducted by maximizing the likelihood of the in-sample dataset, yielding estimated parameters $\beta^*$.
\paragraph{Evaluation metrics.} The quality of estimation is evaluated using log-likelihood measures. Given an observation dataset \(\mathcal{D} = \{\tau_1, \ldots, \tau_n\}\), we define the average log-likelihood under the estimated parameter vector $\beta^*$ as $\mathcal{L}^{RL}(\mathcal{D}\mid \beta^*) = \frac{1}{n} \sum_{i=1}^n\ln P^{\text{\tiny RL}}(\tau_i)$. Since log-likelihood values are always non-positive, values closer to zero indicate better alignment of the model with the observed data. Furthermore, to quantify the relative performance gain of CRL over RL, we further define the percentage improvement metric as:
A positive value of $\%Improve$ indicates that the CRL model achieves better performance (in terms of likelihood prediction) compared to the standard RL model.
The synthetic experiments enable us to systematically assess the effect of incorporating feasibility constraints (such as travel time thresholds or energy limits) into the choice model. In the standard RL formulation, unreasonable paths --- for example, those that violate energy constraints or whose travel times far exceed practical limits --- may still receive positive choice probabilities. This undesirable feature often results in biased parameter estimates and degraded predictive accuracy. By contrast, the CRL model explicitly removes infeasible paths from the universal choice set, ensuring that only feasible routes are considered in the estimation process. This leads to more robust parameter recovery and improved generalization capability. Consequently, the CRL model is expected to outperform the RL model when constraints are taken into consideration, in both for in-sample estimation and out-of-sample prediction
In this experiment, we consider a route choice setting in which the traveler imposes an upper bound on the total travel time. The networks and associated observations are generated as follows.
\paragraph{Graph generation.} We construct directed acyclic graphs (DAGs) of varying sizes, specifically with $20$, $30$, $40$, and $50$ nodes. For each size, $5$ independent DAGs are generated using the random geometric graph method. More precisely, $N$ nodes are uniformly distributed within a $1 \times 1$ geometric space. An edge is drawn between two nodes if their Euclidean distance is smaller than $\frac{2}{\sqrt{N}}$. Additional edges are added if necessary to ensure that the graph is connected. The node with the smallest index is designated as the source, the node with the largest index as the destination, and all edges are oriented from smaller to larger indices, thereby ensuring acyclicity.
\paragraph{Observation generation.} Let $T_{\max}$ denote the longest feasible travel time of any route from source to destination in a given DAG. The cost associated with each link is interpreted as the travel time on that edge. To impose feasibility, we introduce an upper bound $\alpha$ on the total travel time that a traveler is willing to accept, defined as $\alpha = \%threshold \times T_{\max},$ where $\%threshold$ is a parameter specifying the ratio of the upper bound relative to the longest possible route. We consider eight levels of $\%threshold$ ranging from $20\%$ to $90\%$.
Once $\alpha$ is specified, we generate route choice observations under two models:
\paragraph{Experimental protocol.} For each DAG and each $\%threshold$ setting, we conduct $10$ independent trials. In each trial, $3000$ in-sample and $1000$ out-of-sample route observations are generated. The estimated parameters obtained from the in-sample observations are then used to evaluate both in-sample and out-of-sample log-likelihood performance.
To quantify the improvement of CRL over RL, we compute the percentage improvement metric $\%Improve$ (defined in the previous section). For each configuration, the average $\%Improve$ across $10$ trials is reported. This provides a robust comparison of the two models across varying network sizes and travel time thresholds, highlighting the conditions under which the CRL model yields the largest performance gains.
\paragraph{Comparison results.} The estimation results obtained when the RL model is used to generate observations are shown in (ref). Out-of-sample results are almost indistinguishable from in-sample ones, indicating that both the observation size and the number of trials are sufficiently large to ensure consistent parameter estimation.
In terms of performance, the CRL model consistently achieves better (i.e., higher) log-likelihood values than the standard RL model. However, the performance gap between the two models decreases as the upper-bound threshold increases. This behavior is expected: when the threshold approaches $100\%$, nearly all routes remain feasible, and the CRL formulation reduces to the unconstrained RL model. Hence, under such conditions, the two models become virtually identical. At the other extreme, when the threshold is very tight (e.g., $20\%$ or $30\%$ of $T_{\max}$), the improvement of CRL over RL is less pronounced and even fluctuates across trials. This effect can be attributed to the limited number of feasible routes available under such strict constraints, which reduces the variability of the choice set and may cause instability in estimation.
When the observations are generated by the CRL model, the percentage improvements are reported in (ref). In this case, the downward trend of $\%Improve$ is more stable: the improvement decreases smoothly from approximately $8$--$10\%$ at $\%threshold=20\%$ to nearly $0\%$ at $\%threshold=90\%$. This confirms the expected behavior that, as the upper bound becomes less restrictive, the CRL and RL models converge to similar performance.
Another notable observation is that the performance gap between CRL and RL becomes less pronounced as the size of the DAG increases. This phenomenon is natural, since larger graphs imply exponentially larger route choice sets. With the number of observations fixed at $3000$, the sampled trajectories cover only a small fraction of the feasible choice set in larger graphs. As a result, the available data are less informative, and the distinction in performance between CRL and RL diminishes.
Taken together, these results demonstrate that the proposed CRL model offers estimation performance that is at least comparable to, and often better than, the standard RL model in the presence of upper-bound constraints. In particular, CRL better aligns with realistic travel behavior when such feasibility constraints are binding.
We next conduct experiments in a more challenging setting that incorporates an energy consumption constraint into the route choice behavior, mimicking the case of rechargeable vehicles. This setting is particularly relevant for modern transportation networks, where travelers must ensure that their remaining battery energy never falls below zero along the chosen route.
\paragraph{Graph generation.} As in the previous case, we generate DAGs with sizes ranging from $20$ to $50$ nodes. To simulate the availability of recharging infrastructure, a set of “stations” is randomly placed among the nodes of each graph. The number of stations is set to $10\%$ of the DAG size, reflecting the fact that only a limited fraction of nodes allow recharging.
\paragraph{Observation generation.} Since the standard RL model cannot simulate the action of fully recharging energy at stations (and thus cannot generate feasible trajectories under the energy constraint), we rely exclusively on the proposed CRL model to generate observations in this setting. This highlights an important strength of the CRL framework: its ability to naturally incorporate feasibility constraints into the path choice process. For each DAG size, we generate $5$ independent graph instances with randomly placed stations. For each instance, synthetic route choice data are generated under the CRL model.
(ref) reports the estimation errors of both RL and CRL in the energy-constrained setting. The performance gap between the two models is substantially larger here: CRL (orange dots) consistently outperforms RL (blue dots) across all graph sizes. The average improvements of CRL over RL for DAGs with $20$, $30$, $40$, and $50$ nodes are $21\%$, $10\%$, $17\%$, and $13\%$, respectively. This significant gain highlights the importance of explicitly modeling feasibility constraints. While the upper-bound constraint considered previously only limits the set of acceptable routes by travel time, the recharging constraint introduces a more intricate form of path feasibility that requires accounting for energy dynamics along the route. Since the standard RL model cannot capture this complexity, it misallocates probability mass to infeasible trajectories, leading to poorer estimation. By contrast, the CRL model systematically enforces the energy constraint through the extended state space, thereby yielding consistently higher likelihood values.
As discussed earlier, the CRL model entails higher computational requirements compared to the standard RL model. We now briefly examine this aspect. Figure (ref) compares the estimation times of RL and CRL across different network sizes and threshold levels. For small networks (20--30 nodes), the estimation times of the two models are nearly identical, with both completing estimation in under two seconds across all threshold percentages. This suggests that the additional state-space expansion required by CRL does not impose a significant computational burden at modest network scales.
As the network size increases to 40 and 50 nodes, differences between the two models become more noticeable. While the RL model maintains nearly constant estimation times (around $0.4$--$0.6$ seconds), the CRL model exhibits increasing estimation times as the threshold percentage grows, reaching about $2.8$ seconds for the largest networks under the most relaxed constraints. This reflects the fact that CRL estimation must operate on an extended state space, whose size grows both with the number of nodes and with looser feasibility bounds.
Overall, these results highlight a trade-off: CRL ensures behavioral consistency by eliminating infeasible paths, but at the expense of increased computational burden in large and cyclic networks.
\paragraph{Sioux Falls network.} In addition to synthetic datasets, we evaluate the proposed CRL model on the well-known Sioux Falls transportation network. Originally introduced by LeBlanc1975SiouxFalls, this network has become a standard benchmark in the transportation science and operations research literature for testing traffic assignment and route choice models. The Sioux Falls network consists of $24$ nodes and $76$ directed links, together with an origin--destination (OD) demand matrix that specifies travel demand between selected node pairs. Each link is associated with a free-flow travel time and a capacity parameter, allowing link travel times to be modeled under congestion effects (e.g., using the Bureau of Public Roads function).
The Sioux Falls network is particularly attractive as a benchmark for route choice models because it strikes a balance between realism and tractability: it is large enough to capture meaningful network structure and route diversity, yet small enough to permit efficient computation of RL and CRL likelihoods. In our experiments, we use the Sioux Falls network to assess the practical applicability of the CRL model on a realistic network topology and to compare its performance against the standard RL model.
As mentioned in Section (ref), one of the main advantages of the CRL model is that, under mild assumptions on the cost function, the Bellman equations always yield a unique solution. This solution can be computed efficiently either through value iterations or matrix inversion, thereby ensuring stable and efficient estimation. In contrast, as highlighted in MaiFrejinger22, the original RL model often fails to produce reasonable parameter estimates, particularly in networks with many cycles. In such cases, the recursive structure of the Bellman equations may break down or lead to unstable likelihood evaluations. The Sioux Falls network provides a challenging testbed in this respect: its topology contains numerous cycles, making estimation under the standard RL model highly unstable.
The primary objective of this experiment is therefore to compare the estimation stability of RL and CRL on the Sioux Falls network. By evaluating performance on this benchmark, we can assess whether the CRL formulation indeed provides the robustness required for realistic networks with cyclic structures.
\paragraph{Observation generation.} Due to the failure of the RL model in estimation (as reported below), we rely on the CRL model to generate observations. In this setting, the cost function is specified as $c(s,s') = 1$ for every edge $(s,s')$. This specification effectively imposes a constraint on the maximum number of edges that a traveler can traverse to reach the destination. Importantly, this choice satisfies the assumption stated in Section (ref), and therefore guarantees that the value function can always be computed successfully.
Following the same experimental protocol as before, we generate $3000$ in-sample trajectories and $1000$ out-of-sample trajectories. The CRL model incorporates six attributes to simulate route choice probabilities: road capacity, road length, travel time, left turns, right turns, and U-turns. The associated parameter vector used for data generation is $\beta = [-0.5,\; 0,\; 1,\; -0.1,\; -0.05,\; -0.3]^{\top}.$ Note that since some of these coefficients are positive, certain arcs may yield positive utility values. This, in turn, can cause the unconstrained RL model to misbehave and fail during estimation, highlighting the necessity of the CRL framework for stable likelihood evaluation in such settings.
The estimated average log-likelihood values for the two models are reported in (ref). As shown, the RL model fails to return reasonable log-likelihood values across all experimental setups. This failure occurs because the solver is unable to compute the Bellman equations successfully in networks with many cycles, resulting in undefined values. We denote these unsuccessful cases by “-” in the table. In contrast, the CRL model can be estimated successfully in all settings. Furthermore, its estimation results exhibit a clear downward trend as the maximum number of edges allowed by the constraint $\alpha$ increases. When the choice set is very small (e.g., routes with no more than $10$ edges), the estimated log-likelihood values are relatively high. As $\alpha$ increases (e.g., allowing up to $25$ edges), the log-likelihood values decrease substantially. This behavior is intuitive: for a fixed number of observations, expanding the restricted universal choice set introduces many additional feasible paths, thereby lowering the probability assigned to any particular observed route.
These results illustrate two key insights. First, the CRL formulation provides a stable and feasible estimation procedure even in challenging cyclic networks such as Sioux Falls, where the original RL model completely fails. Second, the relationship between $\alpha$ and the log-likelihood reflects the natural trade-off between model flexibility (larger choice sets) and estimation sharpness (higher likelihood concentration on observed data).
In this section, we present a comparative analysis of estimation results for the RL and CRL models. The dataset employed is the same as that used in previous studies on route choice modeling FosgFrejKarl13,MaiFosFre15,MaiBasFre15_DeC, collected in Borlänge, Sweden. The underlying network consists of $3077$ nodes and $7459$ links. Since the network is uncongested, link travel times can be treated as static and deterministic. The sample comprises $1832$ observed trips, each corresponding to a simple path containing at least five links. In total, the dataset covers $466$ destinations, $1420$ distinct origin--destination (OD) pairs, and more than $37{,}000$ link choices. The instantaneous utility function is given as follows:
in which $TT(a)$ is the travel time on link $a$, $LT(a|k)$ is a left turn dummy of the turn from link $k$ to $a$, $LC$ is a constant one value and $UT(a|k)$ is a u-turn dummy from $k$ to $a$.
Both RL and CRL are applied for in-sample estimation on the observation dataset. All experimental settings follow those in the original RL model publication FosgFrejKarl13. In this experiment, the constraint incorporated by the CRL model is a bound constraint on the link count of each route, which is defined as the sum of the $LC$ attribute values over the links in the route. The distribution of link counts across the $1832$ observed routes is illustrated in (ref). The maximum number of links in a single route is $106$, which naturally serves as the upper bound for the constraint. It is important to note that link count is already a discrete variable, making it straightforward to apply the CRL model in this context. Moreover, as discussed in Section (ref), the strict positivity of the cost values (here given by $LC$) ensures that the extended network is cycle-free. This property guarantees that the CRL model can be estimated efficiently using standard solution methods.
The estimation results for both RL and CRL are reported in (ref). Overall, the estimated parameters are very close across the two models, suggesting that both approaches capture the main behavioral patterns in the dataset. However, the CRL model achieves a slightly higher log-likelihood value ($-3.39$ compared to $-3.44$ for RL), corresponding to an improvement of approximately $1.5\%$ in the likelihood value.
We also apply a cross-validation approach to compare the prediction performance of RL and CRL. The full sample set is randomly split into two subsets: 80% of the observations are used for estimation, while the remaining 20% serve as a holdout set to assess predictive capability. In total, 30 different estimation–holdout partitions are generated. For each partition, we estimate the parameters on the estimation set and then compute the average log-likelihood on the holdout set using the estimated parameters. These predicted log-likelihood values across the 30 samples are shown in (ref), with the samples arranged in ascending order of RL’s prediction values for clarity. CRL consistently outperforms RL across all samples, with an average predicted log-likelihood of $-3.38$ compared to $-3.43$ for RL.
This modest yet systematic improvement demonstrates that the CRL formulation is capable of capturing additional structural constraints in traveler behavior that are overlooked by the unconstrained RL model. It should be noted, however, that the magnitude of the improvement is relatively smaller compared to the case of synthetic data reported earlier. This is largely due to the fact that the Borlänge network is uncongested, so travelers are not strongly constrained by travel time or link count. As a result, paths with the shortest travel times dominate the choice probabilities, leaving limited scope for CRL to provide large gains over the unconstrained RL formulation. Nevertheless, even under such favorable conditions for RL, the CRL model still delivers consistent in-sample and out-of-sample improvements, underscoring its robustness in capturing feasibility conditions whenever they are present.
It is worth noting that the computational cost of CRL is substantially higher than that of RL (approximately $50\times$ higher for this real dataset). This increase reflects the added complexity of operating on the extended state space. Nevertheless, the improved model fit demonstrates that CRL provides significant value in situations where datasets involve constraints or atypical features that cannot be adequately captured by the standard RL model. Importantly, estimation remains feasible in practice: it can be completed in under ten hours, and further speedups are possible through parallel computing or decomposition techniques MaiBasFre15_DeC. These observations highlight the practical viability of CRL for large-scale, real-world datasets.
This paper introduced the CRL model, which extends the classical RL framework by explicitly incorporating feasibility constraints into the universal choice set. By enforcing that any path violating a constraint receives zero probability, the CRL model yields behaviorally consistent predictions while retaining the computational advantages of RL. We showed that estimation can be made tractable through a state-space extension, established equivalence to path-based MNL under restricted universal choice sets, and demonstrated extensions to multiple constraints and nested RL. Empirical results on both synthetic and real networks confirm that CRL provides more realistic predictions and stable estimation compared to RL, especially in cyclic networks. Future work may focus on improving computational efficiency of the extended state-space estimation for large-scale networks, as well as exploring relaxed formulations where infeasible paths are penalized rather than strictly excluded, thereby broadening the applicability of CRL in practical contexts.