001.docx CHEMICAL ENGINEERING TRANSACTIONS VOL. 83, 2021 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Jeng Shiun Lim, Nor Alafiza Yunus, Jiří Jaromír Klemeš Copyright © 2021, AIDIC Servizi S.r.l. ISBN 978-88-95608-81-5; ISSN 2283-9216 An Eco-friendly Path Guidance Algorithm for Electric Vehicle Nakyoung Yoo, Donggyun Ku, Minje Choi, Seungjae Lee* 163, Seoulsiripdae-ro, Dongdaemun-gu, Seoul, Republic of Korea, University of Seoul, South Korea. koo2646@naver.com At present, the automobile industry’s interest in eco-friendly electric vehicles is increasing and those vehicles are replacing vehicles using traditional fossil fuels. This study considers how to drive an electric vehicle with maximum efficiency depending on the terrain. Since electric vehicles have poor climbing ability, they have a limitation in that battery efficiency and it decreases when driving on the road with a steep slope. As the speed decreases and the driving distance becomes shorter, it reveals weaknesses on steep roads. In order to overcome this risk, the optimal route was searched using spatial information data. The slope of each link is derived by analyzing 3D spatial information data including geographic and geospatial elements. Since the efficiency of electric vehicles varies depending on the slope, the degree of reduction in the speed of the electric vehicle according to the slope and length of the link is analyzed. The weight for each link is given and applied to the following function. In general, in the transportation field, the BPR function, which is one of the types of VDF, is used to optimize the route and classify the shortest path. However, the slope of the road is not reflected in the current function. By adding a slope-related variable to this, a new VDF system and network are built by constructing a new form of functional formula that includes the speed-reduction weights. By using a* algorithm, the shortest path algorithm, to the constructed network, the path to the destination to be reached is optimized and implemented. Finally, a real-time route guidance system can be built based on this, and route information can be provided to with electric vehicle driver. As a result of the assignment to the traffic route, it was confirmed that there is a significant difference compared to the shortest route assigned simply by distance. In addition, the effectiveness was verified through comparative analysis of the total travel time difference and energy efficiency of the two methods. By applying this algorithm, it was confirmed that the efficiency of use of the electric vehicle was improved. The energy efficiency when performing the route search considering the terrain is about 1.794 higher than when performing a simple route search. The proposed approach helps to achieve the goal of efficient transportation and ultimately promotes green transportation. 1. Introduction With the advent of automobiles, the convenience of traffic has increased. However, as the number of automobiles increases, air pollution problems are emerging (Wei and Zheng, 2018). Automobile emissions increase ozone pollution and air pollution, ruining the global environment and causing climatic change. There is a need to provide the infrastructure for active, shared and zero emission transport modes, (Ku et al., 2020) and an evaluation process for eco-friendly infrastructure should be established (Kim et al., 2020). Accordingly, in recent years, an eco-friendly electric vehicle has appeared. Electric vehicles replace the vehicle's driving energy with electric energy rather than fossil fuels, so applying an optimal mix of energy to additional electrical requirements for the introduction of electric vehicles (Ubando et al., 2019) makes them a long-term clean and sustainable vehicle. To reduce transportation emissions, more than a certain number of electric vehicles are needed (Ramli et al, 2020). However, the slope angle of the uphill increases the electric car's power consumption (Yang et al., 2014). Also, driving on a slope consumes more energy than driving on the flat road or slope (Wai et al., 2015). There is a need to consider the slope. As interest in smart cities has increased, big data, a key enabler of smart transportation systems, is drawing attention (Samiksha et al., 2016). A navigation system or the like is proposed, which uses an information and communication technology to search a real-time traffic network and guide the optimal route according to the current situation (Chen et al., 2012). However, three-dimensional spatial information representing the z- coordinate of the terrain is not utilized. With the advent of the big data era, it is important to utilize useful data DOI: 10.3303/CET2183037 Paper Received: 30/06/2020; Revised: 14/08/2020; Accepted: 16/08/2020 Please cite this article as: Yoo N., Ku D., Choi M., Lee S., 2021, An Eco-friendly Path Guidance Algorithm for Electric Vehicle, Chemical Engineering Transactions, 83, 217-222 DOI:10.3303/CET2183037 217 onto transportation. By using this spatial information, it is possible to build a path finding algorithm and use the data more effectively. GIS was introduced in the algorithm to provide efficient route planning for product distribution and transportation vehicles (Sun, 2017) and it constituted a bi-objective optimization model to provide a route to minimize the distribution distance and transport risk of hazardous substance movement (Chen, 2018). In addition, other prior studies applied PNS and P-graph algorithms and software to enable optimal traffic assignment considering vehicle cost, emissions, and travel time (Barany et al., 2010). Some efficient electric vehicles have appeared, but this algorithm will play an important role in the current transition. The route searched algorithm considering the terrain can provide a more efficient route for the drivers. The purpose of this study is to find a method of utilizing 3D spatial information data that has not been previously considered and to be used as basic data for a traffic route system. 2. Research methodology 2.1 Electric vehicle energy consumption model The battery efficiency of electric vehicles is greatly influenced by the surrounding environment. For example, ambient temperature can affect the battery life of an electric vehicle (Qian et al., 2010), and Changes in driving range, power consumption and emissions due to ambient temperature (Yuksel and Michalek., 2015). Due to this influence, it is difficult to activate the electric vehicle. Especially in the case of a lot of mountainous terrain, the slope of the road affects the energy efficiency of the electric vehicle linearly (Liu et al., 2017). With reference to this, this study will ultimately improve battery usage efficiently by considering the longitudinal direction. In order to measure the energy consumption of electric vehicles for the route, a longitudinal role model according to various variables such as distance and altitude was used (Ehsani et al., 2018). In order to accelerate the vehicle, the electric motor must provide traction. Eq(1) can express the equation for traction force. 𝐹𝐹𝑇𝑇 = 𝑎𝑎 ∙ 𝑓𝑓 ∙ 𝑚𝑚 + 𝐹𝐹𝑅𝑅 (1) where FT is the fraction force by electric motor (N) and FR is the resistance to the vehicle (N). a is the vehicle acceleration (m/s2), f is the mass coefficient of rotating parts, and m is the vehicle mass (g). The resistance force acting on the vehicle is composed of grade, rolling, and air and is defined as follows. Eq(2) represents these three resistances. 𝐹𝐹𝑅𝑅 = 𝑚𝑚 ∙ 𝑔𝑔 ∙ 𝑠𝑠𝑠𝑠𝑠𝑠(𝛼𝛼) + 𝑚𝑚 ∙ 𝑔𝑔 ∙ 𝑐𝑐𝑐𝑐𝑠𝑠(𝛼𝛼) ∙ 𝑐𝑐𝑟𝑟𝑟𝑟 + 𝜌𝜌∙𝐴𝐴∙𝑐𝑐𝑐𝑐 2 ∙ 𝑣𝑣2 (2) where m∙g∙sin(a) is the grade resistances, m∙g∙cos(a)∙crr is the rolling resistances and 𝜌𝜌∙𝐴𝐴∙𝑐𝑐𝑐𝑐 2 ∙ 𝑣𝑣2 is the air resistances. g is the acceleration of gravity, a is the angle of inclination of the road, and crr is the coefficient of friction of the road. Air resistance is affected by speed (v), air density (ρ), vehicle front area (A), and air resistance coefficient (cw). A motor connected to the electric vehicle battery provides traction for vehicle movement. Eq(3) calculates the power consumption of the battery of the electric vehicle, and additional energy according to energy efficiency is consumed in the basic power consumption. 𝑃𝑃𝑒𝑒𝑒𝑒,𝑜𝑜𝑜𝑜𝑜𝑜 = 𝐹𝐹𝑇𝑇∙𝑣𝑣 𝜂𝜂𝜂𝜂 + 𝑃𝑃0 (3) where 𝜂𝜂𝜂𝜂 is the energy efficiency of transmission, motor and power conversion and P0 is the basic consumption of electric power. Auxiliary parts in the car case additional demand for electric power (P0), also known as primary consumption. Eq(4) shows the electric energy consumption model. 𝐸𝐸𝑒𝑒𝑒𝑒 = ∫ 𝑃𝑃𝑒𝑒𝑒𝑒 𝑇𝑇 0 𝑑𝑑𝑑𝑑 (4) This can be applied to the trip path to show an estimate of energy consumption. By applying several energy- related formulas, the energy consumption of an electric vehicle with altitude changes can be estimated. 2.2 Application of the terrain weight In order to construct a road finding algorithm and provide information about drivers, the optimal and shortest path algorithms are applied in the transportation field. In this algorithm, VDF values are assigned according to road grades for each link to perform route finding in consideration of vehicle speed and capacity. The road traffic cost function (VDF, volume-delay function) is a major factor influencing traffic demand prediction, such as traffic (O/D) and traffic analysis networks. Recently, as the demand for increasing the reliability of traffic 218 demand prediction is increasing, various improvement measures have been proposed through VDF improvement studies based on traffic surveys such as traffic volume and traffic speed (Kucharski and Drabicki, 2017). VDF is a function that calculates the travel time of a specific link according to the traffic level, and is a factor that directly affects the travel time calculation and route selection between the starting point and the ending point. The BPR function (Bureau of public roads, 1964), which is applied in Korea as one of the types of VDF, is based on the theory that the travel time of the link increases in proportion to the ratio of traffic to capacity based on free travel time. In this function, variables such as free speed, capacity and parameters are applied differentially for each road hierarchy. However, the BPR function does not reflect the slope of the road and judges it by setting the road section to a flat state, so it cannot reflect the increase in the travel time due to the slope. In order to develop a more accurate optimal path search, the analysis is performed by applying weights reflecting the characteristics of the electric vehicle to the BPR formula. To do this, the fuel consumption of the electric vehicle on the slope is taken into account and the weight is calculated according to the slope and free speed. Add the calculated weight as a slope-related variable and apply it to the equation. Eq(5) is the equation with the corresponding variable added, and Eq(6) is the equation for calculating the gradient variable. 𝑇𝑇𝑖𝑖 = 𝑇𝑇𝑖𝑖 0(1 + 𝛼𝛼(𝑣𝑣/𝑐𝑐)𝛽𝛽) + 𝐺𝐺𝐺𝐺𝑎𝑎𝑑𝑑𝑠𝑠𝐺𝐺𝑠𝑠𝑑𝑑𝑖𝑖 (5) 𝐺𝐺𝐺𝐺𝑎𝑎𝑑𝑑𝑠𝑠𝐺𝐺𝑠𝑠𝑑𝑑𝑖𝑖 = 𝐺𝐺.𝐷𝐷. 𝑆𝑆𝑖𝑖 × 𝑃𝑃𝑖𝑖 (𝑃𝑃𝑖𝑖 > 0) (6) where Ti is the travel time of link i, Ti0 is the free travel time of link i, v/c is the ratio of traffic to capacity (pcu/h), 𝛼𝛼, 𝛽𝛽 is the parameter (𝛼𝛼=0.15, 𝛽𝛽=4), G.D is the link length with slope, Si is the free speed of link i, Pi is the slope weight of link i. Build a new VDF system and network through the derived new form of the formula. When the electric vehicle was driving on a sloped road, the impact of electric vehicle battery consumption on the slope and speed was analyzed. In the previous study, the change in battery efficiency according to the slope was shown as a linear model (Liu et al., 2017) and in another study, battery efficiency according to speed and slope was experimentally shown (Graser et al., 2015). The linear model according to the slope and the battery consumption of the electric vehicle according to the speed was complexly analyzed to calculate the weight according to the speed and slope as shown in the Table 1. Based on the analysis conducted on an electric vehicle with a speed of 20 km/h (Liu et al., 2017), a weight standard was established and battery efficiency was verified according to the slope. In addition, based on this content, the weight of the electric vehicle battery consumption according to the free speed and the slope required for this study was set by weighting the consumption change rate according to the speed suggested in the previous study (Graster et al., 2015). On average, when the electric vehicle was driving at a speed of 20 km/h, it showed additional battery consumption, such as about 1.064 times at 1 % slope, about 1.083 times at 2 %, and about 1.094 times at 3 %, and it was analyzed that the battery consumption increased by about 10- 15 % when driving at a speed of 10 km/h. The weights according to the slope and free speed derived from this are shown in the Table 1. Table 1: Weighting according to gradient and free flow speed (𝑃𝑃𝑖𝑖) Gradient Free Flow Speed 20 km/h 30 km/h 40 km/h 50 km/h 60 km/h 70 km/h 1 % 0.064 0.172 0.213 0.421 0.565 0.723 2 % 0.083 0.193 0.239 0.446 0.593 0.754 3 % 0.093 0.205 0.253 0.461 0.609 0.772 4 % 0.152 0.269 0.333 0.538 0.694 0.865 5 % 0.166 0.284 0.351 0.557 0.715 0.888 In addition, referring to a previous study related to energy consumption of electric vehicles (Liu et al., 2017), the energy consumption according to the slope and the free speed is changed as shown in Table 2. Electric vehicles consume more energy as the speed increases and the slope of the road increases. This means that energy efficiency decreases as the slope of the road increases. 219 Table 2: Energy Consumption according to gradient and free flow speed Gradient Energy Consumption(kWh/km) 20 km/h 30 km/h 40 km/h 50 km/h 60 km/h 70 km/h 0 % 0.1353 0.1465 0.1587 0.1732 0.1892 0.2069 1 % 0.1439 0.1558 0.1688 0.1842 0.2012 0.2200 2 % 0.1530 0.1656 0.1794 0.1958 0.2139 0.2339 3 % 0.1627 0.1761 0.1908 0.2082 0.2275 0.2487 4 % 0.1730 0.1872 0.2029 0.2214 0.2419 0.2644 5 % 0.1839 0.1991 0.2157 0.2354 0.2572 0.2811 2.3 Shortest path search algorithm A route search algorithm is created based on the established network. The methodology applied as a whole is as follows. Figure 1a below predicts the shortest path using the existing algorithm, and Figure1b predicts the path considering the slope. As shown in the figure, the route search results vary depending on whether or not the slope is reflected. This methodology will be applied in practice. Figure 1: (a) existing route algorithm, (b) route algorithm considering slope A* Algorithm is a path search algorithm created by extending the Dijkstra algorithm. In this method, when the cost of the current state is g(x) and the heuristic function when moving from the current state to the next state is h(x), the point where the sum of the two f(x) becomes the minimum is searched first. A dynamic path planning method based on the A * algorithm that effectively searches for the shortest path and avoids collision has been proposed (Wang et al., 2015). This algorithm is simple and high to search efficiency. In addition, it is easy to find the actual shortest distance reflecting the estimated value. An algorithm is implemented that uses it to search for the shortest path to a newly constructed network, considering the slope. Finally, based on this, a route guidance system will be built to provide information about electric vehicle drivers. 2.4 Assumptions in the analysis process The algorithm is built, but there are some limitations, so the analysis is performed assuming the most reasonable value. First, roads have different traffic volumes for each month, day of the week, and time zone, and they change in real time. In this methodology, traffic volume data for each road stored in the road information system is applied. Since this is reliable data surveyed at the national level, it is possible to overcome the limitations. In addition, there are other variables besides the slope that can affect the driving distance. The bandwidth of signals, offset, etc. can affect the driving time and distance However, the algorithm can be analyzed by excluding it because the algorithm has meaning in a macroscopic sense. 3. Result 3.1 Case study In the study, Gangwon-do in Korea, which has a lot of mountainous terrain, was selected as the target site and the built algorithm was applied. First, maps containing elevation data were constructed by extracting elevation data from Google and applying the improved BPR function for each link. In addition, the shortest path is analyzed by applying it to the algorithm using the gradient between nodes. When comparing the changes in traffic volume, the results are shown in Figure 2. As a result of the traffic route assignment, it was confirmed that there is a significant difference compared to the existing shortest route assigned simply by distance. In Figure (a), the traffic volume using (2), which is a shorter and more inclined path, was more, but in Figure (b), (a) (b) 220 the traffic volume of route (1) increased because some traffic was switched to more competitive routes in the topography. Figure 2: (a) existing route algorithm, (b) route algorithm considering slope 3.2 Result analysis When a route was assigned by applying a different algorithm on the network of the case study, the results were different. The effectiveness of these two different results was compared. Table 3 shows the difference in travel distance, travel time, and energy consumption when the two algorithms are applied. When the electric vehicle of the same specification is driving at the same speed of 70 km/h, the travel distance and travel time are slightly increased, but the energy consumption is reduced. Of the two methods, the energy efficiency when performing the route search considering the terrain is about 1.794 higher. Using spatial information, it is possible to provide a more efficient route for drivers. As a result, if traffic assignment is performed using this method, the efficiency becomes higher and effective driving is possible. Table 3: Difference at the same speed Before After Difference Travel distance (km) 13.2 15.5 2.3 Travel time (min) 11.31 13.29 1.97 Energy consumption (kWh) 3.64 3.15 -0.49 Energy efficiency (km/kWh) 3.62 4.93 1.31 Looking at the other side, the difference in the travel distance, travel time, and average speed when they have the same energy consumption is shown in Table 4. When driving with an energy consumption of 2.5 kWh, the travel time is reduced by about 9.3 min. The result is the difference in speed, which varies with the slope. If the route derived in this method is used when consuming the same energy, destination can be reached in a shorter time. Table 4: Difference at the same energy consumption Before After Difference Travel distance (km) 13.2 15.5 2.3 Travel time (min) 30.45 21.19 -9.26 Average speed (km/h) 26.00 43.90 17.9 Energy efficiency (km/kWh) 5.28 6.2 0.92 4. Conclusion In this study, terrain variables were added to the vehicle's route search process to build algorithms and networks. A method has been proposed to enable more efficient operation using improved algorithms. This algorithm recommends that electric vehicles use a different route, even if the route is slightly longer, in mountainous areas with many slopes. It was applied to the actual area through route assignment that reflected this. After that, two different methods were used to derive travel time and energy consumption, and energy efficiency was compared and verified. Finally, the result is that more efficient operation will be possible if the route selected based on battery efficiency is used. (a) (b) 221 It can be applied not only to the electric vehicles that were focused on in this study, but also to eco-friendly transportation methods such as bicycles and personal mobility, which are greatly affected by the slope of the road. It is expected that the algorithm can be applied to induce users. This will create a positive effect that increases the convenience of traffic for users. Through this process, it is possible to expect the effect of activating eco-friendly transportation and reducing carbon emissions according to the increasing traffic. Future research should study how to apply the algorithm to tools that can reflect traffic conditions in real time. In addition, if the factors affecting the efficiency of eco-friendly transportation as well as the terrain are analyzed and added as variables, an improved algorithm will be derived. Acknowledgments This work was supported by the Architecture and Urban Development Research Program in the Ministry of Land, Infrastructure and Transport of Korean government (19TLRPB148659-02). References Chen CLP., Zhou J., Zhao W., 2012, A real-time vehicle navigation algorithm in sensor network environments, IEEE Transactions on Intelligent Transportation Systems, 13(4), 1657-1666. Chen X., 2018, Route Optimization of Hazardous Chemical Logistics Transportation Based on Improved Ant Colony Algorithm. Chemical Engineering Transactions, 71, 637-642. Ehsani M., Gao Y., Longo S., Ebrahimi K., 2018, Modern Electric, Hybrid Electric, and Fuel Cell Vehicles, CRC Press, Texas, US. Graser A., Asamer J., Ponweiser W., 2015, The Elevation Factor: Digital Elevation Model quality and sampling impacts on electric vehicle energy estimation errors, 2015 Models and Technologies for Intelligent Transportation Systems (MT-ITS), Budapest, Hungary. Hu X., Moon I., Seo J., Lee S., Kim S., 2007, An Efficient Shortest Path Search Algorithm Using Expanded Dijkstra Algorithm, Korea Multimedia Society, South of Korea, 149-149. Kang H., Lee B., Jang W., 2008, Path Planning Method Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm, Korea ITS Institute, 18, 212-215. Kim S., Na Y., Na S., Ku D., Lee S., 2020, Cost Estimation Methods in Feasibility Studies on Eco-Friendly Transportation Facilities, Chemical Engineering Transactions, 78, 247-252. Kucharski R., Drabicki A., 2017, Estimating macroscopic volume delay functions with the traffic density derived from measured speeds and flows, Journal of Advanced Transportation, 4629792. Ku D., Bencekri M., Kim J., Lee S., Lee S., 2020, Review of European Low Emission Zone Policy, Chemical Engineering Transactions, 78, 241-246. Liu K., Yamamoto T., Morikawa T., 2017, Impact of road gradient on energy consumption of electric vehicles, Transportation Research Part D: Transport and Environment, 54, 74-81. Qian K., Zhou C., Yuan Y., Allan M., 2010, Temperature effect on electric vehicle battery cycle life in vehicle- to-grid applications, 2010 China International Conference on Electricity Distribution 13th –16th September, Nanjing, China, 1-6. Sun W., 2017, Research on Distribution Management Information Platform of Chemical Products based on GIS. Chemical Engineering Transactions, 59, 571-576. Wai C.K., Rong Y.Y., Morris S., 2015, Simulation of a distance estimator for battery electric vehicle, Alexandria Engineering Journal, 54(3), 359-371. Wang C., Wang L., Qin J., 2015, Path planning of automated guided vehicles based on improved A-Star algorithm, 2015 IEEE International Conference on Information and Automation, Lijiang, China. Wei N., Zheng M., 2018, Influence of Environmental Factors and Vehicle Factors on VOC Volatilization Characteristics in Automobiles, Chemical Engineering Transactions, 71, 331-336. Yang S.C., Li M., Lin Y., Tang T.Q., 2014, Electric vehicle’s electricity consumption on a road with different slope, Physica A: Statistical Mechanics and its Applications, 402, 41-48. Yuksel T., Michalek J.J., 2015, Effects of regional temperature on electric vehicle efficiency, range, and emissions in the United States, Environmental science and technology, 49(6), 3974-3980. 222