Systems and methods for distance and congestion-aware resource deployment
View Patent ↗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.
1. A method for estimating a vehicle deployment region, the method comprising the following operations performed by one or more processors:
partitioning an angular space centered on a vehicle location into a plurality of angular space regions;
selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, each selected geographical location being reachable from the vehicle location within a specified maximum cost;
forming a polygon representing a region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and
presenting information concerning the region to a user.
2. The method of claim 1 , wherein each geographical location is determined using a graph data structure.
3. The method of claim 2 , wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.
4. The method of claim 3 , wherein the graph data structure reflects restrictions imposed by local traffic rules.
5. The method of claim 4 , wherein the graph data structure is constructed using a truncated form of Dijkstra's algorithm.
6. The method of claim 5 , wherein an origin node within the plurality of nodes represents a street intersection nearest to the current or potential location of a vehicle.
7. The method of claim 6 , wherein edges connect the nodes in the graph data structure and represent street segments.
8. The method of claim 7 , further comprising:
assigning traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.
9. The method of claim 8 , 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.
10. The method of claim 8 , wherein the street-level data includes real-time traffic data.
11. The method of claim 8 , wherein the street-level data includes information representing a current average traffic speed for each street segment.
12. The method of claim 1 , wherein presenting information concerning the estimated vehicle deployment region comprises:
displaying the polygon by overlaying it on a map at the vehicle's current or potential deployment location.
13. 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:
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, each selected geographical location being reachable from the vehicle location within a specified maximum cost;
form a polygon representing a vehicle deployment region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and
present, based on the polygon, information concerning the estimated vehicle deployment region to a user.
14. The system of claim 13 , wherein each geographical location is determined using a data graph structure.
15. The system of claim 14 , wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.
16. The system of claim 15 , wherein the graph data structure reflects restrictions imposed by local traffic rules.
17. The system of claim 16 , wherein the graph data structure is constructed using a truncated form of Dijkstra's algorithm.
18. The system of claim 17 , wherein edges connect the nodes in the graph data structure and represent street segments.
19. The system of claim 18 , wherein the set of instructions further cause the at least one processor to:
assign traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.
20. The system of claim 19 , 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.
21. The system of claim 20 , wherein the street-level data includes information representing a current average traffic speed for each street segment.
22. The system of claim 13 , wherein the set of instructions further cause the at least one processor to:
display the polygon by overlaying it on a map at the vehicle's current or potential vehicle deployment location.
23. A non-transitory computer-readable medium storing a set of instructions that are executable by one or more processors to cause the one or more processors to perform a method for estimating a vehicle deployment region, the method comprising:
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, each selected geographical location being reachable from the vehicle location within a specified maximum cost;
forming a polygon representing a vehicle deployment region from the selected geographical locations, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location; and
presenting, based on the polygon, information concerning the estimated vehicle deployment region to a user.
24. The computer-readable medium of claim 23 , wherein each geographical location is determined using a graph data structure.
25. The computer-readable medium of claim 24 , wherein the graph data structure includes a plurality of nodes and each node of the plurality of nodes represents a street intersection.
26. The computer-readable medium of claim 25 , wherein the graph data structure reflects restrictions imposed by local traffic rules.
27. The computer-readable medium of claim 26 , wherein the graph data structure is constructed using a truncated form of Dijkstra's algorithm.
28. The computer-readable medium of claim 27 , wherein an origin node within the plurality of nodes represents a street intersection nearest to the current or potential location of a vehicle.
29. The computer-readable medium of claim 28 , wherein edges connect the nodes in the graph data structure and represent street segments.
30. The computer-readable medium of claim 29 , wherein the instructions further cause the one or more processors to assign traversal costs for edges based at least in part on street-level data associated with street segments corresponding to the edges.
31. The computer-readable medium of claim 30 , 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.
32. The computer-readable medium of claim 30 , wherein the street-level data includes real-time traffic data.
33. The computer-readable medium of claim 30 , wherein the street-level data includes information representing a current average traffic speed for each street segment.
34. The computer-readable medium of claim 30 , wherein presenting information concerning the estimated vehicle deployment region comprises:
displaying the polygon by overlaying it on a map at the vehicle's current or potential deployment location.