Multiple energy routing system

Methods, systems, and automotive vehicles are provided for providing routing for an automotive vehicle from a first location to a second location. The automotive vehicle is configured to operate using a primary energy source and a secondary energy source. An energy indicator is configured to provide a measure of available energy from the primary energy source onboard the automotive vehicle. A processor is coupled to the energy indicator, and is configured to ascertain characteristics of a plurality of segments connecting the first location and the second location, and to select an optimized route between the first location and the second location using the measure of available energy and the characteristics of the plurality of segments.

TECHNICAL FIELD

The present disclosure generally relates to the field of automotive vehicles and, more specifically, to automotive vehicles with a routing system that selects an optimized route of travel.

BACKGROUND

Many automotive vehicles include a navigation system that provides a recommended route for the vehicle to travel to a desired destination. However, the selection of a desired route using existing techniques may not always provide a truly optimal route for vehicles that use multiple sources of energy (such as a hybrid electric vehicle, by way of example).

Accordingly, it is desirable to provide methods for providing routing for automotive vehicles that use multiple sources of energy. It is further desirable to provide improved systems and vehicles that provide for such routing. Furthermore, other desirable features and characteristics of the present invention will be apparent from the subsequent detailed description and the appended claims, taken in conjunction with the accompanying drawings and the foregoing technical field and background.

SUMMARY

In accordance with an exemplary embodiment, a method for providing routing for an automotive vehicle from a first location to a second location, the automotive vehicle configured to operate using a primary energy source and a secondary energy source onboard the automotive vehicle, is provided. The method comprises ascertaining a measure of available energy from the primary energy source, ascertaining characteristics of a plurality of segments connecting the first location and the second location, and selecting an optimized route between the first location and the second location using the measure of available energy and the characteristics of the plurality of segments.

In accordance with another exemplary embodiment, a system for providing routing for an automotive vehicle from a first location to a second location, the automotive vehicle configured to operate using a primary energy source and a secondary energy source onboard the automotive vehicle, is provided. The system comprises an energy indicator and a processor. The energy indicator is configured to provide a measure of available energy from the primary energy source. The processor is coupled to the energy indicator, and is configured to ascertain characteristics of a plurality of segments connecting the first location and the second location, and select an optimized route between the first location and the second location using the measure of available energy and the characteristics of the plurality of segments.

In accordance with a further exemplary embodiment, an automotive vehicle is provided. The automotive vehicle comprises an energy indicator, a drive system, and a processor. The energy indicator is configured to provide a measure of available energy from a primary energy source onboard the automotive vehicle. The drive system is configured to propel the automotive vehicle between a first location and a second location using the primary energy source, if the primary energy source is currently available onboard the automotive vehicle, and a secondary energy source, if the primary energy source is not currently available onboard the automotive vehicle. The processor is coupled to the energy indicator, and is configured to ascertain characteristics of a plurality of segments connecting the first location and the second location, and select an optimized route between the first location and the second location using the measure of available energy and the characteristics of the plurality of segments.

DETAILED DESCRIPTION

FIG. 1illustrates an automotive vehicle100, (or automobile, or vehicle) according to an exemplary embodiment. The vehicle100operates on a primary energy source101and a secondary energy source102. The vehicle100utilizes energy efficient routing based upon a measure of availability of the primary energy source101on board the vehicle, cost functions of the primary and secondary energy sources101,102, and characteristics of road segments between an origin and an intended destination for the vehicle100, as provided in greater detail below. As depicted inFIG. 1, the vehicle includes a body103, a chassis104, a plurality of wheels106, a drive system108, and a navigation system110.

The body103is arranged on the chassis104, and substantially encloses the other components of the vehicle100. The body103and the chassis104may jointly form a frame. The wheels106are each rotationally coupled to the chassis104near a respective corner of the body103to facilitate movement of the vehicle100. In a preferred embodiment, the vehicle100includes four wheels106, although this may vary in other embodiments (for example for trucks and certain other automotive vehicles).

The drive system108is mounted on the chassis104, and drives the wheels106via one or more drive shafts112coupled to the wheels106. The drive system108comprises a propulsion system that propels the vehicle100between a first location (at which the vehicle100is currently located, or from which a current drive or ignition cycle begins) and a second location (namely, a destination as selected by a user of the vehicle) using the primary and secondary energy sources101,102. The drive system108preferably operates using the primary energy source101(for example, electric energy) provided that the primary energy source101is available onboard the vehicle100, and operates using the secondary energy source102(such as gasoline or diesel fuel) when the primary energy source is not available onboard the vehicle100.

