My PBL/Science Fair Project

Conclusion/ Abstract

Our project’s purpose was to create an algorithm capable of ferrying attendees from their homes to an event location in the shortest and most fuel efficient way possible through a system of carpooling, as opposed to having them arriving on their own.

We first programmed our algorithm to pair passengers with volunteering drivers based off of how close they are regarding latitude and longitude coordinates. We then programmed it to create a base case and then switch the order in which two passengers are picked up until no more switching can be done with improvement. The program will also keep track of the shortest distance found using the Haversine Formula (we eventually plan to implement a GPS system or Google Maps). The orders of these passengers will then be shuffled; this process will be repeated up to however many times the operator prefers. At the end, the best results from each shuffle will be compared and a final best distance will be presented.

One of our example scenarios consisted of sixteen people traveling to a soccer field, four of which were volunteers (capacity of three extra passengers each). After finding the distance it would take them to travel on their own, we used our algorithm and generated an improvement of 58% and a saved mileage of 74 miles, which means 3.7 gal of saved gas at 20 mpg and $7.4 at $2/gallon.

Once tested, the algorithm we created works and makes travel and carpooling more faster and efficient.

We would also like to mention our science fair counselor that was along with us to help us in any troubles we encountered Mr. Aziz Koyuncu.

Background Research

Big Picture:

The main idea of our project is logistics and finding the fastest possible routes between locations.

Principles:

• • Programming

    • The programming language, Java, shall be used for this problem

  • Mapping

  • Heuristic/approximation algorithms

    • Generate an algorithm capable of randomizing the order of locations in order to get the shortest possible route (Traveling Salesman Problem)

  • Fastest time for getting from point a to b

Materials Needed:

• • Computer

  • Software capable of running Java

Experimental Procedure:

Driving Question: Which heuristic guarantees the shortest route in between grid points?

Scientific Principle(s):

Traveling Salesman problem, math, programming

Materials:

Any computer enabled with Java (Eclipse)

Procedure:

• 1. First, find or create a database of grid locations

  2. Create a basic program that will simply start at one point and continue on to the next closest point until the chain of points are connected

     1. Make sure this program is able to measure the total distance traveled

  3. Once a basic program is created, add another element into the program that will switch up the travel order of two points per operation randomly and then re-run the equation

• • 1. Do so until there are no more improvements in distance

• 4. After creating the Greedy Heuristic, insert a Genetic Algorithm into the program to include so that every once in a while, the program will completely change up the order in which it connects the dots so as to mimic nature’s way with mutations. Compare your results with the Greedy Heuristic and notice how the resulting distances may change but may also get shorter

  5. (Optional) Add a supplement to the program that records the order of dots traveled so as to make it easier to observe changes

More Information

Data Collection

Observation

Quantitative savings:

Average overall savings: 62%

Average gas savings: 4.065 gallons

Average money savings: ~$8.03 ($8.025)

Average distance savings: 76.15 miles

Qualitative savings:

Environmental savings due less to gas emissions

Reduction in traffic congestion and stress

Reduced traffic accidents due to having less cars in traffic