Fastest Route: Graph Theory Applied

Overview

Objectives/Goals My goal was to determine how graph theory can be applied to determining the fastest route through random stops. Methods/Materials I used maps of my neighborhood, paper and pencils, Microsoft Streets and Trips software. I chose random delivery stops by dropping a pencil onto the map of my neighborhood. I moved the stops onto another blank piece of paper and determined, using graph theory principles, the best route to take. I then measured the actual route and beeline distance from stop to stop and compared them in a ratio. Results My results showed that the beeline distance was considerably shorter than the actual distance. The actual distance was pretty consistently 1.6 times farther than the beeline. Conclusions/Discussion I concluded that graph theory did not provide the most efficient route because it overlooked all natural barriers. I also found that it was consistently 1.6 times less than the actual distance. My results tell me that is a good measurement for geometric shapes, but needs to be changed to work in the real world. My future projects might try to find out how you could use graph theory to find good random routes in the real world.

Competition history

• CSEF 2003 Mathematics & Software · Entry J1218

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2003 project