In certain exemplary embodiments, the drive system108comprises a combustion engine and/or an electric motor/generator, coupled with a transmission thereof. In certain embodiments, the drive system108may vary, and/or two or more drive systems108may be used. By way of example, the vehicle100may also incorporate any number of different types of electrical propulsion systems, such as, for example, a gasoline or diesel fueled combustion engine, a “flex fuel vehicle” (FFV) engine (i.e., using a mixture of gasoline and alcohol), a gaseous compound (e.g., hydrogen and/or natural gas) fueled engine, a combustion/electric motor hybrid engine, and an electric motor.

The navigation system110provides information to occupants of the vehicle, including providing a recommended route of travel for the vehicle to a desired destination based on availability and characteristics of the primary energy source101and the secondary energy source102onboard the vehicle100and characteristics of nearby road segments. In certain embodiments the navigation system110is configured to interface directly or indirectly with a remote server130and/or a user wireless device132of a vehicle occupant (such as a cellular telephone and/or short-range wireless device). In certain other embodiments, the remote server130and/or the user wireless device132may include some or all of the components of, and/or perform some or all of the functions of, the navigation system110.

The navigation system110is preferably disposed onboard the vehicle100, and is coupled to a first energy indicator114and a second energy indicator116. The first energy indicator114measures an indication as to a measure of availability of the primary energy source101. The second energy indicator116measures an indication as to a measure of availability of the secondary energy source102. For example, in one embodiment, the primary energy source comprises electrical energy as utilized via a rechargeable energy storage system (RESS), such as a battery, and the first energy indicator114comprises a sensor and/or system configured to measure a state of charge of the RESS. Also in one such exemplary embodiment, the secondary energy source comprises gasoline, and the second energy indicator116comprises a sensor that measures a level of gasoline in a fuel tank of the vehicle.

The input device120is configured to obtain inputs from a user, preferably from one or more occupants of the vehicle, including information as to a desired destination of travel for the vehicle during a current vehicle drive (or ignition cycle) of the vehicle. By way of example only, the input device120may include one or more buttons, switches, rotary knobs, touch screens, touch panels, capacity panels, swipe operations, and/or one or more other types of devices. As explained in greater detail below, the navigation system110determines a recommended route of travel for the vehicle100based on a measure of availability of the primary energy source101and characteristics of segments connecting a current location of the vehicle100with a desired destination location.

The receiver122is configured to receive signals and/or information pertaining to the vehicle. The receiver122receives information regarding the availability of the primary energy source101and the secondary energy source102, preferably from the first and second energy indicators114,116, respectively (for example, via a vehicle communications and/or a wireless connection). The receiver122receives signals and information regarding a current geographic position or location of the vehicle from one or more satellites131or as part of a global positioning system (GPS). In certain embodiments, the receiver122receives signals via a first wireless connection134(such as a Bluetooth or other short range wireless connection) from the user wireless device132. In addition, in certain exemplary embodiments, the receiver122receives signals and information from the remote server130via a second wireless connection136(such as a cellular wireless network). In one embodiment, wireless connections134,136comprise different types of wireless connections. In another embodiment, wireless connections134,136comprise one or more common or identical wireless connections. The receiver122provides the signals and/or information to the computer system126for processing, and ultimately for use in selecting an optimal (or recommended) route of travel for the vehicle100.

The transmitter124is configured to transmit signals and/or information pertaining to the vehicle. In an exemplary embodiment, the transmitter124transmits signals and information regarding a current geographic position or location of the vehicle to the remote server130. In addition, the transmitter124may also transmit signals and information regarding the current geographic position of the vehicle, and/or a desired route of travel for the vehicle.

The computer system126is coupled between the input device120, the receiver122, the transmitter124, and the display and notification unit128. The computer system126receives the above-described signals, information, and user inputs from the receiver122, the transmitter124, and the input device120. The computer system126processes the various signals, information, and user inputs and provides instructions for the display and notification unit128and/or the transmitter124to provide a recommended route of travel for the vehicle to the desired destination based on the availability and characteristics of the primary energy source101and the secondary energy source102and characteristics of road segments leading to the destination. In addition, in certain embodiments, the computer system126also provides instructions for the transmission of signals and information by the transmitter124to the remote server130for remote, off-board storage or processing, and may also receive information and/or instructions from the remote server130via the receiver122.

