# US 2021/0341302 A1 · Method and Devices for Determining Routes for Routing a Vehicle

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

- Number: US 2021/0341302 A1
- Document ID: US20210341302A1
- Status: Published application
- Kind: A1
- Application number: 17/268,420
- Filed: 2019-08-09
- Published: 2021-11-04
- Earliest claimed: 2018-08-14
- Assignees: Bayerische Motoren Werke Aktiengesellschaft
- Applicants: Bayerische Motoren Werke Aktiengesellschaft
- Inventors: Stefaan DUYM; Dominik JAIN
- Web page: https://patentgrep.com/patent/US20210341302A1

## CPC

- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G01C 21/3407: {specially adapted for specific applications}
- G01C 21/3423: {Multimodal routing}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- 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

Methods for determining routes for routing vehicle include computing, in a digital map a route from route source to route destination. Such methods further include determining sub-route of the computed route, which ends at the destination and along which the vehicle could be parked. And such methods still further include extending the computed route beyond the route destination in area around the route destination until route parking probability of parking route, including links of the determined sub-route and/or of the extension of the computed route, is equal to or greater than predetermined threshold whilst total expected travel time, associated with the extended computed route and comprising driving and walking times, is minimized. The route parking probability is the probability that parking at some point along the extended computed route will be possible and wherein one or more links of the parking route are suitable for parking.

## Claims

### Claim at position 1

1-17. (canceled)

### Claim 18

A method for determining routes for routing a vehicle, the method comprising:
computing, in a digital map, a route from a route source to a route destination;
determining a sub-route of the computed route, which ends at the destination and along which the vehicle could be parked; and
extending the computed route beyond the route destination in an area around the route destination until a route parking probability of a parking route, comprising links of the determined sub-route and/or of the extension of the computed route, is equal to or greater than a predetermined threshold whilst a total expected travel time, associated with the extended computed route and comprising driving and walking times, is minimized,
wherein the route parking probability is the probability that parking at some point along the extended computed route will be possible and wherein one or more links of the parking route are suitable for parking.

### Claim 19 (depends on 18)

The method according to claim 18, wherein the total expected travel time is a probabilistic expectation comprised of driving times from the route source to potential parking locations and walking times from the potential parking locations to the route destination.

### Claim 20 (depends on 18)

The method according to claim 18,
wherein the determining of the sub-route comprises starting at the route destination and link-wise moving back in the computed route towards the route source,
wherein, when link-wise moving back in the computed route, at each corresponding link of the computed route, a respective route parking probability of being able to park at some point along the computed route from the corresponding link to the destination and a respective distance from a predecessor of the corresponding link in the computed route to the route destination are computed,
wherein the link-wise moving back is terminated and the corresponding link is selected as an appropriate start link of the sub-route if the respective route parking probability is greater than or equal to a desired route parking probability or if the respective distance is greater than a first predetermined threshold distance.

### Claim 21 (depends on 18)

The method according to claim 18, wherein the extending of the computed route is executed based on a tree search variant of a best-first search.

### Claim 22 (depends on 18)

The method according to claim 18, wherein the extending of the computed route is executed starting from the route destination.

### Claim 23 (depends on 18)

The method according to claim 18, wherein the extending of the computed route comprises limiting a search space in the digital map to links around the route destination.

### Claim 24 (depends on 23)

The method according to claim 23, wherein the limiting of the search space in the digital map to links around the route destination comprises limiting to links whose start positions and end positions are within a second predetermined threshold distance of the route destination.

### Claim 25 (depends on 18)

The method according to claim 18, wherein a computing of the route parking probability comprises reducing a link parking probability of a link if it has been previously used within the same parking route, the reduction depending on the time that has passed since the last usage.

### Claim 26 (depends on 18)

