Optimal sequenced route query operation and device

• US 20070073897A1
• Filed: 06/20/2006
• Published: 03/29/2007
• Est. Priority Date: 06/21/2005
• Status: Abandoned Application

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Shahabi, Cyrus, Kolahdouzan, Mohammad, Sharifzadeh, Mehdi
• Application Number:
  US11/472,495
• Publication Number:
  US 20070073897A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A computer system that finds an optimal sequenced route through one point from each of a plurality of categories. The routes are found by determining one point from each of the categories and finding the shortest path through the one point through each of those routes.

Claims

1. A method, comprising:

obtaining a set of points, including a plurality of categories defined within the points; and

using a computer to determine an optimal sequenced route from a start point to one point in each said category.

2. A method as in claim 1, wherein said using the computer to determine comprises determining each of a plurality of possible paths through the categories, and finding the shortest said path.

3. A method as in claim 2, wherein said using the computer to determine further comprises reducing the set of paths.

4. A method as in claim 3, wherein said reducing comprises first computing a path using a technique that finds a first path using a single analysis step for each segment of the path, and then removing any path which has an aspect that is longer than said first path.

5. A method as in claim 3, wherein said reducing comprises comparing each of the set of paths to another path, and deleting paths which are not unique.

6. A method as in claim 1, wherein said using a computer carries out processing in metric space.

7. A method as in claim 1, wherein said using a computer carries out processing in vector space.

8. A method as in claim 7, wherein said processing in vector space maintains a set of partial sequenced routes, and iteratively adds additional partial sequenced routes to make more complete partial sequenced routes.

9. A method as in claim 8, wherein said iteratively adds comprises first checking each additional partial sequenced route against a threshold, and rejecting a partial sequenced route which exceed said threshold.

10. A method as in claim 9, wherein said threshold includes a fixed threshold indicative of a length of a greedy route.

11. A method as in claim 9, wherein said threshold includes a fixed threshold indicative of a length of a route determined using a single analysis step for each segment of the path.

12. A method as in claim 9, wherein said threshold includes a variable threshold indicative of a length of previous items in the set.

13. A method as in claim 1, wherein said using a computer comprises forming a query to said set of points which returns an answer.

14. A method as in claim 1, wherein said set of points is optimized for use with an R-tree

15. The method as in claim 14, wherein said using the computer comprises forming range queries forming at least one range query and using a bounding box to reject any route which is outside the range query.

16. A method as in claim 9, wherein the threshold is a metric threshold.

17. A method as in claim 9, wherein the threshold is a circular threshold implemented as a range query.

18. A method as in claim 1, wherein said using a computer comprises analyzing an R-tree index structure.

19. A method as in claim 17, further comprising reducing the number of results by excluding results outside a bounding box.

20. A method, comprising:

obtaining information indicative of a plurality of categories, and a plurality of points for each of the categories;

iteratively determining plural partial sequenced routes for each of the plurality of categories;

eliminating at least some of the partial sequenced routes by comparing each of said partial sequenced routes with a threshold, to form a reduced set of partial sequenced routes; and

using said reduced set to form an optimal sequenced route through one point in each of the plurality of categories.

21. A method as in claim 20, wherein said eliminating comprises comparing with a first constant threshold, and with a second variable threshold.

22. A method as in claim 21, wherein said thresholds are vector values.

23. A method as in claim 21, wherein said thresholds are values that are optimized for use with an R tree.

24. A method as in claim 21, wherein said constant threshold is the length of a route which is calculated non-iteratively.

35. An apparatus as in claim 21, wherein said constant threshold is the length of a route which is calculated non-iteratively.

25. An apparatus, comprising:

A memory, storing a set of points, and storing a relationship that includes a plurality of categories defined within the points; and

a computer to determine an optimal sequenced route from a start point to one point in each said category.

26. An apparatus as in claim 25, wherein said computer determines each of a plurality of possible paths through the categories, and operates to find the shortest said path.

27. An apparatus as in claim 26, wherein said computer reduces the set of paths to minimize an number of said paths.

28. An apparatus as in claim 27, wherein said computer reduces paths using a technique that finds a first path using a single analysis step for each segment of the path, and then removing any path which has an aspect that is longer than said first path.

29. An apparatus as in claim 28, wherein said computer forms partial sequenced routes and iteratively adds to said partial sequenced routes, by first checking each additional partial sequenced route against a threshold, and rejecting a partial sequenced route which exceeds said threshold.

30. An apparatus as in claim 29, wherein said threshold includes a fixed threshold indicative of a length of a greedy route.

31. An apparatus as in claim 29, wherein said threshold includes a fixed threshold indicative of a length of a route determined using a single analysis step for each segment of the path.

32. An apparatus, comprising:

a memory, storing information indicative of a plurality of categories, and a plurality of points for each of the categories;

a computer, iteratively determining plural partial sequenced routes for each of the plurality of categories, and eliminating at least some of the partial sequenced routes by comparing each of said partial sequenced routes with a threshold, to form a reduced set of partial sequenced routes and storing the partial sequenced routes, and using said reduced set to form an optimal sequenced route through one point in each of the plurality of categories.

33. An apparatus as in claim 32, wherein said computer uses a first constant threshold, and with a second variable threshold for said eliminating.

34. An apparatus as in claim 33, wherein said thresholds are values that are optimized for use with an R tree.