As depicted inFIG. 1, the computer system126includes a processor140, a memory142, a computer bus144, an interface146, and a storage device148. The processor140performs the computation and control functions of the computer system126or portions thereof, and may comprise any type of processor or multiple processors, single integrated circuits such as a microprocessor, or any suitable number of integrated circuit devices and/or circuit boards working in cooperation to accomplish the functions of a processing unit. During operation, the processor140executes one or more programs149preferably stored within the memory142and, as such, controls the general operation of the computer system126.

The processor140receives the above-referenced signals, information, and user inputs from the receiver122and the input device120(and, in certain embodiments, from the remote server130, the wireless device132, and/or one or more other devices and/or systems). The processor140processes the signals, information, and user inputs and provides instructions to the display and notification unit128and/or the transmitter124to provide a recommended route of travel for the occupants of the vehicle. In addition, in certain embodiments, the processor140also provides instructions for the transmission of signals and information by the transmitter124to the remote server130for remote storage or processing. The processor140preferably performs these functions in accordance with the steps of the process200described further below in connection withFIGS. 2-4. In addition, in one exemplary embodiment, the processor140performs these functions by executing one or more of the above-referenced programs149stored in the memory142.

The memory142stores one or more programs149for implementing the process200described further below in connection withFIG. 2. In addition, the memory142stores additional values150, including a first function151pertaining to costs and/or other characteristics of the primary energy source101and a second function152pertaining to costs and/or other characteristics of the secondary energy source102. In one embodiment, the first and second functions151,152pertain to monetary costs of operating the vehicle100using the primary and secondary energy sources101,102, respectively. In another embodiment, the first and second functions151,152pertain to energy usage associated with the primary and secondary energy sources101,102, respectively. In yet another embodiment, the first and second functions151,152pertain to carbon content and/or emissions characteristics of the primary and secondary energy sources101,102, respectively. In yet another embodiment, the first and second functions151,152pertain to measures of renewability of the primary and secondary energy sources101,102, respectively.

The memory142can be any type of suitable memory. This would include the various types of dynamic random access memory (DRAM) such as SDRAM, the various types of static RAM (SRAM), and the various types of non-volatile memory (PROM, EPROM, and flash). In certain embodiments, the memory142is located on and/or co-located on the same computer chip as the processor140. It should be understood that the memory142may be a single type of memory component, or it may be composed of many different types of memory components. In addition, the memory142and the processor140may be distributed across several different computers that collectively comprise the computer system126. For example, a portion of the memory142may reside on a computer within a particular apparatus or process, and another portion may reside on a remote computer off-board and away from the vehicle, for example as part of the remote server130.

The computer bus144serves to transmit programs, data, status and other information or signals between the various components of the computer system126. The computer bus144can be any suitable physical or logical means of connecting computer systems and components. This includes, but is not limited to, direct hard-wired connections, fiber optics, infrared and wireless bus technologies.

The interface146allows communication to the computer system126, for example from a vehicle occupant, a system operator, a remote, off-board database or processor, and/or another computer system, and can be implemented using any suitable method and apparatus. In certain embodiments, the interface146receives input from an occupant of the vehicle, preferably via the input device120ofFIG. 1.

The storage device148can be any suitable type of storage apparatus, including direct access storage devices such as hard disk drives, flash systems, floppy disk drives and optical disk drives. In one exemplary embodiment, the storage device148comprises a program product from which the memory142can receive a program149that executes the process200ofFIG. 2and/or steps thereof as described in greater detail further below. Such a program product can be implemented as part of, inserted into, or otherwise coupled to the navigation system110. In another exemplary embodiment, the program product may be directly stored in and/or otherwise accessed by the memory142and/or a disk (e.g., disk154), such as that referenced below.

As shown inFIG. 1, the storage device148can comprise a disk drive device that uses disks154to store data. As one exemplary implementation, the computer system126may also utilize an off-board/off-vehicle Internet website, for example for providing or maintaining data or performing operations thereon.

