Method and system for navigation using bounded geographic regions

Abstract

A navigation system 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 navigation solution.

Claims

1. A method .[.and system.]. of navigation guidance.[., containing, at a minimum: an end-user device with means for.]. .Iadd.using bounded geographic regions (BGRs) comprising the steps of .Iaddend.inputting destinations and receiving .Iadd.routing .Iaddend.guidance .[.or routing.]. .Iadd.with an end-user device.Iaddend.; .Iadd.geo-locating the end-user device using a global-positioning system (GPS) chip-set capable of transmitting and receiving location data; identifying the position of the end-user device with reference to .Iaddend.a map database, containing roads and, optionally, points of interest (POIs); .[.a device and method for determining vehicle position;.]. .[.a server or other.]. .Iadd.using .Iaddend.an assemblage of memory .[.and.]..Iadd., .Iaddend.processing elements.[.;.]..Iadd., 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 elements of the server,.Iaddend. .[.a means for.]. communicating between the end-user device and the server; .Iadd.and accessing .Iaddend.a Node Pair Look-up Table (NPLUT) database which is initially, either partially or fully, loaded with explicit solutions for each Node Pair, and which contains explicit solutions between each potential entry node and each potential exit node of every .[.Bounded Geographic Region (BGR).]. .Iadd.BGR .Iaddend.of interest to the end user.Iadd., each BGR being an area bounded by a defined perimeter, all areas of interest to the end user are included in a BGR; and a node is the point at which a road segment intersects with the defined perimeter of a BGR.Iaddend.; .Iadd.each BGR having at least two nodes, wherein a BGR can be entered at any node and exited at any other node, and a Node Pair is an entry node to and exit node from a BGR.Iaddend. and .[.a.]. .Iadd.using the .Iaddend.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, and to optimize a navigation solution based on .[.the.]. .Iadd.at least one .Iaddend.dependent variable provided by the user and .[.the.]. independent variables .[.which are inherently part of a solution database.]. .Iadd.in the NPLUT.Iaddend..

2. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of calculating with .Iaddend.the .Iadd.navigation .Iaddend.software .[.contains.]. .Iadd.core .Iaddend.an error function .[.calculator.]. and .Iadd.performing .Iaddend.a feedback routine to correct dependent variable values stored in the NPLUT database.

3. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of communicating to and storing in the NPLUT .Iaddend.each end-user's actual value for each Node Pair solution for dependent variables, including.[., but not limited to,.]. .Iadd.at least one of .Iaddend.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.

4. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of capturing and storing in the NPLUT .Iaddend.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.]. .Iadd.analysis of variance (ANOVA) .Iaddend.and .[.MANOVA.]. .Iadd.multivariate analysis of variance (MANOVA) .Iaddend.calculations of the dependent variables stored in the NPLUT, in order to give more accurate estimates during future navigation.

5. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 4, .[.in which.]. .Iadd.further comprising the step of compressing .Iaddend.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.

6. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of creating .Iaddend.the BGRs .[.are created.]. by Virtual Tessellation, by inscribing the Earth in a tessellated cube or partitioned cube, and projecting the tessellation or partition from the cube onto the surface of the Earth.

7. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 6, .[.in which.]. .Iadd.further comprising the step of varying .Iaddend.the tessellation pattern on the cube.Iadd., which .Iaddend.is comprised of squares and rectangles, .Iadd.by reducing geometrically .Iaddend.the area of .[.which is reduced geometrically as.]. the rectangles .[.vary.]. .Iadd.with the rectangles distance .Iaddend.from the center of the cube face, and .Iadd.by increasing .Iaddend.the aspect ratio .[.of which increases with.]. .Iadd.of the rectangles with the rectangles .Iaddend.distance from the center of the cube face.

8. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of calculating .Iaddend.solutions for each Node Pair .[.are calculated.]. using different processors in a multi-processor configuration.

9. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which.]. .Iadd.further comprising the step of calculating, iteratively, with .Iaddend.the navigation software core .[.will iteratively calculate.]..Iadd., .Iaddend.routes using more and more BGRs, until the solutions become sufficiently divergent, or until the last BGR layer exceeds, orthogonally to a line from the origin to the destination, the distance that a vehicle can travel at the maximum posted speed limit in the amount of time defined by the current best solution.

10. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .Iadd.further comprising the step of storing .Iaddend.in .[.which.]. the end-user's device memory only .[.stores.]. detail from Active BGRs.

11. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which the communication.]. .Iadd.further comprising the step of communicating .Iaddend.with the server .[.is made.]. via .Iadd.at least one of .Iaddend.a .Iadd.cellular .Iaddend.wireless .[.or.]. .Iadd.network and a .Iaddend.satellite .Iadd.network .Iaddend.connection .[.to.]. .Iadd.from at least one of .Iaddend.a vehicle, mobile telephone, mobile data terminal, .[.or.]. .Iadd.and .Iaddend.remote electronic device.

12. The .[.invention.]. .Iadd.method of navigation guidance using BGRs .Iaddend.in claim 1, .[.in which the server can also collect.]. .Iadd.further comprising the step of collecting .Iaddend.data.Iadd., with the server, .Iaddend.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.

.Iadd.13. A system of navigation guidance using bounded geographic regions (BGRs), comprising an end-user device with means for inputting destinations and receiving routing guidance; a map database, containing roads and, optionally, points of interest (POIs); a device for geo-locating the end-user device using a global-positioning system (GPS) chip-set capable of transmitting and receiving location data, and a software method, embodied in non-transitory, computer readable medium, which is used by the device for determining vehicle position; an assemblage of memory, processing elements, and associated circuitry, referred to as a server; a means for communicating between the end-user device and the server; a Node Pair Look-up Table (NPLUT) database which is initially, either partially or fully, loaded with explicit solutions for each Node Pair, and which contains explicit solutions between each potential entry node and each potential exit node of every of interest to the end user, each BGR being an area bounded by a defined perimeter, all areas of interest to the end user are included in a BGR, and a node is the point at which a road segment intersects with a defined perimeter of a BGR; and a navigation software core, resident on the server, to identify Node Pairs for each BGR which might be part of a potential solution, and to optimize a navigation solution based on at least one dependent variable provided by the user and independent variables in the NPLUT..Iaddend.

.Iadd.14. The system of navigation guidance using BGRs in claim 13, in which the software contains an error function calculator and a feedback routine to correct dependent variable values stored in the NPLUT database..Iaddend.

.Iadd.15. The system of navigation guidance using BGRs in claim 13, in which each end-user's actual value for each Node Pair solution for dependent variables, including, but not limited to, 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..Iaddend.

.Iadd.16. The system of navigation guidance using BGRs in claim 13, 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..Iaddend.

.Iadd.17. The system of navigation guidance using BGRs in claim 16, 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..Iaddend.

.Iadd.18. The system of navigation guidance using BGRs in claim 13, in which the BGRs are created by Virtual Tessellation, by inscribing the Earth in a tessellated cube or partitioned cube, and projecting the tessellation or partition from the cube onto the surface of the Earth..Iaddend.

.Iadd.19. The system of navigation guidance using BGRs in claim 18, in which the tessellation pattern on the cube is comprised of squares and rectangles, the area of which is reduced geometrically as the rectangles vary from the center of the cube face, and the aspect ratio of which increases with distance from the center of the cube face..Iaddend.

.Iadd.20. The system of navigation guidance using BGRs in claim 13, in which solutions for each Node Pair are calculated using different processors in a multi-processor configuration..Iaddend.

.Iadd.21. The system of navigation guidance using BGRs in claim 13, in which the navigation software core will iteratively calculate routes using more and more BGRs, until the solutions become sufficiently divergent, or until the last BGR layer exceeds, orthogonally to a line from the origin to the destination, the distance that a vehicle can travel at the maximum posted speed limit in the amount of time defined by the current best solution..Iaddend.

.Iadd.22. The system of navigation guidance using BGRs in claim 13, in which the end-user's device memory only stores detail from Active BGRs..Iaddend.

.Iadd.23. The system of navigation guidance using BGRs in claim 13, in which the communication with the server is made via a wireless or satellite connection to a vehicle, mobile telephone, mobile data terminal, or remote electronic device..Iaddend.

.Iadd.24. The system of navigation guidance using BGRs in claim 13, 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..Iaddend.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) There are thirteen relevant drawings.

(2) FIG. 1 is a system communication perspective drawing.

(3) FIG. 2 is an alternative embodiment system communication perspective drawing.

(4) FIG. 3 is an alternative embodiment system communication perspective drawing.

(5) FIG. 4 is an alternative embodiment system communication perspective drawing.

(6) FIG. 5 is an alternative embodiment system communication perspective drawing.

(7) FIG. 6 is an alternative embodiment system communication perspective drawing.

(8) FIG. 7 shows a flow chart for the high level software method embodied by the present novel system.

(9) FIG. 8 shows a flow chart for creating BGRs through virtual tessellation in the resident server.

(10) FIG. 9 shows an alternative method for creating BGRs in the resident server.

