TWI845200B - A system and method of path planning based on charging station and computer-readable medium thereof - Google Patents

Abstract

The present invention provides a system and method of path planning based on charging station and computer-readable medium thereof including a data input module, a data preprocessing module and a path planning module, wherein the data input module inputs a starting and ending points, loading point information, vehicle information of the electric vehicle and charging station information, and then the data preprocessing module converts a mileage of the electric vehicle, distance matrix, power consumption matrix and time matrix. In this way, the path planning module obtains an initial path by the above information, and further obtains an optimal driving path according to the initial path after processing. Therefore, the present invention generates the optimal driving path through the above path planning technology to ensure that the electric vehicle has sufficient power during driving, thereby greatly improving the driving efficiency of the electric vehicle.

Description

A charging station-based route planning system, method, and computer-readable medium thereof

The present invention relates to a route planning technology, and more particularly to a route planning system, method and computer-readable medium based on a charging station.

With the development of technology and the promotion of the government, many people have become more interested in pure electric vehicles, so now electric vehicles have become one of the options that people consider when buying a car.

However, due to the limitations of electric vehicles in charging, such as the limited number of charging stations and the long charging time, the convenience of electric vehicles in driving is far lower than that of gasoline vehicles, causing many people to hesitate and unwilling to buy electric vehicles. Moreover, for freight operators, even if the government strongly supports the use of electric vehicles to transport goods to reduce environmental pollution, if the driving routes of electric vehicles are not well planned, it is easy to lead to significant restrictions on the transportation distance and time of electric vehicles.

Therefore, how to provide a route planning technology that can perfectly plan the driving route of electric vehicles to avoid the electric vehicle's power limiting its driving distance and time, thereby greatly improving the driving efficiency of electric vehicles, has become an issue that the industry urgently needs to solve.

In order to solve the above-mentioned known technical problems or provide related effects, the present invention provides a charging station-based route planning system, which includes: a data input module, which inputs the starting point, the loading point information, the vehicle information of the electric vehicle and the charging station information; a data pre-processing module, which is connected to the data input module and performs data screening based on the charging station information to obtain the usable charging station information, and then the data pre-processing module converts the starting point, the loading point information into the charging station information. The data is converted into data by the vehicle information, the vehicle information and the available charging station information to obtain the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle; and a path planning module is connected to the data pre-processing module to obtain an initial path according to the feasible driving range, the distance matrix, the power consumption matrix and the time matrix of the electric vehicle, and the path planning module further calculates to obtain an optimal driving path according to the initial path.

The present invention further provides a method for planning a route based on a charging station, comprising: a data input module inputting a starting point, a loading point information, vehicle information of an electric vehicle and charging station information; a data pre-processing module performing data screening according to the charging station information to obtain usable charging station information; the data pre-processing module converting the starting point, the loading point information, the vehicle information and the usable charging station information into a data input module; The charging station information used is used for data conversion to obtain the mileage, distance matrix, power consumption matrix and time matrix of the electric vehicle; a path planning module obtains an initial route based on the mileage, distance matrix, power consumption matrix and time matrix of the electric vehicle; and the path planning module further calculates to obtain an optimal driving route based on the initial route.

In the aforementioned embodiment, the data pre-processing module excludes charging stations with no remaining vacancies and charging stations of unqualified types based on the charging station information to obtain the available charging station information.

In the aforementioned embodiment, the route planning module uses the nearest neighbor method to determine the distance between the current location of the electric vehicle and the nearest loading point, and then determines whether the cargo volume of the nearest loading point meets the cargo capacity of the electric vehicle, and whether the electric vehicle can reach the nearest loading point or search point, so as to obtain the initial route.

In the aforementioned embodiment, when the cargo capacity of the electric vehicle is not met, the route planning module searches for the next nearest cargo point, or when the nearest cargo point or the checkpoint cannot be reached, the route planning module searches for the nearest charging station.

In the aforementioned embodiment, the path planning module uses the taboo search method to exchange the loading points in the initial path, calculate multiple first target values, and then use the path corresponding to the smallest target value among the multiple first target values as the first candidate solution. The initial path or the first candidate solution as the current solution is optimized (such as 2-optimization) to obtain an updated path as the second candidate solution, and when the maximum number of iterations is reached, the optimal driving path is obtained.

In the aforementioned embodiment, the path planning module determines whether the path corresponding to the first candidate solution is in a taboo list through a taboo search method, and if the path corresponding to the first candidate solution is not in the taboo list, then the optimization (such as 2-optimization) is performed according to the first candidate solution; conversely, if the path corresponding to the first candidate solution is in the taboo list, then the optimization (such as 2-optimization) is performed according to the current solution.

As can be seen from the above content, the charging station-based route planning system, method and computer-readable medium of the present invention mainly converts the starting point, loading point information, electric vehicle vehicle information and available charging station information into the electric vehicle's drivable mileage, distance matrix, power consumption matrix and time matrix to obtain an initial route, and further calculates based on the initial route to obtain an optimal driving route. Therefore, the present invention uses the above route planning technology to sort the stations and complete the planning route, thereby generating a route with a better estimated driving distance or time to ensure that the electric vehicle has sufficient power during driving, thereby greatly improving the driving efficiency of the electric vehicle.

