I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a throughput and latency, and vertices correspond to road junctions what would an efficient algorithm for determining the equilibrium (such that no car can make a faster route) of traffic look like? And as a bonus question: how would that algorithm change for different types of agents (say we try the find the equilibrium for super rational agents)
$\begingroup$
$\endgroup$
5
-
$\begingroup$ It is unclear to me what you mean by equilibrium. An allocation of traffic such that no driver can cut their driving time by changing their route? Or do you mean maximum possible throughput? Do you have a single starting point and a single destination in mind, or can there be more? Try being more precise. Also, your question should be as self-contained as possible. I suppose no one will watch a video to find out what you're asking. (Certainly not me.) Also, how do roads react to congestion? Your question is very ambiguous. $\endgroup$– Jozef MikušinecDec 8 '21 at 13:43
-
$\begingroup$ (A small correction: multiple sources S and destinations D can be simulated by adding one new start and one destination node ($N_s$ and $N_d$), with edges from $N_s$ to every $s \in S$ , and from every $d \in D$ to $N_d$, all having zero latency and throughput equal to the capacity of the corresponding original start/end node. Because of this, the distinction between a single and multiple starting/ending nodes is not as relevant.) $\endgroup$– Jozef MikušinecDec 8 '21 at 14:04
-
$\begingroup$ An allocation of traffic such that no driver can cut their driving time by changing their route is what I meant. And there is a single destination. @JozefMikušinec $\endgroup$– Ace shinigamiDec 8 '21 at 22:16
-
1$\begingroup$ So, is this what you are looking for? en.wikipedia.org/wiki/Braess%27s_paradox#Finding_an_equilibrium $\endgroup$– Jozef MikušinecDec 8 '21 at 22:21
-
1$\begingroup$ Also, it seems to me that your question has a name: "Traffic equilibrium problem". And there's a paper that discusses it and should contain an algorithm: jstor.org/stable/25767967 I'm new to this site so I don't know if this is enough of an answer, but if you're happy with this as is, let me know and I'll post this comment as an answer. $\endgroup$– Jozef MikušinecDec 8 '21 at 22:27
Add a comment
|
$\begingroup$
$\endgroup$
1
The problem you are interested in is called the Traffic equilibrium problem.
The paper "Traffic Equilibrium and Variational Inequalities" by Stella Dafermos formalizes it, shows that there is a unique equilibrium, and gives an algorithm for computing it.
Note that this works for a particular formalization, for example, it assumes "a fixed travel demand [..] for every origin-destination pair". One could want to model more complex things, like time-dependent travel demand, or arbitrarily complex relations between road congestion and throughput/latency. If you have something specific in mind, I'd recommend to ask another question.
-
$\begingroup$ A publicly available version of the paper is at doi.org/10.1287/trsc.14.1.42 . The paper apparently doesn't give a time bound for the algorithm, so it's not clear whether it is "efficient" as requested in the post. $\endgroup$ Dec 9 '21 at 13:03