Polymers, Message Passing, and London Underground Routes (video)

Infos Complémentaires

13h30 - Pièce 236 - 2ème étage
29 rue d’Ulm, Paris
Contact : benjamin.huard@ens.fr, aleksandra.walczak@ens.fr
http://www.phys.ens.fr/

K. Y. Michael Wong (The Hong Kong University of Science and Technology, China) - Jeudi 16 janvier.

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.

 

You can also watch this video on the multimedia site ENS :savoirs.ens.fr

13h30 - Pièce 236 - 2ème étage
29 rue d’Ulm, Paris
Contact : benjamin.huard@ens.fr, aleksandra.walczak@ens.fr
http://www.phys.ens.fr/