It will be appreciated that while this exemplary embodiment is described in the context of a fully functioning computer system, those skilled in the art will recognize that certain mechanisms of the present disclosure may be capable of being distributed as a program product with one or more types of non-transitory computer-readable signal bearing media used to store the program and the instructions thereof and carry out the distribution thereof, such as a non-transitory computer readable medium bearing the program and containing computer instructions stored therein for causing a computer processor (such as the processor140and/or the processor170) to perform and execute the program. Such a program product may take a variety of forms, and that the present disclosure applies equally regardless of the particular type of computer-readable signal bearing media used to carry out the distribution. Examples of signal bearing media include: recordable media such as floppy disks, hard drives, memory cards and optical disks (e.g., disk154), and transmission media such as digital and analog communication links. It will similarly be appreciated that the computer system126may also otherwise differ from the embodiment depicted inFIG. 1, for example in that the computer system126may be coupled to or may otherwise utilize one or more remote, off-board computer systems and/or other navigation systems, for example as part of the remote server130. As used throughout this application, a remote computer system refers to a computer system that is off-board and outside the vehicle. For example, a remote computer system may be at a central processing facility for use with a number of different vehicles, among other possible examples.

The display and notification unit128is coupled to the computer system126. In a preferred embodiment, the display and notification unit128comprises a visual component160(preferably a display screen, such as a liquid crystal display (LCD) screen) that generates images that are visible to occupants of the vehicle, and an audio component162(such as a speaker) that generates sounds that can be heard by the occupants of the vehicle. It will be appreciated that the display and notification unit128may comprise one or more visual components160and/or audio components162together as one system and/or as separate systems.

As mentioned above, in certain embodiments, various functions of the navigation system110may be performed by the remote server130and/or the wireless device132. The remote server130includes a processor170, a memory172, a transmitter174, and a receiver176. In certain embodiments, the remote processor170, memory172, transmitter174, and receiver176of the remote server130, are similar to, and may perform some or all of the respective functions of (or functions similar to) the processor140, memory142, transmitter124, and receiver122, respectively, of the navigation system110. In certain embodiments, the wireless device132may also include similar components, features, and functionality. Also in certain embodiments, the remote server130(or components thereof), the wireless device132, and/or the navigation system110(or components thereof) may together form a single system.

FIG. 2is a flow chart of a process200for providing routing for a vehicle from a first location to a second location, in accordance with an exemplary embodiment. In a preferred embodiment, the process200can be implemented in connection with the vehicle100, the navigation system110, the remote server130, and/or the wireless device132ofFIG. 1. The process200will also be described below in conjunction withFIGS. 3 and 4, which provide graphical illustrations of certain exemplary implementation of the process200ofFIG. 2in accordance with exemplary embodiments.

As depicted inFIG. 2, the process200includes the step of obtaining user information (step202). The user information includes information as to preferred destination of travel for the vehicle during a current vehicle drive (or ignition cycle) for the vehicle. The desired destination for travel of the vehicle as obtained in step202is referred to herein as the “destination” or the “second location”. In one embodiment, the user information is obtained from a driver or other user of the vehicle via the input device120ofFIG. 1. In another embodiment, the user input is obtained from the wireless device132ofFIG. 1. The desired destination for travel of the vehicle as obtained in step202is referred to herein as the “destination” or the “second location”. Also in a preferred embodiment, the receiver122provides a signal indicative of the destination to the processor140of the computer system126ofFIG. 1for processing. With reference to the exemplary implementations ofFIGS. 3 and 4, the destination is represented by node302inFIG. 3and node420inFIG. 4.

In addition, a vehicle location is determined (step204). In a preferred embodiment, the vehicle location comprises a geographic position of the vehicle at the beginning of a current vehicle drive or ignition cycle, and/or a geographic position of the vehicle at a time in which the user has provided inputs as to a desired destination for step202. The vehicle location of step204is referred to herein as the “origin” or the “first location”. The vehicle location and/or information pertaining thereto is preferably obtained by the receiver122ofFIG. 1, most preferably via satellite signals provided by one or more satellites131ofFIG. 1coupled thereto as part of a global positioning system. In certain embodiments, the receiver122ofFIG. 1may receive the vehicle location and/or information pertaining thereto from another source, such as from the wireless device132and/or the remote server130ofFIG. 1. Also in a preferred embodiment, the receiver122provides a signal indicative of the origin to the processor140of the computer system126ofFIG. 1for processing. With reference to the exemplary implementations ofFIGS. 3 and 4, the origin is represented by node301inFIG. 3and node416inFIG. 4(described in greater detail further below).

In addition, characteristics of the vehicle being driven are obtained (step206). In a preferred embodiment, the vehicle characteristics of step206include the types of the primary and secondary energy sources used to power the vehicle along with measures of economy of energy usage for the vehicle with respect to both the primary and secondary energy sources. For example, in one such preferred embodiment, the vehicle characteristics of step206include measures of energy economy for the vehicle, for each of the primary and secondary energy sources, at different vehicle speeds and on different types of road segments (such as highway driving, city driving, and the like). The vehicle characteristics are preferably stored in the memory142ofFIG. 1and retrieved therefrom by the processor140ofFIG. 1.

