TW201420994A - Computer navigation route planning program product for electric vehicle - Google Patents

Abstract

The present invention relates to a computer navigation route planning program product for electric vehicle comprised a navigation system with a map data-base, an input interface, a processing module and an output interface. The navigation system is ignited by loading a navigation route planning program which is developed by using map information to define a start and a destination by through a plurality of relayed nodes, reasoning an optimized route with minimum mileage cost according to an objective function. The objective function to be optimized is composing a spend cost, a coming cost and a residual cost which is the distance cost weights by an integral power consumption weighting factor. Moreover, the integral power consumption weighting factor may be decomposed into charging station service weighting factor and road priority weighting factor to enforce the reality in electric charging and road grade characteristics. Thus an optimal route planning of an electric vehicle can be achieved.

Description

Navigation route planning computer program product for electric vehicle

The present invention relates to a navigation path planning computer program product for an electric traffic vehicle, and more particularly to an electric vehicle vehicle designed by performing a path objective function including an overall power consumption weight associated with a charging station characteristic and a road characteristic. A computer program product that optimizes the path.

With the advancement of science and technology and the development of the times, people's concept of life has gradually changed, and thus gradually pay attention to the quality of life, which in turn has promoted the prevalence of driving travel, in order to facilitate people to travel more quickly and accurately, so satellite navigation Path planning computer program products have become an indispensable tool for people to travel by car. They use electronic maps and Global Positioning System (GPS) to plan paths and navigate. That is, users only need to input the purpose of going. Later, the satellite navigation path planning computer program product will help the user to find the optimal path to the destination based on the user's location.
However, in recent years, with the rise of environmental awareness, the development of electric vehicles has received attention. In the satellite navigation path planning computer program products of the prior art, although the optimization path can be planned, the charging station position is generally not optimal. Path planning, and because electric vehicles have limited battery life, although the satellite navigation path planning computer program products can be planned to optimize the path, the existing electric vehicles have limited battery life, making the electric vehicle to some The location still needs to find a charging station and deviate from the optimization path, and cannot reach the destination according to the planned optimization path, thereby making the navigation effect poor.
Conventionally, various navigation path planning methods such as Ant Colony Optimization (ACO), Dijkstra algorithm, A* algorithm or Moore/Pape algorithm; The group algorithm is usually used for the planning of random paths. The Dijkstra algorithm starts from the periphery of the starting point and determines the shortest path to each node one by one. The Moore/Pape algorithm is the shortest path calculation method, in the many-to-many The calculation is the fastest, but it is not suitable for one-to-many calculation; the calculation is less and suitable for one-to-many calculation is A* algorithm, which mainly defines an objective function, and then differentiates the objective function to obtain The maximum value (minimum value) of the target value. The objective function usually calculates the cost with F=G+H, finds the least cost as the result to plan the path; where F is the estimated cost from the initial point to the target point, and G is from the initial The actual cost of the point to a node, H is the estimated cost of the best path from a node to the target point; and this algorithm usually takes the road attribute, length and required time of the electronic map data as the calculation. in accordance with.
The prior art of various navigation path planning methods, such as the navigation prompt method disclosed in Taiwan Patent Publication No. TW201122433, utilizes the cost of calculating different paths, and generates a cost difference between the deviation route and the optimization route, and the difference is The smallest path is the path of the navigation prompt; as disclosed in Taiwan Patent Publication No. TW201211508, the use of map data and the identification of the minimum cost path to determine the route from the departure point to the destination; these disclosed techniques only consider mileage-related in the objective function. Cost, but the most power-consuming characteristics of electric vehicles are not directly usable. In addition to the mileage, the overall power consumption characteristics of the electric vehicle are directly related to the type of road, whether there is a charging station or that type of charging station. Related. U.S. Patent Publication No. US20120010767 discloses that a Hybrid electric vehicle (HEV) uses a Battery State-of-charge (SoC) as an objective function for optimization, as shown in Fig. 1, from the starting point Ps in the travel path 9. Through several nodes (Pr1, Pr2, Pr3, and Pr4) to the end point Pt, calculate the battery state of each node and list the possible battery state (SoC ¹ , SoC ² , ..., SoC ⁿ ), optimized The calculation, the combination of the best SoC of each node is calculated, and the road level is considered as the path selection consideration in the subsequent navigation, but the road feature is not included in the calculation of the objective function in the disclosed technology; U.S. Patent No. 8,204,638 incorporates the driving speed into the objective function of the hybrid vehicle for the calculation of the optimal power path; U.S. Patent No. 5,913,917 uses the fractional characteristic of the roadway as the weight.
However, due to the limited power of the electric traffic vehicle, when the existing navigation path planning computer program product or calculation method is applied to the electric vehicle, among the consideration factors of the planned optimization path, only the mileage cost is calculated or the number of the roadway is added. The rate is not the total power consumption; in fact, the cost of road mileage is not only related to the length of the distance, but should consider the overall power consumption situation, power consumption of different road attributes (such as highways, expressways). The power consumption characteristics of provincial roads, county roads, township roads, general roads, and other roads are different.) Whether there are charging stations, etc., only the mileage cost, time cost, or the number of roadway characteristics are used as weights. The method is different from the actual electric vehicle traffic consumption, and cannot be specifically applied to the navigation system of the electric traffic vehicle.

