Smart Navigation: Using Artificial Intelligent Heuristics in Navigating Multiple Destinations

摘要

Navigation applications are becoming an essential need in any mobile device. Finding the best path (time and distance) from an address to another is one of the most asked queries among driving users. Moreover, finding the best path with multiple destinations is a query that could be asked by many, including commercial companies' drivers (similar to the famous "Traveling Salesman Problem"). Google maps, Yahoo maps, and tens of other solutions are examples of such mobile applications. Calculating the best driving path between two addresses is subject to many factors including distance, road situation, road traffic, speed limitations and others. This paper presents the use of smart heuristic functions, as well as an efficient data structure to be used in finding efficient path between multiple points (addresses) rather than one destination. It presents spatial databases, current solutions, heuristics in Graph problems, and finally a smart solution (our new Algorithm A*Multiple) using a smart heuristic function to determine the best path between multiple destinations.