Method and system for fleet navigation, dispatching and multi-vehicle, multi-destination routing

• US 8,775,059 B2
• Filed: 10/25/2012
• Issued: 07/08/2014
• Est. Priority Date: 10/26/2011
• Status: Expired

• Current Assignee: Rightthereware Llc
• Original Assignee: Right There Ware LLC
• Inventors: Heed, John Culver, Heed, Thomas Paul
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): MAZZARA, ANNE MARIE
• Application Number:
  US13/660,977
• Publication Number:
  US 20130110385A1
• Time in Patent Office: 621 Days
• Field of Search: 701/117
• US Class Current: 701/117
• 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/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A system and method for multiple vehicles to be dispatched and routed to multiple destinations, with or without constraints, containing a software core, which uses bounded geographic regions (“BGRs”) and Node Pairs to explicitly optimize, in two dimensions, for user desired dependent variables, by analyzing variance due to standard and user-defined independent variables. The invention stores Node Pair data, and can use error function, feedback, and ANOVA/MANOVA to create a tightly convergent dispatching and navigation solution.

Claims

1. A method and system of navigation guidance, containing, at a minimum, an end-user device with means for inputting destinations and receiving guidance or routing;

a map database, containing roads and, optionally, points of interest;

a device and method for determining vehicle position;

a server or other assemblage of memory and processing elements;

a means for communicating between the end-user device and the server;

a node pair look-up table (NPLUT) database, containing explicit solutions between each potential entry node and each potential exit node of every bounded geographic regions (BGR) of interest to the end user; and

a navigation software core, resident on the server, having the capability to create BGRs of such a size that explicit navigation solutions are possible within the boundaries of the BGR, to identify Node Pairs for each BGR which might be part of a potential solution, to access the NPLUT to get solutions for each Node Pair, and optimize a navigation solution, that uses the Node Pair combinations between the origin and destination, based on the dependent variable provided by the end user and the independent variables which are inherently part of a solution database.

2. The invention in 1, in which the system solves for multi-vehicle-to-multi-destination problems.

3. The invention in 2, in which the system presents Routes to each vehicle.

4. The invention in 2, in which the system tracks each vehicle'"'"'s progress along the Route.

5. The invention in 2, in which the system allows Dispatching for Ride- sharing or Load-sharing fleets.

6. The invention in 2, in which the system will re-route one or more vehicles when a single vehicle'"'"'s progress along its route diverges from the predicted value by more than a user-defined amount.

7. The invention in 2, in which the system solves for the multi-vehicle-to-multi-destination problem, using user-defined Constraints.

8. The invention in 2, in which the software contains an error function calculator and a feedback routine to correct dependent variable values stored in the NPLUT database.

9. The invention in 2, in which each end-user'"'"'s actual value for each Node Pair solution for dependent variables, including time, distance, fuel usage, cost, and any user defined dependent variables, as well as independent variables, are communicated to and stored in NPLUT, either while or after the end-user arrives at the destination.

10. The invention in 2, in which, for each dependent Node Pair value in the NPLUT, associated independent variable factors are captured and stored, both variable and attribute, including, but not limited to, time of day, date, day of the week, temperature, construction, precipitation, driver'"'"'s age, driver'"'"'s profession, driver'"'"'s gender, vehicle type, vehicle age, vehicle mileage, and special event, which can be used to create ANOVA and MANOVA calculations of the dependent variables stored in the NPLUT, in order to give more accurate estimates during future navigation.

11. The invention in 10, in which the NPLUT database is compressed by storing only the necessary ANOVA or MANOVA sums and products from prior navigation iterations, and deleting the underlying data off of which the sums and products are calculated.

12. The invention in 2, in which each end-user'"'"'s device memory only stores detail from Active BGRs.

13. The invention in 2, in which the communication with the server is made via a wireless or satellite connection to a plurality of vehicles, mobile telephones, mobile data terminals, or remote electronic devices.

14. The invention in 2, in which the server can also collect data from other data sources, including, but not limited to, NHTSA traffic sensor information, police report, local traffic reports, and construction reports, for inclusion in the NPLUT as either variable or attribute data associated with a Node Pair.

15. The invention in 2, in which the system is used to monitor and route traffic in congested urban areas.