Planes, trains and molecules: Deriving a generic routing algorithm from the physics of interacting polymers
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....