Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Applying Dijkstra's Algorithm to Simulate Obstacles in Delivery Routes

Booth Id:

Systems Software


Finalist Names:
Hoffmann Meyer, Guillermo (School: Mississippi School for Mathematics and Science)
Barber, David (School: Mississippi School for Mathematics and Science)

The purpose of this experiment was to simulate an automatic vehicle’s delivery route and examine how it recalculates if a road is blocked or slowed. To do this, Dijkstra’s algorithm, which calculates the shortest route between points, was used. First, a python program that employed Dijkstra’s algorithm was found. After that, a grid was arbitrarily chosen, and values were assigned to the lengths between nodes randomly between 1 and 8. These lengths represent time to travel rather than the actual distance. Then, a function to simulate a car moving on the grid was added to the program. After that, the program calculated the optimal path from the top-left node to the bottom right node. Then, a function to add random accidents was added; this would render certain distances unfavorable to cross. The accidents happened at intersections and were manifested in an increase in travel time across a street. When the random accident happened, the program would adjust the node distances and recalculate its path if the accident happened on a path it was going to take. The conclusion was that even if an accident occurs on the path ahead of a vehicle, it could still be the optimal path. If an accident happens on a series of shorter paths, then waiting out the shorter paths could be preferred over taking other streets. Future uses of this research could include observing changes in traffic multiple nodes away from the accident and optimizing paths based on other cars’ movement as well.