System for classifying streets for vehicle navigation

• US 9,020,760 B2
• Filed: 08/16/2012
• Issued: 04/28/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: Fryer, Mark, Bigot, Sebastien Sydney Robert
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): Nguyen, Nga X
• Application Number:
  US13/587,705
• Publication Number:
  US 20130204524A1
• Time in Patent Office: 985 Days
• Field of Search: 701/533, 701/540, 701/527
• US Class Current: 701/533
• 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

Vehicle management systems and associated processes can determine and consider street classifications when selecting routes for fleet vehicles. In one embodiment, a system for calculating routes for a plurality of vehicles in a vehicle fleet includes a computer system. The computer system is configured to receive custom data to classify streets of a network of streets in a geographic region for use in calculating routes. Based at least in part on the received custom data, the computer system can calculate custom routes on the network of streets between waypoint locations. In addition, the computer system can determine a classification for each street of the network of streets based at least in part on the calculated custom routes. The classification can include a score indicative of a hierarchical ranking of each street for calculating routes for the fleet vehicles on the network of streets in the geographic region.

Claims

1. A system for calculating routes for a plurality of vehicles in a vehicle fleet, the system comprising:

output interface circuitry configured to communicate with a fleet of vehicles; and

processing circuitry comprising computer hardware configured to;

identify one or more custom characteristics of one vehicle of a fleet of vehicles or of routes traveled by the one vehicle, the one or more custom characteristics comprising one or more of a vehicle type, a route optimization preference, and an avoidable road condition;

calculate a plurality of simulated routes for the one vehicle on a network of streets in a geographic region between a plurality of selected waypoint locations using the one or more custom characteristics to influence determination of the plurality of simulated routes, the plurality of simulated routes comprising trial routes across the network indicative of preferred paths of travel by the one vehicle in the network and not actual paths to be traveled by the one vehicle in the network;

based at least on the plurality of simulated routes, assign one of a plurality of classifications to individual streets of the network according to an estimated importance of the individual streets of the network to routes of different lengths;

store the assigned classifications in a computer database;

subsequent to the storage of the assigned classifications, identify a starting waypoint location and an ending waypoint location for an actual route to be traveled by a fleet vehicle of the fleet of vehicles, an attribute of the fleet vehicle or of routes traveled by the fleet vehicle matching at least one of the one or more custom characteristics;

access the assigned classifications from the computer database;

calculate the actual route on the network between the starting waypoint location and the ending waypoint location using the assigned classifications to exclude at least some of the individual streets of the network from evaluation for inclusion in the actual route; and

output, via the output interface circuitry, data representing the actual route for presentation to a driver of the fleet vehicle.

2. The system of claim 1, wherein the assigned classifications are indicative of a hierarchical ranking of the individual streets of the network.

3. The system of claim 1, wherein a common classification of the plurality of classifications is indicative of a similar degree of importance for use in routes on the network that have a similar length.

4. The system of claim 1, wherein the processing circuitry is configured to assign one of the plurality of classifications to one of the individual streets of the network further according to a first distance from the one of the individual streets to an initial waypoint location of one of the plurality of simulated routes and a second distance from the one of the individual streets to a final waypoint location of the one of the plurality of simulated routes.

5. The system of claim 1, wherein the processing circuitry is configured to assign a first classification of the plurality of classifications to one of the individual streets of the network when a first distance and a second distance exceed a first threshold and a second classification of the plurality of classifications to the one of the individual streets of the network when the first distance or the second distance do not exceed the first threshold, the first distance comprising a distance from the one of the individual streets to an initial waypoint location of one of the plurality of simulated routes and the second distance comprising a distance from the one of the individual streets to a final waypoint location of the one of the plurality of simulated routes.

6. The system of claim 5, wherein after the processing circuitry assigns the first classification to the one of the individual streets, the processing circuitry is configured to assign the one of the individual streets a third classification of the plurality of classifications when a third distance and a fourth distance exceed a second threshold greater than the first threshold, the third distance comprising a distance from the one of the individual streets to an initial waypoint location of another of the plurality of simulated routes and the fourth distance comprising a distance from the one of the individual streets to a final waypoint location of the another of the plurality of simulated routes.

7. The system of claim 1, wherein the processing circuitry is configured to calculate one simulated route between every set of two of the plurality of selected waypoint locations.

8. The system of claim 1, wherein at least some of the plurality of selected waypoint locations comprise intersections between two or more of the individual streets of the network.

9. The system of claim 1, wherein the processing circuitry is configured to exclude the at least some of the individual streets of the network from evaluation for inclusion in the actual route when the at least some of the individual streets are assigned a first classification of the plurality of classifications and the at least some of the individual streets are located outside of a first boundary around the starting waypoint location and a second boundary around the ending waypoint location, a size of the first boundary and the second boundary corresponding to the first classification assigned to the at least some of the individual streets.

