CVEN 4402 Week 8 Workshop
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CVEN 4402 Week 8 Workshop
The Logit Model and Stochastic User Equilibrium
In this workshop, we will present a basic example of how to solve the Stochastic User Equilibrium problem. Stochastic User Equilibrium (SUE) arises when user choose routes based on a Logit Assignment model, in which the probability of choosing each path is determined by the path cost.
While in a regular Deterministic User Equilibrium (DUE) setting, the path with the lowest cost is chosen, in a SUE setting, the path with the lowest cost merely has a higher probability of being chosen. This model results in a more robust, more reliable model: in reality, it is common for us to see paths that are not least cost paths receive a certain amount of flow. Some of this can be attributed to user error: for most people, estimating the true cost of travel along a path is impossible. As users, we develop approximate estimates of path costs, and this error in estimation can be modeled using the logit assignment model.
Stochastic User Equilibrium
In relation to stochastic user equilibrium, the logit assignment model assigns probabilities based on the following expression:
e−ec(k)
p(choosing path k) =
Where the function c(k)represents the cost of path k, and the denominator is the expression summed over all possible paths for a given OD.
We will focus first on a simple version of an algorithm for SUE that focuses on path enumeration. The outline of the algorithm is as follows:
1. Set all flows to 0.
2. Given current flows, calculate link costs.
3. Given link costs, calculate the cost of each path.
4. Given the cost of each path and a pre-calibrated logit model, calculate the path probabilities
5. Multiply the path probabilities with the OD demand to generate path flows.
6. Average auxiliary solution with previous solution using MSA method.
7. Repeat 2-6 until convergence.
We will focus on a 3 path problem to illustrate this method.
Question 1
Consider the network above with a demand of 20 units from node 1 to 4. For path choice, assume a logit model given by the parameter 
= 0. 1. Determine the stochastic equilibrium solution after 3 MSA iterations.
More complex networks and cycles
You will notice that the network we examined was extremely simple. So simple, in fact, that no cycles exist. This may not seem important, but consider the example below to see why cycles greatly change the solution approach used to solve the SUE problem.
The issue arises due to the fact that in the logit assignment model, even a path with a very high cost will have a strictly positive probability of being chosen. Consider the network below:
The network above consists of a link from 1 to 2, and a link from node 1 back to itself. Now, intuitively, no one travelling from node 1 to 2 should ever use the cycle from 1 to 1, as it will just increase travel time. However, if we consider the “path” options of 1-2, and 1-1-2 (i.e., cycling one time and then travelling to node 2), we obtain the following path choice probabilities (assume e = 0. 1):
e −0. 1∗1
p(1 − 2) = = 0.525
e −0. 1∗2
p(1 − 1 − 2) = = 0.475
That is, in the example above, if we include the two path options, 47.5% will follow a path that is strictly worse. If we consider paths corresponding to strategies in which we cycle more times, the results are even more skewed:
e −0. 1∗1
p(1 − 2) = = 0.289
e −0. 1∗2
p(1 − 1 − 2) = = 0.261
e −0. 1∗3
p(1 − 1 − 1 − 2) = = 0.237
e −0. 1∗4
p(1 − 1 − 1 − 1 − 2) = = 0.214
In general, we must make sure to consider paths that are “reasonable” . This goes beyond the scope of this class, but a method to address this issue is presented in Sheffi: the STOCH algorithm. The key to this algorithm is, at each iteration, to identify paths which satisfy the condition of always getting closer to the destination, which can be done efficiently.
2022-09-08