=Paper=
{{Paper
|id=Vol-2631/paper2
|storemode=property
|title=Development of the Information System for Finding the Best Route for Electric Cars
|pdfUrl=https://ceur-ws.org/Vol-2631/paper2.pdf
|volume=Vol-2631
|authors=Oleh Veres,Pavlo Ilchuk,Olha Kots,Vladyslav Yerofieiev
|dblpUrl=https://dblp.org/rec/conf/momlet/VeresIKY20
}}
==Development of the Information System for Finding the Best Route for Electric Cars==
Development of the Information System for Finding the Best Route for Electric Cars Oleh Veres1[0000-0001-9149-4752], Pavlo Ilchuk2[0000-0003-4636-2309], Olha Kots3[0000-0001-7123- 3635] , Vladyslav Yerofieiev4[0000-0000-0000-0000] Lviv Polytechnic National University, Lviv, Ukraine oleh.m.veres@lpnu.ua1, pavlo.g.ilchuk@lpnu.ua2, olha.o.kots@lpnu.ua3, v.yerofieiev@gmail.com4 Abstract. The work is devoted to the research and development of a prototype information system for finding the best route for electric vehicles. Available ap- proaches and software for optimal travel planning are explored. The algorithm for optimizing the choice of charging stations along the route is proposed. Algo- rithms for finding routes between charging stations on a graph are improved. The multicriteria problem of choosing the optimal solution by the method of global criterion is solved. Charging stations can be selected depending on the charging time and the number of charging stations. We use the object-oriented approach for information systems design. The application requirements are justified. Con- sidering the features of the iOS platform, the REST architecture was used. Test analysis confirmed the effectiveness of the program. The construction of the best route depends on the type of vehicle, battery capacity, distance and number of charging stations available. Keywords: graph, criterion, optimal, route, information system, project 1 Introduction Most car companies produce their own electric motors and refuse internal combustion engines [1-3]. Many countries plan to abandon gasoline cars in near future. Sweden wants to ban sales of internal combustion engines in 2030. In particular, Norway plans to abandon internal combustion engines in 2025. Last year, almost half of the sales of cars in this country came from "clean" cars. The share of electric vehicles was 31.2%, the rest were hybrids. In addition, Denmark, Israel, Ireland, Iceland, the Netherlands, as well as France, intend to abandon internal combustion engines by 2030. The same term refers to China, the world leader in electric vehicles manufacture, and India. Total number of registered electric vehicles in Ukraine in 2018 amounted to 12 thou- sand pieces; in 2019 this quantity increased in 1.7 times. The Ministry of Infrastructure of Ukraine, within the framework of the program to stimulate the development of the electric transport market in the country, intends to increase the share of electric vehicle sales in the domestic car market to 15% by 2020. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Today, the infrastructure of charging stations in Ukraine is not developed, and the battery capacity is 500 km maximum, so long distances in most cases may not be achievable. The problem means optimization of the route for electric vehicles. The more charging stations there will be, the more expensive it will cost the car owner. The advisability of additional stop should be considered. In addition, each charging station has different voltage and current characteristics that directly affect the battery life. Development of decision-making information systems that take into account all the parameters while optimizing and finding the cheapest, fastest and shortest route is be- coming relevant today. 2 Analysis of Recent Research and Publications Solution multicriterion problems finding optimal solutions are relevant among scien- tists and specialists in information technology and software. Leading automotive com- panies that develop electric motor vehicles are interested in designing and implement- ing information support systems for decision-making to address the challenges of build- ing optimal routes [4-7]. Jonathan D. Adler analyzes the models and methods of solving the problem of find- ing the route for electric vehicles [8]. Specifically, he has done the overview of the main ways to solve the routing optimization problem and has proposed some optimization algorithms. The Heuristic Multi-Spatial Sampling algorithm provides competitive re- sults in terms of solution quality and computation time. This is one of the simplest methods used to solve the optimization problem. In addition, most algorithms work only with the linear speed of the car, leading to the error results. Also there was proposed the simple two-phase heuristic to solve the problem of find- ing the route for electric vehicles. The results of the experiments have confirmed the computing ability of the algorithm. The nonlinear charging function was used to reduce the error and plan the best route. At the end of the algorithm, in the case of a complex route, it was suggested to conduct the local search for charging stations found. This could give the opportunity to improve the result and reduce the route cost. Jose-Alejandro Montoya has analyzed several problems related to system operation and infrastructure design [9]. Problems arise when switching from standard gasoline vehicles to those that use alternative fuels or electricity. In the research there was pro- posed the method for finding the route of an electric vehicle through the network of charging stations. The route was laid without other transport means, and the stations had unlimited capacity. The problem – the electric vehicle routing with nonlinear charging function (eVRP- NL) [9]. There is proposed the iterative local search (ILS) enhanced with heuristic con- centration (HC). The basis of the proposed method is the neighborhood scheme, which is to solve a new variant of the problem of charging the vehicle on a fixed route (FRVCP). This problem consists in optimizing the charging decisions of a route serving a fixed sequence of customers. Depending on the configuration, ILS HC solves the underlying FRVCP either using a greedy heuristic or a commercial solver. Four pre- processing strategies are proposed to improve productivity, eliminating uncomfortable detours for CSs. The experiments proved the value of equipping eVRP-NL algorithms with components capable of making optimal charging decisions. Optimal eVRP-NL Solutions – use multiple mid-route charges, use partial charges, and use a non-linear segment of the battery charge function. 2.1 Analysis of Alternative Solutions Available Zap-Map is the UK's leading platform with more than 80,000 monthly visits. Charging Station Map is available for iOS / Android / Desktop platforms. The app helps electric vehicle drivers plan their route and share the location of charging stations with the com- munity. Fig. 1. Mobile App «Zap-Map» The disadvantages of this platform are in finding solutions. Not many factors are taken into account when planning. It is impossible to plan routes with intermediate waypoints. There is no planning in Ukraine. A Better Route Planne (ABRP) – is the great way to plan routes for electric cars. It helps not only Tesla owners, other vehicles owners can use it to find their routes too. Fig. 2. Web pages of applications «ABRP» The disadvantage is the limited number of electric vehicle models, implementation on the only one platform, limited configuration functionality. Today, the issue of route planning according to the growing demand for electric ve- hicles is still at the early stage. The available solutions don’t take into account such important facts as energy recovery and weather conditions that affect battery life. In most implementations, optimization can use charging stations that are located on the other side of the motorway, even if they are on the correct side it leads to an error in the calculations. The algorithms don’t take into account the actual distance to the station, but measure the distance "by air". Measuring the real distance is a difficult operation for calculating. The problem of left-hand traffic, which is the main one in 34% of the countries of the world, should also be taken into account. Therefore, the task of developing the project of an information system for deciding on the choice of the optimal route for an electric car based on a set of criteria is relevant. Proposed information system will help electric motor vehicle drivers to plan routes beyond the reach of a single charge, taking into account a number of factors and con- ditions of a specific route, car, travel budget, weather conditions and charging stations. The information system for finding the best path for electric motor vehicles should be implemented as an application for mobile phones. It should be possible to use it directly in the car's multimedia panel as an Apple CarPlay application. 3 Problem Analysis and Rationale for Solving the Problem The information system should implement an optimization algorithm to select charging stations along the route. The advanced algorithm for finding routes between charging stations on a graph is used for this purpose. When constructing the global criterion for choosing the optimal route, the possibility of choosing charging stations is considered, depending on the charging time and their number. Let's look at the system as a whole and determine the general requirements for sys- tem operation and user interaction. The information system of route optimization for electric cars has to: allow the user to enter the coordinates or address of two or more points; allow the user to enter a car model or choose one of the available ones; provide the user with an optimal route from the start point to the end point; provide information on charging stations; provide an approximate status of the battery capacity at stations; provide approximate charging and travel time; provide an approximate cost of travel. The goal tree was developed to achieve the overall goal of the project. The main task is to create a project of a route optimization information system for electric cars. The criteria for evaluating the objectives and objectives of the project are achieved as fol- lows. Usability is achieved through the implementation of a naive platform interface, and following the "apple developer human interface guidelines", what let users to use the experience of using the iOS operating system interfaces. Scalability is achieved through abstraction and API that allow extending system modules and adding other components. It is proposed to use online services, which are updated without interference and without changing the access interfaces. Availability means, that the information system is a mobile application and a soft- ware module, availability of which is provided by standard operating system tools. Responsive should be applied to design development. Sensible web design involves the use of HTML and CSS to automatically resize, hide, reduce, or enlarge pages. 4 Development of the Information System Project The general functional requirements for the information system are presented in the Use Case diagram (See Fig. 3). You can track how the user is working with the system and what tasks the system is deciding. Fig. 3. Use case diagram of the information system Implementations are subject to the module of coordinate selection, description of the characteristics of the truck and the construction of the optimal route. Other UML diagrams also have been formed and they reflect the information system design tasks. The component diagram has been constructed for understanding the inter- connection of individual modules of the information system (See Fig. 4). Fig. 4. Component diagram It is proposed four modules for the system: User Interface – user interaction with the system; EV Route Optimizer – executes business logic and data processing; Weather Cloud API – get weather information in the region; Apple Maps API – module maps; implements interfaces: receiving data on charging stations; getting routes between points; battery charge remaining. The sequence of operations information system optimization route is given in the Se- quence (interaction) diagram (See Fig. 5). Fig. 5. Sequence diagram Input data for the information system are: geolocation data by the beginning and the end of the route; weather conditions; battery capacity model; data on available charging stations. Data from the weather module is processed in JSON format (See Fig. 6). Fig. 6. An example of weather conditions The results of the system are: route for electric vehicle with charging stations; duration of the trip; cost of the trip; battery capacity at the intermediate and final points of the route. The Class diagram was developed to implement the information system interfaces (See Fig. 7). Fig. 7. Class diagram EV Route Optimizer – the main class that contains all the business logic. It has an OptimizeRoute method that accepts RoutePlan and returns it with charging stations. EV Route Optimizer interacts with abstract classes – WeatherProvider, Counsump- tionProvider and CharginStationProvider. The class implements the advanced algo- rithm for finding routes between charging stations on the graph. The algorithm for solv- ing the multi-criteria problem of finding optimal solutions by the global criterion method takes into account the possibility of choosing charging stations, depending on the charging time and their number. WeatherProvider – abstract interface; announces a temperature method (at: Geo- Coordinates) that returns the temperature at the specified location. CounsumptionProvider – abstract interface; has a ConsumptionFor (plan: RoutePlan) method that returns the value of the charge spent to overcome the route. CounsumptionProvider interacts with RouteProvider, which converts RoutePlan to Route. Route – the RouteSegment aggregator. It is a GeoLocation track and has the attribute speed – the maximum speed in a given segment of the route. CharginStationProvider – abstract interface. It is a ChargingStation aggregator, which is the ChargingConnector aggregator that is responsible for charging station pa- rameters. The Activity diagram reflects the state of the information system during its operation and is the dynamic representation of the interrelation of internal and external events (See Fig. 8). Fig. 8. Activity diagram External events are the temperature and availability of charging stations near the search point. After the point of entry into the optimization module it calculates the route. It deter- mines how much capacity it takes to overcome the route. If enough, the system shuts off. Otherwise, we receive and process weather and charging data along the route. If there is at least one station, we select the best one and add it. We start calculating the route again, but with added station. If no station was found while searching for a charg- ing station, the algorithm stops. 5 Implementation of the Information System Prototype In accordance with existing business analytics standards, the following requirements apply to the project implementation of the technical environment, software and plat- form through which the system is implemented and deployed [10-12]: mobile application programming language: Swift; weather service: darksky.net; mobile devices: iPhone XS, iPhone XS Max iPhone XR, iPhone X, iPhone 8, iPhone 8 Plus, iPhone 7, iPhone 7 Plus, iPhone 6s, iPhone 6s Plus, iPhone SE, iPod touch 7th generation, 12.9-inch iPad Pro 3rd generation (2018 model), 12.9-inch iPad Pro 2nd generation, 12.9-inch iPad Pro 1st generation, 11-inch iPad Pro (2018 model), 10.5-inch iPad Pro, 9.7-inch iPad Pro, iPad 6th generation (2018 model), iPad 5th generation (2017 model), iPad Air 3 (2019 model), iPad Air 2, iPad mini 5 (2019 model), iPad mini 4; data transfer protocol: JSON; card service: Apple maps; Data encoding: UTF-8. Swift – a general-purpose programming language built using a modern approach to security, performance, and software models [13, 14]. Apple Maps – Apple's mapping service for operating systems iOS і macOS [15]. The information system will interact with the weather service through JSON (JavaS- cript Object Notation) [15-18]. It is an unified text format that is available for writing and interpretation in almost all programming languages. Darksky.net's weather service is free of charge up to 1000 requests per day. 5.1 Project Assignment Considering the features of the iOS platform, it would be the best to use an architecture that mimics or at least is similar to the REST architecture. This approach will allow the iOS application to access the database not through direct connection but through HTTPs protocol. In this case, the resources of the web-oriented system server will be used to obtain data from the database and to process them. RESTful architecture-based design approach will easily separate the client application from the software interfaces to work with the database, which is an undeniable benefit to the system. The developing appli- cation is independent of the database structure and used relational DBMS [19, 20]. The disadvantage of using the RESTful approach is using the intermediary between the client and the database server. This is not critical or very important for developing iOS application. Functional stability requires using the specific database server and Google Cloud Messaging (GCM) service. In order to provide instant messaging, GCM functionality, the GCM must have access to the database that cannot actually be provided without using a web server. Three servers are used to ensure the functionality and stability of the iOS application. IDE xCode will be used to implement the mobile application. It is intended for pro- gramming applications in languages such as Swift and Objective-C for iOS, MacOS, WatchOS and TWOS. Postman utility will be used to establish client-to-server communication via REST. With this tool, it is possible to check the output data from the server before the program implementation, in order to prepare the required response models from the server. With the built-in xCode application, InterfaceBuilder builds interconnections be- tween screens and transitions. The designer outlines the user interface with the main dimensions and transitions between screens (See Fig. 9). Fig. 9. Interface Design 6 Results of the Project The application starts from the list of cars (See Fig. 10). One of the 22 offered models can be selected. Each item in the list include: a photo of the car, the name, the year of the particular model, the battery capacity (kilowatt-hour) and the approximate distance that the car can travel on a single charge. Fig. 10. List of cars After selecting the car, the user goes to the map screen (See Fig. 11). Use the Long Tap gesture to select the start and the end points of the route (See Fig. 12 and Fig. 13). Fig. 11. Home screen Route Fig. 12. Choosing location Fig. 13. Selected location After selecting the final and initial location on the map, the user will get the result of the charging station search algorithm and the built route (See Fig. 14). There are depicted following elements: Basic Visual Data – the start and the end points; charging stations as intermediate waypoints; the route, including charging stations; Auxiliary Visual Data – charging station search radius (large red circle); charging stations that were excluded from the path search step (small red circles); charging stations that were included in the path search but were not the best option (small green circles). Fig. 14. The algorithm result The search for a route from Lviv to Kiev for the Smart ForTwo electric car 2017, with a battery capacity of 17.6 kWh, a 110 km power reserve is shown (See Fig. 14). You can select another model and optimize for the new calculation using the «Сars» button. 6.1 Analysis of Application Results Several test tasks have been done for testing the performance and results of the optimi- zation algorithm. Test 1. Optimize route from Lviv to Kiev for all 22 vehicles available in the app (Table 1). Table 1. Optimization results of Lviv - Kiev route for different cars Modell Search Path Number The number of Number of Number of time (s) length of sta- stations that stations not stations on (km) tions were searched in search the way Audi e-tron 2.08 538.78 14 11 3 1 Quattro BMW i3 1.91 542.75 14 11 3 2 Chevrolet Bolt 1.10 538.78 14 11 3 1 EV Fiat 500e 1.21 541.93 14 11 3 4 Ford Focus 2.06 537.89 14 11 3 3 Electric Honda Clarity 1.01 541.93 14 11 3 4 BEV Hyundai Ioniq 0.96 537.87 14 11 3 2 Jaguar I-Pace 1.87 538.78 14 11 3 1 Mazda MX30 1.97 537.87 14 11 3 2 Nissan Leaf SL 1.83 542.75 14 11 3 2 Opel Ampera-e 1.86 538.78 14 11 3 1 Peugeot e- 0.99 542.72 14 11 3 1 2008 Porsche 1.78 538.72 14 11 3 1 Taycan Renault ZOE 2.13 537.87 14 11 3 2 SEAT Mii 2.04 542.75 14 11 3 2 Electric Smart Fortwo 2.26 542.00 14 11 3 5 Tesla Model 3 1.97 538.78 14 11 3 1 Tesla Model S 1.77 538.69 14 11 3 0 Tesla Model X 1.04 538.78 14 11 3 1 Volkswagen 1.90 538.78 14 11 3 1 I,D,3 Volkswagen e- 0.83 542.72 14 11 3 1 Golf Volvo XC40 2.05 538.78 14 11 3 1 Recharge P8 The average search time for 11 out of 14 charging stations is 1.67 seconds. Smart Fortwo cars need the most charging stations to overcome the route – 5 stations. Tesla Model S is able to overcome the distance without extra charge. For clarity, the diagram (See Fig. 15) of the search time versus model type was built. The results range from 0.83 to 2.26 seconds and have a difference of 1.42 seconds. 2,50 2,00 Time in seconds 1,50 1,00 0,50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Car numer in the list Fig. 15. Run time of Lviv - Kiev route algorithm for different cars Test 2. Construction of routes with varying length and across different regions, what will increase the amount of input data (Table 2). Table 2. Optimization results for routes of different lengths and locations Route Search Path Number The number Number of Number time length of sta- of stations stations not of stations (s) (km) tions that were in search on the searched way Lviv ⇢ Krakow 1.92 327.71 44 16 28 0 Lviv ⇢ Warsaw 9.16 604.62 369 53 316 1 Barcelona ⇢ Madrid 6.94 939.01 510 239 271 2 Barcelona ⇢ Lisbon 17.44 632.43 1240 280 960 5 Lviv ⇢ Berlin 15.90 412.98 1451 147 1,304 2 Stuttgart ⇢ Schmal- lenberg 35.79 650.11 2168 686 1,482 1 Stuttgart ⇢ Berlin 45.38 1,473.83 5744 798 4,946 2 Milan ⇢ Sofia 42.52 1,251.71 6017 407 5,610 7 Barcelona ⇢ Schmallenberg 78.97 1,455.105 10,000 749 9,251 9 The time-dependence diagram on the number of charging station data is built (See Fig. 16). 71 61 Time in seconds 51 41 31 21 11 1 44 369 510 1240 1451 2168 5744 6017 10000 Number of charging stations on the route Fig. 16. Time-dependence diagram on the number of charging stations on the route Testing analysis confirmed the effectiveness of the application and showed the depend- ence of time to build the optimal route on the distance and number of available charging stations. The information system makes it possible to build the optimal route between the set of points for electric vehicles (See Fig. 17). Fig. 17. Application interface 7 Conclusion Due to the increasing demand for electric vehicles, it is necessary to optimize routes for this type of transport when traveling over long distances. The power reserve and the number of charging stations don’t satisfy all users at the present stage of the electric vehicles development. As the result of the researches, the project of the route optimization information sys- tem was developed. The object-oriented approach to design was used. Requirements for the application implementation are justified. Given the features of the iOS platform, the REST architecture was used. The prototype of the information system was tested. The average search time for 11 out of 14 charging stations is 1.67 seconds. Smart Fortwo cars need the most charging sta- tions to overcome the route – 5 stations. Tesla Model S is able to overcome the distance without extra charge. The results range from 0.83 to 2.26 seconds and have a difference of 1.42 seconds. The time dependence of the construction of the optimal route on the distance and the number of available charging stations is revealed. The result of the project is the information system that makes it possible to plan an electric vehicle trip over long distances, taking into account the necessary stops at charging stations. The system must process the data received from external resources and solve the task of finding a route under certain conditions. The system will allow users to use electric vehicles as conveniently as vehicles with conventional gas or diesel. With the convenience of using electric vehicles, most users will be able to use an environmentally friendly fuel type, which will ensure a better environment in the future. The developed application meets the standards of quality and fulfills the task, namely: optimization of the path for cars with electric motors. The user interface com- plies with the standards set for the design of mobile application interfaces, has the pre- dictable behavior and interaction with the user interface. Further research will focus on improving the methods and algorithms for solving the multi-criteria problem of constructing the optimal route for electric vehicles. References 1. Berman, B., Gartner, J.: Selecting electric vehicles for fleets. http://www.navigantre- search.com/wp-content/uploads/2013/02/RB-SEVF-13-Executive-Summary.pdf. Last Ac- cessed 16/04/2015 (2013) 2. Toth, P., Vigo, D.: An overview of vehicle routing problems. In.: The vehicle routing prob- lem. Society for Industrial and Applied Mathematics. PP. 1–26 (2001) 3. Hall, R., Partyka, J.: On the road to mobility–2008 survey of vehicle routing software spot- lights integration with portable phones. OR/MS Today by Institute for Operations Research and the Management Sciences. (2008) 4. Felipe, A., Ortuno, M. T., Righini, G., Tirado, G.: A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review 71. PP.111 – 128 (2014) 5. Toth, P., Vigo, D.: Vehicle routing: problems, methods, and applications. Vol. 18. Siam. (2014) 6. Chen, J., Dosyn, D., Lytvyn, V., Sachenko, A.: Smart Data Integration by Goal Driven On- tology Learning. In: Advances in Big Data. Advances in Intelligent Systems and Comput- ing. – Springer International Publishing AG 2017. PP. 283-292 (2017) 7. Su, J., Vysotska, V., Sachenko, A., Lytvyn, V., Burov, Y.: Information resources process- ing using linguistic analysis of textual content. In: Intelligent Data Acquisition and Ad- vanced Computing Systems Technology and Applications, Romania, PP. 573-578 (2017) 8. Jonathan D.: Adler Routing and Scheduling of Electric and Alternative-Fuel Vehicles ARIZONA STATE UNIVERSITY May 2014. Access mode: https://repository.asu.edu/at- tachments/134788/content/Adler_asu_0010E_13619.pdf (2014) 9. Montoya Jose-Alejandro: Electric Vehicle Routing Problems : models and solution ap- proaches. Université d’Angers. Access mode: https://tel.archives-ouvertes.fr/tel- 01441718/document (2016) 10. The PMI Guide to Business Analysis : standards. PMI (2017) 11. Veres O., Kunanets N., Pasichnyk V., Veretennikova N., Korzh R., Leheza A.: Develop- ment and operations – the modern paradigm of the work of IT project teams. In.: Computer Science and Information Technologies (CSIT2019). PP. 103–106 (2019) 12. Lytvyn, V., Vysotska, V., Veres, O., Rishnyak, I., Rishnyak, H.: The Risk Management Modelling in Multi Project Environment. In: Computer Science and Information Technolo- gies (CSIT2017). PP. 32-35 (2017) 13. Swift programming language, https://swift.org/about/ 14. Human Interface Guidelines, https://developer.apple.com/design/human-interface-guide- lines/ios/overview/themes/ 15. Apple maps, https://www.apple.com/ios/maps/ 16. JSON. Access mode: https://www.json.org 17. Change Control Process in Software Engineering with Steps. Access mode: https://www.guru99.com/change-control-business-analyst.html 18. Software Development Life Cycle, https://medium.com/@jilvanpinheiro/software-develop- ment-life-cycle-sdlc-phases-40d46afbe384 19. Shakhovska, N., Veres, O., Bolubash, Y., Bychkovska-Lipinska, L.: Data space architecture for Big Data managering. In.: Computer Science and Information Technologies (CSIT 2015). PP. 184-187 (2015) 20. Veres, O., Shakhovska, N.: Elements of the formal model big date. In: Perspective Technol- ogies and Methods in MEMS Design (MEMSTECH’2015). PP. 81-83 (2015)