Charge scheduling and route planning of commercial electric vehicles by considering the effect of battery degradation

Official URL: https://risc01.sabanciuniv.edu/record=b3157887_(Table of contents)

Battery is a critical component of electric vehicles (EVs) due to its limited useful economic life and high production cost. Hence, better recharging and discharging practices through coordinated and improved route planning decisions may be a remedy for maintaining good battery health and avoiding fast degradation. In this study, we investigate the effect of considering the battery degradation-related cost on the route and charge planning of commercial EVs within the context of the Electric Traveling Salesman Problem with Time Windows (ETSPTW) and Electric Vehicle Routing Problem with Time Windows (EVRPTW). First, we extend the mathematical programming formulation of the ETSPTW, where the objective function minimizes the costs associated with battery degradation and energy consumption. Next, we develop a Variable Neighborhood Search (VNS) based matheuristic enhanced with an exact solver employed for the post-optimization of heuristic solutions. Our matheuristic also includes a new mechanism designed specific to our problem. Then, we perform computational experiments using benchmark instances from the literature, and our results demonstrate that the proposed matheuristic achieves good quality solutions within reasonable computational time. We also extend the mathematical model of the EVRPTW by considering the battery degradation and conduct a computational study by solving small-size instances from the ii literature on a commercial solver. Our results in both problem settings show that incorporating battery degradation in the problem may yield significant changes in the route plans. On the one hand, it offers a potential for substantial reduction in operational costs compared to the solutions obtained by minimizing energy consumption only. On the other hand, it leads to more frequent recharges en route, which brings in additional operational hurdles.