Navigation system, route search server, route search method and route search program

• US 8,798,918 B2
• Filed: 01/10/2006
• Issued: 08/05/2014
• Est. Priority Date: 04/20/2005
• Status: Active Grant

• Current Assignee: Navitime Japan Co. Ltd.
• Original Assignee: Navitime Japan Co. Ltd.
• Inventors: Onishi, Keisuke, Kikuchi, Shin, Aihara, Kenichi
• Primary Examiner(s): MANCHO, RONNIE M
• Application Number:
  US11/328,447
• Publication Number:
  US 20060241857A1
• Time in Patent Office: 3,129 Days
• Field of Search: 701/208, 701/211, 701/213, 701/400, 701/409, 701/410, 701/420, 701/426, 701/468, 701/408, 701/412, 701/416, 701/418, 701/430, 701/431, 701/438, 701/467, 340/995.14, 340/988
• US Class Current: 701/420
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

An example navigation system enables searching for an optimum route through a one-time route searching process where several destination or departure locations exist. The navigation system includes a point of interest (POI) attribute information database for accumulating POI attribute information, a network data edit unit and a virtual node setup unit. The navigation system determines whether there is a plurality of POIs in a certain departure location and/or a destination location by making reference to relevant data in the POI attribute information database. If there are several POIs, the virtual node setup unit sets up a virtual node connected to each node of the plurality of POIs through links having identical link cost. The network data edit unit then adds the virtual node to the searching network data, and a route search unit functions to search for routes using the searching network data containing the added virtual node.

Claims

1. A navigation system searching a route from a departure node to a destination node using a network data searching unit, the system comprising:

a point of interest (POI) attribute information database storing POI attribute information;

a network data edit unit; and

a virtual node setup unit,

wherein the navigation system determines whether there is a plurality of POIs existing in a departure location and/or a destination location by making reference to relevant data in the POI attribute information database,

wherein, when the navigation system has determined a plurality of POIs, the virtual node setup unit sets up a virtual node for connection to each node of the plurality of POIs through links having identical link cost,

wherein the network data edit unit temporarily adds a link cost of the virtual node to a link cost of the network data searching unit, and a route search unit configured to search for routes using the link cost of the network data searching unit and the temporarily added link cost of the virtual node, and

wherein the virtual node is a virtual point without a specific longitude and latitude.

2. The navigation system according to claim 1, wherein the link cost from each POI to the virtual node is equal to “

0”

.

3. The navigation system according to claim 1, further comprising a navigation terminal transmitting route searching conditions, and a route search server connected to the navigation terminal via a network.

4. A route server connected to a navigation terminal transmitting route searching conditions via a network, the route search server comprising:

a POI attribute information database storing POI attribute information, a network data edit unit and a virtual node setup unit,

wherein the route search server determines whether there is a plurality of POIs in a departure location and/or a destination location by making reference to relevant data in the POI attribute information database,

wherein, when the route server has determined a plurality of POIs, the virtual node setup unit sets up a virtual node for connection to each node of the plurality of POI through links having identical link costs,

wherein the network data edit unit temporarily adds a link cost of the virtual node to a link cost of a network data searching unit, and a route search unit configured to search for routes using the link cost of the network data searching unit and the temporarily added link cost of the virtual node, and

wherein the virtual node is a virtual point without a specific longitude and latitude.

5. The route search server according to claim 4, wherein the link cost from each POI to the virtual node is equal to “

0”

.

6. A route search method of searching a route from a departure node to a destination node using a network data searching unit, wherein the navigation system includes POI attribute information database storing POI attribute information, a network data edit unit and a virtual node setup unit,

the route search method comprising:

determining whether there is a plurality of POI in a departure location and/or a destination location by making reference to relevant data in the POI attribute information database;

if the navigation system has determined a plurality of POIs, setting up a virtual node for connection to each node of the plurality of POIs through links having identical link cost by using the virtual node setup unit;

temporarily adding a link cost of the virtual node to a link cost of the network data searching unit by using the network data edit unit, and searching routes, with the aid of a route search unit, using the link cost of the network data searching unit and the temporarily added link cost of the virtual node,

wherein the virtual node is a virtual point without a specific longitude and latitude.

7. The route search method according to claim 6, further comprising the step of setting the link cost from each POI to the virtual node to “

0”

.

8. A route search method in a navigation system including a navigation terminal transmitting route searching conditions and a route search server connected to the navigation terminal via a network,

wherein the route search server includes a POI attribute information database storing POI attribute information, a network data edit unit, and a virtual node setup unit,

the method comprising:

determining whether there is a plurality of POIs in a departure location and/or a destination location by making reference to relevant data in the POI attribute information database;

if the navigation system has determined a plurality of POIs, setting up a virtual node for connection to each node of the plurality of POIs through links having identical link cost by using the virtual node setup unit;

temporarily adding a link cost of the virtual node to a link cost of a network data searching unit by using the network data edit unit, and searching routes with the aid of a route search unit using the link cost of the network data searching unit and the temporarily added link cost of the virtual node

wherein the virtual node is a virtual point without a specific longitude and latitude.

9. The route search method according to claim 8, further comprising the step of setting each link cost from the POI to the virtual node to “

0”

.

10. A program executed and stored in a computer readable medium which allows a computer constituting a route search server connected to a navigation terminal via a network transmitting route search conditions and including a POI attribute information database storing POI attribute information, a network data edit unit, and a virtual node setup unit, to execute processes comprising:

determining whether there is a plurality of POIs in a departure location and/or a destination location by making reference to relevant data in the POI attribute information database;

if the navigation system has determined a plurality of POIs, setting up a virtual node for connection to each node of the plurality of POIs through links having identical link cost by using the virtual node setup unit; and

temporarily adding a link cost of the virtual node to a link cost of a network data searching unit by using the network data edit unit, and searching routes, with the aid of a route search unit, using the link cost of the network data searching unit and the temporarily added link cost of the virtual node,

wherein the virtual node is a virtual point without a specific longitude and latitude.

11. The program according to claim 10, which allows the computer constituting the route search server to execute a process of setting the link cost from each POI to the virtual node to “

0”

.

12. A method comprising:

receiving a route search request comprising a departure location and a destination location; and

searching, with reference to navigation data, for a route between the departure location and the destination location,

wherein the method further comprises;

determining, with reference to a points of interest (POI) database, whether points of interest (POI) are present in the vicinity of one or both of the departure location and the destination location;

setting up a first virtual node on the departure location side and including the first virtual node in the navigation data if one or more points of interest are present in the vicinity of the departure location, wherein the first virtual node is connected by first links to the points of interest in the vicinity of the departure location, each first link having the same link cost; and

setting up a second virtual node, having no location information on latitude and longitude, on the destination location side and including the second virtual node in the navigation data if one or more points of interest are present in the vicinity of the destination location,

wherein the first virtual node is connected by second links to the points of interest in the vicinity of the destination location, each second link having the same link cost,

wherein the searching for a route comprises one-time searching with reference to the network data which includes any set-up first or second virtual node, and

wherein the virtual node is a virtual point without a specific longitude and latitude.

13. The method according to claim 12, wherein the link cost of each first link and each second link is zero.

14. The method according to claim 12, wherein no location information values are assigned to the first or second virtual nodes.

15. A route search server comprising one or more processing systems configured to perform the method of claim 12.