Vehicle fleet routing system

• US 10,311,385 B2
• Filed: 08/10/2016
• Issued: 06/04/2019
• Est. Priority Date: 06/15/2012
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Looman, William George, Hidayat, Jefferson Ray Tan, Kok, Katherine Winnie, Dunlop, Mark Robert
• Primary Examiner(s): Jeanty, Romain
• Application Number:
  US15/233,838
• Publication Number:
  US 20170061335A1
• Time in Patent Office: 1,028 Days
• Field of Search: 705 725
• CPC Class Codes: G01C 21/3632 Guidance using simplified or iconic instructions, e.g. using arrows G01C21/365 takes precedence
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals
• CPC Class Codes: G06Q 10/0833 Tracking
• CPC Class Codes: G06Q 10/08355 Routing methods
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

In one embodiment, a system includes a memory device and a hardware processor. The memory can store multiple locations positioned along a network of streets in a geographic region. The hardware processor can assign some of the multiple locations to multiple territories associated with multiple vehicles by iteratively: determining whether an allocation threshold is met for the multiple territories and, in response to determining that the allocation threshold is unmet for at least two of the multiple territories, assigning one of the multiple locations not yet assigned to the multiple territories to one of the at least two of the multiple territories. In addition, the hardware processor can generate multiple routes connecting the multiple locations for the multiple vehicles so that each of the multiple routes connects the locations of the multiple locations assigned to one of the multiple territories.

Claims

1. A system for routing vehicles in a vehicle fleet, the system comprising:

a plurality of vehicles in the vehicle fleet,

a plurality of display devices comprising a vehicle-based display unit or a handheld mobile device, each display device of the plurality of display devices associated with a corresponding vehicle of the plurality of vehicles, and

a vehicle management system in communication with the plurality of display devices over a network, wherein, said vehicle management system comprises;

a memory device configured to store a plurality of locations positioned along a network of streets in a geographic region; and

a hardware processor in communication with the memory device, the hardware processor configured to;

assign at least some of the plurality of locations to a plurality of territories associated with the plurality of vehicles by iteratively;

determining whether one or more allocation thresholds is met for the plurality of territories based at least on the locations of the plurality of locations already assigned to the plurality of territories, each of the one or more allocation thresholds denoting a performance level for at least one of the plurality of territories, each of the plurality of territories having an associated reference location positioned in the geographic region, and

in response to determining that the one or more allocation thresholds is unmet for at least two of the plurality of territories, assigning one of the plurality of locations not yet assigned to the plurality of territories to one of the at least two of the plurality of territories based at least on a proximity of the one of the plurality of locations not yet assigned to the plurality of territories to (i) the reference location associated with the one of the at least two of the plurality of territories and (ii) the reference location associated with another of the at least two of the plurality of territories;

generate a plurality of routes connecting the plurality of locations on the network of streets for the plurality of vehicles so that each of the plurality of routes connects the locations of the plurality of locations assigned to one of the plurality of territories; and

output the plurality of routes and feedback to the plurality of display devices for presentation to a plurality of drivers of the plurality of vehicles, wherein the feedback includes a real-time suggested driving route modification based on traffic or weather conditions.

2. The system of claim 1, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether a first allocation threshold of the one or more allocation thresholds is met for a first territory of the plurality of territories, the first allocation threshold being met when a total value for the locations of the plurality of locations assigned to the first territory meets or exceeds the first allocation threshold.

3. The system of claim 2, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether the first allocation threshold is met for a second territory of the plurality of territories different from the first territory.

4. The system of claim 1, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether a first allocation threshold of the one or more allocation thresholds is met for a first territory of the plurality of territories, the first allocation threshold being met when a fuel usage for a first route connecting the locations of the plurality of locations assigned to the first territory meets or exceeds the first allocation threshold.

5. The system of claim 1, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether a first allocation threshold of the one or more allocation thresholds is met for a first territory of the plurality of territories, the first allocation threshold being met when a total time-on-site for the locations of the plurality of locations assigned to the first territory meets or exceeds the first allocation threshold.

6. The system of claim 5, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether a second allocation threshold of the one or more allocation thresholds is met for a second territory of the plurality of territories, the second allocation threshold being different from the first allocation threshold and being met when a total time-on-site for the locations of the plurality of locations assigned to the second territory meets or exceeds the second allocation threshold.

