|
Polymers, Message Passing, and London Underground Routesold_uid | 13279 |
---|
title | Polymers, Message Passing, and London Underground Routes |
---|
start_date | 2014/01/17 |
---|
schedule | 15h |
---|
online | no |
---|
location_info | salle 3 |
---|
summary | Route planning is important in many applications, ranging from subway traffic
to Internet communication. The challenge is to optimize the path choices of all
subscribers taking into account that they are competing for the same pool of
resources. From the statistical physics point of view, there is an analogy
between interacting polymers and route planning. Polymers that repel each other
are similar to path choices that avoid each other. Thus, understanding the
behavior of repelling polymers gives us insights on how to reduce congestions
in traffic networks. Conversely, polymers that attract each other are similar
to concentrating path choices, and give us insights on how to consolidate
traffic during off-peak hours. We use this analogy to analyze properties of
optimized traffic networks and derive routing algorithms. The routing algorithm
operates by having nodes in the network exchanging messages among themselves.
We apply the algorithm to traffic data obtained from Oyster cards of the London
Underground network, and found that it outperforms state-of-the-art algorithms
in terms of congestion reduction. |
---|
responsibles | Berestycki, Nadal |
---|
| |
|