第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
A Route Search Method for Electric Vehicles in Consideration of ....pdf
2011 IEEE Intelligent Vehicles Symposium (IV)
Baden-Baden, Germany, June 5-9, 2011
978-1-4577-0891-6/11/$26.00 ©2011 IEEE
920
Abstract— In this paper, we propose a new route search method for electric vehicles (EVs), which calculates a route with stopping over charging stations to have extra battery charge when current remaining charge is not enough to reach the destination. In this method, firstly we divided cases into three; the case of reaching the destination straight from the departure point, the case of stopping at one charging station and the case of stopping at several charging stations. In the cases of stopping over at least one charging station, potential charging stations are selected first, and then a route is obtained by Dijkstra’s algorithm from routes with some of those stations. Travel distance, estimated travel time between charge stations and time to fully charge after the EV’s arrival at each charging stations are calculated and also used for the calculation of travel cost between charging stations. Offering these routes for EV users will eliminate some of the major concerns about EVs such as limited range or sparse charging stations and will contribute to the spread of EVs. In order to confirm appropriateness of the route and examine the impact of increased execution time by this method, authors implemented the method and compared its execution time with that of conventional route search method. As a result, we confirmed that this method calculates routes with accessible charging stations according to the EV’s range. We also found that the search of charging stations with this method requires extra execution time, but the time increases by less than a half of the time required for the search of the route with some of these stations by conventional method. I. INTRODUCTION In recent years, many car companies are getting active in development and production of electric vehicles (EVs) as a measure against global warming and exhaustion of fossil fuels. Unlike internal combustion engine vehicles (ICEVs) which use fossil fuels, EVs only use electricity while running. Electricity generated by solar power or nuclear power generation does not consume fossil fuels and emits less greenhouse gases. Also ICEVs are less efficient in energy conversion than generation of electricity. Moving from ICEVs to EVs should contribute to ecology. Thus, some governments are promoting EVs and subsidy programs for EV are operated in Japan, the U.S., Europe and so on. But there are still some disadvantages of driving EVs. (1) The range of EVs, more specifically travel distance without recharging batteries, is shorter than that of ICEVs because of the limited capacity of the batteries. (2) Battery charging stations are not common enough to be found everywhere Y. Kobayashi, N. Kiyama and H. Aoshima are with Hitachi, Ltd., Yokohama Research Laboratory, 292, Yoshida, Totsuka, Yokohama, Kanagawa, 244-0817 Japan (e-mail: {yuichi.kobayashi.ma, noboru.kiyama.sn, hirokazu.aoshima.mw} @hitachi.com). M. Kashiyama is with Hitachi Automotive Systems, Ltd., 4-12-6, Higashishinagawa, Shinagawa, Tokyo, 140-0002 Japan (e-mail: masamori.kashiyama.cv@hitachi.com). needed. In order to eliminate concerns of users about shortage of charging stations, information services which provide charging stations’ information such as a location or availability are implemented in Japan [1][2]. These services provide information over the Internet and devices such as smartphones or car navigation units can receive the information. They can be seen as telematics services for EVs, but users must think about remaining battery charge and locations of charging stations by themselves while driving. Thus it is not a comprehensive solution to eliminate the concerns. In this paper, a route search method for EVs is proposed. The method takes EV’s range and location of charging stations into account. If the vehicle could not reach the destination with remaining battery at that time, some charging stations are selected as potential stations. Route distance between charging stations, estimated traveling time and estimated charging time required at a charging station are used for the calculation of traveling cost between the stations in the search. Then the most cost effective route is selected based on Dijkstra’s algorithm [3] from routes with appropriate charging stations on the way to the destination. Offering such route to EV users will eliminate some of the major concerns in driving EVs and contribute to the spread of EVs. This method was implemented to evaluate efficiency of this route search method and its impact on execution time. Then using location data of hypothetical charge stations, execution time of the implementation was compared with that of conventional search method. Through the evaluation, it was confirmed that the route was a combination of sub routes within the range and led to the destination from the departure point. In comparison with conventional route search method, the proposed method requires extra calculation for searching potential charging stations. But in the evaluation, the execution time required for searching potential charging stations was less than the execution time for searching a route with some of those charge stations. This paper is organized as follows. In Section 2, we introduce the related work. The detailed description of the method is given in Section 3. In Section 4, we describe experimental results from the simulations. Finally, Section 5 concludes this paper. II. PRIOR WORK A. Telematics Services Telematics services for ICEVs are provided from various car companies in the world. Telematics are services which use on-board communication units such as a mobile phone A Route Search Method for Electric Vehicles in Consideration of Range and Locations of Charging Stations Yuichi Kobayashi, Noboru Kiyama, Hirokazu Aoshima and Masamori Kashiyama
921
and provide information such as car traffic information or weather information, giving remote control of vehicle air-conditioner or door lock, etc., aiming to improve functionality of vehicles. Examples of such telematics services are G-BOOK1 [4] of Toyota or OnStar2 [5] of General Motors. Those services have been provided for ICEVs. B. Route Search Algorithm There have been several attempts for improving accuracy of route search algorithm itself or using traffic information to provide the most suitable route based on the traffic situation at the time, and in order to achieve the objective, those search systems take advantage of growing ITS (Intelligent Transportation Systems) infrastructures such as VICS (Vehicle Information and Communication System) [6] or TPEG (Transport Protocol Experts Group) [7]. UTOSPF[8] proposed a route search algorithm which calculates an optimum route based on real-time traffic information provided from sensor network comprised of road side terminals. Kono et al.[9] proposed a route search system which uses information such as real-time traffic information and geometric information such as inclination of the route, then calculates optimum route in terms of not route distance but gas consumption by avoiding congested points or ascending slope. There were researches of route search algorithm which uses other kinds of information. Kim et al.[10] proposed a route search algorithm considering time, distance, cost and safety of travel. Since the route search taking these four factors into account is NP complete, an approximate optimum route is provided using genetic algorithm. Zhang et al. [11] proposed a route search algorithm which provides the best route for sightseeing based on tourist information on web or visibility of scenic sites. III. THE ALGORITHM OF PROPOSED METHOD In the proposed method, we provide a route called “EV Assist Route.” EV Assist Route is a route which allows user to stop over some charging stations to charge a battery before it being dead if the EV can not directly reach destination with the current remaining charge. Thanks for charging at charging stations on the way, the EV can reach the destination. EV needs to reach the destination or some charging stations before running short of battery charge. Thus the proposed method firstly selects potential charging stations, and then searches the best route from routes with some of the selected charging stations. To provide EV Assist Route, this method needs to search 1 G-BOOK is a trade mark or a registered trade mark of Toyota in Japan or some other countries. 2 OnStar is a trade mark or a registered trade mark of OnStar in the United State or some other countries. the most cost effective route from routes with some charging stations. The cost mentioned here means a traveling distance or travel time required to move from one point to another and it will be described in detail later. This algorithm would provide a route with the minimum traveling cost from several potential routes which allows user to stop over at some charging stations. When the number of charging stations between the starting point and the destination is small, such as two for example, every potential route can be calculated. But there could be a much larger number of charging stations on the potential routes. Thus it is not feasible to search all of them. In this algorithm, travel time between charging stations is pre-calculated to accelerate route search. The algorithm uses conventional route search algorithm for the search of sub routes between points on a route. Sub route means a route from the departure point to a charging station, a route between charging stations and a route from a charging station to the destination. If this route search function is defined as F, input parameters for F are start point and end point. Output parameters of F are a route, distance of the route and traveling time of the route. Hereafter, R(P1, P2) stands for calculated route between start point P1 and end point P2, D(P1, P2) stands for route distance and T(P1, P2) stands for traveling time. Connection of routes is described by the “+” symbol. That means a route from point S to point G via point T is described as R(S, T) + R(T, G). Details of the algorithm are described as follows. Input and output parameters for the algorithm are defined as shown in Table I. Remaining Battery Level and Battery Level when TABLE I INPUT/OUTPUT DATA FOR/FROM PROPOSED METHOD Data Parameter Symbol Remaining Battery Level BLR (kWh) Battery Level when Fully Charged BLF (kWh) Electric Mileage EM (km/kWh) Charging Stations (Location Information) CSi ( i = 0, 1, 2, … ) CSi’s Charging Efficiency CEi (kW) Departure Point (Location Information) Dep Input Destination (Location Information) Des Search Result of EV Assist Route EVR(Dep,Des) Travel Distance EVD(Dep,Des) (km) Travel Time EVT(Dep,Des) (h) Remaining Battery Level After EVs’ Arrival BLA (kWh) Output Potential Stopover Charging Station SCSj ( j = 0, 1, 2, … )
922
Fully Charged between input parameters should be retrieved from the vehicle. Electric Mileage can be calculated from the driving record of the vehicle. Location and Charging Efficiency of a charging station described in the latter part are provided by database and Departure Point and Destination are given by user. (The Departure Point could be specified with the current position of the vehicle.) Reachable range of the vehicle is calculated with Electric Mileage and Remaining Battery Level. Reachable Range RR is calculated by EMBLRRR×= Likewise reachable range with full charged battery RF is calculated by EMBLRFF×= As described above, information of charging stations consists of location, charging type and so on. Currently charging is mainly divided into two types, “normal charge” and “quick charge”. Normal charge is compatible with ordinary electric outlet at home. But it requires quite a longer charging time such as several hours and is not suitable for use during travel. On the other hand, quick charge takes a shorter charging time, such as around 30 minutes, but it requires dedicated infrastructure of electricity. This prevents wide spread of charging stations having the quick charge facility. In this proposed method, the difference between normal charge station and quick charge station is expressed by Charging Efficiency, which is equivalent to output electric power. Charging Efficiency is expected to be provided by database along with location of charging stations. Details of this algorithm are to be described below for four cases, A: case of not dropping at any charging stations, B: case of dropping at one charging station, C: case of dropping at more than two charging stations and D: case of no route successfully reaching destination. A. Case of not dropping at any charging stations If the vehicle can reach the destination straight from the departure point with the current battery charge, conventional route calculation should be efficient. Thus using conventional route search result R(Dep, Des), route distance D(Dep, Des), travel time T(Dep, Des), and remaining battery level after EV arrival (BLA) are calculated and provided as EV Assist Route. BLA is calculated by EMDesDepDBLBLRA/),(−= B. Case of dropping at one charging station If the vehicle can not reach the destination straight from the departure point with the current battery charge, firstly overlapping area of two circles shown below are calculated. Circle 1: A circle having the departure point Dep as the center and reachable range RR as the radius. Circle 2: A circle having the destination Des as the center and reachable range with full charged battery RF as the radius. When there is ’one’ charging station in the overlapping area, the vehicle can go from the departure point to the destination, stopping over at the charging station and getting fully charged. Because of calculation cost, overlapping area is calculated with Euclidean distance, not with route distance, then the route is verified to see if the charging station on the route is really reachable with its route distance. If only one route is found, the route is provided as EV Assist Route for the case. If several routes are available, the most cost effective route is selected as EV Assist Route. Further details are described for the case that several charging stations are available in the overlapping area. Fig. 1 shows a situation where two charging stations are available in the overlapping area, CS1 is a normal charge station and CS2 is a quick charge station. When user prefers less travel distance, a route with CS1 is provided. When user prefers less travel time, a route with CS2 is provided. This is because of big difference of charging time between normal charge and quick charge; extra travel time for long distance is less than extra time for normal charge. In order to make a selection, it is necessary to evaluate extra time required for the longer driving distance and difference in charging time caused by charging types. In this method, charging time is calculated based on remaining battery level when arriving at the charging station and charging type of the charging station, and the charging time is added to travel time of the sub-routes. When driving from point A to charging station CSi and fully charged at the station, charging time at CSi is stated as CT(A, CSi). If point A is the departure point Dep, iiRFiCEEMCSDepDBLBLCSDepCT/)/),((),(+−=If point A is a charging station CSh ( h = 0,1,2… ) , iihihCEEMCSCSDCSCSCT/)/),((),(= Thus total driving time EVT(Dep, Des) with charging time Fig. 1. An Example of EV Assist Route with One Charging Station.
923
being taken into account is ),(),(),(),(DesCSTCSDepCTCSDepTDesDepEVTiii++= Comparing such total driving time, a decision is made as to whether to select a quick charging station despite longer driving distance or normal charging station accessible with shorter driving distance. Once a charging station to stop at is selected, conventional route search result including the station, driving distance of the route, EVT(Dep, Des) of the route and total driving time and remaining battery level at the destination is provided as EV Assist Route. The route, total driving distance and remaining battery level at the destination are calculated as below. EMDesSCSDBLBLDesSCSDSCSDepDDesDepEVDDesSCSRSCSDepRDesDepEVRFA/),(),(),(),(),(),(),(11111−=+=+= When there is not an overlapping area or no available charging station is located in the overlapping area, EV Assist Route with several charging stations is calculated in a way described in the next paragraph. C. Case of dropping at two or more charging stations When EV can not reach the destination from the departure point with the current remaining charge and there is no available charging station in the overlapping area described in the above paragraph, a route with several charging stations is searched. As the first step of this search, potential charging stations are selected. Distance L stands for distance between the departure point and the destination. L/2 and reachable range RR are compared and a bigger value is used for the radius of two circles. The center of one of the circles is the departure point and the center of the other circle is the destination. Also two common tangential lines of those circles are drawn. Charging stations in an area surrounded with those two circles and two common tangential lines are selected potential charging stations (Fig. 2). The reason to define the radius of the circles as L/2, in case L/2 > RR, is to avoid having a smaller number of potential charging stations because of a smaller area to search potential charging stations. On the other hand, the reason to define the radius as RR, in case L/2 < RR, is to have all charging stations in the range reachable with the current remaining charge as potential charging stations. The more charging stations are taken into account as potential stopping over points, the less likely it becomes to exclude better routes from search, but at the same time the more calculation time is required to search route. Thus this method restricts the area of potential charging stations as described above. Traveling cost between neighboring points is calculated with the departure point Dep, the destination Des and potential charging stations CSi and then the total travel cost and travel route from Dep are calculated using Dijkstra’s algorithm. The criteria to determine neighboring points is that if the starting point is the departure point, the ending point is in the range reached with the remaining battery charge and if the starting point is not the departure point, the ending point is in the range reached with the fully charged battery. The definition of the traveling cost would vary according to priority in the expected route. If traveling distance is prioritized, distance between points should be used for the calculation of traveling cost. If traveling time is prioritized, traveling time between points and charging time at potential charging stations should be used for the calculation of traveling cost. The traveling cost C(P1, P2) in case of prioritizing traveling time is, if P1 is the departure point, ()iiiCSDepTCSDepCTCSDepC,),(),(+= if P2 is the destination, ()()DesCSTDesCSCii,,= Fig. 2. The Regions to Search for Potential Charging Stations. (a) In Case of RR > L/2, (b) In Case of RR < L/2 Fig. 3. An Example of EV Assist Route with Two or more Charging Stations.
924
if both P1 and P2 are potential charging stations CSi and CSj, ()()jijijiCSCSTCSCSCTCSCSC,),(,+= In case of Fig. 3, for example, the route with CS1 and CS2 is the result for EV Assist Route if traveling distance is prioritized, but the route with CS3, CS4 and CS5 is the result for EV Assist Route, since there are more quick charging stations among the potential charging stations. Once potential charging stations SCS1…j (j=2,3,…) are determined, the route with those stations, total driving distance of the route, total driving time of the route and remaining charge at the destination are provided as EV Assist Route. The route and the total driving distance are, ),(),(),(),(),(),(),(),(1111DesSCSDSCSDepDSCSDepDDesDepEVDDesSCSRSCSDepRSCSDepRDesDepEVRjj+++=+++=LL Total driving time is, ),(),(),(),(),(),(),(),(11212111DesSCSTSCSSCSCTSCSSCSTSCSSCSCTSCSSCSTSCSDepCTSCSDepTDesDepEVTjjjjj+++++++=−−L Remaining battery level after arrival of EV (BLA) is, EMDesSCSDBLBLjFA/),(−= In order to accelerate execution time, travel distance D(CSi, CSj) travel time T(CSi, CSj) and charging time required after arrival CT(CSi, CSj) are calculated for each neighboring charging stations in advance. In preparation of this, the criteria to consider two charging stations as neighboring stations is whether traveling distance between them is less than 320km. This is longer than the range of EV today, but the range can be extended in the future and extension of the range is in fact under consideration. In the search of EV Assist Route, driving distance between two charging stations based on those values is used to determine if they are neighboring stations. When the driving distance is less than reachable range with a fully charged battery, the stations are judged to be neighboring, and the distance is used in Dijkstra’s algorithm. It is to reduce the execution time of conventional search function F in the search. D. Case of no route leading to the destination In the two cases shown below, it is not feasible to reach the destination with remaining battery charge at the departure point. 1. Destination is out of range from the departure point and no charging station is available in the range. 2. Traveling cost derived by Dijkstra’s algorithm is infinite when you try to stop over at two ore more charging stations. In these cases, it is announced that reaching destination is not likely to be accomplished and conventional route search result with R(Dep, Des), D(Dep, Des) and T(Dep, Des) is provided as reference information. In order to show range with remaining battery charge at the departure point, the route is to be shown in two parts, reachable part and unreachable part, in different colors for example. IV. SIMULATION AND EVALUATION In order to evaluate efficiency of the proposed EV Assist Route, a system which shows the route on a map was implemented and examined with hypothetical charging stations and charging efficiency data. The system was implemented with the algorithm putting priority on driving time, and applied to Japanese map. Hypothetical charging stations were selected up to 2500, the locations of those charging stations were selected randomly from those of existing gas stations. Random selection from about 40,000 existing gas stations can distribute hypothetical charging stations in the same way as the gas stations in the real world with more in cities and less in country sides. Also 2200 stations were set as normal charge stations and 300 stations were set as quick charge stations. In this evaluation, Battery Level when Fully Charged was set to 24kWh, Electric Mileage was set to 5km/kWh, that means range with fully TABLE III EVALUATION RESULT BY PROPOSED METHOD No. Departure Point Destination BLR (kWh) RR (km)Travel Distance (km) Travel Time(h) # ofSCSPOI Search Time(s) Route SearchTime(s)Total Search Time(s) 1 Narita Airport Maihama Station 4 20 62.7841.5421 3.46 7.06 10.52 2 Narita Airport Maihama Station 12 60 58.4340.8740 2.71 5.63 8.34 3 Narita Airport Maihama Station 24 12058.4340.8740 2.78 5.63 8.41 4 Narita Airport Hachioji Station 4 20 121.9413.0332 6.40 13.41 19.81 5 Narita Airport Hachioji Station 12 60 112.7722.3031 6.41 16.20 22.61 6 Narita Airport Hachioji Station 24 120109.5481.6520 4.24 9.09 13.33 7 Narita Airport Atami Station 4 20 200.5224.9532 6.01 16.98 22.99 8 Narita Airport Atami Station 12 60 200.5224.7862 6.29 16.98 23.27 9NaritaAirportAtamiStation241201679533834167413982072
925
charged battery was 120km. Also Charging Efficiency was set as 2kW for normal charge and 48kW for quick charge, and charging time for full charge was 12 hours for normal charge and 30 minutes for quick charge. In the evaluation of execution time of the algorithm, three variations of range for remaining charge were evaluated for each of three different sets of departure point and destination: that means 9 patterns of route searches. In the evaluation, execution time was measured in two parts, execution time for selecting potential charging stations (POI; Point of Interest Search Time) and for searching route with some of the selected charging stations using conventional route search method (Route Search Time). The execution time was measured three times for each pattern and average times are shown in Table II. Seeing the result of execution time, POI Search Time was less than half of Route Search Time. The proposed method requires extra execution time for POI Search and Route Search with the restriction of stopping over some charging stations before exceeding the range reachable with the remaining battery charge. Even though these execution times can be considered as much shorter than manual selection of route by EV user; user selects charging station by himself and verifies if the route with the selected charging station enables him to reach the destination. We think the method is efficient enough to be used. Pre-calculation time for driving cost between charging stations was around one hour for this 2500 charging stations. It would also be efficient enough if update of charging stations is like weekly, etc. Seeing the cases with the same total driving distance, No.2 and No. 3, or No. 7 and No. 8, there was a difference in POI Search Time according to the range with remaining battery charge. We think the reason for the difference is that the number of potential charging stations increased according to the range and that the number of calculations for traveling cost increased. Same tendency can be seen in No. 7 and No. 9. Comparing to No. 9, No. 7 had more charging stations in the route but execution was done faster. This should be a result of pre-calculation of travel cost, and the number of accessible charging stations with remaining battery charge at the departure point is more dominant in total execution time than the number of charging stations in the route. In order to evaluate appropriateness of the route, EV Assist Route searches were executed 5 patterns each for 5 major Japanese cities, 25 patterns in total. For all of those routes, it was confirmed that the routes led to the destination with accessible charging stations. V. CONCLUSION In this paper, we proposed EV Assist Route to eliminate concerns for EV such as shorter range or shortage of charging stations. The proposed method provides a route which allows user to reach the destination stopping over appropriate charging stations before exceeding the range reachable with remaining battery charge. Further extension would be required in some aspects of the method. There were cases that the method provided a route which made user get off a highway halfway because the charge was running short on the highway. Thus making plan to charge before getting on a highway, for example, is expected. It may also be desirable to consider business hours of charging stations or information on charging station availability at the time. In addition, taking into account some factors such as temperature, traffic information or inclination of the route which affects battery performance or electric mileage would be beneficial to improve estimation of reachable range. Furthermore execution time should be accelerated by pre-calculation of travel cost between charging stations, etc. As mentioned above, we should seek further improvement of the method. REFERENCES [1] NAVITIME, Available: http://www.navitime.co.jp/pcstorage/html/ evcharge/ (only in Japanese) [2] Available: http://itunes.apple.com/my/app/id405936200?mt=8# (only in Japanese) [3] E.W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische mathematik, vol. 1, num. 1, p.p. 269-271, 1959. [4] G-BOOK, Available: http://g-book.com/pc/default.asp [5] OnStar, Available: http://www.onstar.com/web/portal/home [6] VICS, Available: http://www.vics.or.jp/english/vics/index.html [7] TPEG, Available: http://www.tpeg.org/ [8] K. Faez, and M. Khanjary , “UTOSPF: A distributed dynamic route guidance system based on Wireless Sensor Networks and Open Shortest Path First protocol,” IEEE International Symposium on Wireless Communication Systems 2008, p.p. 558-562, 2008. [9] T. Kono, T. Fushiki, K. Asada and K. Nakano, “Fuel Consumption Analysis and Prediction Model for “Eco” Route Search,” 15th World Congress on Intelligent Transport Systems, 2008. [10] B.K. Kim, J.B. Jo, J.R. Kim, M. Gen, “Optimal Route Search in Car Navigation Systems by Multi-objective Genetic Algorithms,” International Journal of Information, vol. 4, p.p. 9-18, 2009. [11] J. Zhang, and H. Kawasaki, and Y. Kawai, “Tourist Route Search System Based on Web Information and the Visibility of Scenic Sights,” 2nd International Symposium on Universal Communication, p.p. 154-161, 2008.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