1: Route planning system based on charging stations

11: Data input module

12: Data pre-processing module

13: Path planning module

S21 to S25: Steps

S24-1 to S24-12: Steps

S25-1 to S25-8: Steps

Figure 1 is a schematic diagram of the architecture of the charging station-based route planning system of the present invention.

Figure 2 is a schematic diagram of the process of the charging station route planning method of the present invention.

Figure 2A-1 and Figure 2A-2 are schematic diagrams of the process of the nearest neighbor method of the present invention.

Figure 2B is a schematic diagram of the process of the taboo search method of the present invention.

The following is a specific and concrete example to illustrate the implementation of the present invention. People familiar with this technology can easily understand other advantages and effects of the present invention from the content disclosed in this manual.

It should be noted that the structures, proportions, sizes, etc. depicted in the drawings attached to this specification are only used to match the contents disclosed in the specification for understanding and reading by people familiar with this technology, and are not used to limit the restrictive conditions for the implementation of the present invention. Therefore, they have no substantial technical significance. Any modification of the structure, change of the proportion relationship or adjustment of the size should still fall within the scope of the technical content disclosed by the present invention without affecting the effects and purposes that can be achieved by the present invention. At the same time, the terms such as "one", "first", "second", "upper" and "lower" used in this specification are only used to facilitate the clarity of the description, and are not used to limit the scope of the implementation of the present invention. The changes or adjustments in their relative relationships shall be regarded as the scope of the implementation of the present invention without substantially changing the technical content.

FIG1 is a schematic diagram of the structure of the charging station-based path planning system 1 of the present invention, and the charging station-based path planning system 1 includes: a data input module 11, a data pre-processing module 12 and a path planning module 13.

In one embodiment, the charging station-based path planning system 1 is established in a server (network server, general-purpose server, file server, storage unit server, etc.) or a computer or other electronic device with an appropriate calculation mechanism, wherein each module in the charging station-based path planning system 1 (the data input module 11, the data pre-processing module 12 and the path planning module 13) can be software, hardware or firmware; if it is hardware, it can be a processing unit, processor, computer or server with data processing and computing capabilities; if it is software or firmware, it can include instructions that can be executed by a processing unit, processor, computer or server, and can be installed on the same hardware device or distributed on different multiple hardware devices.

In one embodiment, the data input module 11 inputs the starting point, loading point information (such as location, cargo volume, etc.), electric vehicle vehicle information (such as remaining power, power consumption, battery capacity, cargo capacity, minimum power limit, applicable charging station type, etc.) or/and charging station information (such as location, brand, vacancy, charging power, etc.).

In one embodiment, the data pre-processing module 12 is communicatively connected to the data input module 11, and the data pre-processing module 12 determines whether the remaining space, the charging time and the charging station type are in compliance with the charging station information, and then selects the available charging stations, and calculates the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle.

In one embodiment, the route planning module 13 is communicatively connected to the data pre-processing module 12, and performs route planning to generate an optimal driving route to ensure that the electric vehicle will not have a problem of insufficient power during driving. At the same time, the route planning module 13 outputs a planned route result, and the planned route result includes an estimated total driving distance and a total driving time.

FIG2 is a schematic diagram of the process of the charging station route planning method of the present invention, and FIG1 is also referred to for explanation.

In step S21, a data input module 11 inputs a call point, a loading point information, an electric vehicle vehicle information and/or a charging station information.

In step S22, a data pre-processing module 12 receives the origin, the loading point information, the vehicle information and/or the charging station information, and performs data screening based on the charging station information to obtain usable charging station information from the charging station information.

In one embodiment, the data pre-processing module 12 excludes charging stations with no remaining vacancies and charging stations of unqualified types based on the charging station information to obtain the available charging station information. For example, unqualified charging stations are those whose charging specifications do not match the electric vehicle to be charged, so they are excluded.

In step S23, the data pre-processing module 12 converts the departure point, the loading point information, the vehicle information and/or the available charging station information to obtain the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle.

In step S24, a path planning module 13 uses various methods (such as the nearest neighbor method) to obtain an initial path based on the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle.

In one implementation, the path planning module 13 executes the nearest neighbor method or a similar method to obtain the initial path, wherein, as shown in FIG. 2A-1 and FIG. 2A-2, the nearest neighbor method includes the following steps:

In step S24-1, start: obtain the coordinates of the starting point and the current loading volume from the route planning module 13. For example: the current loading volume is set to 0 by default.

In step S24-2, the nearest loading point is searched: the route planning module 13 uses the time matrix to find the loading point j closest to the current location i of an electric vehicle according to the current location i (such as the starting point).

