Planes, trains and molecules: Deriving a generic routing algorithm from the physics of interacting polymers
Optimized traffic on the London subway network. A total of 218 real passenger source–destination pairs are optimized, corresponding to 5% of the data recorded by the Oyster card system between 8:30 AM and 8:31 AM on one Wednesday in November 2009 [cf. citation (35) in paper]. The network consists of 275 stations. (B). Red nodes correspond to stations with nonzero traffic. The size of each node and the thickness of each edge are proportional to traffic through them. (Insets) Zoomed-in views of the central region. Nodes are drawn according to their geographic position. Copyright © PNAS, doi:10.1073/pnas.1301111110
Finding a single optimal route is easy, but optimizing the combination
of multiple routes is a challenge found in a wide range of applications including Internet instant messaging, peer-to-peer networks, subway traffic, airport flight management, water distribution systems, sensor deployment, military convoy logistics, and trip planning. Historically, due to the computational complexity of deriving a global path optimization (that is, one that simultaneously considers all path possibilities), existing routing algorithms typically optimize each paths in isolation. As a consequence, the resulting solutions are less than optimal. Recently, however, scientists at Aston University, United Kingdom and The Hong Kong University of Science and Technology used the physics of interacting polymers (large molecule composed of many repeated subunits, known as monomers) and disordered systems to analyze macroscopic properties of generic path optimization problems. By so doing, they derived a simple yet global, routing algorithm capable of simultaneously considering all individual path alternatives. The researchers then demonstrated the algorithm utility by applying it to Internet-like random graphs, travel on the London Underground, and the global airport network. Moreover, their analysis revealed phase transitions, scaling laws, non-monotonic growth (that is, not always stable or increasing), and other new routing phenomena related to physics.
Research Fellow Chi Ho Yeung discussed the research he and his colleagues, Profs. David Saad and K. Y. Michael Wong, conducted – and the challenges they face – with Phys.org. “While, employing tools in physics to solve the system analytically was indeed our most difficult task,” Yeung tells Phys.org, “the analogy between polymers and paths is actually easy to understand. A polymer is a long molecule chain likes a string with two ends,” he illustrates, “Suppose I represent my travel path by a polymer: the two ends will be fixed representations of my starting point and destination, and the polymer body will be flexible depending on my path choice. If every traveler represents their path this way, we’d have a system of polymers on a transportation network – meaning that to suppress congestion, we’d introduce a repulsive force between polymers to discourage users using the same route. On the other hand, to encourage passengers share their path we’d introduce an attraction.”
Read more at: Phys.org