HKUST Physicists Derive Optimal Routes for Transportation, Communication and Logistics Networks

2013-10-30

Dr Chi-ho Yeung and Prof Michael Wong from the Department of Physics at the Hong Kong University of Science and Technology (HKUST) in collaboration with Prof David Saad from Aston University in the UK have applied polymer physics to derive a novel approach for coordinating optimal routes for individual passengers. Their simulations using data from the London underground network show that the new method reduces crowding experienced by passengers by 24%, while journeys take only 5% longer on average. The findings have been published in the   Proceedings of the National Academy of Sciences (PNAS) of the USA.

An immediate application of the results would be a next-generation navigation system which coordinates the path of road users or passengers. Logistics, air traffic, and communication networks, such as the internet, may also benefit. Instead of identifying only the shortest path for individuals, as given by conventional pathfinder applications and GPS navigation devices, the research team's new method aims to coordinate individual routes to avoid congestion in peak hours and to optimize the use of resources in off-peak hours.

Coordinating multiple paths is a long-standing research problem in Mathematics and Computer Science. The shortest path seems a reasonable choice to make but, perhaps surprisingly, is a bad one in many cases. During peak hours, popular routes are likely to be congested when travelers follow their respective shortest paths, making travel slower when compared with slightly longer but less crowded routes. Diversifying the paths is more efficient. In addition, path-sharing in off-peak hours can help to consolidate routes in the transportation network, thus saving resources.

By applying polymer physics, the research team has found a novel way of coordinating passenger paths. Polymers are major components of textiles, plastics, and are even used to build modern-day airplanes. Each polymer is a molecular chain, similar to a string with two ends. If a polymer is used to represent a path, the two ends are fixed representing the starting point and the destination, while the body of the polymer is flexible depending on the choice of path. The research team then used polymers to represent the path of all users of a transportation network. To avoid congestion, the researchers introduced a repulsive force between polymers to discourage overlapping paths. They introduced an attractive force between polymers to encourage path-sharing in off-peak hours. Using tools from theoretical physics, the team obtained the optimal arrangement of polymers, and hence a coordinated path for all commuters.

The  journal seeks to publish research with the greatest impact in a wide range of fields. The HKUST-Aston joint research was selected by PNAS editors as a highlight in both online and published versions, and highlighted by prestigious journals and media, including Nature PhysicsPNAS,  science blog and the worldwide  science news website Phys.org..

For media enquiries, please feel free to contact :

Ella Au Yeung

Tel: 2358 6306

Email: ellaauyeung@ust.hk

 
 Prof Michael Wong (left) and Dr Chi-ho Yeung
Prof Michael Wong (left) and Dr Chi-ho Yeung
18570