Preserving original route information after recalculation of a route

Patent metadata

Field	Value
Publication number	US-11035681-B2
Application number	US-201816041571-A
Country	US
Kind code	B2
Filing date	Jul 20, 2018
Priority date	Jul 20, 2018
Publication date	Jun 15, 2021
Grant date	Jun 15, 2021

Abstract

A device provides, to a navigation device, original route information that includes information indicating directions from an origination to a destination, and waypoints. The device receives, from the navigation device, a request for a new route from a current location to the destination, and receives the original route information when the request is associated with an original route stored in the data structure. The device identifies a point along the original route, closest to the current location, and calculates a route from the point along the original route to the current location. The device combines the route and the original route at the point along the original route to create a new route from the current location to the destination, and provides, to the navigation device, new route information for the new route, where the new route information includes information indicating waypoints between the current location and the destination.

First claim

What is claimed is:

1. A device, comprising:
one or more memories; and
one or more processors, communicatively coupled to the one or more memories, to:
receive, from a navigation device associated with a vehicle, a first request for a first route from an origination to a destination;
provide, to the navigation device, first route information based on the first request,
the first route information including:
information indicating directions from the origination to the destination, and
information indicating one or more waypoints between the origination and the destination;

receive, from the navigation device, sensing information from a sensor indicating a current location of the navigation device;
receive, from the navigation device and based on receiving the sensing information, a second request for a second route from the current location of the vehicle to the destination,
the second request being automatically requested by the navigation device when the vehicle begins moving from the current location;

determine whether the second request is associated with a stored route;
receive, from a data structure, the first route information when the second request is determined to be associated with an original route stored in the data structure;
identify a point along the first route that is closest to the current location;
calculate a third route from the point along the first route to the current location;
combine the third route and the first route at the point along the first route to create the second route from the current location to the destination;
utilize a binary search model to map the second route to second route information for the second route,
wherein the binary search model identifies a position of a target value within a sorted array of the data structure; and

provide, to the navigation device, the second route information,
the second route information including:
information indicating directions from the current location to the destination, and
information indicating the one or more waypoints between the current location and the destination.

2. The device of claim 1 , wherein the one or more processors, when determining whether the second request is associated with the stored route, are to:
determine that the destination identified in the second request is associated with the destination of the first route stored in the data structure; and
determine that the first route information is associated with the first route based on determining that the destination identified in the second request is associated with the destination of the first route.

3. The device of claim 2 , wherein the one or more processors, when receiving the first route information, are to:
receive, from the data structure, the first route information based on determining that the first route information is associated with the first route.

4. The device of claim 1 , wherein, when identifying the point along the first route that is closest to the current location, the one or more processors are to:
identify the point along the first route that is closest to the current location based on a predetermined distance between the point and the current location.

5. The device of claim 1 , wherein the one or more processors are further to:
identify, in the data structure, the second route information for the second route from the current location to the destination; and
receive the second route information for the second route from the data structure.

6. The device of claim 1 , wherein the second route information includes:
information indicating one or more new waypoints between the current location and the destination.

7. The device of claim 1 , wherein the one or more processors are further to:
create the information indicating the directions from the current location to the destination, of the second route information, based on geographic street information stored in the data structure.

8. A non-transitory computer-readable medium storing instructions, the instructions comprising:
one or more instructions that, when executed by one or more processors of a device, cause the one or more processors to:
receive, from a navigation device associated with a vehicle, a first request for a first route from an origination to a destination;
provide, to the navigation device, first route information based on the first request,
the first route information including:
information indicating directions from the origination to the destination, and
information indicating one or more waypoints between the origination and the destination;

receive, from the navigation device, sensing information from a sensor indicating a current location of the navigation device;
receive, from the navigation device and based on receiving the sensing information, a second request for a second route from the current location of the vehicle to the destination,
the second request being automatically requested by the navigation device when the vehicle begins moving from the current location;

determine whether the second request is associated with a stored route;
receive, from a data structure, the first route information when the second request is determined to be associated with an original route stored in the data structure;
identify a point along the first route that is closest to the current location;
calculate a third route from the point along the first route to the current location;
utilize a binary search model to map the second route to second route information for the second route,
wherein the binary search model identifies a position of a target value within a sorted array of the data structure;

combine the third route and the first route at the point along the first route to create the second route from the current location to the destination; and
provide, to the navigation device, the second route information,
the second route information including:
information indicating directions from the current location to the destination, and
information indicating the one or more waypoints between the current location and the destination.

9. The non-transitory computer-readable medium of claim 8 , wherein the one or more instructions, that cause the one or more processors to determine whether the second request is associated with the stored route, comprise:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to:
determine that the destination identified in the second request is associated with the destination of the original route stored in the data structure; and
determine that the first route information is associated with the first route based on determining that the destination identified in the second request is associated with the destination of the first route.

10. The non-transitory computer-readable medium of claim 9 , wherein the one or more instructions, that cause the one or more processors to receive the first route information, comprise:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to:
receive, from the data structure, the first route information based on determining that the first route information is associated with the first route.

11. The non-transitory computer-readable medium of claim 8 , wherein the one or more instructions, that cause the one or more processors to identify the point along the first route that is closest to the current location, comprise:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to:
identify the point along the first route that is closest t

Assignees

• Verizon Patent & Licensing Inc

Inventors

• Rehorst Victor J
• Lear Peter J
• Liang Weiyu

Classifications

• G01C21/343 Primary

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

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3679

  Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence) · CPC title