7. The system of claim 1, wherein the hardware processor is configured to determine whether the one or more allocation thresholds is met for the plurality of territories by determining whether a first allocation threshold of the one or more allocation thresholds is met for a first territory of the plurality of territories, the first allocation threshold being met when a total estimated driving time for a first route connecting the locations of the plurality of locations assigned to the first territory meets or exceeds the first allocation threshold.

8. The system of claim 1, wherein the hardware processor is configured to revise a position of the reference location associated with a first territory of the plurality of territories subsequent to the hardware processor determining that a first allocation threshold of the one or more allocation thresholds is unmet for the first territory.

9. The system of claim 8, wherein the hardware processor is configured to revise the position of the reference location associated with the first territory based at least on the locations of the plurality of locations assigned to the first territory.

10. The system of claim 1, wherein the hardware processor is configured to:

assign one or more of the plurality of locations to the plurality of territories based at least on outlier detection; and

reassign one or more of the locations of the plurality of locations assigned to a first territory of the plurality of territories to a second territory of the plurality of territories different from the first territory to even out one or more criteria for the first territory and the second territory.

11. The system of claim 10, wherein the one or more criteria comprise a total amount of return for each of the first territory and the second territory.

12. The system of claim 10, wherein the one or more criteria comprise a total time-on-site for each of the first territory and the second territory.

13. The system of claim 1, wherein the hardware processor is configured to determine a number of territories to include in the plurality of territories, the number of territories being a minimum number of territories to use to service a set of stops where each of the plurality of territories is associated with a different vehicle of the plurality of vehicles.

14. The system of claim 1, wherein at least some of the plurality of territories overlap one another.

15. A method for routing vehicles in a vehicle fleet, the method comprising:

under control of a hardware processor of a vehicle management system, the vehicle management system configured to communicate with a plurality of display devices, each display device of the plurality of display devices associated with a corresponding vehicle of a plurality of vehicles;

assigning one or more locations of a plurality of locations not yet assigned to a plurality of territories to one of a first territory of the plurality of territories and a second territory of the plurality of territories based at least on a proximity of the one or more locations not yet assigned to the plurality of territories to a first reference location associated with the first territory and a second reference location associated with a second territory;

in response to assigning the one or more locations not yet assigned to the plurality of territories to the first territory, determining whether a first allocation threshold for the first territory is met based at least on the locations of the plurality of locations assigned to the first territory, the first allocation threshold denoting a first performance level for the first territory;

in response to determining that the first allocation threshold is unmet, assign one or more first additional locations of the plurality of locations not yet assigned to the plurality of territories to the first territory based at least on a proximity of the one or more first additional locations not yet assigned to the plurality of territories to the first reference location;

in response to assigning the one or more locations not yet assigned to the plurality of territories to the second territory, determining whether a second allocation threshold for the second territory is met based at least on the locations of the plurality of locations assigned to the second territory, the second allocation threshold denoting a second performance level for the second territory;

in response to determining that the second allocation threshold is unmet, assigning one or more second additional locations of the plurality of locations not yet assigned to the plurality of territories to the second territory based at least on a proximity of the one or more second additional locations not yet assigned to the plurality of territories to the second reference location;

generating a first route connecting the locations of the plurality of locations assigned to the first territory on a network of streets in a geographic region;

generating a second route connecting the locations of the plurality of locations assigned to the second territory on the network of streets;

outputting the first route to a first display device of the plurality of display devices for presentation to a first driver of a first vehicle of the plurality of vehicles;

outputting the second route to a second display device of the plurality of display devices for presentation to a second driver of a second vehicle of the plurality of vehicles, the second display device different from the first display device; and

outputting feedback to the first and the second display devices for presentation to the first and second drivers, respectively, wherein the feedback includes a real-time suggested driving route modification based on traffic or weather conditions.

16. The method of claim 15, wherein the first allocation threshold is met when a total value for the locations of the plurality of locations assigned to the first territory meets or exceeds the first allocation threshold.

17. The method of claim 16, wherein the first allocation threshold is the same as the second allocation threshold.

18. The method of claim 15, further comprising prior to said assigning the one or more first additional locations to the first territory, revising a position of the first reference location based at least on the locations of the plurality of locations assigned to the first territory.

19. The method of claim 15, further comprising reassigning one or more of the locations of the plurality of locations assigned to the first territory to the second territory to even out one or more criteria for the first territory and the second territory.

20. The method of claim 15, further comprising:

displaying the first route on the first display device to the first driver of the first vehicle; and

displaying the second route on the second display device to the second driver of the second vehicle.