Real-time computation of vehicle service routes

• US 9,958,272 B2
• Filed: 03/13/2013
• Issued: 05/01/2018
• Est. Priority Date: 08/10/2012
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: Morris, IV, Arthur Newth, Mason, Ralph James
• Primary Examiner(s): Khatib, Rami
• Assistant Examiner(s): Wiltey, Nicholas K
• Application Number:
  US13/800,719
• Publication Number:
  US 20140046585A1
• Time in Patent Office: 1,875 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/205 Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental

Abstract

A route scheduling system for a vehicle or fleet of vehicles can recalculate a scheduled route based on input received after the formulation and/or dispatch of the initial route. The additional inputs can be used for recalculation and changes in route selection, which may include a variety of inputs, such as weather conditions, traffic conditions, customer needs, vehicle inventory, and emergency situations. The recalculation of the routes can allow for route selection to be performed in real-time in order for fleets and vehicles to optimize the allocation of resources.

Claims

1. A method for dynamically updating a vehicle route, using a system comprising a vehicle management system (VMS) comprising digital logic circuitry, a memory storing executable instructions, a communication module, a vehicle in a fleet of vehicles comprising an in-vehicle device with a vehicle computer, a sensing device, a Global Positioning System (GPS) and a display, the digital logic circuitry programmed with the executable instructions that configure the digital logic circuity to perform the method comprising:

identifying a first vehicle from a fleet of vehicles;

calculating a first route having a first route constraint based at least partly on a first set of data, wherein the first route constraint is based, at least in part, on routing algorithm constraints associated with operation of the first vehicle on the first route, wherein the routing algorithm constraints comprise vehicle maintenance, time of day, break time, transit time, road closure/restrictions, and hazardous weather, wherein a weight indicative of importance is assigned in real-time to one or more of the routing algorithm constraints;

providing over a network, to an in-vehicle device of the first vehicle, an electronic representation of the first route, the electronic representation presented using a display device and/or audio device of the first vehicle to a driver of the first vehicle;

receiving over the network, information of a disruptive event captured by a sensing device in the first vehicle configured to sense the disruptive event subsequent to receiving an indication that the first vehicle is traversing a portion of the first route, wherein the indication is based, at least in part, on Global Positioning System (GPS) data associated with a real-time position of the first vehicle;

determining whether the disruptive event prevents the first vehicle from performing a scheduled task;

based on the determination that the first vehicle is prevented from performing the scheduled task,

calculating plural sets of feasible alternative routes in real-time to perform the scheduled task using available vehicles in the fleet of vehicles taking into account characteristics and actual positions of the available vehicles;

selecting a first set of alternative routes from the plural sets of feasible alternative routes that satisfy a series of computer-based thresholds, the series of computer-based thresholds is programmatically selected based on information comprising energy use, distance, schedule specific constraint, battery capacity, amount of fuel, customer needs, and vehicle location that are updated at intervals in real-time over the network from the available vehicles in the fleet of vehicles, wherein the first set of alternative routes provides an optimal set of alternative routes to perform the scheduled task by at least one of the available vehicles; and

based on the selecting of the first set of alternative routes associated with the at least one of the available vehicles that satisfies the series of computer-based thresholds and reception of an indication of an approval of the first set of alternative routes, replacing at least a portion of the first route with a portion of the first set of alternative routes and outputting an electronic representation of the first set of alternative routes for presentation to a driver of the at least one of the available vehicles.

2. The method of claim 1 further comprising requesting administrator approval for replacing at least a portion of the first route with the portion of the first set of alternative routes in response to the selection of the first set of alternative routes.

3. The method of claim 1, wherein the plural sets of alternative routes are calculated based on one or more of the following:

a time component, a distance component, and an energy usage component.

4. The method of claim 1, wherein the first set of alternative routes is configured for two of the available vehicles.

5. The method of claim 4 further comprising transmitting the first set of alternative routes to all of the available vehicles in the fleet in response to determining that the first vehicle can no longer service the first route.

6. The method of claim 1, wherein the approval of the first set of alternative routes by personnel comprises approval by a fleet manager.

7. A system for dynamically updating vehicle routes, the system comprising:

a vehicle in a fleet of vehicles comprising an in-vehicle device, digital logic circuitry, a memory storing executable instructions, a Global Positioning System (GPS), a sensing device, a display device and an audio device;

a data repository configured to store data used to calculate vehicle routes;

a vehicle management system comprising computer hardware, and a communication module configured to transmit and receive data over a network, the vehicle management system configured to at least;

calculate an initial vehicle route having a plurality of route characteristics based on the data stored in the data repository, wherein at least one route characteristic is a constraint associated with operation of a vehicle on the initial vehicle route;

provide data representing the initial vehicle route to a navigation device associated with the vehicle or a driver;

subsequent to receiving an indication that the vehicle or the driver is traversing a portion of the initial vehicle route, receive information of a disruptive event captured by the sensing device in the vehicle affecting the initial vehicle route, wherein the indication is based, at least in part, on Global Positioning System (GPS) data associated with a real-time position of the vehicle;

determine whether the disruptive event prevents the vehicle from performing a scheduled task;

based on the determination that the vehicle is prevented from performing the scheduled task, calculate plural sets of feasible alternative routes to perform the scheduled task using available vehicles in the fleet of vehicles taking into account characteristics and actual positions of the available vehicles;