The main purpose of the present invention is to provide a navigation path planning computer program product for an electric vehicle, and define a path objective function by using the mileage cost and the overall power consumption weight, and calculating an optimized path after calculating the total mileage cost of each path. In order to provide a navigation computer program product that is more in line with electric traffic vehicles.
According to an object of the present invention, a navigation path planning computer program product is provided, which mainly considers an overall power consumption factor in a consideration factor for planning an optimization path; the navigation path planning computer program product is applicable to a navigation system, and The navigation system is configured on a vehicle computer, a notebook computer, a map navigation computer, a handheld computer, a smart phone, etc., and is not limited; a navigation path planning program is loaded by a navigation system, and the navigation system includes a map data. A map database, an input interface, a processing unit, and an output interface; perform the following steps:


S1: The user defines a starting point as a current point by using the input interface and the map database, and the navigation path planning program plans a plurality of paths from the current planning point to the end point. n;
S2: the processing module uses the map database and the current planning point to load map information including a plurality of relay nodes and map information of loading a plurality of charging station locations; and find each adjacent to the current planning point A relay node is each path i (i = 1, 2, ..., i, ... N paths), each path i includes a relay node, and if there is a charging station on the path i, the path i also includes the path Charging station location;
S3: The processing module calculates a total mileage cost F _i of each path i by using a route objective function F(n) of the navigation path planning program; wherein the path objective function F(n) is As defined by equation (1):

Where F(n) is the total mileage cost function of path n, G(n) is the cost-consuming cost function, and H(n) is the residual mileage cost function; where H(n) residual mileage cost function is as in equation (2) Expanded:

Where h(n) is the linear distance cost function from the current planning point to the end point, W(n) is the overall power consumption weight function; and equation (2) represents the residual mileage cost function H(n) is the linear distance cost of the residual mileage. The product of the function h(n) and the overall power consumption weight function W(n), that is, the residual mileage cost is not only the cost of the distance, but should also be multiplied by the weight of the overall power consumption;
S4: the navigation path planning program minimizes the path objective function F(n), that is, finds the minimum total mileage cost F* of the paths, and calculates the relay node corresponding to the minimum total mileage cost, which is defined as An continuation of an approaching node; wherein the optimized path is a set of paths that travel from the starting point along at least one of the contiguous traveling nodes to the end point; wherein the total mileage cost of each path i is F _i And the path objective function is optimized as in equations (3) and (4):


S5: when the electric traffic vehicle travels to the connecting traveling node, the navigation path planning program determines whether the connecting traveling node is the end point;
S6: when the determination result in step S5 is NO, the navigation path planning program re-defines the connection traveling node to the above starting point, and repeatedly performs the above steps S1 to S5; the output interface outputs the navigation path planning program execution At least one of the process or execution results.
Wherein, in the step S3, the mileage cost function G(n) is the actual consumed mileage cost function G ₁ (n) of each relay node that has actually passed through the starting point, and the upcoming mileage cost The sum of the functions G ₂ (n), the overall power consumption weight W is the weight of the charging station defined by the location of the charging station Weight with road The product, such as formula (5) and formula (6);


Calculate the i-th using the equation (5) with the path objective function F(n), the cost-consuming cost function G(n), the actual cost-consuming cost function G ₁ (n), and the forthcoming mileage cost function G ₂ (n) When the total mileage cost of the path is F _i , the cost mileage G _i of each path i of each of the relay nodes adjacent to the current planning point is found in the open list, and the residual corresponding to each path i Mileage cost H _i ; wherein the cost of mileage G _i is the sum of the actual cost-consuming mileage G _1i of each relay node that has actually passed through the starting point and the forthcoming mileage cost G _2i ; The mileage cost H _i is calculated from the linear distance cost h _{i of} the relay node to the end point and the overall power consumption weight W of each path i.
Preferably, the navigation path planning computer program product of the present invention, the navigation path planning program of the navigation system further performs the following steps in step S1:
S11: The navigation path planning program lists each of the relay nodes adjacent to the current planning point into an open list.
The following steps are further performed in step S5:
S51: The navigation path planning program includes the connection traveling node in a close list.

Preferably, the navigation path planning computer program product of the present invention, when the processing module calculates the total mileage cost F _i of each path i by one path objective function F(n) of the navigation path planning program, the overall consumption The electric weight W is the charging station weight defined by the charging station position Weight with road The product is as in (6);

