Vehicle fleet routing system

• US 9,037,406 B2
• Filed: 10/09/2012
• Issued: 05/19/2015
• Est. Priority Date: 10/07/2011
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: Mason, Ralph James, Hidayat, Ray, Morris, Arthur Newth, Beavon, Jeremy, Russell, Michael, Dunlop, Mark
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): Torchinsky, Edward
• Application Number:
  US13/648,243
• Publication Number:
  US 20130096815A1
• Time in Patent Office: 952 Days
• US Class Current: 701/482
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/123 indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, tramstransmission of navigation instructions to vehicles G08G1/0968
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

Vehicle management systems and associated processes can incorporate calculations for categorizing locations on a map as within one or more territories based on proximity of the location to predetermined points with in the territories. The systems and processes can also incorporate techniques for estimating total distance required to traverse a route reaching all of a set of predetermined stops, without using a routing algorithm that would provide a usable route for a vehicle, but is less computationally demanding. The systems and processes can also include techniques for incorporating legs of a route that extend through a temporary exclusion zone.

Claims

1. A system for generating a user interface for a manager of vehicles in a vehicle fleet and controlling routing of the vehicles between stop locations in a geographic region, the user interface providing functionality for the manager to interactively assign and move locations of individual points on a graphical road map, the individual points defining territories around the individual points that are serviceable by the vehicles, the territories being depicted on the graphical road map as shadows that are darker closer to the individual points and paler farther from the individual points according to increasing driving time from the individual points, the system comprising:

a vehicle management system comprising computer hardware, the vehicle management system configured to;

receive, from a user device, selection of an optional mode of operation corresponding to a technique for generating territories associated with respective vehicles in a vehicle fleet;

electronically generate a user interface for presentation by the user device to a user of the user device, the user interface comprising functionality, when operating in the optional mode of operation, to depict a plurality of predetermined stop locations for at least first and second vehicles of the vehicle fleet on a graphical road map, for the user to specify a first user identification of locations of first and second points on the graphical road map, and for the user to specify a second user indication to move the location of the first point to a different location;

receive, from the user device, the first user identification of the locations of the first and second points;

determine a first plurality of concentric areas on the graphical road map corresponding to increasing driving time from the location of the first point and a second plurality of concentric areas on the graphical road map corresponding to increasing driving time from the location of the second point;

wherein the user interface further comprises functionality to;

depict a first territory of the territories surrounding the location of the first point as a first shadow of a first color on the graphical road map and a second territory of the territories surrounding the location of the second point as a second shadow of a second color different from the first color on the graphical road map, the first shadow being darker in at least one of the first plurality of concentric areas closer to the location of the first point and paler in at least one of the first plurality of concentric areas farther away from the location of the first point, the second shadow being darker in at least one of the second plurality of concentric areas closer to the location of the second point and paler in at least one of the second plurality of concentric areas farther away from the location of the second point, and

depict the locations of the plurality of predetermined stop locations classified as within the first territory in the first color and the locations of the plurality of predetermined stop locations classified as within the second territory in the second color on the graphical road map,

wherein in response to receiving the second user indication to move the first point to the different location, the vehicle management system is configured to;

determine a third plurality of concentric areas on the graphical road map corresponding to increasing driving time from the different location, and

cause the user interface to depict the first territory as surrounding the different location as a third shadow of the first color on the graphical road map, the third shadow being darker in at least one of the third plurality of concentric areas closer to the different location and paler in at least one of the third plurality of concentric areas farther away from the different location.

2. The system of claim 1, wherein the user interface further comprises functionality for the user to specify a third user indication to assign the first territory to the first vehicle, and the vehicle management system is further configured to assign the first territory to the first vehicle based at least on the third user indication to assign the first territory to the first vehicle.

3. The system of claim 1, wherein the user interface further comprises functionality to depict at least some of the plurality of predetermined stop locations between the locations of the first and second points on the graphical road map in a third color different from the first and second colors, the third color being a color resulting from blending of the first and second colors.

4. The system of claim 1, wherein the vehicle management system is further configured to:

assign a cost to each of the plurality of predetermined stop locations based at least on a proximity of each of the plurality of predetermined stop locations to the locations of the first point; and

classify the at least some of the plurality of predetermined stop locations as within one of the first and second territories further based at least on the assigned costs of the at least some of the plurality of predetermined stop locations.

