Cluster-based approach for route planning optimization of electric vehicles

This Master's Thesis presents a comprehensive exploration of a project aimed at enhancing minimum travel time path research algorithms for electric vehicles. The algorithm used for defining the minimum travel time path is Dijkstra's algorithm, which is implemented on a cost matrix constructed by assigning a specific recharging station within a map to each column and row. The value contained in each cell is the sum of the travel time taken from the station connected to the column to the station connected to the row, to which is added the recharging time required to restore the battery to its initial charge level. The first part of this project focuses on constructing a vehicle and battery recharging model to ensure compliance with the vehicle's range limits, as well as accurately modeling the battery recharging profile for better evaluation of recharging time. This involves defining a vehicle model that includes: a more accurate assessment of the power required at the wheels by incorporating an inertial coefficient to account for the rotational inertia of driveline components; constructing an efficiency map of the electric motor based on its nominal parameters; defining a regeneration coefficient to modulate the regenerative capacity of the vehicle based on its driving speed, and specifying a non-constant recharging profile using the CP-CV charging protocol. The second part of this project focuses on reducing the processing time involved with the construction of the cost matrix, which will subsequently be used in the Dijkstra's algorithm. This reduction is primarily achieved by clustering the recharging stations based on their geographic density using the DBSCAN algorithm, thereby reducing the number of recharging stations to be considered within the cost matrix in areas with high density of recharging stations. Additionally, to the cost matrix obtained with clustered recharging stations, a series of pruning techniques were further applied. The objective of these techniques is to reduce the number of recharging stations considered to only those that are essential for defining the desired route. The primary function of these pruning techniques is to deem as non-essential, for defining the minimum travel path, all recharging stations whose geographic coordinates fall outside a defined straight corridor with a specified width, beginning and ending at the departure and arrival coordinates of the desired journey. Overall, the project's innovations significantly improved the original program, with potential applications in artificial intelligence and route planning, combining computational approaches with cognitive principles to enhance efficiency and reduce processing times. This research marks a significant advancement in the domain of electric vehicle route planning, offering valuable insights for future developments in sustainable transportation and artificial intelligence.