Among them, the weight of the charging station It can be decomposed into the mileage cost contribution (charge station active weight Ws) due to the location of the charging station and the mileage cost contribution (charging station type weight Wst) due to the type of charging station, as in equation (7);

The road weight It can be decomposed into mileage cost contribution (road priority Wr) due to road grade, power consumption contribution (power consumption rate weight Wc) due to different road grades, and power consumption contribution due to different road connection levels ( Link road type weight Wct), as in equation (8):

Preferably, the navigation path planning computer program product of the present invention further includes a weight database that stores various weight data, including the charging station active weight Ws, the charging station type weight Wst, and the road priority. The data of the weight Wr, the power consumption rate weight Wc and the connected road type weight Wct; may be input and updated by the user in advance through the input interface, or may be pre-downloaded and updated or built in the weight database via the navigation system, and the weight database may also be used. Combined with the map database, it is not limited.

In a subsequent embodiment, the proposed embodiment weights the charging station
Road weight You can define your own style:
(1) The value of the active station weight Ws of the charging station, such as: the weight value of the charging station in service, the value of the charging station without the service weight, is not limited;
(2) The value of the weight of the charging station type Wst, such as: the weight value of the fast charging station type, the weight value of the charging station replacement station type, and the weight value of the mobile charging station type, which are not limited;
(3) The value of the road priority weight Wr, such as: highway priority weight value, fast road priority weight value, provincial road priority weight value, county road priority weight value, township priority weight value, urban main road priority weight value, The weight value of the secondary road priority in the urban area and the weight value of the lane priority are not limited;
(4) The value of power consumption rate weight Wc, such as: highway power consumption weight value, fast road power consumption weight value, provincial power consumption weight value, county power consumption weight value, rural road power weight value, urban area The value of the main road power consumption weight, the urban secondary road power consumption weight value, and the lane power consumption weight value are not limited;
(5) The value of the road type weight Wct, such as the ring type weight value, the general road type weight value, the main road type weight value, the system interchange type weight value, the integrated intersection type weight value, the interchange type weight value, The weight value of the side lane type and the weight value of the rest station type are not limited.

The computer program product of the navigation path of the electric traffic vehicle of the present invention may have one or more of the following advantages:
(1) The navigation path planning computer program product of the present invention can plan the navigation path of the electric traffic vehicle through a processing module by using the map information of the map database, and calculate the electric traffic vehicle from a starting point. An optimized path for a relay node to reach an end point; the electric vehicle can be brought to the end point from the starting point with a minimum total mileage cost.
(2) The navigation path planning computer program product of the present invention uses the mileage cost and the power consumption weight as the path objective function in the optimized path planning, thereby the most important power consumption factor of the electric traffic vehicle to the mileage cost. Weighting, so that the path objective function is consistent with the most basic needs of the electric vehicle, the best path obtained by the operation not only considers the mileage cost, but also the power consumption factor; compared with the conventional technology, due to the existing satellite navigation When the path planning computer program product is applied to the electric traffic vehicle, the consideration factor of the planned optimization path does not include the power consumption factor, so that the electric vehicle is driven due to different road conditions or the total mileage cost due to charging. Increase, that is, the driving path is not a shortcoming of the true optimized path of the electric traffic vehicle; furthermore, since the electric traffic vehicle has limited power, it is often required to be charged due to insufficient power in the middle, and the navigation path of the electric traffic vehicle in the conventional technology Planning, not considering the mileage cost caused by charging, so that the electric vehicle must still find a charging station to a certain location. Path from the optimum, thus making the navigation ineffective.
(3) The navigation path planning computer program product of the present invention can be integrated with various power consumption factors in order to be more realistic with the electric traffic vehicle in the optimized path planning, and the weighted power consumption factor. For example, the active weight of the charging station, the weight of the charging station, the weight of the road, the weight of the power consumption rate, and the weight of the connected road types improve the accuracy and practicability of the navigation of the electric vehicle.
(4) The present invention provides a navigation computer program product for an electric traffic vehicle, which can be loaded into a navigation path planning program by using a navigation system, and the user uses the input interface and the map database to define a starting point and an end point, and navigate. The path planning program uses the map information and data data of the map database to calculate the best path with the minimum mileage cost that has considered the power consumption factor. It is displayed on the display interface and provided to the electric vehicle vehicle driver for reference.