In step S24-3, the cargo capacity is checked: the path planning module 13 determines whether the cargo capacity of the nearest loading point j is greater than the cargo capacity of the electric vehicle. If the cargo capacity of the nearest loading point j is greater than the cargo capacity of the electric vehicle, step S24-4 is executed; otherwise, if the cargo capacity of the nearest loading point j is less than or equal to the cargo capacity of the electric vehicle, step S24-5 is executed.

In step S24-4, search for another nearest loading point: the path planning module 13 determines whether the loading capacity of all other loading points is greater than the loading capacity of the electric vehicle. If the loading capacity of all other loading points is greater than the loading capacity of the electric vehicle, execute step S24-12; on the contrary, if at least one of the loading capacity of all other loading points is less than or equal to the loading capacity of the electric vehicle, use the time matrix to obtain another nearest loading point j' from all other loading points, so that the path planning module 13 sets j = j' , and executes step S24-3.

In step S24-5, the remaining power is checked: the route planning module 13 calculates the remaining power of the electric vehicle when it reaches the nearest loading point j according to the power consumption matrix, and determines whether the remaining power when it reaches the nearest loading point j is less than the minimum power limit W _min of the electric vehicle. If the remaining power when it reaches the nearest loading point j is less than the minimum power limit W _min of the electric vehicle, step S24-8 is executed; otherwise, if the remaining power when it reaches the nearest loading point j is greater than or equal to the minimum power limit W _min of the electric vehicle, step S24-6 is executed.

In step S24-6, it is checked whether there is enough power to return to the search point after arriving at the nearest loading point: the path planning module 13 obtains the power consumption of the electric vehicle from the nearest loading point j to the search point according to the power consumption matrix, and determines whether the remaining power of the electric vehicle when arriving at the nearest loading point j is greater than the power consumption when returning to the search point. If the remaining power of the electric vehicle when arriving at the nearest loading point j is greater than the power consumption when returning to the search point, step S24-9 is executed; conversely, if the remaining power of the electric vehicle when arriving at the nearest loading point j is less than or equal to the power consumption when returning to the search point, step S24-7 is executed.

In step S24-7, it is checked whether there is enough power to reach the nearest charging station after arriving at the nearest loading point: the path planning module 13 obtains the power consumption of the electric vehicle from the nearest loading point j to the nearest charging station p according to the power consumption matrix, and determines whether the remaining power of the electric vehicle when arriving at the nearest loading point j is less than the power consumption when arriving at the nearest charging station p . If the remaining power when arriving at the nearest loading point j is less than the power consumption when arriving at the nearest charging station p , step S24-8 is executed; conversely, if the remaining power when arriving at the nearest loading point j is greater than or equal to the power consumption when arriving at the nearest charging station p , step S24-9 is executed.

In step S24-8, it is checked whether the nearest charging station can be reached from the current location: the path planning module 13 determines whether the remaining power of the electric vehicle can reach the nearest charging station p from the current location i according to the power consumption matrix. If the nearest charging station p can be reached from the current location i , step S24-11 is executed; otherwise, if the nearest charging station p cannot be reached from the current location i , the process ends.

In step S24-9, loading is performed: the path planning module 13 plans the electric vehicle to the nearest loading point j for loading, so that the path planning module 13 sets the current point i = the nearest loading point j , and determines whether there are other loading points. If there are other loading points, the charging station information is updated and the process returns to step S24-2; if there are no other loading points, the process executes step S24-10.

In step S24-10, check whether the vehicle can return to the detection point: the route planning module 13 determines whether the remaining power of the electric vehicle is sufficient to return to the detection point. If the remaining power of the electric vehicle can return to the detection point, step S24-12 is executed; otherwise, if the remaining power of the electric vehicle cannot return to the detection point, step S24-11 is executed.

In step S24-11, charging is performed: the path planning module 13 plans the electric vehicle to the nearest charging station p for charging, so that the path planning module 13 sets the current location i = the nearest charging station p , and determines whether there are other loading points. If there are other loading points, the charging station information is updated and the process returns to step S24-2; if there are no other loading points, the process executes step S24-12.

In step S24-12, the route is completed: the route planning module 13 plans the electric vehicle to return to the end point to obtain the initial route, and if all stations have been entered, it stops and goes to the nearest charging station for charging.

Returning to FIG. 2, in step S25, the path planning module 13 uses various heuristic algorithms (such as Tabu Search (TS)) to obtain an optimal driving path based on the initial path.

In one embodiment, the taboo search method is a heuristic algorithm that can solve combinatorial optimization problems, such as the traveling salesman problem (TSP). Furthermore, the taboo search method is based on the hill climbing algorithm, and a memory mechanism is added to include the neighboring optimal solutions that have been visited into the taboo list to avoid repeating the same movement mode in the past and to jump out of the local optimal solution as much as possible.

In one embodiment, the taboo search method will use a step-by-step method to find a better solution based on the initial path, and the taboo search method will give a penalty value to the infeasible solution caused by the cargo load and power, so as to change the order of the cargo points and charging stations in the initial path, and then find the best position of the cargo points and charging stations in the path to obtain the optimal driving path. As shown in FIG2B, the taboo search method includes the following steps:

In step S25-1, the path planning module 13 inputs the initial path as a current solution.

In step S25-2, the path planning module 13 exchanges the loading points in the initial path (the current solution) to calculate multiple first target values after the exchange (such as calculating the total driving distance or total driving time after the loading points are exchanged), and selects one of the minimum total driving distance or total driving time from the multiple first target values, and then uses the corresponding exchanged path as the first candidate solution.

In step S25-3, the path planning module 13 determines whether the path corresponding to the first candidate solution is in a taboo list, wherein if the two exchanged loading points are not in the taboo list, step S25-4 is executed; otherwise, if the two exchanged loading points are in the taboo list, step S25-5 is executed.

In step S25-4, the routing module 13 allows the two loading points to be exchanged to update the current solution to the first candidate solution, wherein if the first candidate solution does not meet the constraint, a penalty value is added.

In step S25-5, the routing module 13 does not allow the two loading points to be exchanged to maintain the current solution and updates the taboo list, wherein a penalty value is added if the current solution does not meet the constraint.

In step S25-6, the path planning module 13 performs optimization (such as 2-optimization) to select two non-adjacent loading points from the current solution or the first candidate solution, flip the path between the two loading points to obtain an updated path, and use the updated path as the second candidate solution, and calculate its second target value. If there is a charging station in the updated path, the charging station is moved to each position in the updated path to calculate the target value of each position of the charging station in the updated path, and the most improved position of the charging station in the updated path (i.e., the position with the least total driving length or total driving time) is selected as the second candidate solution.

In step S25-7, the path planning module 13 determines whether the process has reached the maximum number of iterations. If the maximum number of iterations has been reached, the final solution (i.e., the optimal driving path) is obtained and the process ends; otherwise, if the maximum number of iterations has not been reached, step S25-8 is executed.

In step S25-8, the path planning module 13 increases the number of iterations by 1, updates the taboo list, and returns to step S25-2 to exchange the loading points in the updated path and execute subsequent steps.

The following is a specific embodiment of the schematic diagram of the structure of the charging station route planning system 1 of the present invention, and is also explained with reference to Figures 1 and 2.

In this embodiment, a data input module 11 inputs the starting and ending points, the loading point information, the vehicle information of the electric vehicle and/or the charging station information, wherein the starting and ending points include a starting point O and a loading point P, and the coordinates of the starting point O are O(0,0) and the coordinates of the loading point P are P(0,0); the loading point information includes a first loading point A, a second loading point B and a third loading point C, and the coordinates of the first loading point A are A(2,3) and the loading volume is 3, the coordinates of the second loading point B are B(5,6) and the loading volume is 2, and the coordinates of the third loading point C are C(3,8) and the loading volume is 1; the vehicle information includes the initial remaining power is 100%, the power consumption is 0.1 (i.e., 1 kWh of electricity is consumed to start 0.1 unit distance ), battery capacity is 100kWh, cargo capacity is 10 units (such as 10 boxes, etc.), minimum power limit is 20%, applicable charging station type is X brand charging station; the charging station information includes the first charging station a, the second charging station b, the third charging station c and the fourth charging station d, and the location, brand, vacancy and charging power of these charging stations a, b, c, d are respectively: the first charging station a={(3,7), X, yes, 120kw}; the second charging station b={(3,3), X, no, 120kw}; the third charging station c={(6,6), Y, yes, 120kw}; the fourth charging station d={(5,5), X, yes, 120kw}.

Furthermore, a data pre-processing module 12 receives the starting point, the loading point information, the vehicle information and/or the charging station information from the data input module 11, and the data pre-processing module 12 performs data screening on the charging station information to exclude charging stations with no remaining space and incompatible types. Therefore, the data pre-processing module 12 excludes the second charging station b and the third charging station c to screen out the first charging station a and the fourth charging station d that can be used.

The data pre-processing module 12 calculates the charging time of the first charging station a and the fourth charging station d and the mileage of the electric vehicle based on the charging station information. Specifically, the charging time required for each 1% charge at the first charging station a and the fourth charging station d is about 0.5 minutes (the time required to charge from 0% to 100% is 100/120kw×60=50 minutes, and the charging time required for each 1% charge is 50 (minutes)/100%=0.5 minutes), and the vehicle information shows that the mileage for each 1% charge is 0.1 unit distance (0.1=0.1 (power consumption)×100 (battery capacity)/100%).

The data pre-processing module 12 calculates a distance matrix according to the coordinates of the starting point O, the search point P, the first charging station a and the fourth charging station d through a European distance calculation formula (1), as shown in Table 1 below, wherein the European distance calculation formula (1) is as follows:

Table 1: Distance Matrix

The data pre-processing module 12 calculates based on the distance matrix and the mileage per 1% of the electric power is 0.1 unit distance to obtain a power consumption matrix, and the power consumption matrix is shown in Table 2 below:

Table 2: Power Consumption Matrix

