An analysis of route optimization techniques for navigation and guidance systems

Summary form only given. Many applications of navigation and guidance systems require the selection of best routes for their operations. A best route is what a navigation and guidance system uses for providing route guidance instructions using navigation sensors. The definition of best route may be different from one application to another. In some applications a best route may be the fastest route where in some others it may be the safest route. The real-time nature of navigation and guidance systems imposes a response time constraint in computing best routes. The complexity of this computation increases when many parameters and large size of road networks are involved. Conventional algorithms are mostly not suitable for navigation and guidance systems, as they can not meet the real-time requirement. Alternative approaches, such as heuristic algorithms, have been proposed. Although these algorithms can meet the real-time requirement, they do not guarantee the best routes. In this paper, first route optimization for navigation and guidance systems, the type of parameters, and the complexity of computing best routes are discussed. Then the different algorithms and conventional algorithms, heuristics, knowledge bases, for computing best routes in navigation and guidance systems are discussed and analyzed