# US 2019/0376810 A1 · Methods and systems for generating route information in map application executed by electronic device

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

- Number: US 2019/0376810 A1
- Document ID: US20190376810A1
- Status: Published application
- Kind: A1
- Application number: 16/225,448
- Filed: 2018-12-19
- Published: 2019-12-12
- Earliest claimed: 2018-06-07
- Assignees: Yandex Europe AG
- Applicants: Yandex Europe AG
- Inventors: Petr Vladislavovich PROKHORENKOV; Ivan Fedorovich SMIRNOV
- Web page: https://patentgrep.com/patent/US20190376810A1

## CPC

- G01C 21/3685: {the POI's being parking facilities}
- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G01C 21/3676: {Overview of the route on the road map}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G08G 1/143: {inside the vehicles}
- G08G 1/144: {on portable or mobile units, e.g. personal digital assistant [PDA]}
- G08G 1/147: {where the parking area is within an open public zone, e.g. city centre}
- 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)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

There is disclosed a method of generating a parking route. The method is executable by the server and comprises: receiving an indication of a geo-position associated with an electronic device; generating, based on the geo-position, a set of parking candidates; determining a parking-spot-probability at each of the set of parking candidates; generating the parking route containing at least some of the set of parking candidates such as to optimize: a distance to the destination position; total travel time through the parking route; a total parking probability that is based on the parking-spot-probability at each of at least of the set of parking candidates.

## Claims

### Claim 1

A method of generating a parking route to a destination position, the parking route to be displayed in a map application, the map application executable by an electronic device, the electronic device connectable to a server via a communication network, the method executable by the server, the method comprising:
receiving, from the electronic device, an indication of a geo-position associated with the electronic device;
generating, based on the geo-position, a set of parking candidates;
determining, by the server, a parking-spot-probability at each of the set of parking candidates;
generating, by the server, the parking route containing at least some of the set of parking candidates, the generating being executed to optimize the parking route based on:
a distance from the least some of the set of parking candidates to the destination position;
total travel time through the parking route;
a total parking probability that is based on the parking-spot-probability at each of at least of the set of parking candidates.

### Claim 2 (depends on 1)

The method of claim 1, wherein the geo-position includes a current position of the electronic device and an indication of the destination position, and wherein the generating the set of parking candidates comprises generating the set of parking candidates such that:
each of the set of parking candidates located within a pre-determined radius from at least one of: the current position and the destination position.

### Claim 3 (depends on 2)

The method of claim 2, wherein the generating the parking route is executed such as to:
minimize the distance from a given one of the least some of the set of parking candidates to the destination position, the given one being an actual parking location;
minimize the total travel time.

### Claim 4 (depends on 3)

The method of claim 3, wherein the total travel time is the travel time from the current location to the actual parking location.

### Claim 5 (depends on 1)

The method of claim 1, wherein optimizing the parking route comprises applying a Pareto optimality algorithm.

### Claim 6 (depends on 2)

The method of claim 2, wherein the generating the parking route comprises, for a given one of the set of parking candidates:
determining a distance from the current location to the given one of the set of parking candidates;
determining a single-state optimization value, the single-state optimization value based on the probability to park at the given one of the set of parking candidates, the single-state optimization value being representative of:
the distance from the given one of the set of parking candidates to the destination position;
the total travel time through the parking route from the current location to the given one of the set of parking candidates;
the total parking probability that is based on the parking-spot-probability at the given one of the set of parking candidates.

### Claim 7 (depends on 6)

The method of claim 6, wherein the generating the parking route, for the given one of the set of parking candidates, further comprises:
determining a two-state optimization value, the two-state optimization value based on the probability to park at a next sequential one following the given one of the set of parking candidates, the two-state optimization value being representative of:
the distance from the next sequential one of the set of parking candidates to the destination position;
the total travel time through the parking route from the current location to next sequential one;
the total parking probability that is based on the parking-spot-probability at the given one of the set of parking candidates and the next sequential one.

### Claim 8 (depends on 6)

The method of claim 6, the method further comprising repeating the determining step of an N-th-state optimization values using a N-next sequential ones following the next sequential one following the given one of the set of parking candidates.

### Claim 9 (depends on 8)

The method of claim 8, the method further comprising repeating the determining process for all of the set of parking candidates.

### Claim 10 (depends on 9)

The method of claim 9, the method further comprising pruning the N-th-state optimization values that have both the total travel time and the distance being under a pre-determined respective threshold value.

### Claim 11 (depends on 9)

The method of claim 9, the method further comprising:
selecting the at least some of the set of parking candidates from the set of parking candidates based on the N-th-state optimization values that are associated with the total parking probability above a pre-determined threshold value.

### Claim 12 (depends on 11)

The method of claim 11, wherein the selecting the at least some of the set of parking candidates from the set of parking candidates further comprises:
based on a minimal value of an average distance to the destination position, the average distance being a contribution to a total distance value of each individual distances of members of a group associated with a particular state of the N-th-state optimization values.

### Claim 13 (depends on 7)

The method of claim 7, wherein the method further comprises:
calculating the total parking probability as a sum of the parking-spot-probability at the given one of the set of parking candidates and the parking-spot-probability at the next sequential one.

### Claim 14 (depends on 8)

The method of claim 8, wherein the repeating the determining process for all of the set of parking candidates is executed iteratively for all of the set of parking candidates, whereby the iterative process involves starting with a given one and growing a chain of candidates to an N-th length of the at least some of the set of parking candidates.

### Claim 15 (depends on 2)

The method of claim 2, wherein the method further comprises retrieving the destination position from the map application.

### Claim 16

A server configured to generate a parking route, the vehicle route to be displayed in a map application, the map application executable by an electronic device, the electronic device connectable to the server via a communication network, the server comprising:
a network interface for communication via the communication network;
a processor coupled to the network interface, the processor configured to:
receive, from the electronic device, an indication of a geo-position associated with the electronic device;
generate, based on the geo-position, a set of parking candidates;
determine, by the server, a parking-spot-probability at each of the set of parking candidates;
generate, by the server, the parking route containing at least some of the set of parking candidates, the generating being executed to optimize the parking route based on:
a distance from the least some of the set of parking candidates to the destination position;
total travel time through the parking route;
a total parking probability that is based on the parking-spot-probability at each of at least of the set of parking candidates.
