Read on Twitter
Perturbed utility stochastic traffic assignment
We use some cool math to solve huge equilibrium problems really quickly!
Working paper here:
1/N
#dkforsk #dktrp #EconTwitter #transportation
@cykelnorden @ThomasKjrRasmu2 @JRehbeckpapers.ssrn.com/sol3/papers.cf…
We use some cool math to solve huge equilibrium problems really quickly!
Working paper here:
1/N
#dkforsk #dktrp #EconTwitter #transportation
@cykelnorden @ThomasKjrRasmu2 @JRehbeckpapers.ssrn.com/sol3/papers.cf…
We deal with the problem of computing Nash equilibrium (SUE) in a large congestible traffic network.
Travelers make individually optimal route choices, taking travel times into account.
Travel times, in turn, depend on the individual choices.
2/N
Travelers make individually optimal route choices, taking travel times into account.
Travel times, in turn, depend on the individual choices.
2/N
This is a huge problem. For real traffic networks we have many million decision variables.
Naive algorithms, iterating demand and supply, are way too slow.
We need something really fast!
3/N
Naive algorithms, iterating demand and supply, are way too slow.
We need something really fast!
3/N
This will allow us to use the perturbed utility route choice (PURC) model for large-scale applications with congestion. E.g. to analyze road pricing.
The PURC model has some attractive features:
4/N
pnas.org/doi/10.1073/pn…
The PURC model has some attractive features:
4/N
pnas.org/doi/10.1073/pn…
-> It includes the whole network, no choice sets are required
-> Substitution patterns are induced directly by the network structure
-> It predicts true zero flow in irrelevant parts of the network
-> It can be estimated by plain regression
5/N
-> Substitution patterns are induced directly by the network structure
-> It predicts true zero flow in irrelevant parts of the network
-> It can be estimated by plain regression
5/N
The predicted flow for an individual is the solution to a large optimization problem.
Finding equilibrium with many thousand individuals is a huge problem!
But we can do it!
6/N
Finding equilibrium with many thousand individuals is a huge problem!
But we can do it!
6/N
How do we do it?
-> We set up the equilibrium problem as one convex constrained optimization problem
-> We find the dual Lagrange function in closed form. This is an unconstrained and smaller convex problem
-> This allows us to use fast first-order methods
7/N
-> We set up the equilibrium problem as one convex constrained optimization problem
-> We find the dual Lagrange function in closed form. This is an unconstrained and smaller convex problem
-> This allows us to use fast first-order methods
7/N
-> We use accelerated gradient descent
-> We add some quasi-Newton scaling of the gradient
-> We update network travel times by one Newton step at every iteration
And get something really fast!
8/N
-> We add some quasi-Newton scaling of the gradient
-> We update network travel times by one Newton step at every iteration
And get something really fast!
8/N
Much faster than the primal algorithm 9/N
The runtime is about linear in problem size
(we are testing problems with 10^8 decision variables!)
10/N
(we are testing problems with 10^8 decision variables!)
10/N
We also test on a range of standard problems
Our fastest dual algo is 100x faster than the slowest. A primal algo is just out of the question
11/N
Our fastest dual algo is 100x faster than the slowest. A primal algo is just out of the question
11/N
In conclusion:
We can compute Nash equilibrium (SUE) with huge congestible traffic networks and a demand model (PURC) that just includes the whole network as it is.
:-)
12/END
We can compute Nash equilibrium (SUE) with huge congestible traffic networks and a demand model (PURC) that just includes the whole network as it is.
:-)
12/END
@threadreaderapp unroll
• • •
Missing some Tweet in this thread? You can try to
force a refresh
