An effective and efficient matheuristic for the electric vehicle routing problem with capacitated recharging stations

In this paper, we address the problem of routing a fleet of electric vehicles (EVs) to serve a set of customers, geographically distributed, within their time windows. We assume that EVs may also be recharged en route, and the amount of energy recharged at a recharging station (RS) is a decision variable itself, that is, partial recharges are allowed. We also assume that each RS has a limited number of chargers, and, therefore, possible overlaps at RSs among EVs have to be properly managed. We formulate the resulting electric vehicle routing problem with time windows and capacitated recharging stations (EVRPTW-CRS) through mixed integer linear programming (MILP). Given the hardness of the EVRPTW-CRS, we design a MILP-based adaptive large neighborhood search. A result comparison with the state-of-the-art exact algorithm shows both the effectiveness and the efficiency of the proposed matheuristic, on a set of benchmark instances, considering both a linear and a piecewise-linear recharging function. An extensive sensitivity analysis on possible variation of some critical parameters is also carried out.