In order to make the present invention more clear and detailed, the preferred embodiment and the following drawings are used to describe the structure of the present invention and its technical features as described later.
Please refer to FIG. 2 , which is a schematic diagram of a navigation path planning computer program product of the present invention. In the figure, the navigation path planning computer program product 10 includes a navigation system 11 and a navigation path planning program 12, which will be The navigation path planning program 12 is loaded to execute the navigation path planning. The navigation system 11 is composed of a map database 111, an input interface 112, a processing module 113, and an output interface 114. The map database 111 stores the driving. The location of the location, the type of road, the type of connected road, the distance (or the coordinates of each location), and even the location of the charging station in the map database 111, whether the charging station is capable of charging, the type of charging station, etc.; The processing module 113 is generally composed of hardware, software and firmware, and can receive data entered by the input interface 112, obtain data from the map database 111 or other databases (such as the weight database 13), execute software programs, and perform mathematics. Or logic operations, etc., and displaying the computed information on the output interface 114. Please refer to FIG. 3 , which is a schematic diagram of the application of the navigation path planning computer program product of the present invention. The navigation system 11 is depicted by a map navigation computer, and the weight database 13 can be read by a memory card (such as an SD card). Take, but not limited to this; the best path after the operation can be displayed on the screen of the map navigation computer (output interface 114).

