"HEAD START" ROUTE SELECTING ALGORITHM FOR REDUCING DRIVER'S WAITING TIME
Tomoyuki Nakamura, Osafumi Nakayama, M Iwasaki · Steps Forward. Intelligent Transport Systems World CongressVERTIS · 1995
This paper describes various basic route selecting algorithms, such as the Dijkstra and the A*, a new route selecting algorithm that can reduce driver's waiting time in a car navigation system. The head start algorithm can display calculated routes immediately after the driver sets his or her destination because its calculation is already initiated. While the car is at a stop, such as when the driver leaves the car, the Dijkstra algorithm is initiated from the current position. The calculation results of surrounding nodes are recorded. When the driver gets back into the car and inputs the destination, if the destination is within the already calculated area, the route can be derived only by reading the calculation result. Even if the destination is out of the area, from the destination to the calculated area, the A* algorithm is used, thereby shortening the calculation time considerably. This paper also describes a so-called head algorithm that can save memory required to store calculation results of the head start algorithm. This paper, at first, presents the results of an investigation into basic route selecting algorithms. Various algorithms were examined through simulations using actual map data. These algorithms were evaluated with respect to their calculation time and capability for selecting the optimum route. The latter part of this paper presents a new original method called the head start algorithm and the onion head start algorithm.