10. The system of claim 1, wherein

the one or more custom characteristics comprise the vehicle type;

when the vehicle type is a first vehicle type, the processing circuitry is configured to exclude a first set of the individual streets of the network from evaluation for inclusion in the actual route; and

when the vehicle type is a second vehicle type different from the first vehicle type, the processing circuitry is configured to exclude a second set of the individual streets of the network from evaluation for inclusion in the actual route, the first set of the individual streets being different from the second set of the individual streets.

11. Non-transitory physical computer storage comprising instructions stored thereon for implementing, in one or more processors, a method of calculating routes for a plurality of vehicles in a vehicle fleet, the method comprising:

identifying one or more custom characteristics of one vehicle of a fleet of vehicles or of routes traveled by the one vehicle, the one or more custom characteristics comprising one or more of a vehicle type, a route optimization preference, and an avoidable road condition;

calculating a plurality of simulated routes for the one vehicle on a network of streets in a geographic region between a plurality of selected waypoint locations using the one or more custom characteristics to influence determination of the plurality of simulated routes, the plurality of simulated routes comprising trial routes across the network indicative of preferred paths of travel by the one vehicle in the network and not actual paths to be traveled by the one vehicle in the network;

based at least on the plurality of simulated routes, assigning one of a plurality of classifications to individual streets of the network according to an estimated importance of the individual streets of the network to routes of different lengths;

storing the assigned classifications in a computer database;

subsequent to the storage of the assigned classifications, identifying a starting waypoint location and an ending waypoint location for an actual route to be traveled by a fleet vehicle of the fleet of vehicles, an attribute of the fleet vehicle or of routes traveled by the fleet vehicle matching at least one of the one or more custom characteristics;

accessing the assigned classifications from the computer database;

calculating the actual route on the network between the starting waypoint location and the ending waypoint location using the assigned classifications to exclude at least some of the individual streets of the network from evaluation for inclusion in the actual route; and

outputting, via output interface circuitry, data representing the actual route for presentation to a driver of the fleet vehicle.

12. The non-transitory physical computer storage of claim 11, wherein the assigned classifications are indicative of a hierarchical ranking of the individual streets of the network.

13. The non-transitory physical computer storage of claim 11, wherein a common classification of the plurality of classifications is indicative of a similar degree of importance for use in routes on the network that have a similar length.

14. The non-transitory physical computer storage of claim 11, wherein said assigning comprising assigning one of the plurality of classifications to one of the individual streets of the network according to a first distance from the one of the individual streets to an initial waypoint location of one of the plurality of simulated routes and a second distance from the one of the individual streets to a final waypoint location of the one of the plurality of simulated routes.

15. The non-transitory physical computer storage of claim 11, wherein said assigning comprises assigning a first classification of the plurality of classifications to one of the individual streets of the network when a first distance and a second distance exceed a first threshold and a second classification of the plurality of classifications to the one of the individual streets of the network when the first distance or the second distance do not exceed the first threshold, the first distance comprising a distance from the one of the individual streets to an initial waypoint location of one of the plurality of simulated routes and the second distance comprising a distance from the one of the individual streets to a final waypoint location of the one of the plurality of simulated routes.

16. The non-transitory physical computer storage of claim 15, wherein after assigning the first classification to the one of the individual streets, further comprising assigning the one of the individual streets a third classification of the plurality of classifications when a third distance and a fourth distance exceed a second threshold greater than the first threshold, the third distance comprising a distance from the one of the individual streets to an initial waypoint location of another of the plurality of simulated routes and the fourth distance comprising a distance from the one of the individual streets to a final waypoint location of the another of the plurality of simulated routes.

17. The non-transitory physical computer storage of claim 11, wherein said calculating the plurality of simulated routes comprising calculating one simulated route between every set of two of the plurality of selected waypoint locations.

18. The non-transitory physical computer storage of claim 11, wherein at least some of the plurality of selected waypoint locations comprise intersections between two or more of the individual streets of the network.

19. The non-transitory physical computer storage of claim 11, further comprising excluding the at least some of the individual streets of the network from evaluation for inclusion in the actual route when the at least some of the individual streets are assigned a first classification of the plurality of classifications and the at least some of the individual streets are located outside of a first boundary around the starting waypoint location and a second boundary around the ending waypoint location, a size of the first boundary and the second boundary corresponding to the first classification assigned to the at least some of the individual streets.

20. The non-transitory physical computer storage of claim 11, wherein

the one or more custom characteristics comprise the vehicle type;

when the vehicle type is a first vehicle type, further comprising excluding a first set of the individual streets of the network from evaluation for inclusion in the actual route; and

when the vehicle type is a second vehicle type different from the first vehicle type, further comprising excluding a second set of the individual streets of the network from evaluation for inclusion in the actual route, the first set of the individual streets being different from the second set of the individual streets.