"HEAD START" ROUTE SELECTING ALGORITHM FOR REDUCING DRIVER'S WAITING TIME

This paper describes various basic route selecting algorithms, such as the Dijkstra and the A*, a new "head start" 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 "onion head start" 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.

  • Supplemental Notes:
    • Five volumes of papers and one volume of abstracts comprise the published set of conference materials.
  • Corporate Authors:

    VERTIS

    TORANOMOM 34 MORI BUILDING 1-25-5
    TORANOMON, MINATOKU, TOKYO 105  Japan 
  • Authors:
    • Nakamura, T
    • Nakayama, O
    • Iwasaki, M
  • Conference:
  • Publication Date: 1995-11

Language

  • English

Media Info

  • Pagination: p. 2031

Subject/Index Terms

Filing Info

  • Accession Number: 00724448
  • Record Type: Publication
  • Report/Paper Numbers: Volume 4
  • Files: TRIS
  • Created Date: Aug 21 1996 12:00AM