A measure is obtained as to the availability of the primary energy source onboard the vehicle (step208). In one embodiment, the measure of step208comprises an amount of energy of the primary energy source that is available onboard the vehicle for operating the vehicle. In another embodiment, the measure of step208comprises an estimated distance that the vehicle can be driven while the vehicle is operated using the available energy of the primary energy source that is onboard the vehicle. The measure of step208is preferably provided by the first energy indicator114ofFIG. 1and/or calculated by the processor140ofFIG. 1based on measurements and/or other information provided thereto by the first energy indicator114ofFIG. 1. For example, in one embodiment, if the primary energy source comprises electrical energy as utilized via an RESS, then the measure of step208may be ascertained based on a state of charge of the RESS. By way of further example, in another embodiment, if the primary energy source comprises gasoline, then the measure of step208may be ascertained based on a level of gasoline in a fuel tank of the vehicle.

A heuristic cost is determined between the origin of step204and the destination of step202(step210). In one preferred embodiment, the heuristic cost of step210comprises a “best case” estimate as to an amount of energy that would be used by the vehicle in travelling from the origin to the destination, using only the primary energy source, and under ideal conditions for primary energy source usage. Specifically, in one preferred embodiment, the heuristic cost of step210is determined by calculating a Euclidean, straight line distance between the origin and the destination (for example, “as the crow flies”, without regard to the direction of road segments therebetween), and determining an amount of energy usage that would be required for the vehicle to travel using the primary energy source along this distance assuming that the posted speed limits, concentration of traffic lights, and traffic patterns along this distance are ideal for energy economy for usage of the primary energy source. The heuristic cost of step210is preferably calculated by the processor140ofFIG. 1.

A determination is then made as to whether there is sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the destination under the heuristic assumptions of step210(step212). The determination of step212is preferably made based on the measure of availability of the primary energy source from step208and the heuristic cost of step210. Specifically, in one embodiment, the determination of step212is based on whether the measure of availability of the primary energy source of step208is greater than or equal to the heuristic cost of step210. The determination of step212is preferably made by the processor140ofFIG. 1.

If it is determined that there is sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the destination under the heuristic assumptions of step210, then a scaling factor for the process is set equal to the best case (i.e., lowest, or most energy efficient) energy usage for the primary energy source per unit of distance (for example, kilowatts per mile) assuming ideal travel conditions for the primary energy source (such as posted speed limits, concentration of traffic lights, and traffic patterns that are most energy efficient for the primary energy source) and utilizing the first function151ofFIG. 1(step214). Conversely, if it is determined that there is not sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the destination under the heuristic assumptions of step210, then the scaling factor for the process is instead set equal to the best case (i.e., lowest, or most energy efficient) energy usage for the secondary energy source per unit of distance (for example, kilowatts per mile) assuming ideal travel conditions for the secondary energy source (such as posted speed limits, concentration of traffic lights, and traffic patterns that are most energy efficient for the secondary energy source) and utilizing the second function152ofFIG. 1(step216). The scaling factor of either step214or step216(whichever is calculated) is used in assessing nearby travel nodes for consideration for possible inclusion in the recommended route of travel for the vehicle, as discussed further below.

An open set of possible nodes is initiated (step218). The open set of nodes changes throughout various iterations. At any particular point in time, the open set comprises a set of nodes that are to be examined for possible inclusion in the recommended route. During a first iteration, the open set is initialized to comprise the origin of step204. The open set is preferably initiated and updated by the processor140ofFIG. 1.

A closed set of possible nodes is also initiated (step220). The closed set of nodes also changes throughout various iterations. At any particular point in time, the closed set comprises a set of nodes that have already been considered for possible inclusion in the recommended route (as used herein, the terms “recommended route”, “optimal route”, and “selected route” are synonymous with one another). During a first iteration, the closed set is initialized to comprise an empty set. In one embodiment, each node represents a point in a path or roadway that is a predetermined distance from a preceding node, or that represents a turn in direction or fork in the road from a segment of a preceding node. In one such embodiment, the predetermined distance is equal to one hundred feet; however, this may vary in other embodiments. The closed set is preferably initiated and updated by the processor140ofFIG. 1.

