In This Issue

Whether planning water distribution routes, military convoy movements, internet traffic, or simply the best way to the airport, path optimization algorithms are essential for everyday logistics. Global optimization techniques that consider all path choices simultaneously are computationally difficult. As a result, most existing routing algorithms choose paths individually, but these methods tend to favor the shortest path regardless of the choice’s impact on other routes. Chi Ho Yeung et al. (pp. 13717–13722) have borrowed from the physics of polymers to create a simple, generic, and distributed global path optimizing algorithm. The researchers tested their statistical physics-based technique on large real-world data sets, including the London Underground subway system and global air traffic. Compared to current methods, the algorithm decreased overall congestion at the cost of a slightly longer path length. The algorithm worked best with intermediate traffic densities, where optimization is particularly difficult. In addition to solving common optimization problems, the authors suggest that the technique may also reveal properties of optimal routing scenarios that are otherwise difficult to uncover. — J.M.