Comparison of Optimization Techniques for Road Networks

Team: 31

School: Desert Academy

Area of Science: Graph Theory, Computer Science

Interim:

Our project will focus on the optimization problem of designing an ideal road layout for any given city. We intend to compare the effectiveness of genetic algorithms and stochastic gradient descent in generating a road layout for a city. This is essentially a graph theory program that seeks to minimize the amount of time it takes cars to travel from the business district to their homes

Thus far we have been working on two separate models, one in Octave and one in Python. The Python model uses the library networkx and creates a scatter plot of nodes, some of which are designated 'work' nodes, others are 'home' nodes, with have random locations inside a specific radius. The program creates edges between random nodes and the edges are given the attribute of distance based on the location of the nodes they connect. Then the average shortest path distance is calculated using the built-in path finding algorithm and the population of workers in the city. The distance is multiplied by a scaling factor to account for the 'capacity' of a given edge to determine the traveling time.

The Octave model creates a random number of nodes and randomly places them as complex numbers in the Argand plane, within a city limit that is the radius of the plane. Edges are randomly placed between nodes, where the number of edges is greater than the number of nodes. Each node, whose magnitude is less than a certain radius, is designated a start node, while the others are designated end nodes. The shortest path is calculated using a path-finding algorithm and the total time taken is then calculated using an equation that takes into account the number of nodes, the number of edges, and the number of cars at that node, each with their own proportionality constant.

The reason we have implemented two different road networks is to get a sense of the potential and limitations of the two separate languages. This allows us to work independently and then come together and compare our methods. Our current plan is to use the python model to develop the genetic algorithm and the Octave model for stochastic gradient descent, but eventually the models will be integrated.

Sources:

This is the networkx Python library: http://networkx.lanl.gov/

Graph theory applications in transportation systems http://people.hofstra.edu/geotrans/eng/methods/ch1m2en.html

Team Members:

  Sara Hartse
  Sean Colin-Ellerin

Sponsoring Teacher: Jocelyne Comstock

Mail the entire Team