Taking the time factor into consideration, the data pre-processing module 12 first uses the quartile method to eliminate outliers based on the travel time in the historical arrival/departure data between each point, and then uses the average method to calculate the average of the historical travel time to obtain the time matrix between each point, and the time matrix is shown in Table 3 below:

Table 3: Time Matrix

In order to obtain the expected stay time of each loading point, the data pre-processing module 12 uses a linear regression method to calculate the regression curve of the stay time and delivery volume of each loading point based on the stay time and delivery volume in the historical arrival/departure data using the least square method, and then uses the regression curve and delivery volume to calculate the expected stay time of each loading point, and the expected stay time is shown in Table 4 below:

Table 4: Estimated duration of stay

A path planning module 13 executes a nearest neighbor method based on the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle to obtain an initial path.

Specifically, when the electric vehicle starts from the starting point O, the starting point O is taken as the current point i , and assuming that the amount of cargo loaded is 0, the power consumption is 0 and the power is 100%, the loading point j closest to the current point i is found according to the time matrix as the first loading point A.

In one embodiment, the path planning module 13 determines whether the cargo volume of the nearest loading point j (i.e., the first loading point A) is greater than the cargo capacity of the electric vehicle, and when the cargo volume (3) of the first loading point A is less than the cargo capacity (10) of the electric vehicle, the path planning module 13 calculates the remaining power of the electric vehicle when it reaches the first loading point A according to the power consumption matrix, for example: 100% (power of the electric vehicle) - 36% (power consumption when reaching the first loading point A) = 64% (remaining power when reaching the first loading point A), and determines that the remaining power when reaching the first loading point A (64%) is greater than the minimum power limit W _min (20%) of the electric vehicle.

Next, the route planning module 13 obtains the power consumption (36%) of the electric vehicle from the first loading point A to the search point according to the power consumption matrix, and when it is determined that the remaining power (64%) of the electric vehicle arriving at the first loading point A is greater than the power consumption (36%) of returning to the search point, the electric vehicle has enough power to return to the search point P. Therefore, the route planning module 13 plans the electric vehicle to the first loading point A for loading. In addition, there are still other stations that have not been entered (i.e., the second loading point B and the third loading point C), so the route planning module 13 updates the charging station information, and at this time, the first loading point A is taken as the current point i and the nearest loading point j is determined.

In one embodiment, the path planning module 13 determines whether the cargo volume of the nearest loading point j (i.e., the second loading point B) closest to the first loading point A is greater than the cargo capacity of the electric vehicle, and when the cargo volume (2) of the second loading point B is less than the cargo capacity of the electric vehicle (7=10-3), the path planning module 13 then determines the cargo volume of the second loading point B according to the power consumption matrix. The remaining power of the electric vehicle from the first loading point A to the second loading point B is calculated, for example: 64% (remaining power of the electric vehicle) - 42% (power consumption to reach the second loading point B) = 22% (remaining power to reach the second loading point B), and it is determined that the remaining power to reach the second loading point B (22%) is greater than the minimum power limit W _min (20%) of the electric vehicle.

Next, the route planning module 13 obtains the power consumption (78%) of the electric vehicle from the second loading point B to the search point according to the power consumption matrix, and when it is determined that the remaining power (22%) of the electric vehicle when arriving at the second loading point B is less than the power consumption (78%) when returning to the search point, the electric vehicle does not have enough power to return to the search point P. Therefore, the route planning module 13 obtains the power consumption (10%) of the electric vehicle from the second loading point B to the nearest charging station p (i.e., the second charging station d) according to the power consumption matrix, and when it is determined that the remaining power (22%) of the electric vehicle arriving at the second loading point B is greater than the power consumption (10%) of arriving at the second charging station d, the route planning module 13 plans the electric vehicle to carry goods at the second loading point B. In addition, there are still other stations that have not been entered (i.e., the third loading point C), so the route planning module 13 updates the charging station information, and at this time, the second loading point B is used as the current location i and the nearest loading point j is determined.

In one embodiment, the path planning module 13 determines whether the cargo volume of the nearest loading point j (i.e., the third loading point C) closest to the second loading point B is greater than the cargo capacity of the electric vehicle, and when the cargo volume (1) of the third loading point C is less than the cargo capacity of the electric vehicle (5=7-2), the path planning module 13 calculates the remaining power of the electric vehicle from the second loading point B to the third loading point C according to the power consumption matrix, for example: 22% (remaining power of the electric vehicle) - 28% (power consumption to reach the third loading point C) = -6%, to determine that the remaining power of the electric vehicle is insufficient to reach the third loading point C.

Next, the route planning module 13 plans the electric vehicle to charge at the second charging station d, and according to the remaining power (12%) of the electric vehicle when it arrives at the second charging station d, it is calculated that it takes 44 minutes for the electric vehicle to charge to 100%, for example: 44 minutes = (100%-12%) × 0.5 minutes. In addition, there are other stations that have not been entered (i.e., the third loading point C), so the route planning module 13 updates the charging station information, and at this time, the second charging station d is used as the current location i and the nearest loading point j is determined.