An identification is made as to nodes that satisfy the criteria for inclusion as candidates for the recommended route of travel (step222). Preferably, a map stored in the memory142ofFIG. 1is utilized to identify various travel nodes that are between the origin of step204and the destination of step202and/or that may be close enough to one or both of the origin and/or the destination so as to be within a feasibility boundary for the recommended route of travel, using an appropriate scaling factor from step214or216. Specifically, if it was determined in step212that there is sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the destination under the heuristic assumptions of step210, then the scaling factor of step214(using the first function151ofFIG. 1) is utilized in step222. Conversely, if it was determined in step212that there is not sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the destination under the heuristic assumptions of step210, then the scaling factor of step216(using the second function152ofFIG. 1) is utilized instead in step222. The identification of step222is preferably made by the processor140ofFIG. 1.

A heuristic distance is calculated for each of the nodes identified during step222(step224). In one preferred embodiment, for each node, the heuristic distance is a Euclidean, straight line distance between the origin and the node (for example, “as the crow flies”, without regard to the direction of road segments therebetween). The heuristic distance is preferably calculated by the processor140ofFIG. 1.

A separate determination is then made for each node identified in step222as to whether there is sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the node under a best case scenario for use of the primary energy source (preferably, similar to the heuristic assumptions of step210, for example including optimal posted speed limits, concentration of traffic lights, traffic patterns, and the like) (step226). The determinations of step226are preferably made based on the measure of availability of the primary energy source from step208, the distance of step224, and the first function151ofFIG. 1for the primary energy source.

In steps228and230described below, a first score (referred to herein as a “G-Score”) is then determined for each of the nodes identified in step222and stored in memory. The G-Score of a particular node represents an estimated energy cost of travelling from the origin to the particular node. The calculation of the G-Score for a particular node is dependent upon the distance of step224and the determination of step226of the respective node. Specifically, if it is determined in step226that there is sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the node under consideration, then the G-Score is calculated based on the distance of step224for the particular node and the first function151ofFIG. 1for the primary energy source (step228). Conversely, if it is determined in step226that there is not sufficient availability of the primary energy source onboard the vehicle to travel from the origin to the node under consideration, then the G-Score is calculated instead based on the distance of step224for the particular node and the second function152ofFIG. 1for the secondary energy source (step230). The G-Score is preferably calculated by the processor140ofFIG. 1and stored in the memory142for subsequent usage during the process (for example, in step248, described further below).

A current node is selected from the list of nodes identified in step222(step232). In a first iteration of step232, the current node comprises the origin of step204, or the node at which the vehicle is currently positioned. In subsequent iterations, the current node comprises a node along a path between the origin of step204and the destination of step202that is currently under consideration. The current node is preferably selected by the processor140ofFIG. 1.

A determination is made as to whether the current node of step232represents the destination of step202(step234). This determination is preferably made by the processor140ofFIG. 1. If it is determined that the current node represents the destination, then the process proceeds to steps262and264, described further below. Conversely, if it is determined that the current node does not represent the destination, then the process proceeds instead to step236, described directly below.

An identification is made as to each of the neighbor nodes near the current node of step232(step236). Specifically, during step236, an identification is made as to each of the nodes of step222that are immediately adjacent to, or are connected by a single road segment to, the current node of step232. By way of example, with reference toFIG. 4, the origin416ofFIG. 4has four neighbor nodes, namely, node409, node415, node417, and node423. The neighbor nodes are preferably identified by the processor140ofFIG. 1.

One of the neighbor nodes of step236is then selected for analysis (step238). Preferably, each of the neighbor nodes is analyzed, one at a time, each in a different iteration. The selection of the neighbor in step238may be selected at random, or based on direction (for example, East or West, North or South, clockwise or counterclockwise, or the like). The selection of the neighbor is preferably made by the processor140ofFIG. 1.

A determination is made as to whether the selected neighbor of step238is a member of the closed set of step220(step240). This determination is preferably made by the processor140ofFIG. 1. If it is determined that the selected neighbor is in the closed set (that is, that the selected neighbor has already been analyzed for possible inclusion in the optimal route), then the process returns to step238, and a different neighbor node is selected. Steps238and240repeat in this manner until a neighbor node is selected that is not in the closed set. Once it is determined in an iteration of step240that the selected neighbor of the most recent iteration of step238is not in the closed set, then the process proceeds to step241, described directly below.

