Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Auto-generation of High-Efficiency Transportation Networks

Booth Id:

Materials Science


Finalist Names:
Huang, Ian (School: Sewickley Academy)
Yang, William (School: Sewickley Academy)

In this project, we built a mathematical model to automatically generate efficient transportation networks given a simulated urban environment with variable population distribution and other physical constraints of the network. We first analyzed the characteristics of 31 topological structures confined in a 12x12 plane, with 21 stations and 72 units in total network length. Using Dijkstra’s algorithm, we determined each structure’s efficiency. The Gaussian Mixture Model was used to simulate population distributions, and helped to calculate efficiencies under the changes in population arrangements. This research revealed the geometrical traits that yielded best efficiency in both uniform and varied population distributions. The auto-generation model uses the Genetic Algorithm to generate the optimal locations of a predefined number of stations such that their locations have traits observed to lead to better efficiency. We used Prim's algorithm to connect all stations, and added more routes upon this tree such that the efficiency of a network is improved until the network length reaches a user-inputted quota. We mathematically modeled Beijing’s subway system and population distribution, and found that our program can auto-generate a network 10% more efficient than the current subway system. We are very confident that this model is not only applicable to other cities, but also in different domains of network design. In summary, we built a mathematical model to generate the most efficient transportation network given fixed conditions, thus providing a new approach to transportation network design.