<p>The problem you are interested in is called the Traffic equilibrium problem.</p>
<p><a href="https://www.jstor.org/stable/25767967" rel="nofollow noreferrer">The paper</a> &quot;Traffic Equilibrium and Variational Inequalities&quot; by Stella Dafermos formalizes it, shows that there is a unique equilibrium, and gives an algorithm for computing it.</p>
<p>Note that this works for a particular formalization, for example, it assumes &quot;a fixed travel demand [..] for every origin-destination pair&quot;. 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.</p>

CC BY-SA 4.0
2021-12-09T13:03:50.973Z
A publicly available version of the paper is at https://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.
Neal Young
CC BY-SA 4.0
2021-12-08T22:44:54.187Z
2021-12-08T22:59:51.507Z
2021-12-08T22:59:51.507Z
Jozef Mikušinec
<p>I watched a <a href="https://www.youtube.com/watch?v=Cg73j3QYRJc&amp;t=496s" rel="nofollow noreferrer">youtube video</a> 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)</p>

CC BY-SA 4.0
2021-12-08T13:43:53.170Z
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.
Jozef Mikušinec
CC BY-SA 4.0
2021-12-08T14:04:02.850Z
(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.)
Jozef Mikušinec
CC BY-SA 4.0
2021-12-08T22:16:08.473Z
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
Ace shinigami
CC BY-SA 4.0
2021-12-08T22:21:31.500Z
So, is this what you are looking for? https://en.wikipedia.org/wiki/Braess%27s_paradox#Finding_an_equilibrium
Jozef Mikušinec
CC BY-SA 4.0
2021-12-08T22:27:47.587Z
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: https://www.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.
Jozef Mikušinec
<ds.algorithms><graph-theory><gt.game-theory>
Algorithm for finding traffic equilibrium
Ace shinigami
# Algorithm for finding traffic equilibrium

(Asked by: username_0 on 2021-11-28)

I watched a [youtube video](https://www.youtube.com/watch?v=Cg73j3QYRJc&t=496s) 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)

**Tags:** ds.algorithms, graph-theory, gt.game-theory

> **Comments:**
> **username_1**: 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.  
> **username_1**: (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.)  
> **username_0**: 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  
> **username_1**: So, is this what you are looking for? https://en.wikipedia.org/wiki/Braess%27s_paradox#Finding_an_equilibrium  
> **username_1**: 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: https://www.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.  

---

## 1 answers

### Answer by username_1 on 2021-12-08. Score: 1 | Accepted answer

The problem you are interested in is called the Traffic equilibrium problem.

[The paper](https://www.jstor.org/stable/25767967) "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.

> **Comments:**
> **username_2**: A publicly available version of the paper is at https://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.  

---

