Systems and methods for distance and congestion-aware resource deployment

• US 8,786,605 B1
• Filed: 10/24/2013
• Issued: 07/22/2014
• Est. Priority Date: 10/24/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Curtis, Spike, Janatpour, Dustin, Bailey, Drew
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): BUTTRAM, ALAN T
• Application Number:
  US14/062,835
• Time in Patent Office: 271 Days
• Field of Search: 345/440, 345/629, 701409-460, 701511-517, 340988-994, 3409951-99528
• US Class Current: 345/440
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 50/26 Government or public services business processes related to the transportation industry G06Q50/40
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D
• CPC Class Codes: G08G 1/205 Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental

Abstract

Computer-implemented systems and methods are disclosed for distance and congestion-aware resource deployment. In some embodiments, a method is provided to estimate a vehicle deployment region. The method includes constructing a graph data structure using at least in part a single invocation of a form of Dijkstra'"'"'s algorithm. The method additionally includes partitioning an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of the vehicle. The method also includes selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location, and wherein each selected geographical location was determined, using the graph data structure, to be reachable from the vehicle location within a specified maximum cost. The method further includes forming a polygon representing a vehicle deployment region from the selected geographical locations.

Claims

1. A method for estimating a vehicle deployment region, the method comprising the following operations performed by one or more processors:

constructing a graph data structure using at least in part a single invocation of a form of Dijkstra'"'"'s algorithm;

partitioning an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of a vehicle;

selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location, and wherein each selected geographical location was determined, using the graph data structure, to be reachable from the vehicle location within a specified maximum cost; and

forming a polygon representing a vehicle deployment region from the selected geographical locations.

2. The method of claim 1, wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.

3. The method of claim 2, wherein the graph data structure reflects restrictions imposed by local traffic rules.

4. The method of claim 3, wherein the form of Dijkstra'"'"'s algorithm is a truncated form of Dijkstra'"'"'s algorithm.

5. The method of claim 4, wherein an origin node within the plurality of nodes represents a street intersection nearest to the current or potential location of a vehicle.

6. The method of claim 5, wherein edges connect the nodes in the graph data structure and represent street segments.

7. The method of claim 6, further comprising:

assigning traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.

8. The method of claim 7, wherein the traversal cost of an edge is based at least in part on the time it would take to traverse a street segment corresponding to the edge.

9. The method of claim 7, wherein the street-level data includes real-time traffic data.

10. The method of claim 7, wherein the street-level data includes information representing a current average traffic speed for each street segment.

11. The method of claim 1, further comprising:

displaying the vehicle deployment region by overlaying it on a map at the vehicle'"'"'s current or potential deployment location.

12. A system for estimating a vehicle deployment region, the system comprising:

a memory device that stores a set of instructions; and

at least one processor that executes the set of instructions to perform the following operations;

construct a graph data structure using at least in part a single invocation of a form of Dijkstra'"'"'s algorithm;

partition an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of a vehicle;

select, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, wherein each selected geographical region in an angular space region is a geographical location furthest from the center of the angular space, and wherein each selected geographical location within an angular space region was determined, using the graph data structure, to be reachable from the vehicle location within a specified maximum cost; and

form a polygon representing a vehicle deployment region from the selected geographical locations.

13. The system of claim 12, wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.

14. The system of claim 13, wherein the graph data structure reflects restrictions imposed by local traffic rules.

15. The system of claim 13, wherein the form of Dijkstra'"'"'s algorithm is a truncated form of Dijkstra'"'"'s algorithm.

16. The system of claim 13, wherein edges connect the nodes in the graph data structure and represent street segments.

17. The system of claim 16, wherein the at least one processor further executes the set of instructions to perform the following operation:

assigning traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.

18. The system of claim 17, wherein the traversal cost of an edge is based at least in part on the time it would take to traverse a street segment corresponding to the edge.

19. The system of claim 18, wherein the street-level data includes information representing a current average traffic speed for each street segment.

20. The system of claim 13, wherein the set of instructions further cause the at least one processor to:

display the vehicle deployment region by overlaying it on a map at the vehicle'"'"'s current or potential vehicle deployment location.