Route search device, route search method, and route search program

Patent metadata

Field	Value
Publication number	US-11835347-B2
Application number	US-201917611117-A
Country	US
Kind code	B2
Filing date	May 14, 2019
Priority date	May 14, 2019
Publication date	Dec 5, 2023
Grant date	Dec 5, 2023

Abstract

Routes can be found while improving the convenience of guidance for users. A route-searching device includes a search-condition acquisition unit that acquires search conditions for searching a route including a starting point and a destination; a route-data storage unit that stores a link ID, the node IDs of the starting point and the end point of a link, and road network information concerning a road network and including a link length; an instruction-data storage unit that stores instruction data including a type associated with the node ID, a value for the type, and a coefficient for the value; and a route generation unit that generates route candidates including the shortest route based on the search conditions and the road network information, calculating, for each of the route candidates, an index value based on information included in the instruction data, and outputting, as a search route, the route candidate with the index value improved from the index value of the shortest route.

First claim

The invention claimed is:

1. A route-searching device comprising:
a search-condition acquirer configured to acquire search conditions for searching a route including a starting point and a destination;
a route-data store configured to store a link ID, node IDs of a starting point and an end point of a link, and road network information concerning a road network and including a link length;
an instruction-data store configured to store instruction data including a type associated with the node ID, a value for the type, and a coefficient for the value; and
a route generator configured to:
generate route candidates including a shortest route based on the search conditions and the road network information,
determine, for each of the route candidates, an index value based on information included in the instruction data, wherein, for the route candidates having route lengths equal to or less than a route length determined with a predetermined magnification relative to the shortest route, the route generator updates the index value based on the information included in the instruction data so as to reduce or increase a route length obtained as a sum of lengths of links included in the route candidates having route lengths equal to or less than the route length determined with the predetermined magnification,
and
output, as a search route, the route candidate with the index value improved from the index value of the shortest route.

2. The route-searching device according to claim 1 , wherein the route generator generates the route candidates in an ascending order of route lengths by using a predetermined algorithm.

3. The route-searching device according to claim 2 , wherein the index value is generated by correcting the lengths of the links included in the route candidates having a route length equal to or less than the route length determined with the predetermined magnification, according to a coefficient corresponding to the type associated with the node ID included in the link.

4. The route-searching device according to claim 1 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

5. A computer-implemented method for route searching, comprising:
acquiring, by a search-condition acquirer, search conditions for searching a route including a starting point and a destination;
generating, by a route generator, route candidates including a shortest route based on the search conditions, a stored link ID, node IDs of a starting point and an end point of a link, and road network information concerning a road network and including a link length;
determining, by the route generator, for each of the route candidates, an index value based on information included in instruction data including a type associated with the node ID, a value for the type, and a coefficient for the value, wherein for the route candidates having route lengths equal to or less than a route length determined with a predetermined magnification relative to the shortest route, the route generator updates the index value based on the information included in the instruction data so as to reduce or increase a route length obtained as a sum of lengths of links included in the route candidates having route lengths equal to or less than the route length determined with the predetermined magnification; and
providing, as a search route, the route candidate with the index value improved from the index value of the shortest route.

6. A computer-readable non-transitory recording medium storing computer-executable route-searching program instructions that when executed by a processor cause a computer system to:
acquire, by a search-condition acquirer, search conditions for searching a route including a starting point and a destination;
generate, by a route generator, route candidates including a shortest route based on the search conditions, a stored link ID, node IDs of a starting point and an end point of a link, and road network information concerning a road network and including a link length;
determine, by the route generator, for each of the route candidates, an index value based on information included in instruction data including a type associated with the node ID, a value for the type, and a coefficient for the value, wherein, for the route candidates having route lengths equal to or less than a route length determined with a predetermined magnification relative to the shortest route, the route generator updates the index value based on the information included in the instruction data so as to reduce or increase a route length obtained as a sum of lengths of links included in the route candidates having route lengths equal to or less than the route length determined with the predetermined magnification; and
provide, as a search route, the route candidate with the index value improved from the index value of the shortest route.

7. The route-searching device according to claim 2 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

8. The route-searching device according to claim 3 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

9. The computer-implemented method according to claim 5 ,
wherein the route generator generates the route candidates in an ascending order of route lengths by using a predetermined algorithm.

10. The computer-implemented method according to claim 5 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

11. The computer-readable non-transitory recording medium according to claim 6 ,
wherein the route generator generates the route candidates in an ascending order of route lengths by using a predetermined algorithm.

12. The computer-readable non-transitory recording medium according to claim 6 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

13. The computer-implemented method according to claim 9 ,
wherein the index value is generated by correcting the lengths of the links included in the route candidates having a route length equal to or less than the route length determined with the predetermined magnification, according to a coefficient corresponding to the type associated with the node ID included in the link.

14. The computer-implemented method according to claim 9 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

15. The computer-readable non-transitory recording medium according to claim 11 ,
wherein the index value is generated by correcting the lengths of the links included in the route candidates having a route length equal to or less than the route length determined with the predetermined magnification, according to a coefficient corresponding to the type associated with the node ID included in the link.

16. The computer-readable non-transitory recording medium according to claim 11 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

17. The computer-implemented method according to claim 13 , wherein if the value is included in the search route, information on the value corresponding to the search route is included.

18. The computer-readable non-transitory recording medium according to claim 15 , wherein if the value is included in t

Assignees

• Nippon Telegraph & Telephone

Inventors

• Tsutsumida Kyota
• Mochizuki Mitsuru
• Matsuda Osamu
• Seshimo Hitoshi

Classifications

• G01C21/343 Primary

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title

• G01C21/34 Primary

  Route searching; Route guidance · CPC title