Planes, trains and molecules: Deriving a generic routing algorithm from the physics of interacting polymers

Share via AddThis
Posted August 21, 2013

Planes, trains and molecules: Deriving a generic routing algorithm from the physics of interacting polymers

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 “While, employing tools in physics to solve the system analytically was indeed our most difficult task,” Yeung tells, “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:

51,154 science & technology articles


Our Articles (see all)

General News

Follow us

Facebook   Twitter   Pinterest   StumbleUpon   Plurk
Google+   Tumblr   Delicious   RSS   Newsletter via Email

Featured Video (see all)

Skilled workers: Study shows the talents of leafcutter ants
Leafcutter ants are agricultural pests that range from the southern United States through much of South America. Their…

Featured Image (see all)

NASA’s James Webb Space Telescope Primary Mirror Fully Assembled
The 18th and final primary mirror segment is installed on what will be the biggest and most powerful…