Discovering the best path between point A and point B is critical for everything from rapidly delivering messages over the Internet to rushing patients to emergency rooms as quickly as possible. Now research on interactions between polymers has apparently helped devise a simple, flexible routing algorithm capable of considering all routes between points simultaneously, work applied to the global airport network, random networks resembling Internet networks, travel on the London Underground network based on passenger data, and detailed this week in the Proceedings of the National Academy of Sciences.
Scientists have long wanted a way to figure out the best combinations of paths between all points in a network, but such a task becomes dramatically more difficult the more points and paths there are to compute. One possibility involves calculating what the best path is between each pair of points independent of the needs of what might be the best path for other pairs of points, but the problem with this kind of “selfish” approach is that any paths it envisions could interfere with traffic on routes it did not predict.
“I usually choose the shortest route when I get to work — I think many people do. It seems to be a decent choice,” says statistical physicist Chi Ho Yeung, now at the Hong Kong University of Science and Technology. “However, when everyone does the same during peak hours, it will likely overload some popular routes, leading to delays, and may even be slower on these shortest routes than through a slightly longer one.”
People normally choose the shortest paths during off-peak hours as well. Although this ensures a fast journey, the fact the whole transportation network has to keep active even when little of it gets used is a waste of energy.
To hunt for better routing algorithms, Yeung and his colleagues investigated the physics of interacting polymers.
“A polymer is a long molecule chain like a string with two ends,” Yeung says. “Suppose I represent my travel path by a polymer. The two ends of the polymer will be fixed representing my starting point and destination; the body of the polymer will be flexible depending on my path choice. Now everyone does the same and represents their path by a polymer. We then have a system of polymers on a transportation network.”
“To suppress congestion, we introduce a repulsive force between polymers to encourage users going through different routes,” Yeung says. “We introduce an attraction if we want passengers to share their path.”
Surprisingly, “at a price of modest increase in the average path length, we found that the global cost is substantially decreased in simulations when individuals take their path suggested by our algorithm,” Yeung says. In other words, although everyone travels a little farther on average, they might move faster because of reduced traffic.
“In peak hours, traffic is well-balanced and congestion is suppressed, and in off-peak hours, the sharing of routes is encouraged to increase the number of idle stations and train lines, which may be discontinued to save energy. These results imply that a large amount of resources can be saved from existing transportation networks if individual passenger paths are globally organized.”
A comparison between this new routing strategy and the one where everyone simply chooses the shortest path reveals substantial improvements.
“As shown by our simulations, at a price of only 6 percent increase in average path length, 20 percent and 4 percent of the assumed costs are saved on the London Metro network when one aims to balance or consolidate traffic, respectively.”
Many existing routing algorithms are designed for specific tasks, such as satisfying constraints on how many people they might carry. Such algorithms usually cannot be used for different tasks, such as improving traffic during off-peak hours.
“It is not the case for our algorithm,” Yeung says. Their system is based on a model of interacting polymers that can accommodate different types of interactions between polymers. The result is a single algorithm that can achieve a variety of goals “by tuning a single parameter controlling the attractive and repulsive strengths between polymers. Indeed, our approach can take into account interactions other than attraction and repulsion, which may have other interesting applications.”
The new model also intriguingly found that while the average path length rose as the number of travelers increased, average path length peaked after reaching a certain point even as traffic kept growing. This and other discoveries hint at interesting phenomena in routing at large scales, avenues to pursue in future research.
One current limitation of this system is that it does not account for applications “where the amount of traffic between individual destination pairs is rapidly changing,” Yeung says. The next step therefore maybe is to develop routing algorithms based on this framework that address such dynamic routing tasks.