ROUTE OPTIMIZATION INCLUDING POINTS OF INTEREST

• US 20150285652A1
• Filed: 10/24/2013
• Published: 10/08/2015
• Est. Priority Date: 10/25/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Peri, Omer Shmuel, Soffer, Ronen Aharon, Yissachar, Amir, Sagi, Noam
• Granted Patent: US 9,726,510 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

A method for navigation includes receiving in a mobile computing device (24) a designation of an origin (32, 92) and a destination (34, 94) of an itinerary of a user of the device. An optimal primary route (96) is computed from the origin to the destination. Multiple points of interest (40, 98, 100) are identified in proximity to the optimal primary route. A respective first optimal sub-route (42) is computed between the origin and each of the points of interest, and a respective second optimal sub-route (44) is computed between the destination and each of the points of interest. One or more alternative routes (102, 104) from the origin to the destination via one or more of the points of interest are presented to the user on the mobile computing device, by combining the respective first and second optimal sub-routes computed for the one or more of the points of interest.

Claims

1. A method for navigation, comprising:

receiving in a mobile computing device a designation of an origin and a destination of an itinerary of a user of the device;

computing an optimal primary route from the origin to the destination;

identifying multiple points of interest in proximity to the optimal primary route;

computing for the identified points of interest a respective first optimal sub-route between the origin and each of the points of interest and a respective second optimal sub-route between the destination and each of the points of interest; and

presenting to the user, on the mobile computing device, one or more alternative routes from the origin to the destination via one or more of the points of interest by combining the respective first and second optimal sub-routes computed for the one or more of the points of interest.

3. The method according to claim 1, wherein presenting the one or more alternative routes comprises selecting one or more of the points of interest responsively to the respective first and second optimal sub-routes computed for the points of interest, and displaying the one or more alternative routes that pass through the one or more selected points of interest.

4. The method according to claim 3, wherein selecting the one or more of the points of interest comprises computing respective scores for the points of interest responsively both to the respective first and second optimal sub-routes and to respective qualitative evaluations of the points of interest, and choosing the one or more of the alternative routes responsively to the respective scores.

6. The method according to claim 4, wherein the qualitative evaluations take into account at least one scoring factor, selected from a group of scoring factors consisting of:

respective value of goods or services offered at the points of interest;

prioritization of needs of the user; and

navigation preferences of the user.

9. The method according to claim 4, wherein choosing the one or more of the alternative routes comprises displaying to the user a prioritized list containing two or more of the alternative routes, and wherein the method comprises receiving a selection by the user of one of the alternative routes in the prioritized list, and providing the user with navigation instructions along the one of the alternative routes selected by the user, wherein computing the respective scores comprises learning user preferences from the selection, and applying the learned preference in computing the scores for subsequent routes.

2. (canceled)

5. (canceled)

7-8. -8. (canceled)

10-12. -12. (canceled)

13. Apparatus for navigation, comprising:

a memory, configured to contain a database containing map data and points of interest; and

a processor, which is configured to receive a designation of an origin and a destination of an itinerary of a user of a mobile computing device, and using the database, to compute an optimal primary route from the origin to the destination, to identify a plurality of the points of interest that are in proximity to the optimal primary route, to compute for the identified points of interest a respective first optimal sub-route between the origin and each of the points of interest and a respective second optimal sub-route between the destination and each of the points of interest, and to present to the user, on the mobile computing device, one or more alternative routes from the origin to the destination via one or more of the points of interest by combining the respective first and second optimal sub-routes computed for the one or more of the points of interest.

15. The apparatus according to claim 13, wherein the processor is configured to select one or more of the points of interest responsively to the respective first and second optimal subroutes computed for the points of interest, and to display the one or more alternative routes that pass through the one or more selected points of interest.

16. The apparatus according to claim 15, wherein the processor is configured to compute respective scores for the points of interest responsively both to the respective first and second optimal sub-routes and to respective qualitative evaluations of the points of interest, and to choose the one or more of the alternative routes responsively to the respective scores.

20. The apparatus according to claim 16, wherein the processor is configured to provide to the user a prioritized list containing two or more of the alternative routes, to receive a selection by the user of one of the alternative routes in the prioritized list, and to provide the user with navigation instructions along the one of the alternative routes selected by the user.

21. The apparatus according to claim 20, wherein the processor is configured to learn user preferences from the selection, and to apply the learned preference in computing the scores for subsequent routes.

22. The apparatus according to claim 21, wherein the processor is configured to sort the identified points of interest, with respect to each of the origin and the destination, in an order of remoteness from the origin or the destination, and to compute the first or second optimal sub-routes according to the order from most to least remote.

23. The apparatus according to claim 21, wherein the first and second optimal sub-routes found by the processor comprise at least one single sub-route that reaches two or more of the points of interest.

24. The apparatus according to claim 21, wherein the processor is configured to identify one or more advertisements relating to a point of interest in proximity to one of the alternative routes, and to present the advertisement to the user.

14. (canceled)

17-19. -19. (canceled)

25. A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to:

receive a designation of an origin and a destination of an itinerary of a user of a mobile computing device;

compute an optimal primary route from the origin to the destination;

identify a plurality of the points of interest that are in proximity to the optimal primary route;

compute for the identified points of interest a respective first optimal sub-route between the origin and each of the points of interest and a respective second optimal sub-route between the destination and each of the points of interest; and

present to the user, on the mobile computing device, one or more alternative routes from the origin to the destination via one or more of the points of interest by combining the respective first and second optimal sub-routes computed for the one or more of the points of interest.

27. The product according to claim 25, wherein the instructions cause the computer to select one or more of the points of interest responsively to the respective first and second optimal subroutes computed for the points of interest, and to display the one or more alternative routes that pass through the one or more selected points of interest.

28. The product according to claim 27, wherein the instructions cause the computer to compute respective scores for the points of interest responsively both to the respective first and second optimal sub-routes and to respective qualitative evaluations of the points of interest, and to choose the one or more of the alternative routes responsively to the respective scores.

29. The product according to claim 28, wherein the scores are computed so as to favor the alternative routes that minimize additional travel relative to the optimal primary route.

30. The product according to claim 28, wherein the qualitative evaluations take into account at least one scoring factor, selected from a group of scoring factors consisting of:

respective value of goods or services offered at the points of interest;

prioritization of needs of the user; and

navigation preferences of the user.

33. The product according to claim 28, wherein the instructions cause the computer to provide to the user a prioritized list containing two or more of the alternative routes, to receive a selection by the user of one of the alternative routes in the prioritized list, and to provide the user with navigation instructions along the one of the alternative routes selected by the user, wherein the instructions cause the computer to learn user preferences from the selection, and to apply the learned preference in computing the scores for subsequent routes.

34. The product according to claim 33, wherein the instructions cause the computer to sort the identified points of interest, with respect to each of the origin and the destination, in an order of remoteness from the origin or the destination, and to compute the first or second optimal sub-routes according to the order from most to least remote.

26. (canceled)

31-32. -32. (canceled)

35-36. -36. (canceled)