Referring to FIG. 5, it is a schematic diagram showing a planning method of a navigation path planning method according to an embodiment of the present invention. In the figure, a navigation path planning method is planned to calculate an electric vehicle from a starting point Ps via a relay node Pr1 and a relay. Node Pr2 (path 1: Or via the relay node Pr1 via the charging station Cs and the relay node Pr3 (path 2: ) and arrive at the optimal route of the end point Pt. Referring to FIG. 4, it is a schematic flowchart of a method for guiding a navigation path according to an embodiment of the present invention. In the figure, the navigation path planning method includes the following steps:
S1: using the map database 111, defining a current planning point Pc, planning a plurality of paths n from the current planning point Pc to the ending point Pt; and including each relay node (Pr) adjacent to the current planning point Pc An open list; wherein, if the electric traffic vehicle starts from the starting point Ps, when the path is first planned, the starting point Ps defines a current planning point Pc; if the electric vehicle carrier line reaches the relay node Pr1 under planning When a path is used, the relay node Pr1 is the defined current planning point Pc;
S2: using the map database 111, loading map information of each relay node (Pr) of the adjacent current planning point Pc and map information of each charging station position (Cs) loaded into the adjacent current planning point Pc Finding each relay node adjacent to the current planning point Pc as each path i (i=1, 2, . . . , i, . . . N paths), each path i includes at least one relay node, if the path i There is a charging station, and the path i also includes the charging station location;
In the steps S1 and S2, the preferred embodiment is applied to the navigation path planning computer program product 10 of the present invention. The navigation system 11 or the user uses the input interface 112 to define the starting point Ps as a current planning point Pc. The navigation system 11 uses the map information of the map database 111 to include each of the relay nodes adjacent to the current planning point Pc in the open list. Further, after the user sets the starting point Ps and the ending point Pt by the navigation path planning computer program product 10 in the electric traffic vehicle, and determines to start the planning path, the navigation system 11 starts the navigation path planning program 12 From the map database 111 (the map database 111 is located in the database of the navigation path planning computer program product 10 or the cloud system database), a map containing a plurality of charging station locations Cs and a plurality of relay nodes Pr is loaded. Information, and lists the plurality of relay nodes that need to pass through the optimization path from the starting point Ps to the ending point Pt, and then defines the starting point Ps as a current planning point Pc, and then each adjacent The relay nodes Pr of the starting point Ps are included in the open list. For example, if the user takes the station as the starting point Ps and the Taipei is the end point Pt, the relay node (Pr) adjacent to the station includes Dajia, Houli and Fengyuan, so the system will list the three relay nodes of Dajia, Houli and Fengyuan into the open list; for different display design, the navigation system 11 can open the list or other resources. It is displayed on the output interface 114.
S3: Calculating a total mileage cost F _i of each path i by a path objective function F(n); wherein the total mileage cost F _i is defined by the path objective function F(n), as in equation (9):

Wherein F _i is the path of the total mileage cost i's, G _i is the cost mileage costs, H _i is the residual mileage costs; wherein the path i of H _i residual mileage costs may be as formula (2) are defined, with the total mileage cost F _{i is} calculated as equation (10):

Where h _i is the straight-line distance cost of the current planning point Pc of the path i to the end point Pt, and W _i is the overall power consumption weight value of the path i; the formula (10) represents the residual mileage cost function H _i is equal to the straight-line distance cost h of the residual mileage _{i is} the product of the overall power consumption weight value W _i ; wherein the mileage mileage cost G _i of the path i is the actual mileage cost G _1i and the upcoming mileage consumed by each relay node that has actually passed through the starting point Ps The sum of the cost function G _2i and the overall power consumption weight W _{i is the} weight of the charging station defined by the location of the charging station Weight with road The product of.
Charging station weight Can be the product of the charging station active weight Ws and the charging station type weight Wst; road weight The product may be the product of the road priority weight Wr, the power consumption rate weight Wc, and the connected road type weight Wct; therefore, the total mileage cost F _{i is} calculated as Equation (11);

In step S3, the preferred embodiment is applied to the navigation path planning computer program product 10 of the present invention. The processing module 113 and the navigation path planning program 12 calculate the total mileage cost for each path i according to the path objective function F(n). F _i , as in the above three relay nodes of Dajia, Houli and Fengyuan, the processing module 113 and the navigation path planning program 12 calculate the total mileage cost F ₁ via the Dajia, and the total mileage cost F after the passage. ₂ and the total mileage cost F ₃ via Fengyuan; for different display designs, the navigation system 11 can display the total mileage cost of each path and its size order or other information on the output interface 114.
S4: Minimizing the path objective function F(n), that is, finding the minimum total mileage cost (F _{i, i=1, n} ) of the paths in each path is F*, and calculating the minimum total mileage cost The corresponding relay node is defined as a splicing node Pa (approaching node); wherein the optimized path is a path set that travels from the starting point Ps along at least one of the contiguous traveling nodes Pa to the end point Pt .
In step S4, the preferred embodiment is applied to the navigation path planning computer program product 10 of the present invention. The processing module 113 and the navigation path planning program 12 find a minimum total mileage cost among the total mileage costs F _i . F*, and the corresponding relay node is defined as a continuous travel node Pa. Furthermore, taking the above three nodes of Dajia, Houli and Fengyuan as an example, assuming that there is a charging station in the path of Dajia and the total mileage cost F is the lowest, then the navigation path planning computer program product 10 immediately selects a large A relay node Pr acts as a relaying node Pa, indicating that the big armor is the relay node of the next driving; for different display screen designs, the navigation system 11 can map each path and the preferred connecting node Pa or other information. The display or text is displayed on the output interface 114.
S5: When the electric vehicle is traveling to the connecting node Pa, it is determined whether the connecting node Pa is the end point Pt; if the connecting node Pa is the ending point Pt, the connecting node Pa is included in a closed list.
In step S5, the preferred embodiment is applied to the navigation path planning computer program product 10 of the present invention. In step S5, when the electric vehicle is traveling to the connecting node Pa, the connecting node Pa is included in the closing list. Taking the above three nodes of Dajia, Houli and Fengyuan as an example, since the big armor has been selected as the continuous traveling node Pa in step S4, the user drives the electric traffic vehicle to the big armor, and the navigation path at this time The planning computer program product 10 will include the continuation of the node A of the big armor in the closed list, so as to indicate that the big arm has passed and will not be included in the calculation in the next calculation. In addition, it is worth mentioning that, in step S5, the remaining relay nodes Pr each adjacent to the current planning point Pc are serialized into the open list, that is, the two relay nodes in Houli and Fengyuan will Included in the open list for the next calculation. For different display designs, the navigation system 11 can display a close list, an open list, or other information on the output interface 114 as a graphic or text.
S6: When the determination result in the step S5 is NO, the connection traveling node Pa is redefined as the above-mentioned starting point Ps, and the above steps S1 to S5 are repeatedly executed.
In step S6, the preferred embodiment is applied to the navigation path planning computer program product 10 of the present invention. The navigation path planning computer program product 10 determines whether the big armor is the end point Pt, and if the big armor is not set by the user. At the end point Pt, the continuation of the travel node Pa is newly defined as the starting point Ps, and steps S1 to S5 are repeated, that is, the big armor is regarded as the starting point Ps, and then the planning path is continued until the continuation of the traveling node Pa is The end point Ps is used to plan the optimization path; if the big armor is the end point Ps set by the user, the step ends. For different display designs, the navigation system 11 can display the immediate status or other information of the navigation path plan on the output interface 114 as a graphic or text.
In order to make the preferred embodiment of the present invention clearer, please refer to FIG. 5, which is a schematic diagram showing the planning of the navigation path planning method according to the preferred embodiment of the present invention. As shown in Figure 5, Ps is the starting point, Pr1, Pr2, and Pr3 are relay nodes, and Pt is the end point, where the electric traffic vehicle travels from the starting point Ps to the relay node Pr1 (in this case) After the node Pr1 is the starting point for starting the next path planning, that is, the current planning point Pc), there will be two relay nodes Pr2 and Pr3 (path 1 and path 2) to calculate the total mileage cost F _i (i= 1, 2 of the two paths). Further, G ₁ is the actual cost of the mileage from the starting point Ps to the relay node Pr1, and G _2i (i=1, 2) is the relay node Pr1 to the relay node Pr2 (path 1) or the relay node Pr1. The mileage cost to the relay node Pr3 (path 2) is further consumed; further, G _2i is the product of the distance from the i-th path relay node Pr1 to the relay node (Pr2 or Pr3) and the road priority weight Wri, and In h _i (i=1, 2), h ₁ is the linear distance cost of the relay node Pr1 to the end point Pt (path 1) or the relay node Pr2 to the end point Pt (path 1), and h ₂ is a relay node The linear distance cost from Pr3 to the end point Pt (path 2).
Wherein, in terms of the total mileage cost F _{1 of the} relay node Pr2 (path 1), its G ₁ is the actual consumed mileage cost from the starting point Ps to the relay node Pr1, and the G ₂₁ is the relay node Pr1. Towards the point cost of the relay node Pr2 (path 1), further, G ₂₁ is the product of the distance between the relay node Pr1 and the relay node Pr2 and the road priority weight Wr1, and h ₁ is the relay node. The linear distance cost from Pr2 to the end point Pt (path 1) and h ₂ are the linear distance costs from the relay node Pr3 to the end point Pt (path 2).
For another embodiment, as shown in FIG. 3, the navigation path planning computer program product 10 includes a navigation system 11, a navigation path planning program 12, and a weight database 13, wherein the weight database 13 includes charging station weights. Weight with road The information, for the non-limiting embodiment, can be input by the user, built in the navigation path planning computer program product 10, or can be downloaded from the cloud, as in the following example:
(1) The value of the active station weight Ws of the charging station, such as:

Whether the charging station on the path is in service (in operation) or not in service (out of service), giving different weights.
(2) The value of the charging station type weight Wst, such as:

Different weights are given to different types of charging stations on the path, such as a fast charging station that requires a higher mileage cost, and a rechargeable battery replacement station that can replace the battery (removing the entire battery pack and replacing it with another battery) With the mobile charging station (such as a tow battery with a battery behind the car for quick replacement), the mileage cost is close, and the same weight is given in this embodiment.
(3) The value of the road priority weight Wr, such as:


The choice of various roads on the path is given different weights according to their different mileage costs.
(4) The value of the power consumption rate weight Wc, and it is mainly set according to the reference rate of the road type, such as:

There are different power consumption benchmarks for various roads on the path, and different weights are given according to different mileage costs; usually the power consumption reference can be referenced by the speed of various roads.
(5) The value of the road type weight Wct, such as:


There are different mileage costs for various connected roads connected by roads on the path, and different weights are given according to different mileage costs.
The overall power consumption weight W _i is the product of the charging station active weight Ws, the charging station type weight Wst, the road priority weight Wr, the power consumption rate weight Wc, and the connected road type weight Wct in the path i; therefore, for the path 1 (relay) From node Pr2 to end point Pt), the overall power consumption weight W ₁ = Ws ₁ * Wst ₁ * Wr ₁ * Wc ₁ * Wct ₁ . If the path of the relay node Pr1 to the relay node Pr2 does not have a charging station, and the road type of the traveling path is a highway, and the connected road type is a system communication channel, the active weight of the charging station Ws ₁ is 1 The road priority weight Wr ₁ is 0.8; the power consumption rate weight Wc ₁ is 0.033; the connected road type weight Wct ₁ is 1; and the charging station type weight Wst ₁ can be 1, according to which the overall power consumption weight W the multiplication result is ₁ * 1 * 1 * 0.8 * 1 0.033.
Similarly, in terms of the total mileage cost F _{2 of the} relay node Pr3 (path 2), its G ₁ is the actual cost of the mileage from the starting point Ps to the relay node Pr1, and the G ₂₂ is the relay node. The distance from Pr1 to the relay node Pr3 is about to be further consumed. Further, G ₂₂ is the product of the distance between the relay node Pr1 and the relay node Pr3 and the road priority weight Wr, and h ₂ is the relay node Pr3 to the end point. Straight distance cost of Pt.