select a first set of alternative routes from the plural sets of feasible alternative routes that satisfy a series of thresholds associated with energy use, distance, schedule specific constraint, battery capacity, amount of fuel, customer needs, and vehicle location, wherein the first set of alternative routes is an optimal set of alternative routes to perform the scheduled task by at least one of the available vehicles;

based on the selection of the first set of alternative routes associated with the at least one of the available vehicles that satisfies the series of thresholds and reception of an indication of an approval of the first set of alternative routes, replace at least a portion of the initial vehicle route with at least one portion of the first set of alternative routes; and

transmit over the network to an in-vehicle device in the at least one of the available vehicles, an electronic representation of the first set of the alternative routes, the electronic representation presented using the display device and/or audio device of the at least one of the available vehicles.

8. The system of claim 7, wherein the vehicle management system is further configured to request approval for the first set of alternative routes prior to transmitting, over the network to the in-vehicle device of the at least one of the available vehicles, the electronic representation of the first set of alternative routes.

9. The system of claim 7, wherein the vehicle management system is further configured to calculate the initial vehicle route for the vehicle and to calculate the first set of alternative routes for the at least one of the available vehicles, wherein the vehicle and the at least one of the available vehicles are different types of vehicles.

10. The system of claim 7, wherein a navigation device in the in-vehicle device comprises Global Positioning System (GPS) functionality.

11. Non-transitory physical computer storage comprising instructions stored thereon that, when executed in one or more processors, cause the one or more processors to implement operations for dynamically updating vehicle routes, the operations comprising:

identifying a vehicle in a fleet of vehicles;

calculating an initial route having a first constraint, wherein the first constraint is based, at least in part, on at least one constraint associated with operation of the vehicle on the initial route;

providing data representing the initial route to a navigation device associated with the vehicle;

receiving information of a disruptive event that impacts the initial route subsequent to receiving an indication that the vehicle is traveling a portion of the initial route, wherein the indication is based, at least in part, on Global Positioning System (GPS) data associated with a real-time position of the vehicle;

determining whether the disruptive event prevents the vehicle from performing a scheduled task;

based on the determination that the vehicle is prevented from performing the scheduled task, calculating plural sets of feasible alternative routes to perform the scheduled task using available vehicles in the fleet of vehicles taking into account characteristics and real-time positions of the available vehicles;

selecting a first set of alternative routes from the plural sets of feasible alternative routes that satisfy a series of thresholds associated with energy use, distance, schedule specific constraint, battery capacity, amount of fuel, customer needs, vehicle location and traffic, wherein the first set of alternative routes provides an optimal set of alternative routes to perform the schedules task by at least one of the available vehicles;

based on the selecting of the first set of alternative routes associated with the at least one of the available vehicles that satisfies the series of thresholds and reception of an indication of an approval of the first set of alternative routes, transmitting data representing the first set of alternative routes to a navigation device of the at least one of the available vehicles.

12. The non-transitory physical computer storage of claim 11, wherein the operations further comprise replacing the initial route with the first set of alternative routes.

13. The non-transitory physical computer storage of claim 11, wherein the operations further comprise requesting approval for the first set of alternative routes prior to transmitting data representing the first set of alternative routes to the navigation device of the at least one of the available vehicles.

14. The non-transitory physical computer storage of claim 11, wherein the operations further comprise calculating the initial route for the vehicle and calculating the first set of alternative routes for the at least one of the available vehicles, wherein the vehicle and the at least one of the available vehicles are different types of vehicles.

15. The non-transitory physical computer storage of claim 11, wherein the information of the disruptive event comprises information related to one or more of the following:

weather conditions, traffic conditions, customer needs, vehicle inventory, and an emergency situation.

16. A method for dynamically updating vehicle routes, the method comprising:

receiving information related to an initial route of a vehicle in a fleet of vehicles subsequent to receiving an indication that the vehicle traveling is a portion of the initial route, wherein the information related to the initial route comprises at least one constraint characteristic associated with operation of the vehicle on the initial route, wherein the indication is based, at least in part, on Global Positioning System (GPS) data associated with a real-time position of the vehicle;

receiving information related to a disruptive event,

determining whether the disruptive event prevents the vehicle from performing a scheduled task;

based on the determination that the vehicle is prevented from performing the scheduled task, calculating plural sets of feasible alternative routes to perform the scheduled task using available vehicles in the fleet of vehicles taking into account characteristics and actual positions of the available vehicles;

selecting a first set of alternative routes from the plural sets of feasible alternative routes that satisfies a series of thresholds associated with energy use, distance, schedule specific constraint, battery capacity, amount of fuel, customer needs, and vehicle location, wherein the first set of alternative routes provides an optimal set of alternative routes to perform the scheduled task using at least one of the available vehicles; and

based on the selecting of the first set of alternative routes associated with the at least one of the available vehicles that satisfies the series of thresholds and reception of an indication of an approval of the first set of alternative routes, transmitting the first set of alternative routes for presentation to a driver of the at least one of the available vehicles.

17. The method of claim 16, wherein the information related to the initial route of the vehicle comprises information regarding a changed preference of a user associated with the initial route.

18. The method of claim 16, wherein the information related to the initial route of the vehicle comprises information regarding one or more new stops to be added to or changed for the initial route.

19. The method of claim 16, wherein the one or more characteristics of the initial route and the first set of alternative routes comprise one or more of the following:

travel time and energy use.