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

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.

We claim: 
     
       1. A method and system of navigation guidance, containing, at a minimum, an end-user device with means for comprising the steps of
 inputting destinations and a destination and dependent variable into an end-user device; 
 communicating the destination and dependent variable from the end-user device to an assemblage of non-transitory, computer-readable memory, processing elements, and associated circuitry, referred to as a server; 
 receiving from the server to the end-user device routing guidance or routing from an origin to the destination; 
 using 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; 
 geo-locating the end-user device using a global-positioning system (“GPS”) chip-set capable of transmitting and receiving location data; and 
 using a computer-readable instruction set, called the navigation software core, resident on the non-transitory, computer-readable memory of the server, by
 dividing a geographic region of the map database containing the origin and destination into a plurality of bounded geographic regions (“BGRs”), each BGR being sized so that an explicit navigation solution is possible within the boundaries of the BGR, each BGR having at least two nodes, each node being formed by an intersection of a road in the map database with a boundary of a BGR, wherein a BGR can be entered at any node and exited at any other node, 
 generating a node pair look-up table (NPLUT) database, containing, as dependent variables, previously stored explicit navigation routing solutions between each potential entry node and each potential exit node of every bounded geographic regions (BGR) of interest to the end user based on the origin and the destination, actual node-to-node transit times, and data describing at least the day of the week, time of day, and weather for each previous solution (“independent variables”); 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 identifying, in response to the destination and dependent variable, Node Pairs for each BGR which might be part of a potential solution, 
 to accessaccessing the NPLUT to get solutions for each Node Pair, and using ANOVA and MANOVA techniques to 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 solutionof the NPLUT database. 
 
 
     
     
       2. The invention method of navigation guidance in claim  1 , in which the system solves further comprising the step of solving for multi-vehicle-to-multi-destination problems multiple vehicles going to multiple destinations. 
     
     
       3. The invention method of navigation guidance in claim  2 , in which the system presents further comprising the step of Routes to each vehicle. 
     
     
       4. The invention method of navigation guidance in claim  2 , in which the system tracks further comprising the step of tracking each vehicle's progress along the Route. 
     
     
       5. The invention method of navigation guidance in claim  2 , in which the system allows further comprising the step of allowing Dispatching for Ride- sharing or Load-sharing fleets. 
     
     
       6. The invention method of navigation guidance in claim  2 , in which the system will re-route further comprising the step of re-routing one or more vehicles when a single vehicle's progress along its route diverges from the predicted value by more than a user-defined an amount derived from a user-defined service standard. 
     
     
       7. The invention method of navigation guidance in claim  2 , in which the system solves further comprising the step of solving for the multi-vehicle-to-multi-destination problem multiple vehicles going to multiple destinations, using user-defined Constraints. 
     
     
       8. The invention method of navigation guidance in claim  2 , in which the software contains further comprising the step of using an error function calculator and a feedback routine to correct the dependent variable values stored in the NPLUT database. 
     
     
       9. The invention method of navigation guidance in claim  2 , in which further comprising the steps of communicating with the NPLUT and storing each end-user's actual value for each Node Pair solution for the 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 the NPLUT, either while or after the end-user arrives at the destination. 
     
     
       10. The invention method of navigation guidance in claim  2 , in which comprising the further steps of capturing and storing, for each dependent Node Pair value in the NPLUT, at least one associated independent variable factors are captured and stored, both variable and attribute, including, but not limited to, from the list of 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: and creating 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 method of navigation guidance in claim  10 , in which further comprising the steps of updating the NPLUT database is compressed by storing only the necessary ANOVA or MANOVA sums and products sum of squares from prior each navigation iterations, and deleting the underlying data off of which the sums and products are calculated iteration. 
     
     
       12. The invention method of navigation guidance in claim  2 , in which further comprising the step of storing on each end-user's device memory only stores the detail from Active BGRs. 
     
     
       13. The invention method of navigation guidance in claim  2 , in which wherein the communication with the server is made via a least on of wireless or and satellite connection to a plurality of devices from the list of vehicles, mobile telephones, mobile data terminals, or and remote electronic devices. 
     
     
       14. The invention method of navigation guidance in claim  2 , in which the server can also collect further comprising the steps of collecting data from other data sources, including, but not limited to, at least one of which is NHTSA traffic sensor information, police report, local traffic reports, and construction reports,; communicating the data to the server; and associating the data with a Node Pair for inclusion in the NPLUT as either variable or attribute data associated with a Node Pair. 
     
     
       15. The invention method of navigation guidance in claim  2 , in which the system is used to monitor and route further comprising the step of monitoring and routing traffic in congested urban areas. 
     
     
       16. A system of navigation guidance comprising an end-user device capable of inputting destinations and at least one dependent variable, and receiving routing guidance;
 an assemblage of non-transitory, computer-readable memory, processing elements, and associated circuitry referred to as a server and a computer-readable instruction set called the navigation software core, resident on the non-transitory computer-readable memory of the server;   a map database containing roads, stored within the non-transitory computer-readable memory elements of the server;   a global-positioning system (“GPS”) chip-set, within the end-user device, capable of transmitting and receiving location data;   a means for communicating between the end-user device and the server using a wireless transceiver and a data communication network;   a node pair look-up table (NPLUT) database;   wherein the navigation software core, when executed, is capable of determining the position of the end-user device from the GPS location data;   wherein the navigation software core, when executed, causes the system to divide a portion of the map database, containing the destination and the origin into a plurality of bounded geographic regions (BGRs) of such a size that explicit navigation solutions are possible within the boundaries of the BGR, each BGR having at least two nodes and each node being formed by an intersection of a road with a boundary of the BGR, wherein a BGR can be entered at any node and exited at any other node;   wherein the NPLUT database contains, as dependent variables, previously stored explicit navigation routing solutions between each potential entry node and each potential exit node of every BGR of interest based on the origin and destination, actual node-to-node transit times, and data describing at least the day of the week, time of day, and weather for each previous solution (“independent variables”);   wherein the navigation software core, when executed, further causes the system, in response to input of the destination and the at least one dependent variable, to identify node pairs between the origin and the destination, and provide routing guidance from the origin to the destination, performing an ANOVA, selecting the optimum sequence of BGR entry nodes and exit nodes based upon the ANOVA of previously stored explicit navigation solutions of the NPLUT and the dependent and independent variable.   
     
     
       17. The system of navigation guidance in claim 16, wherein the system solves for multiple vehicles going to multiple destinations. 
     
     
       18. The system of navigation guidance in claim 17, in which the system presents Routes to each vehicle. 
     
     
       19. The system of navigation guidance in claim 17, in which the system tracks each vehicle's progress along the Route. 
     
     
       20. The system of navigation guidance in claim 17, in which the system allows Dispatching for Ride-sharing or Load-sharing fleets. 
     
     
       21. The system of navigation guidance in claim 17, 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 an amount derived from a user-defined service standard. 
     
     
       22. The system of navigation guidance in claim 17, in which the system solves for multiple vehicles going to multiple destinations, using user-defined Constraints. 
     
     
       23. The system of navigation guidance in claim 17, in which the software method contains an error function calculator and a feedback routine to correct the dependent variable values stored in the NPLUT database. 
     
     
       24. The system of navigation guidance in claim 17, in which each end-user's actual value for each Node Pair solution for the 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. 
     
     
       25. The system of navigation guidance in claim 17, 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. 
     
     
       26. The system of navigation guidance in claim 25, in which the NPLUT database is updated by storing only the ANOVA or MANOVA sums and sum of squares from each navigation iteration. 
     
     
       27. The system of navigation guidance in claim 17, in which each end-user's device memory only stores detail from Active BGRs. 
     
     
       28. The system of navigation guidance in claim 17, 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. 
     
     
       29. The system of navigation guidance in claim 17, 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. 
     
     
       30. The system of navigation guidance in claim 17, in which the system is used to monitor and route traffic in congested urban areas.