An effective matheuristic approach for solving the electric traveling salesperson problem with time windows and battery degradation

Official URL: https://dx.doi.org/10.1016/j.engappai.2024.107943

Battery is a critical component of an electric vehicle (EV) due to its limited useful economic life and high cost. Good recharging and discharging practices through coordinated and improved route planning decisions in logistics operations may constitute a remedy for maintaining good battery health and avoiding fast degradation, hence, cutting down the costs and reducing adverse environmental effects associated with its disposal. In this study, we investigate the influence of battery degradation cost on the route and charge planning of delivery EVs within the context of the Electric Traveling Salesperson Problem with Time Windows (ETSPTW). First, we introduce the ETSPTW and Battery Degradation (ETSPTW-BD) and present its mathematical model. Since the problem is intractable even for small-size problem instances in the presence of battery degradation, we develop a matheuristic approach that integrates the Variable Neighborhood Search algorithm with an exact solver employed for enhancing the heuristic solutions to solve realistic problems in terms of problem size and constraints. Then, we perform an extensive computational study to validate the performance of the proposed matheuristic and provide managerial insights on the role of battery degradation in routing and charging decisions. Our numerical experiments show substantial cost reduction (up to 11%) can be achieved by incorporating battery degradation into the problem as compared to the solutions obtained by minimizing energy consumption only. However, we also observe that the recharge frequency along the tours may increase, which presents an additional operational challenge for logistics service providers.