Applying Dijkstra's Algorithm to Simulate Obstacles in Delivery Routes

Overview

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.

Competition history

• ISEF 2020 Systems Software · Entry SOFT011T

Resources

• ISEF abstract page ↗

Related projects

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