# US 10,502,579 B2 · Method and apparatus for determining modal routes between an origin area and a destination area

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

- Number: US 10,502,579 B2
- Document ID: US10502579B2
- Status: Granted
- Kind: B2
- Application number: 15/334,003
- Filed: 2016-10-25
- Published: 2018-04-26
- Granted: 2019-12-10
- Earliest claimed: 2016-10-25
- Assignees: HERE Global B.V.
- Applicants: HERE Global B.V.
- Inventors: James Fowe; Filippo Pellolio
- Web page: https://patentgrep.com/patent/US10502579B2

## CPC

- G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles}
- G01C 21/3676: {Overview of the route on the road map}
- 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

An approach is provided for determining one or more modal routes between one or more origin areas and one or more destination areas based on trajectory data. The approach involves querying, by a processor, a trajectory database to retrieve one or more trajectories that contain one or more probe points located within the one or more origin areas and the one or more destination areas. The approach also involves clustering, by the processor, the one or more trajectories into one or more trajectory clusters based on a distance. The approach further involves determining, by the processor, respective counts of the one or more trajectories within each of the one or more trajectory clusters. The approach further involves presenting, by the processor, at least one of the one or more trajectory clusters as the one or more modal routes based on the respective counts.

## Claims

### Claim 1

A method for determining one or more modal routes between one origin area and one destination area based on trajectory data comprising:
querying, by a processor, a trajectory database to retrieve trajectories that contain probe points located within the origin area and the destination area, wherein the probe points are collected from one or more sensors of a plurality of devices traveling between the origin area and the destination area, and wherein the probe points indicate a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
clustering, by the processor, the trajectories into trajectory clusters;
processing the trajectories to reduce sinuosity of the trajectories to generate respective other trajectories, wherein clustering of the trajectories comprises clustering the other trajectories in place of the trajectories;
determining, by the processor, respective counts of the trajectories within each of the trajectory clusters; and
presenting and recommending, by the processor, at least one of the trajectory clusters as the one or more modal routes in a user interface based on the respective counts that are higher than the remaining trajectory clusters, wherein the trajectory clusters comprise a representative trajectory selected as one of the trajectories in each cluster with a minimum sum of distances from other trajectories in the each cluster.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining the respective counts based on the other trajectories within each of the trajectory clusters;
selecting from among the trajectory clusters the one or more modal routes based on the respective counts of the other trajectories; and
retrieving the trajectories corresponding to the other trajectories in the selected trajectory clusters to present.

### Claim 3 (depends on 1)

The method of claim 1, wherein the sinuosity is reduced by reducing a number of turns occurring in the trajectories.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
trimming the trajectories based on the origin area and the destination area prior to the generating the other trajectories, the clustering of the trajectories, the presenting of the at least one of the trajectory clusters as the one or more modal routes, or a combination thereof.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
receiving an input specifying one origin point, one destination point, one origin radius centered on the origin point, and one destination radius centered on the destination point,
wherein the origin area is defined by the origin point and the origin radius and the destination area is defined by the destination point and the destination radius.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
determining the representative trajectory for each of the trajectory clusters presented as the one or more modal routes,
wherein the representative trajectory represents a respective one of the one or more modal routes.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
calculating a journey time, a volume, the sinuosity, or a combination thereof associated with the one or more modal routes; and
presenting the journey time, the volume, the sinuosity, or a combination thereof in the user interface in association with the one or more modal routes.

### Claim 8

An apparatus for determining one or more modal routes between one origin area and one destination area based on trajectory data, comprising:
at least one processor; and
at least one memory including computer program code for one or more programs,
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
query a trajectory database to retrieve trajectories that contain probe points located within the origin area and the destination area, wherein the probe points are collected from one or more sensors of a plurality of devices traveling between the origin area and the destination area, and wherein the probe points indicate a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
cluster the trajectories into trajectory clusters;
process the trajectories to reduce sinuosity of the trajectories to generate respective other trajectories, wherein clustering of the trajectories comprises clustering the other trajectories in place of the trajectories;
determine respective counts of the trajectories within each of the trajectory clusters; and
present and recommend at least one of the trajectory clusters as the one or more modal routes in a user interface based on the respective counts that are higher than the remaining trajectory clusters, wherein the trajectory clusters comprise a representative trajectory selected as one of the trajectories in each cluster with a minimum sum of distances from other trajectories in the each cluster.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein the apparatus is further caused to:
determine the respective counts based on the other trajectories within each of the trajectory clusters;
select from among the trajectory clusters the one or more modal routes based on the respective counts of the other trajectories; and
retrieve the trajectories corresponding to the other trajectories in the selected trajectory clusters to present.

### Claim 10 (depends on 8)

The apparatus of claim 8, wherein the apparatus is further caused to:
trim the trajectories based on the origin area and the destination area prior to the generating the other trajectories, the clustering of the trajectories, the presenting of the at least one of the trajectory clusters as the one or more modal routes, or a combination thereof.

### Claim 11 (depends on 8)

The apparatus of claim 8, wherein the apparatus is further caused to:
receive an input specifying one origin point, one destination point, one origin radius centered on the origin point, and one destination radius centered on the destination point,
wherein the origin area is defined by the origin point and the origin radius and the destination area is defined by the destination point and the destination radius.

### Claim 12 (depends on 8)

The apparatus of claim 8, wherein the apparatus is further caused to:
determine the representative trajectory for each of the trajectory clusters presented as the one or more modal routes,
wherein the representative trajectory represents a respective one of the one or more modal routes.

### Claim 13

A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps, for determining one or more modal routes between one origin area and one destination area based on trajectory data:
querying a trajectory database to retrieve trajectories that contain probe points located within the origin area and the destination area, wherein the probe points are collected from one or more sensors of a plurality of devices traveling between the origin area and the destination area, and wherein the probe points indicate a position, a heading, a speed, a time, or a combination thereof of each of the plurality of devices;
clustering the trajectories into trajectory clusters;
processing the trajectories to reduce sinuosity of the trajectories to generate respective other trajectories, wherein clustering of the trajectories comprises clustering the other trajectories in place of the trajectories;
determining respective counts of the trajectories within each of the trajectory clusters; and
presenting and recommending at least one of the trajectory clusters as the one or more modal routes in a user interface based on the respective counts that are higher than the remaining trajectory clusters, wherein the trajectory clusters comprise a representative trajectory selected as one of the trajectories in each cluster with a minimum sum of distances from other trajectories in the each cluster.

### Claim 14 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the apparatus is further caused to perform:
determining the respective counts based on the other trajectories within each of the trajectory clusters;
selecting from among the trajectory clusters the one or more modal routes based on the respective counts of the other trajectories; and
retrieving the trajectories corresponding to the other trajectories in the selected trajectory clusters to present.

### Claim 15 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the apparatus is further caused to perform:
trimming the trajectories based on the origin area and the destination area prior to the generating the other trajectories, the clustering of the trajectories, the presenting of the at least one of the trajectory clusters as the one or more modal routes, or a combination thereof.

### Claim 16 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the apparatus is further caused to perform:
receiving an input specifying one origin point, one destination point, one origin radius centered on the origin point, and one destination radius centered on the destination point,
wherein the origin area is defined by the origin point and the origin radius and the destination area is defined by the destination point and the destination radius.