In addition, if the path of the relay node Pr1 to the relay node Pr3 has the charging station Cs, and the type of the charging station Cs is a rechargeable battery replacement station, and the road type of the traveling path is a highway, the road type is connected. For the system exchange channel, the current station weight Ws of the charging station is 0.5; the road priority weight Wr is 0.8; the power consumption rate weight Wc is 0.033; the connected road type weight Wct is 1 and the charging station type weight Wst is 0.4. According to this, the product of the overall power consumption weight W is 0.5*0.8*0.033*1*0.4. Therefore, after comparing the total mileage cost F of the relay nodes Pr2 and Pr3, it can be found that the total mileage cost F _{2 of the} relay node Pr3 is small, so that the planned path will use the relay node Pr3 as the optimal path.
In order to make the preferred embodiment of the present invention clearer, please refer to FIG. 2 and FIG. 6A to FIG. 6D together. FIGS. 6A to 6D are diagrams showing a preferred embodiment of the present invention applied to a navigation path planning computer program. Schematic diagram of the planned path of the product. As shown in the figure, after the above steps are started, the step S1 is used to use the map information to define the starting point as a current planning point Pc, and to include each of the relay nodes Pr adjacent to the current planning point Pc. List. Furthermore, the user sets A as the starting point and E as the ending point. When starting the planning path, the system defines the starting point A as the current planning point Ps and the three relay nodes B1 and B2. And B3 is included in the open list.
In step S2, the navigation system 11 causes the processing module 113 to start calculating the total mileage cost F _i via the paths i of B1, B2, and B3 in accordance with the path objective function F(n) described above. More specifically, since the total power consumption weight W of the residual mileage cost H includes a charging station active weight Ws, only the starting point A has a charging station Cs1 in the path to the relay node B1, so the relay node B1 The total mileage cost F is small, and the route from the departure point A to the relay nodes B2 and B3 will not pass through the charging station, so the total mileage cost F will be larger than that of the relay node B1.
In step S3, the processing module 113 and the navigation path planning program 12 calculate the total mileage cost F _i corresponding to each of the relay nodes (each path i) respectively adjacent to the current planning point Pc in the open list. . Further, after the above calculation, the processing module 113 and the navigation path planning program 12 calculate the total mileage cost F _i of each of the relay nodes B1, B2, and B3 according to the equation (11) in step S3. The F ₁ system 30 of the node B1, the F ₂ system 60 of the relay node B2, and the F ₃ system 70 of the relay node B3.
In step S4, the processing module 113 and the navigation path planning program 12 find a minimum total mileage cost F* among the total mileage costs F _i and define the corresponding relay node as a continuous traveling node Pa. Further, since in step S3, the F ₁ system 30 of the relay node B1, the F ₂ system 60 of the relay node B2, and the F ₃ system 70 of the relay node B3 are found, the processing module 113 And the navigation path planning program 12 further finds the relay node B1 in step S4 because its F ₁ system is the smallest, and thus the relay node B1 is defined as the connection traveling node Pa, and the navigation path planning computer program product 100 outputs at this time. The interface 114 displays a screen as shown in Fig. 6A.
It is determined in step S5 whether or not the subsequent traveling node Pa is the end point Pt. Furthermore, when the user drives the electric vehicle to the relay node B1, the navigation path planning computer program product 10 will include the relay node B1 in the shutdown list, thereby indicating that the relay node B1 has passed and is calculated in the next calculation. Not included in the calculation, in addition, the navigation path planning computer program product 10 will include relay nodes B2 and B3 in the open list. In addition, since the connection traveling node Pa is the relay node B1 and the end point is E, the determination result is no, so the direct connection node Pa is newly defined as the starting point Ps, that is, the relay is directly performed in step S6. The node B1 is redefined as the starting point Ps, and then steps S1 to S5 are repeatedly performed. It is worth mentioning that in the process of repeated execution, in the open list with the relay node B1 as the starting point Ps, the navigation path planning computer program product 10 will relay the nodes B2, B3, C1, C2 and C3. In the open list, in the preferred embodiment, since the relay nodes B2 and B3 are considered to go back through a verification mechanism, the relay nodes B2 and B3 are then excluded from the open list.
In the next iterative process, the relay node B1 is the starting point Ps, the path has relay nodes C1, C2, and C3, and the charging station Cs2, and the computer program product 10 is planned via the navigation path according to formula (11). A preferred path is selected. For example, there is a charging station Cs2 on the path of the relay node C2. After the operation, the total mileage cost F is small, so that the continuous traveling node is C2. At this time, the navigation path planning computer program product 10 The output interface 114 displays the picture as shown in FIG. 6B, and since the relay node C2 is not the end point E, steps S1 to S5 are repeated.
During the second iteration, the navigation path planning computer program product 10 selects a preferred path from the relay nodes D1, D2, and D3. For example, although there is a charging station Cs4 on the path to the relay node D1, The path is higher through the lane, the road priority weight Wr and the power consumption rate weight Wc are higher, so the total mileage cost F is larger, and the total mileage cost F of the relay node D2 is smaller, so that the continuous traveling node Pa is connected. The system is D2. At this time, the display interface 114 of the navigation path planning computer program product 10 displays the screen as shown in FIG. 6C, and since the relay node D2 is not the end point E, steps S1 to S5 are repeatedly executed.
In the subsequent process of the third iteration, the route to the destination E is planned, and the optimized path P* as shown in Fig. 6D is planned.
The features and spirit of the present invention will be more apparent from the detailed description of the preferred embodiments. On the contrary, the intention is to cover various modifications and equivalents within the scope of the invention as claimed.

10. . . Navigation path planning computer program product

11. . . Navigation System

111. . . Map database

112. . . Input interface

113. . . Processing module

114. . . Output interface

12. . . Navigation path planning program

13. . . Weight database

A. . . Starting point

B1, B2, B3. . . Relay node

C1, C2, C3. . . Relay node

Cs, Cs1, Cs2, Cs3, Cs4, Cs5, Cs6. . . charging station

D1, D2, D3. . . Relay node

E, Pt. . . Terminal point

Pa. . . Following the node (approaching node)

Pc. . . Current plan point

Pr, Pr1, Pr2, Pr3. . . Relay node

Ps. . . Starting point

R*. . . Optimized path

S1~S6. . . Steps