During step241, various characteristics are obtained regarding the selected neighbor node of the most recent iteration of step238. The characteristics preferably pertain to various characteristics of a road segment connecting the selected neighbor node of step238with the current node of step232. The characteristics preferably include a distance of the road segment, a grade or angle of the road segment, posted speed limits (and/or an average posted speed limit), a measure of a concentration of traffic lights along the road segment, historical traffic patterns (such as historical average driving speeds) along the road segment, and/or real-time driving conditions along the road segment (e.g., a current average speed along the road segment, weather conditions along the road segment, any accidents or traffic slowdowns along the road segment, or the like). The characteristics are preferably obtained by the processor140ofFIG. 1. Certain of the characteristics (for example, the historical data) may be obtained by the processor140ofFIG. 1from data stored in the memory142ofFIG. 1, while certain other of the characteristics (for example, the real-time data) may be obtained from the remote server130and/or the wireless device132ofFIG. 1.

A determination is made as to whether there is sufficient availability of the primary energy source to travel from the origin to the neighbor node of step238via the current node of step232(step242). Preferably, during step242an updated estimate of the availability of the primary energy source is utilized from previous calculations (in a prior iteration) as to the amount of energy usage that would be required to travel from the origin to the current node of step232. The first function151ofFIG. 1is then applied to the road segment characteristics of step241to determine an incremental energy cost of travelling from the current node of step232to the neighbor node of step238.

If the incremental energy cost is less than or equal to the updated estimate of the availability of the primary energy source after reaching the current node of step232, then it is determined that there is sufficient availability of the primary energy source for travel to the neighbor node of step238. Accordingly, a temporary G-Score is calculated for the neighbor node based on usage of the primary energy source (step244). During step244, the temporary G-Score is calculated based on the characteristics of step241of the road segment between the current node and the neighbor node and the first function151ofFIG. 1pertaining to the primary energy source. The temporary G-Score of step244is preferably calculated by the processor140ofFIG. 1.

Conversely, if the incremental energy cost is greater than the updated estimate of the availability of the primary energy source after reaching the current node of step232, then it is determined that there is not sufficient availability of the primary energy source for travel to the neighbor node of step238. Accordingly, a temporary G-Score is calculated for the neighbor node based instead on usage of the secondary energy source (step246). During step246, the temporary G-Score is calculated based on the characteristics of step241of the road segment between the current node and the neighbor node and the second function152pertaining to the secondary energy source. The temporary G-Score of step246is preferably calculated by the processor140ofFIG. 1.

A determination is made as to whether the temporary G-Score of step244or step246(whichever is calculated in a particular iteration, based on the determination of step242, described above) is less than the stored G-Score of step228or step230(whichever was calculated for that particular node) (step248). This determination is preferably made by the processor140ofFIG. 1.

If it is determined that the temporary G-Score of steps244,246is greater than or equal to the stored G-Score of steps228,230for the particular node under consideration as the neighbor node of step238for a particular iteration, then the process returns to step238, as a new neighbor node is selected that is also adjacent to the current node of step232. Steps238-248thereafter repeat in a new iteration for this newly selected neighbor node.

Conversely, if it is determined that the temporary G-Score of steps244,246is less than the stored G-Score of steps228,230for the particular node under consideration as the neighbor node of step238for a particular iteration, then the G-Score of the particular node under consideration is re-set to equal the temporary G-Score of step244or step246(whichever was calculated for the particular node under consideration) (step250). This step is preferably performed by the processor140ofFIG. 1.

In addition, a second score (referred to herein as an “H-Score”) is also calculated for this node (step252). As referenced herein, the H-Score represents an expected energy cost, preferably a heuristic expected energy cost, for the vehicle to travel from the node under consideration to the destination of step202. Similar to the Heuristic G-Score of steps224-230, the calculation of the H-Score preferably includes the determination of a Heuristic distance between the node under consideration and the destination (most preferably a Euclidean or straight line distance “as the crow flies”), a determination of whether there is sufficient availability of the primary energy source onboard the vehicle to complete travel between the node and the destination, and the application of (i) the first function151ofFIG. 1if there is sufficient availability of the primary energy source for the vehicle to travel between the node and the destination, or (ii) the second function152ofFIG. 1if there is not sufficient availability of the primary energy source for the vehicle to travel between the node and the destination. The H-Score is preferably calculated by the processor140ofFIG. 1.

A third score (referred to herein as an “F-Score”) is also calculated for this node (step254). As referenced herein, the F-Score represents an expected energy cost for the vehicle to travel from the origin to the destination through the node under consideration, preferably via a most energy-efficient route of travel of those potential routes of travel between the origin and the destination that pass through the node under consideration. The F-Score is preferably calculated by the processor140ofFIG. 1by adding together the G-Score (as updated in step250) to the H-Score (as calculated in step252).

