# US 2015/0149078 A1 · Apparatus and method for route searching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0149078 A1
- Document ID: US20150149078A1
- Status: Published application
- Kind: A1
- Application number: 14/411,552
- Filed: 2013-07-01
- Published: 2015-05-28
- Earliest claimed: 2012-06-29
- Assignees: TomTom Development Germany GmbH
- Applicants: TomTom Development Germany GmbH
- Inventors: Andreas Profous; Johannes Robert Fischer; Andreas Menge
- Web page: https://patentgrep.com/patent/US20150149078A1

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G01C 21/3469: {Fuel consumption; Energy use; Emission aspects}
- G01C 21/3476: {using point of interest [POI] information, e.g. a route passing visible POIs}
- G01C 21/3679: {Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence)}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

Embodiments of the present invention provide a one-to-many route searching method comprising searching map data to select links to form a plurality of routes from a departure node according to a cost function, and determining an extent of each route according to an objective function, wherein the searching of the map data is performed to a search boundary based upon a cost of an unreachable node.

## Claims

### Claim 1

A one-to-many route searching method, comprising:
searching map data to select links to form a plurality of routes from a departure node according to a cost function; and
determining an extent of each route according to an objective function,
wherein the searching of the map data is performed to a search boundary based upon a cost of an unreachable node.

### Claim 2 (depends on 1)

The method of claim 1, wherein the search boundary extends beyond the unreachable node.

### Claim 3 (depends on 1)

The method of claim 1, wherein the unreachable node is a first node selected according the cost function determined to be unreachable according to the objective function.

### Claim 4 (depends on 3)

The method of claim 3, wherein the search boundary has a cost based upon the cost of the unreachable node.

### Claim 5 (depends on 1)

The method of claim 1, wherein the cost of the unreachable node is an accumulated cost of links between the departure node and the unreachable node along a route there-between determined according to the cost function.

### Claim 6 (depends on 1)

The method of claim 1, wherein each route is formed from a plurality of network links each having a lowest cost determined according to the cost function.

### Claim 7 (depends on 6)

The method of claim 6, wherein the cost function determines a cost of each link based upon one or more of length, travelling time and travelling speed of the link.

### Claim 8 (depends on 1)

The method of claim 1, wherein the extent of each route is determined by the objective function based upon or more of energy cost, travelling time and travelling distance.

### Claim 9 (depends on 8)

The method of claim 8, wherein the extent of each route is determined by the objective function from the departure node.

### Claim 10 (depends on 1)

The method of claim 1, wherein each link in the map data has an associated importance and the searching only selects links having an associated importance of equal to or greater than a predetermined importance.

### Claim 11 (depends on 10)

The method of claim 10, wherein one or more regions are arranged around the departure node and/or one or more points-of-interest (POI) having an associated importance of less than the predetermined importance, and the searching is enabled to selected links within the respective regions having an importance of equal to or greater than the importance associated with the region.

### Claim 12 (depends on 10)

The method of claim 10, wherein the searching is enabled to select links from a node having an associated importance of less than the predetermined importance if a link having the node as an endpoint has an associated importance of less than the predetermined importance.

### Claim 13 (depends on 10)

The method of claim 10, wherein the importance associated with each link is a functional road classification (FRC).

### Claim 14

A computing device, comprising a processor and a memory storing map data, the processor being arranged to execute a one-to-many route searching module for searching the map data to determine a plurality of routes from an initial node, wherein the module is arranged to search the map data up to a search boundary to select links to form the plurality of routes according to a cost function, and to determine an extent of each route according to an objective function; and wherein the search boundary is based upon a cost associated with an unreachable node.

### Claim 15 (depends on 14)

The computing device of claim 14, wherein the search boundary has a cost greater than the unreachable node.

### Claim 16 (depends on 14, 15)

The computing device of claim 14 or 15, wherein module is arranged to select a link from each visited node having a lowest cost determined according to the cost function to form each of the plurality of routes.

### Claim 17 (depends on 14)

The computing device of claim 14, wherein the module is arranged to determine a cost of each link based upon one or more of length, travelling time and/or travelling speed of the link.

### Claim 18 (depends on 14)

The computing device of claim 14, wherein the module is arranged to determine the extent of each route according to the objective function based upon or more of energy cost, travelling time and/or travelling distance.

### Claim at position 19

19-20. (canceled)

### Claim 21 (depends on 1)

A non-transitory computer readable medium comprising computer readable instructions, which, when executed on a computer, cause the computer to perform a method according to claim 1.
