New Mexico Supercomputing Challenge

Designing efficient transportation networks for the future

Team: 55

School: Los Alamos High

Area of Science: Engineering


Interim:

Problem Definition: We plan to design a program that can optimize a semi-spatial interconnected network with multiple layers. One layer is short range, slow and cheap, and connected to a second, more expensive, fast layer of greater internodal distance. This is a model of future networks, that will allow for more efficient distribution of commodities by injection of consumer based supply (prosumers.) This can also be viewed as a model of future supercomputing environments where powerful mobile devices interact with servers in the cloud. The objective is efficient transmission/computing that dynamically avoids congestion, whether the model is for the distribution of power, transportation networks, or patterns of globalization. Finally, it will have to rapidly adapt to unexpected conditions and with increasing effectiveness.

Problem Solution: We will use Python and MATLAB to help simulate the traffic across the transportation network of a large city. A genetic algorithm will be used to continually refine and provide more efficient ways to get across the system. We will simulate the system by making a grid, or any other shape, and having a delay to get through each particular segment of it. For example, this could represent a road system, with different amounts of traffic for each part of each road. We could also have two or more different systems that work side by side, such as a road-subway network, then try to find the fastest way using a combination of both systems. Most importantly, due to the vast speedup over traditional methods, our program could eventually be used to design increasingly efficient computing devices.

Progress to date: Currently, we have programmed a simple environment that simulates a five-by-five grid-like road system. Each segment of the “road” has a different random value associated with the travel delay time. The goal of the program is to optimize the time taken to travel from one side to the other. At this point we are using a permutation-based pathfinder, that acts all-seeing in order to find the fastest path. Next, we plan to program a simple adaptive algorithm for this situation, allowing the program to adapt over many permutations. We will then make a network that would realistically simulate the three dimensional structure of modern infrastructure with constantly changing delay values. Finally, we aim to build and analyze a random, complex, multilevel network with multiple inputs and outputs.

Expected results: The successful implementation of this program could help to improve the permeability of modern transportation networks. It would allow city planners to quickly and easily identify the more congested areas of a city, and then focus their efforts there. However, in order to create a highly efficient transportation route in a complex city, the simulation would need to be run over a long time. Once a solution had been “compiled” for a certain region, then the transportation market could be considerably improved. For example, it could create an incredibly efficient package distribution network that could quickly and efficiently adapt to changing conditions.

Works Cited:

Dorogovtsev, S.N., A.V. Goltsev, and J.F.F. Mendes. "Critical Phenomena in Complex Networks."Reviews of Modern Physics 6 Oct. 2008: n. pag. Web.

M.E.J. Newman, “The Structure and Function of Complex Networks”, SIAM Review, 45, pp. 167-256, 2003.

Morris, R.G., and M. Barthelemy. "Transport on Coupled Spatial Networks." Physical Review Letters 18 Sept. 2012: n. pag. Web.

R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks”, Reviews of Modern Physics, 74, pp. 47-97, 2002.

"The Python Language Reference." The Python Language Reference -€” Python V2.7.3 Documentation. Python Software Foundation, n.d. Web. 09 Dec. 2012.


Team Members:

  Alexander Swart
  ani Nadiga

Sponsoring Teacher: Lee Goodwin

Mail the entire Team

For questions about the Supercomputing Challenge, a 501(c)3 organization, contact us at: consult @ challenge.nm.org

New Mexico Supercomputing Challenge, Inc.
Post Office Box 30102
Albuquerque, New Mexico 87190
(505) 667-2864

Supercomputing Challenge Board of Directors
Board page listing meetings and agendas
If you have volunteered for the Challenge, please fill out our In Kind form.