In addition, the current node of step232is identified as the “parent” node for the neighbor node under consideration and stored in memory (step256). Preferably, this identification is made by the processor140ofFIG. 1and stored in the memory142ofFIG. 1.

A determination is then made as to whether there are any additional neighbor nodes of step236remaining for consideration for the current node of step232(step257). This determination is preferably made by the processor140ofFIG. 1. If it is determined in step257that there are any additional neighbor nodes still to be considered, then the process returns to step238, as a new neighbor node is selected. Steps238-257repeat in new iteration(s) until it is determined in an iteration of step257that all of the neighbor nodes have been considered for the current node.

Once a determination is made that each of the neighbor nodes for the current node has been considered, then a determination is made as to which of the neighbor nodes under consideration for the current node has the lowest F-Score (step258). This determination is preferably made by the processor140ofFIG. 1. The selected neighbor node of step258with the lowest F-Score is then moved to the closed step and identified as the new “current node” (step260). Steps258and260are preferably performed by the processor140ofFIG. 1.

The process then returns to step232, and steps232-260repeat in a new iteration with the node selected in step258serving as the “current node” in the next iteration. Steps232-260repeat in this manner for various other iterations, each having a new, updated “current node”, until a determination is made in an iteration of step234that the current node is the desired destination of step202. Once it is determined in an iteration of step234that the current node is the same as the destination, the process has found an optimal route for the vehicle to travel from the origin to the destination.

Accordingly, the optimal path is reconstructed by linking together the “parent” nodes of the selected current nodes in succession (step262). This is preferably performed by the processor140ofFIG. 1. In addition, the optimal (or recommended) route is presented to the vehicle users (step264). Specifically, the optimal route is preferably provided for the driver and/or other occupants or users of the vehicle via the navigation system110ofFIG. 1for display on the display and notification unit128(for example, via the visual component160and the audio component162) via instructions provided by the processor140ofFIG. 1. In certain embodiments, the optimal (or recommended) route is provided instead for the users on the wireless device132ofFIG. 1.

With reference to the first exemplary implementation ofFIG. 3, if there is not sufficient availability of the primary energy source for the vehicle to travel between the origin301and the destination302ofFIG. 3, the optimal route will include a first portion308using the primary energy source and a second portion310using the secondary energy source.FIG. 3also shows various other searched alternatives312, as well as a heuristic estimate of cost306, per the discussion above.

With reference to the second exemplary implementation ofFIG. 4, and as discussed above, the optimal route of travel will depend upon the characteristics of the road segments between the nodes and the amount of the primary energy source available onboard the vehicle. For example, if there is a relatively large supply of the primary energy source (for example, electrical energy), then a more direct route may connect the origin416and the destination420via a city street stretching between nodes416,417,418,419, and420, with a first portion431using the primary power source and a second portion432using the secondary power source (for example, gasoline). By way of further example, if there is a relatively small supply of the primary energy source (for example, electrical energy), then a more indirect route may connect the origin416and the destination420via a highway stretching between nodes416,409,410,411,412,413, and420, with a first portion441using the primary power source and a second portion442using the secondary power source (for example, gasoline).

Accordingly, improved methods are providing for providing routing for automotive vehicles that optimize energy efficiency and/or minimizes energy-related costs based on an availability of a primary energy source (such as electric energy) and based on different respective functions for the primary energy source and the secondary energy source (such as gasoline or diesel fuel). In addition, improved systems and vehicles are provided that provide for such improved routing.

It will be appreciated that the disclosed vehicles, systems, and processes may differ from those depicted in the Figures and/or described above. For example, the navigation system110and/or various parts and/or components thereof (and/or of the vehicle100) may differ from those ofFIG. 1and/or described above. Similarly, certain steps of the process200may be unnecessary and/or may vary from those depicted inFIGS. 2 and/or 3and/or described above. It will similarly be appreciated that various steps of the process200may occur simultaneously or in an order that is otherwise different from that depicted inFIGS. 2and/3and/or described above. It will similarly be appreciated that, while the disclosed methods and systems are described above as being used in connection with automobiles such as sedans, trucks, vans, and sports utility vehicles, the disclosed methods and systems may also be used in connection with any number of different types of vehicles, and in connection with any number of different systems thereof and environments pertaining thereto.