A matheuristic algorithm to solve the electric vehicle routing problem with capacitated charging stations
Résumé
In this research we focus on an electric vehicle routing problem in which 1) vehicles can be partially recharged between customer visits, 2) the quantity of energy recharged is a piecewise linear function of the time spent charging and of the current state of charge of the vehicle, and 3) the number of vehicles simultaneously charging at each charging station does not exceed the number of available chargers. The objective is to minimize the total time needed to serve all the customers. In this problem, resource synchronization takes place at nodes whose visit is a decision that depends on the sequence of customers served on the routes and on the objective. We propose two mixed integer linear programming formulations of the problem based either on charging stations replication and recharging paths. Solving the model using a commercial solver allows us to solve only small-sized instances. To tackle large-sized instances, we propose an hybrid algorithm that combines two components: an iterated local search algorithm responsible for generating a pool of high-quality routes and a branch-and-cut algorithm responsible for assembling a solution to the problem from the generated pool. We perform a comparison between four assembling strategies. Our computational results show that the strategies have different degrees of effectiveness and efficiency in addressing the capacity constraints of charging stations.