Figure 1 is a schematic diagram of a conventional technology path planning method;
2 is a structural diagram of a computer program product of the navigation path planning of the present invention;
Figure 3 is a schematic diagram of the application of the navigation path planning computer program product of the present invention;
4 is a schematic diagram showing steps of executing a navigation path planning program of a navigation path planning computer program product according to a preferred embodiment of the present invention;
5 is a schematic diagram showing the path planning of a navigation path planning computer program product according to a preferred embodiment of the present invention; and FIGS. 6A to 6D are diagrams showing the path planning of a preferred embodiment of the present invention applied to a navigation path planning computer program product. schematic diagram.

10. . . Navigation path planning computer program product

11. . . Navigation System

111. . . Map database

112. . . Input interface

113. . . Processing module

114. . . Output interface

12. . . Navigation path planning program

13. . . Weight database

Claims (10)

A navigation path planning computer program product is loaded into a navigation path planning program by a navigation system. The navigation system comprises a map database, an input interface, a processing module and an output interface; and the following steps are performed:
S1: The user defines a starting point as a current planning point by using the input interface and the map database, and the navigation path planning program plans a plurality of paths from the current planning point to the end point;
S2: the processing module uses the map database and the current planning point to load map information including a plurality of relay nodes and map information of loading a plurality of charging station locations, wherein each path includes a relay node;
S3: the processing module calculates a total mileage cost of the path of the current planning point through the relay node by using a route objective function of the navigation path planning program;
S4: the navigation path planning program minimizes the total mileage cost, and calculates the relay node corresponding to the minimum total mileage cost, and defines it as a continuous traveling node; wherein the optimized path is a set of paths that travel from the starting point along at least one of the successive traveling nodes to the end point;
S5: when the electric traffic vehicle travels to the connecting traveling node, the navigation path planning program determines whether the connecting traveling node is the end point;
S6: when the determination result in step S5 is NO, the navigation path planning program re-defines the connection traveling node to the above starting point, and repeatedly performs the above steps S1 to S5; the output interface outputs the navigation path planning program execution At least one of the process or execution result;
Wherein, the path objective function is a total mileage cost function of each path, which is an additive combination of a cost mileage function and a residual mileage cost function;
Wherein, the cost-consuming cost function is a combination of an upcoming mileage cost function and an actual cost-of-cost function; wherein the cost-cost function is the above-mentioned path from the starting point that has actually passed through the path Following the actual cost of the node, the actual cost of the mileage is the mileage cost of the route from the current planning point to the relay nodes.
The residual mileage cost is the product of the straight line distance cost from the relay nodes to the end point and an overall power consumption weight.

The navigation path planning computer program product according to claim 1, wherein the navigation system further comprises a step S11 in performing the step S1:
S11: Include each of the relay nodes adjacent to the current planning point in an open list;
In the step S5, the step S51 is further included:
S51: The connected travel node is included in a close list.

For example, in the navigation path planning computer program product described in claim 1, the navigation path planning program uses the path objective function to calculate one of the paths of the current planning point through the relay node in step S3. Mileage cost, wherein the overall power consumption weight is the product of one of the charging station weights defined by the charging station location and a road weight.

For example, in the navigation path planning computer program product described in claim 3, the navigation path planning program is in step S3, the charging station weight is the product of the active weight of the charging station and the weight of a charging station type; wherein the road The weight is the product of a road priority weight, a power consumption rate weight, and a link road type weight.

The navigation path planning computer program product according to claim 4, wherein the navigation system further comprises a weight database, wherein the weight database stores data of the charging station weight and the road weight, and the user uses the input interface. Pre-inputted, pre-downloaded via the navigation system or built into one of the weight databases or a combination thereof.

The navigation path planning computer program product according to claim 5, wherein the weight database includes the charging station active duty weight, the charging station type weight, the road priority weight, the power consumption rate weight, and the connected road type Weight data.

The navigation path planning computer program product according to claim 6, wherein the power consumption rate weight data of the weight database includes: a highway power consumption weight, a fast road power consumption weight, and a provincial road power consumption. At least one of the weight, the power consumption of a county road, the power weight of a township road, the weight of a main road in an urban area, the weight of a secondary road in an urban area, and the weight of a lane.

The navigation path planning computer program product according to claim 6, wherein the weighted database of the linked road type weight data includes: a ring type weight, a general road type weight, a main road type weight, and a At least one of system channel type weight, one type of intersection type weight, one type of channel type weight, one type of class weight, and one rest station type weight.

The navigation path planning computer program product according to claim 6, wherein the charging station type weight data of the weight database comprises: a fast charging station type weight, a charging battery replacement station type weight, and a mobile charging One of the data of the station type weight; wherein the charging station active weight data of the weight database comprises: at least one of a charging station service weight, and a charging station no service weight data.

For example, the navigation path planning computer program product described in claim 6 wherein the weight priority data of the weight database includes: a highway priority weight, a fast road priority, a provincial priority, and a county priority At least one of the weight, the priority of a township, the priority of a major road in a city, the priority of a secondary road in a city, and the priority of a lane.