(11) FIG. 10 shows a flow chart for fleet customer set-up on the resident server.

(12) FIG. 11 shows is a flow chart of a server based navigation method using BGRs and Node Pairs.

(13) FIG. 12 shows a flow chart for the hand-held or remote electronic device software process.

(14) FIG. 13 shows the Earth inscribed in a tessellated cube.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(15) The following description represents the inventors' current preferred embodiment. The description is not meant to limit the invention, but rather to illustrate its general principles of operation. Examples are illustrated with the accompanying drawings.

(16) FIG. 7 shows a high level flow chart for the software method associated with the system. Some operations are only performed on set-up of operation: 99 initial START, 26 loading map database; 62 create BGRs through sub-routine, and 56 system initialization. The map database 26 can be purchased from any map database vendor, or a crowd-sourced map database can be used. The system initialization includes such administrative routines as forming the NPLUT, populating the NPLUT with any available data, creating a user database, populating the user database with any available data, and similar tasks. Once the system has been initialized 56 and the BGRs have been created with the BGR sub 62, the system is capable of taking navigation input 55.

(17) FIG. 13 shows the Earth 301 inscribed in a tessellated cube 302. On a computer, the virtual Earth 301 can be rotated or tilted until a geographic land mass of interest is centered. Under almost all circumstances, even though the Earth 301 is an oblate spheroid, the geographic region of interest can be made to be almost parallel with a face of the inscribing cube 302. By properly selecting the size of the tessellation on the cube 302, one can influence the size of the BGR projected onto the Earth 301. This method is called Virtual Tessellation, because the pattern on the Earth 301 is not technically a tessellation, because all of the BGRs will not be the same shape and size.