In one embodiment, the route planning module 13 determines whether the cargo volume of the nearest loading point j (i.e., the third loading point C) closest to the second charging station d is greater than the cargo capacity of the electric vehicle, and when the cargo volume (1) of the third loading point C is less than the cargo capacity (5) of the electric vehicle, the route planning module 13 calculates the remaining power of the electric vehicle from the second charging station d to the third loading point C according to the power consumption matrix, for example: 100% (remaining power of the electric vehicle) - 36% (power consumption when reaching the third loading point C) = 64%, and determines that the remaining power (64%) when reaching the third loading point C is greater than the minimum power limit W _min (20%) of the electric vehicle.

Next, the route planning module 13 obtains the power consumption (78%) of the electric vehicle from the third loading point C to the search point according to the power consumption matrix, and when it is determined that the remaining power (64%) of the electric vehicle when arriving at the third loading point C is less than the power consumption (85%) when returning to the search point, the electric vehicle does not have enough power to return to the search point P. Therefore, the path planning module 13 obtains the power consumption (10%) of the electric vehicle from the third loading point C to the nearest charging station p (i.e., the first charging station a) based on the power consumption matrix, and when it is determined that the remaining power (64%) of the electric vehicle arriving at the third loading point C is greater than the power consumption (10%) of arriving at the first charging station a, the path planning module 13 plans the electric vehicle to the third loading point C for loading.

In addition, the electric vehicle has entered all stations, so the route planning module 13 determines whether the electric vehicle has enough power to return to the search point P, and because the remaining power (64%) of the electric vehicle arriving at the third loading point C is less than the power consumption (85%) to return to the search point. Therefore, the route planning module 13 plans the electric vehicle to charge from the third loading point C to the nearest charging station p (i.e., the first charging station a), and the remaining power of the electric vehicle arriving at the first charging station a is 54%, so the route planning module 13 calculates that it takes 23 minutes for the electric vehicle to charge 100%, for example: 23 minutes = (100%-54%) × 0.5 minutes. Finally, the route planning module 13 plans the electric vehicle to return from the first charging station a to the detection point P.

Thus, the path planning module 13 obtains the initial path of the electric vehicle, namely: starting point O→first loading point A→second loading point B→second charging station d→third loading point C→first charging station a→query point P. Furthermore, the path planning module 13 obtains the total travel length of 21 distance units (21=3.6+4.2+1+3.6+1+7.6) according to the initial path and the distance matrix; the estimated travel time is 26 minutes (26=5+5+2+5+6+3) according to the initial path and the time matrix; and the estimated travel time is 26 minutes (26=5+5+2+5+6+3) according to the regression curves of the loading points A, B, C and the distribution The estimated stay time is 23 minutes (23=10+8+5); the estimated charging time is 67 minutes (67=44+23) based on the charging time of the charging stations a and d; and the estimated total driving time is 116 minutes (116=26+23+67) based on the estimated driving time, the estimated stay time and the estimated charging time.

In another embodiment, after the path planning module 13 obtains the initial path of the electric vehicle, a taboo search method is used to try to obtain the final solution, that is, the best driving path.

Specifically, the goal of this embodiment is to minimize driving time, and if the goal is to minimize driving distance, it can be done through a distance matrix.

Furthermore, the set definition of this embodiment is as follows:

N。 G : the set of all loading points, G

N.

N。 P : the set of all charging stations, P

N.

N : The set of all loading points and charging stations, where 0 represents the starting point and 0' represents the end point.

。 A : The set of all points connected by lines.

.

Next, the parameters and variables of this embodiment are defined as follows:

W _max : The maximum power limit of an electric vehicle.

W _min : The minimum power limit of an electric vehicle.

Q : Cargo capacity restrictions on electric vehicles.

d _ij : the distance from point i to point j .

t _ij : time from point i to point j .

r _ij : The power consumption required to travel from point i to point j .

z _j : the remaining power of the electric vehicle when it reaches point j .

q _j : cargo demand at point j .

x _ij : A binary variable, which is 1 if point i travels to point j , otherwise it is 0.

In addition, the restriction formula of this embodiment is used for the taboo search method, and the restriction formula is as follows:

Restriction (1): Each loading point can only be entered once at most.

x _ij

1

j

G

x _ij

1

j

G

Restriction (2): Each charging station can only be entered once at most.

x _ij

1

j

P

x _ij

1

j

P

Restriction (3): Each loading point must be entered and exited once.

(i,j)

A,i≠j

( i , j )

A , i ≠ j

Restriction (4): When the electric vehicle reaches each loading point, the remaining power cannot be less than the minimum power limit.

W _min

i

P z _i

W _min

i

P

Constraint (5): When the electric vehicle arrives at each charging station, the remaining power must be greater than 0.

0

i

P z _i

0

i

P

Restriction (6): When the electric vehicle reaches each loading point, the cargo volume must be less than or equal to the maximum cargo volume limit.

