A Fast Efficient Technique for Finding a Path through Multiple Destinations

Overview

Objectives/Goals In a real world situation, members of different organizations often need to travel to multiple destinations without passing through the same place twice. However, identifying an efficient path to travel through multiple destinations can be extremely difficult and time-consuming problem. In this work, I propose an algorithm/technique to find an efficient path covering many destinations, within a short amount of time. The path starts from the source location and goes through all the destination locations. This heuristic uses Dijkstra's algorithm to find different paths between different pairs of destinations and then determines the Least-Cost path for each segment. This approach allows people and organizations to save time, fuel and money. As a result, this technique saves environment as well. Methods/Materials I have completed this project in Windows laptop that has Chrome Browser. Javascript programming language and Dracula graph library were used to implement the core path-finding algorithm. I used html language to develop the web-based application for accepting user#s input locations and few other settings. Google Maps and Directions APIs were used to display the final output in the web-browser. Results I have run several sample test situations that involves between 5 and 50 destination locations. My data shows that the algorithm produces an efficient path within 31 to 372 seconds, depending on the number of destinations. For many such test situations, I have visually verified that the resulting paths are the best possible paths that a human could have generated by using trial and error over several hours of time. These data and observations confirm that the proposed algorithm is efficient and fast. Conclusions/Discussion I developed an algorithm/technique to quickly find an efficient path that covers multiple destinations. For many test situations, I have visually verified that the resulting paths are the best possible paths. For the problem involving 50 locations, this technique takes only 372 seconds to compute the path (exhaustive approach for 50 locations would have taken years). I conclude that the proposed approach is ready for real-world usage in the organizations and companies. Since the user requires very little time and knowledge, this approach will be quite appealing and useful to many users in the community.

Competition history

• CSEF 2017 Mathematical Sciences · Entry S1507

Resources

• CSEF project summary ↗

Related projects

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

Browse more like this

• All Mathematics projects
• CSEF Mathematics projects
• Every CSEF 2017 project