5. The system of claim 4, wherein the vehicle management system is further configured to classify at least some of the plurality of predetermined stop locations as within one of the first and second territories so that a total of the assigned costs of the locations of the plurality of predetermined stop locations classified as within the first territory are about the same as a total of the assigned costs of the locations of the plurality of predetermined stop locations classified as within the second territory.

6. The system of claim 4, wherein the vehicle management system is configured to generate the first and second routes further based at least on the assigned costs of the locations of the plurality of predetermined stop locations classified as within the first and second territories.

7. The system of claim 4, wherein the vehicle management system is further configured to assign the cost to each of the plurality of predetermined stop locations according to a non-linear function depending at least on the proximity of each of the plurality of predetermined stop locations to the location of the first point.

8. The system of claim 7, wherein the non-linear function further depends at least on vehicle drive times from each of the plurality of predetermined stop locations to the location of the first point.

9. The system of claim 8, wherein the vehicle management system is configured to generate the first and second routes further based at least on the assigned costs of the locations of the plurality of predetermined stop locations classified as within the first and second territories.

10. A system for providing a user interface for a manager of vehicles in a vehicle fleet and assisting in routing of the vehicles between stop locations in a geographic region, the user interface providing functionality for the manager to interactively assign and move locations of individual points on a graphical road map, the individual points defining territories around the individual points that are serviceable by the vehicles, the territories being depicted on the graphical road map as shadows that are darker closer to the individual points and paler farther from the individual points, the system comprising:

a user device comprising computer hardware configured to;

display a user interface received from a vehicle management system, the user interface comprising functionality for;

depicting on a graphical road map, a plurality of predetermined stop locations for at least first and second vehicles of a vehicle fleet,

a user to specify a first user identification of a location of a first point on the graphical road map as a center of a first territory and specify a location of a second point on the graphical road map as a center of a second territory, the first territory being associated with the first vehicle and the second territory being associated with the second vehicle,

depicting the first territory associated with the first point as a first plurality of concentric shadows of a first color on the graphical road map and the second territory associated with the second point as a second plurality of concentric shadows of a second color different from the first color on the graphical road map, at least one of the first plurality of concentric shadows being darker near the location of the first point and at least another of the first plurality of concentric shadows which is farther away from the location of the first point being paler than the at least one of the first plurality of concentric shadows, at least one of the second plurality of concentric shadows being darker near the location of the second point and at least another of the second plurality of concentric shadows which is farther away from the location of the second point being paler than the at least one of the second plurality of concentric shadows,

depicting a first subset of the plurality of predetermined stop locations on the graphical road map which are proximate to the location of the first point according to increasing drive time from the location of the first point in the first color and a second subset of the plurality of predetermined stop locations on the graphical road map which are proximate to the location of the second point according to increasing drive time from the location of the second point in the second color,

depicting a first route on the graphical road map, the first route including the first subset of the plurality of predetermined stop locations depicted in the first color,

depicting a second route on the graphical road map, the second route including the second subset of plurality of predetermined stop locations depicted in the second color,

the user to specify a second user indication to move the first point to a different location, and

after receiving the second user indication to move the first point to the different location, depicting the different location of the first point on the graphical road map as the center of the first territory and the first territory as a third plurality of concentric shadows of the first color on the graphical road map, at least one of the third plurality of concentric shadows being darker near the different location and at least another of the third plurality of concentric shadows which is farther away from the different location being paler than the at least one of the third plurality of concentric shadows; and

transmit, to the vehicle management system, the first user identification of the first and second points and the second user indication to move the first point to the different location.

11. The system of claim 10, wherein the user interface further comprises functionality for the user to specify a third user indication to assign the first territory to the first vehicle, and the user device is further configured to transmit, to the vehicle management system, the third user indication to assign the first territory to the first vehicle.

12. The system of claim 10, wherein a greater paleness of the first plurality of concentric shadows indicates greater driving time from the location of the first point, and a greater paleness of the second plurality of concentric shadows indicates greater driving time from the location of the second point.

13. The system of claim 10, wherein the user interface further comprises functionality to:

depict a third subset of the plurality of predetermined stop locations on the graphical road map which are proximate to the different location of the first point according to increasing drive time from the different location of the first point in the first color, and

depict a third route on the graphical road map, the third route including the third subset of the plurality of predetermined stop locations depicted in the first color.

14. The system of claim 10, wherein the user interface further comprises functionality for depicting at least some of the locations of the plurality of predetermined stop locations between the first and second points on the graphical road map in a third color different from the first and second colors.

15. The system of claim 14, wherein the third color is a color resulting from blending the first and second colors.