Vehicle fleet routing system

• US 9,068,852 B2
• Filed: 02/08/2013
• Issued: 06/30/2015
• Est. Priority Date: 02/08/2012
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: Mason, Ralph James, Fryer, Mark, Mitchell, David John
• Primary Examiner(s): Nguyen, John Q
• Assistant Examiner(s): ODEH, NADEEM N
• Application Number:
  US13/763,533
• Publication Number:
  US 20130297207A1
• Time in Patent Office: 872 Days
• Field of Search: 701/533, 701/410, 701/467
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A vehicle management system is described herein that can perform a variety of features related to managing fleets of vehicles. For example, the vehicle management system includes a routing module that can perform a variety of functions. Some of these functions can include determining a first route between locations using a simplified routing network and then determining a second route between the locations using a more exhaustive routing network. Further, the routing module can store information about the natural flow through intersections, improving control of routes through intersections. Some or all of these features may be used together, or any of these features may be omitted in any given embodiment.

Claims

1. A system for calculating a route for a vehicle, the system comprising:

a computer system comprising computer hardware configured to;

determine a first route from a start node toward an end node on a first routing network until a first groove node is reached, the first route connecting the start node and the first groove node on the first routing network, the start node and the end node defining a route to be traveled by a vehicle, the first groove node not being the end node;

determine a second route from the end node toward the start node on the first routing network until a second groove node is reached, the second route connecting the end node and the second groove node on the first routing network, the second groove node not being the start node;

determine a groove route from the first groove node to the second groove node on a second routing network, the groove route connecting the first groove node and the second groove node on the second routing network, the second routing network comprising a subset of nodes of the first routing network and fewer road links than the first routing network;

determine an initial route comprising the first route, the groove route, and the second route, the initial route connecting the start node and the end node;

revise the initial route to include an alternative route on the first routing network in place of at least a portion of the groove route, wherein the computer system comprising computer hardware is configured to revise the initial route by;

determining the alternative route from a plurality of road links of the first routing network,

preferring to incorporate in the alternative route those of the plurality of road links that are closer to the groove route than others of the plurality of road links that are farther from the groove route, and

preferring to incorporate in the alternative route those of the plurality of road links near the groove route that have a higher road link classification than others of those of the plurality of road links near the groove route; and

output data representing the revised initial route for presentation to a driver of the vehicle.

2. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route based at least in part on weather along the groove route.

3. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route based at least in part on traffic along the groove route.

4. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route based at least in part on construction along the groove route.

5. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route based at least in part on an overpass height along the groove route.

6. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route based at least in part on a fuel efficiency for the vehicle to travel the groove route.

7. The system of claim 1, wherein the nodes of the first routing network comprise intersections of the plurality of road links of the first routing network.

8. The system of claim 1, wherein the computer system comprising computer hardware is configured to select the second routing network from a plurality of groove routing networks based at least in part on a Euclidean distance between the start node and the end node.

9. The system of claim 1, wherein the computer system comprising computer hardware is configured to select the second routing network from a plurality of groove routing networks.

10. The system of claim 1, wherein the computer system comprising computer hardware is configured to revise the initial route using a heat map.

11. A method for calculating a route for a vehicle, the method comprising:

using a computer system comprising computer hardware for;

determining a first route from a start node toward an end node on a first routing network until a first groove node is reached, the first route connecting the start node and the first groove node on the first routing network, the start node and the end node defining a route to be traveled by a vehicle, the first groove node not being the end node;

determining a second route from the end node toward the start node on the first routing network until a second groove node is reached, the second route connecting the end node and the second groove node on the first routing network, the second groove node not being the start node;

determining a groove route from the first groove node to the second groove node on a second routing network, the groove route connecting the first groove node and the second groove node on the second routing network, the second routing network comprising a subset of nodes of the first routing network and fewer road links than the first routing network;

determining an initial route comprising the first route, the groove route, and the second route, the initial route connecting the start node and the end node;

revising the initial route to include an alternative route on the first routing network in place of at least a portion of the groove route, wherein said revising comprises revising the initial route by;

determining the alternative route from a plurality of road links of the first routing network,

preferring to incorporate in the alternative route those of the plurality of road links that are closer to the groove route than others of the plurality of road links that are farther from the groove route, and

preferring to incorporate in the alternative route those of the plurality of road links near the groove route that have a higher road link classification than others of those of the plurality of road links near the groove route; and

outputting data representing the revised initial route for presentation to a driver of the vehicle.

12. The method of claim 11, further comprising selecting the second routing network from a plurality of groove routing networks based at least in part on a Euclidean distance between the start node and the end node.

13. The method of claim 11, wherein said revising comprises revising the initial route using a heat map.

14. Non-transitory physical computer storage comprising instructions stored thereon for implementing, in one or more processors, a process for calculating a route for a vehicle, the process comprising:

determining a first route from a start node toward an end node on a first routing network until a first groove node is reached, the first route connecting the start node and the first groove node on the first routing network, the start node and the end node defining a route to be traveled by a vehicle, the first groove node not being the end node;

determining a second route from the end node toward the start node on the first routing network until a second groove node is reached, the second route connecting the end node and the second groove node on the first routing network, the second groove node not being the start node;

determining a groove route from the first groove node to the second groove node on a second routing network, the groove route connecting the first groove node and the second groove node on the second routing network, the second routing network comprising a subset of nodes of the first routing network and fewer road links than the first routing network;

determining an initial route comprising the first route, the groove route, and the second route, the initial route connecting the start node and the end node;

revising the initial route to include an alternative route on the first routing network in place of at least a portion of the groove route, wherein said revising comprises revising the initial route by;

determining the alternative route from a plurality of road links of the first routing network,

preferring to incorporate in the alternative route those of the plurality of road links that are closer to the groove route than others of the plurality of road links that are farther from the groove route, and

preferring to incorporate in the alternative route those of the plurality of road links near the groove route that have a higher road link classification than others of those of the plurality of road links near the groove route; and

outputting data representing the revised initial route for presentation to a driver of the vehicle.

15. The non-transitory physical computer storage of claim 14, wherein the process further comprises selecting the second routing network from a plurality of groove routing networks.

16. The non-transitory physical computer storage of claim 14, wherein said revising comprises revising the initial route using a heat map.