(18) FIG. 8 shows a method of generating BGRs using Virtual Tessellation. First, the system inscribes the Earth in a cube 44. The center of the cube face 45 is centered over the geographic region of interest. A starting tessellation size 46 for the face of the cube is selected. The Standard Surface Area (SSA) is the target surface area for the BGRs. A BGR SSA of approximately 1 sq. km seems ideal. Next, the variation limit for the SSA 64 is set. This number should be small (less than 10%). All BGRs should have a surface area very close to the SSA in order to minimize the potential for confounded data (non-orthogonal independent variables during an analysis of variance). If desired, the size of the tessellation squares 47 on the inscribing cube can be varied. Although this is computationally more difficult, it will minimize SSA variation (only the inner most piece is a square, with each proceeding layer being rectangles with higher and higher aspect ratios. The cube tessellation is projected onto the Earth 48 to create initial BGRs. The SSA of all BGRs is assessed 49. If the SSA analysis is okay 50, the BGRs are stored 53, and the BGR generation process ends 59. If the SSA analysis is not okay 50, all the BGRs are erased 51. Next, the system adjusts the starting tessellation size 52, the outer layer tessellation ratio (how quickly the outer layers of the tessellated cube face become rectangles of higher and higher aspect ratio) is adjusted 63, and adjust the SSA variation limit 64. The whole process is then started again 47.

(19) FIG. 9 shows the flow chart for an alternative embodiment for generating BGRs. The process is started 58 by finding the centroid of the geographic region of interest 65. A single BGR is created 66 with a surface area equal to the SSA and at least four sides. The SSA variation limit is set 64. A layer of BGRs is created around the existing BGR(s), in which the new layer of BGRs has its perimeter minimized 67. The SSA for the layer is analyzed 49. As long as the SSA analysis is okay, additional layers of BGRs are added. If the SSA is not okay 50, the SSA for just the last layer is analyzed 69. If the last layer includes BGRs which overlap the border of the geographic region of interest 70, and that is the sole cause of the unacceptable SSA, the BGRs are stored 71. If it is not edge geography 70, the last layer of BGRs is erased 51. The allowable maximum perimeter will be increased by 10% from the previous iteration 68, and a new layer of BGRs will be created 67. The process continues until the entire geographic region of interest is covered with BGRs 72.

(20) In FIG. 7, once the BGR routine 62 has occurred, Fleet Set-up 61 (FIG. 10) can occur. In FIG. 10, each customer or fleet is enrolled with a Fleet Set Up 80. This includes populating a database with information about the Vehicles 81, Drivers 86, and Services Offered 91. Data collected about Fleet Vehicles 81 includes number of vehicles 82, types of vehicles (including fuel type) 83, mileage of vehicles 84, and other user defined vehicle data (independent variable or attribute data) 85. Data collected about drivers includes name 87, driver number or identifier 88, employment type (employee, independent contractor, owner/operator, etc.) 89, and other user defined driver data (independent variable or attribute data) 90. Data collected about fleet services includes customer type 92, service standards 93, service area 94, and other user defined service data (independent variable and attribute data) 95. The database also allows user defined fueling stations 96. Once all of the data has been defined, it is loaded into a database 97, and the routine ends 98.

(21) From FIG. 7, End User Nav Input Request 32 is received via a wireless means. FIG. 1 shows an embodiment of wireless communication and geo-location, which is necessary for navigation. The end user is in a vehicle 201, which has a remote electronic device (RED), either built-in or mounted. The vehicle 201 geo-locates via a GPS chip-set, a gyro, and/or a satellite transceiver. A plurality of satellites 200 provides GPS signals to the vehicle's 201 GPS transceiver. The vehicle 201 is then able to communicate its location to a central server 203, using a wireless network 202. The wireless network 202 can be a cellular or mobile phone network, a radio-frequency network, or other wireless means. The transmission could also be made over a mixed means network, such as a i-fi network that downloads and uploads requests to the server via a wired internet connection (not shown).

(22) FIG. 2 shows an alternative embodiment for the communication and geo-location system. In FIG. 2, the vehicle 201 has been replaced with a cellphone, MDT, or RED 204. The cellphone, MDT, or RED 204, geo-locates via the satellite network 200. The cellphone, MDT, or RED 204, communicates with the server 203, via a wireless network 202.

(23) FIG. 3 shows an alternative embodiment for the communication and geo-location system in FIG. 2. In this system, the wireless network 202 is used for both geo-location and communication with the server. The cellphone, MDT or RED 204 can use multiple cellphone towers or antennae to identify its current location. This data can be transmitted, along with a navigation request, to the remote server 203.

(24) FIG. 4 shows an alternative embodiment for the communication and geo-location system in FIG. 2. In this system, satellites 200 are used for both geo-location and communication. Although GPS satellites are not currently multi-tasked for communication, it is conceivable, in the future, that both geo-location information and communication would happen with the same satellite 200. However, this system is architected according to current satellite trends: one set of satellites 200 provides geo-location information, and another satellite 200 is used for communication to the remote server 203.

(25) FIG. 5 shows an alternative embodiment for the communication and geo-location system in FIG. 1. In this system, the wireless network 202 is used for both geo-location and communication with the server. The vehicle 201 can use multiple cellphone towers or antennae to identify its current location. This data can be transmitted, along with a navigation request, to the remote server 203.

(26) FIG. 6 shows an alternative embodiment for the communication and geo-location system in FIG. 1. In this system, satellites 200 are used for both geo-location and communication. One set of satellites 200 provides geo-location information, and another satellite 200 is used for communication to the remote server 203.

(27) In FIG. 7, an end-user nav request 32 is communicated through one of the communication and geo-location systems in FIG. 1 through FIG. 6. Whether a vehicle 201 or a cell-phone, MDT, or RED 204, the user interacts with the system through a user software method, generally referred to as a user application. In FIG. 12, the User Application starts 101 by insuring that the user is registered 102. If the user is registered 102, destination input 128 occurs. The user can add multiple destinations 127, 128, either specifying the order or allowing the system to order the trip. Once input is complete 127, the data is transmitted 129 to the remote server via the means shown in FIGS. 1-6. At this point we will handle the remote server 203 as a black-box that produces a navigation route, given the destination input 128. The remote server 203 transmits the route, where it is received 129 by the end user. At pre-determined intervals, the end user's application 101 will ping 130 the remote server 203, by transmitting 126 its location. The remote server 203 will compare the user's progress versus what the remote server predicts the user's progress ought to be. If the progress towards the destination lies outside the acceptance criteria, the remote server 203 will transmit a re-route signal 125 to the user's application 101. The end user's unit will notify the end user of the re-route, while the remote server 203 provides an alternative route. The new route will be received 126 by the end user's application 101. Eventually, re-route or not, the end user will arrive at the destination 124. After arriving at the destination, the end user's application 101 will transmit a final ping 123 to the remote server 203, so that the remote server has a complete history of the trip.

(28) When starting the end user application 101, if the user is not registered, the unit can allow registration by opening an account 103. After opening the account 103, the user selects ping frequency 104, navigation preferences 106, and navigation exclusions 105. The user then has to complete independent variables concerning him- or herself, and his or her vehicle. Driver information 107 includes years driving 108, driving record 109, miles driven per year 110, age 111, marital status 112, home address 113, where the user learned to drive 114, the user's profession 115, the user's gender 116, and other company- or group-defined data 117. The vehicle information 118 includes vehicle owner 119, make and model 120, model year 121 and miles on the vehicle 122. The independent variable data should be of very high quality, because the user will be aware that their accuracy in answering the questions may directly relate to how well the system can navigate for them.

(29) FIG. 7 shows that Guidance 60 occurs after End User Input 32. In FIG. 11, Guidance 60 begins by selecting nav optimizing factors 1. Once the BGRs have been created, it is possible for the invention to create navigation solutions. FIG. 11 shows a single vehicle navigation solution. The user starts by selecting an optimizing factor 1, or dependent variable: time, distance, fuel, cost, or an user defined dependent variable. Next, the user, if desired, excludes certain solutions from consideration 2, such as interstates, tollways, bridges, or other potential routes. The user enters one or more destinations 3 using the input device. If inputting more than one destination, the user can select 6 an automatic 10 or manual 5 ordering of the destinations. When selecting a manual 5 ordering, the automatic destination ordering module 10 will defer to the manual entry. Once ordered, the origin and the next or only destination is identified 9. If there is only a single destination input at the beginning 7, the navigation core moves directly to identifying origin and destination 9.

(30) To calculate between an origin and destination, the invention will identify the BGRs that lie, linearly, between the origin and destination 8, and designates them as Active. These BGRs are termed Gen 1. In the BGR containing the origin, the origin is designated the sole entry node 12. In the BGR containing the current destination 9, the current destination is designated as the sole exit node 13. In all other BGRs, Node Pairs are created by selecting only those nodes which have a BGR on both sides 11. The navigation core than creates a Node Pairs list for all Active BGRs 16. In multi-processor systems, the navigation core will simultaneously create a temporary BGR array for all Node Pairs under consideration 20, and survey the NPLUT 14 to see if solutions exist for any Node Pairs under consideration 17. If the Node Pairs solution exists in the NPLUT, it is placed in the temporary BGR array 20. If not, using weighting functions for each street classification, the invention makes dependent variable calculations for each Node Pair of each BGR 19, capturing route information for each potential solution. The invention will delete any exclusions from the potential solution set 21. Since only a limited set of BGRs are used for the initial calculation, not all nodes of each BGR is a potential entry and/or exit. The data generated from the nodes of interest can be stored in an array, in a temporary database format, or in any other data-handling format that allows quick access 20. This temporary data can be stored in cache storage, on the hard-drive, or in any other type of suitable memory element. In a multi-core processor environment, such calculations are speedy, because each BGRs can be independently calculated.

(31) The invention then creates an initial trial route by finding the initial minimum solution from the origin to the destination, travelling only through BGRs that lie, linearly, between the origin and destination 22. As a boundary condition for the initial route calculation, the exit node of one BGR is the entry node of the adjoining BGR. By creating a matrix of possible solutions, the invention yields an explicit solution.

(32) Once the initial trial route is identified, the solution engine adds all BGRs that were adjacent to Gen 1 BGRs 23, 18, and largely repeats the above process. The new BGRs are termed Gen 2. Gen 1 BGRs now use all nodes in the calculation. Gen 2 BGRs use a reduced set of nodes, because not all nodes have an adjoining BGR associated with them.

(33) To calculate the Gen 2 trial route, the potential solutions calculated in the Gen 1 calculation are excluded, because they are found in the temporary array 20. The invention, again, applies the boundary condition that the exit node of one BGR is the entry node of the adjoining BGR. By creating a matrix of possible unique solutions (excluding Gen 1 solutions), the invention yields an explicit solution, the Gen 2 trial route 22.

(34) The process is repeated for Gen 3, in much the same way as for Gen 2 23, 18. All BGRs adjoining Gen 2 BGRs are added to the calculation. All previously considered trial solutions are excluded from the potential solution set. An explicit solution for the Gen 3 trial route is calculated.

(35) Call Gen A the optimum solution. The exit criteria is selected so that C generations are completed, where C=A+B, where C is the total number of generations, A is the optimum generation, and B is the number of desired divergent solutions calculated after the optimum solution. For example, if the Gen 1 trial route is preferable to the Gen 2 or Gen 3 trial route, and the calculations stop, presenting the Gen 1 trial route to the user as the preferred route, C=3, A=1, and B=2.

(36) In practice, B is related to the distance between the origin and destination 23. Additionally, selection of B can be optimized through a simple error feedback function, where the error is related to the distance. The upper limit of B is set by the maximum speed limit. In other words, the process ends when the vehicle would have to exceed the maximum allowable speed limit around the periphery in order to offer a more preferable solution to the dependent variable than the currently available solution.