The method according to claim 18, wherein the route parking probability being a probability of parking at some point along the parking route R, is determined as follows:
r
⁡
(
R
)
=
∑
i
=
1
|
R
|
⁢
q
⁡
(
R
,
i
)
,
wherein |R| denotes a number of links of the parking route R, and q(R, i) denotes a route link parking probability that, when traveling along the parking route R, the vehicle will be parked on the i-th link of the parking route R.

### Claim 27 (depends on 26)

The method according to claim 26, wherein the route link parking probability q(R, i) that, when traveling along the parking route R, the vehicle will be parked on the i-th link of the parking route R is determined as follows:
q
⁡
(
R
,
i
)
=
p
⁡
(
R
,
i
)
⁢
∏
j
=
1
i
-
1
⁢
(
1
-
p
⁡
(
R
,
j
)
)
,
wherein p(R, i) denotes a link parking probability that a parking space will be available on the i-th link of the parking route R, and wherein p(R, j) denotes a link parking probability that a parking space will be available on the j-th link of the parking route R.

### Claim 28 (depends on 27)

The method according to claim 27, wherein the link parking probability that a parking space is available and considered usable on the i-th link is determined as follows,
p(R,i)=pRiwp(R,i),
wherein pRi denotes the probability with which a free parking space is expected to be available on the i-th link of route R, and wherein wp (R, i) indicates the degree to which the probability pRi should be applied with regard to the route.

### Claim 29 (depends on 18)

The method according to claim 18, wherein the extending of the computed route comprises applying a priority function ƒ(R) for a best-first search, which, by defining the order in which candidate routes are considered during the search, guides the search in order to find routes with short total travel times, the total travel times including both the drive time and the walk time from the potential parking locations to the route destination.

### Claim 30 (depends on 29)

The method according to claim 29, wherein a value of the priority function ƒ(R) is a lower bound on the expected travel duration of all extensions of route R, such as
f
⁡
(
R
)
=
∑
i
=
1
|
R
|
⁢
q
⁡
(
R
,
i
)
⁢
(
t
DrivePark
⁡
(
R
,
i
)
+
t
F
⁢
o
⁢
o
⁢
t
⁡
(
R
,
i
)
)
+
(
1
-
r
⁡
(
R
)
)
⁢
t
Drive
(
R
,

R
|
)
,
wherein tDrivePark(R, i) is the total travel time on route R for the case where the vehicle is assumed to park on the i-th link, tFoot(R, i) is the walk time from the i-th link in R to the route destination and tDrive(R, |R|) is the drive time required for the entire route R.

### Claim 31 (depends on 29)

The method according to claim 29, wherein a value of the priority function ƒ(R) is an estimate of time expected to be wasted when choosing route R, such as
f
⁡
(
R
)
=
∑
i
=
1
|
R
|
⁢
(
1
-
p
⁡
(
R
,
i
)
)
⁢
(
t
Drive
⁡
(
R
,
i
)
-
t
Drive
⁡
(
R
,
i
-
1
)
+
t
F
⁢
o
⁢
o
⁢
t
⁡
(
R
,
i
)
)
,
wherein tDrive(R, i) is the drive time on route R up to the end of the i-th link, wherein tDrive(R, 0) is defined to be 0 for all R, wherein tFoot(R, i) is the walk time from the i-th link in R to the route destination.

### Claim 32 (depends on 18)

The method according to claim 18, wherein the extending of the computed route comprises truncating a fringe of a best-first search, wherein the fringe comprises a set of candidate routes that could be explored next, and wherein the truncating of the fringe comprises deleting routes from the fringe that are associated with a lowest route parking probability, if the set of nodes of the fringe is larger than a predetermined fringe size threshold.

### Claim 33 (depends on 32)

The method according to claim 32, wherein the extending of the computed route comprises omitting a consideration of a potential route R and preventing an addition of the potential route R to the fringe if another route has been previously found which ends in the same point as R and is associated with a route parking probability that is at least as high as the route parking probability of the potential route R.

### Claim 34 (depends on 18)

A device configured to determine routes for routing a vehicle, wherein the device is further configured to execute the method according to claim 18.