q _j

Q

i

G

q _​

Q

i

G

Constraint (7): The relationship between the power consumption of electric vehicles, that is, the remaining power of the electric vehicle when it arrives at each loading point minus the power consumption to the next loading point must be greater than the remaining power at the next loading point.

z _i

i

G∪{0},(i,j)

A z _i - r _ij

z _i

i

G ∪{0},( i , j )

A

Therefore, the taboo search method will use the shifting method (as shown in FIG. 2B ) to change the order of the loading points A, B, C and the charging stations a, d in the initial path to find the best positions of the loading points A, B, C and the charging stations a, d in the path.

Among them, the parameter values used in the taboo search method of this embodiment are as follows:

1. Maximum cargo capacity limit Q of electric vehicles: a fixed capacity limit for each vehicle. For example, the maximum cargo capacity limit Q is set to 10.

2. Maximum power limit W _max for electric vehicles: Each vehicle has a fixed maximum power limit. For example, the maximum power limit W _max is set to 100.

3. Minimum power limit W _min for electric vehicles: A fixed minimum power limit for each vehicle. For example, the minimum power limit W _min is set to 20.

4. Penalty value α for infeasible solution of cargo capacity: If the cargo capacity limit Q is exceeded after the step, the penalty value α is added to the target value. For example, the penalty value α is set to 1000.

5. Penalty value β for infeasible solution of electricity: If there is not enough electricity to reach the charging station or loading point after moving, the penalty value β is added to the target value. For example: the penalty value β is set to 1000.

6.Maximum Iteration: The maximum number of times the taboo search method is executed. When the maximum number of iterations is reached, the taboo search method stops executing. For example: the maximum number of iterations is set to 5.

For example, the path planning module 13 inputs the initial path (i.e., starting point O→first loading point A→second loading point B→second charging station d→third loading point C→first charging station a→query point P) as a current solution, and the path planning module 13 swaps the loading points in the initial path (the current solution). For example, the path planning module 13 swaps the first loading point A→second loading point B→second charging station d→third loading point C→first charging station a→query point P. The cargo point A and the second cargo point B are exchanged in sequence, the second cargo point B and the third cargo point C are exchanged in sequence, and the first cargo point A and the third cargo point C are exchanged in sequence, and the multiple first target values after the cargo point exchange are calculated respectively, so as to select one of the multiple first target values with the least total travel time, and then use the relative exchanged path as the first candidate solution.

Furthermore, after the path planning module 13 determines that the path corresponding to the first candidate solution is in a taboo list, the current solution is maintained and the taboo list is updated. In addition, if the path planning module 13 determines that the current solution does not meet the constraint, a penalty value (such as 1000) is added to the target value calculated by the current solution.

Then, the path planning module 13 performs optimization (such as 2-optimization) to select two non-adjacent loading points from the current solution, and flip the path between the two loading points to obtain an updated path, for example: select the first loading point A and the third loading point C to flip the stations between the first loading point A and the third loading point C, that is, starting point O→third loading point C→second loading point B→fourth charging station d→first loading point A→first charging station a→end point P.

In addition, since the updated path has the fourth charging station d, the path planning module 13 moves the fourth charging station d to each position in the updated path to calculate the target value (such as the total driving length) of the fourth charging station d at each position in the updated path, and selects the smallest target value of the fourth charging station d in the updated path as the second candidate solution.

Afterwards, the path planning module 13 determines whether the current process has reached the maximum number of iterations. If the maximum number of iterations has been reached, the process ends. Otherwise, if the maximum number of iterations has not been reached, the loading points in the updated path are exchanged, and the subsequent steps are executed until the maximum number of iterations has been reached, thereby obtaining an optimal driving path. (i.e. the final solution), for example: the optimal driving route is: starting point O→the fourth charging station d→the second loading point B→the third loading point C→charging station a→the first loading point A→the end point P, the total driving length is 7+1+2.8+1+4.1+3.6=19.5 distance units, which is better than the total driving length of the initial route of 21 distance units.

In summary, the charging station-based route planning system, method and computer-readable medium of the present invention converts the starting and ending points, loading point information, electric vehicle vehicle information and available charging station information into the electric vehicle's drivable mileage, distance matrix, power consumption matrix and time matrix to obtain an initial route, and further processes the initial route to obtain an optimal driving route. Therefore, the present invention uses the above-mentioned route planning technology to sort the stations and complete the planned route, thereby generating a route with a better estimated driving distance or time to ensure that the electric vehicle has sufficient power during driving, thereby greatly improving the driving efficiency of the electric vehicle.

1. The charging station-based route planning system and method of the present invention can analyze the starting and ending points, loading point information, electric vehicle vehicle information and charging station information to obtain the initial route using the nearest neighbor method, and then find a relatively better route through the taboo search method.

2. The charging station-based route planning system and method of the present invention analyzes the charging station information, eliminates unsuitable charging stations in advance, finds the currently suitable charging stations, and then performs route planning.

3. The charging station-based route planning system and method of the present invention analyzes the loading point information, performs pre-processing on the data, considers the estimated arrival time, and then performs route planning to improve the efficiency of route planning.

The above implementation forms are only illustrative of the principles and effects of the present invention, and are not intended to limit the present invention. Anyone familiar with this technology can modify and change the above implementation forms without violating the spirit and scope of the present invention. Therefore, the scope of protection of the present invention should be as listed in the scope of the patent application.

S21 to S25: Steps

Claims (13)

A charging station-based route planning system includes: 1. A data input module for inputting the departure and arrival points, loading point information, electric vehicle information, and charging station information; A data pre-processing module is communicatively connected to the data input module and performs data screening based on the charging station information to obtain the available charging station information. The data pre-processing module then performs data conversion on the departure point, the loading point information, the vehicle information and the available charging station information to obtain the electric vehicle's feasible driving range, distance matrix, power consumption matrix and time matrix; and A path planning module is communicatively connected to the data pre-processing module to obtain an initial path according to the mileage of the electric vehicle, the distance matrix, the power consumption matrix and the time matrix. The path planning module then further calculates to obtain an optimal driving path according to the initial path. As described in claim 1, the charging station-based route planning system, wherein the data pre-processing module excludes charging stations with no remaining vacancies and charging stations of unqualified types based on the charging station information, so as to obtain the available charging station information. As described in claim 1, the route planning system based on the charging station, wherein the route planning module uses the nearest neighbor method to determine the distance between the current location of the electric vehicle and the nearest loading point, and then determines whether the cargo volume of the nearest loading point meets the cargo capacity of the electric vehicle, and whether the electric vehicle can reach the nearest loading point or the search point, so as to obtain the initial route. A charging station-based route planning system as described in claim 3, wherein when the electric vehicle's cargo capacity is not met, the route planning module searches for the next nearest cargo point, or when the nearest cargo point or the checkpoint cannot be reached, the route planning module searches for a nearest charging station. As described in claim 1, the route planning system based on the charging station, wherein the route planning module uses the taboo search method to exchange the loading points in the initial route, calculate multiple first target values, and then use the path corresponding to the smallest target value among the multiple first target values as the first candidate solution, and optimize the initial route or the first candidate solution as the current solution to obtain an updated route as the second candidate solution, and when the maximum number of iterations is reached, the optimal driving route is obtained. A charging station-based path planning system as described in claim 5, wherein the path planning module determines whether the path corresponding to the first candidate solution is in a taboo list through the taboo search method, and wherein, if the path corresponding to the first candidate solution is not in the taboo list, the optimization is performed based on the first candidate solution; conversely, if the path corresponding to the first candidate solution is in the taboo list, the optimization is performed based on the current solution. A charging station-based route planning method includes: A data input module inputs the departure and arrival point, loading point information, electric vehicle vehicle information, and charging station information; A data pre-processing module performs data screening based on the charging station information to obtain usable charging station information; The data pre-processing module converts the departure point, the loading point information, the vehicle information and the available charging station information to obtain the feasible driving range, distance matrix, power consumption matrix and time matrix of the electric vehicle; A path planning module obtains an initial path according to the feasible driving range of the electric vehicle, the distance matrix, the power consumption matrix and the time matrix; and The route planning module further calculates to obtain an optimal driving route based on the initial route. The method for planning a route based on charging stations as described in claim 7 further includes the data pre-processing module excluding charging stations with no remaining vacancies and charging stations of unqualified types based on the charging station information to obtain the available charging station information. The charging station-based route planning method as described in claim 7 further includes the route planning module using the nearest neighbor method to determine the distance between the current location of the electric vehicle and the nearest loading point, and then determining whether the cargo volume of the nearest loading point meets the cargo capacity of the electric vehicle, and whether the electric vehicle can reach the nearest loading point or search point, so as to obtain the initial route. The charging station-based route planning method as described in claim 9 further includes the route planning module finding the next nearest loading point when the electric vehicle does not meet its cargo capacity, or finding the nearest charging station when the nearest loading point or the checkpoint cannot be reached. The charging station-based route planning method as described in claim 7 further includes the route planning module using a taboo search method to exchange the loading points in the initial route, calculate a plurality of first target values, and then use the path corresponding to the smallest target value among the plurality of first target values as the first candidate solution, and optimize the initial route or the first candidate solution as the current solution to obtain an updated route as the second candidate solution, and when the maximum number of iterations is reached, the optimal driving route is obtained. The charging station-based path planning method as described in claim 11 further includes the path planning module determining whether the path corresponding to the first candidate solution is in a taboo list through the taboo search method, and wherein, if the path corresponding to the first candidate solution is not in the taboo list, then the optimization is performed based on the first candidate solution; conversely, if the path corresponding to the first candidate solution is in the taboo list, then the optimization is performed based on the current solution. A computer-readable medium, used in a computing device or a computer, stores instructions for executing a charging station-based route planning method as described in any one of claims 7 to 12.

Images