The electric vehicle routing problem with partial charge, nonlinear charging function, and capacitated charging stations

International audienceWe study the electric vehicle routing problem with partial charge, nonlinear charging function, and capacitated charging stations (E-VRP-NL-C). Decisions in the E-VRP-NL-C concern not only the sequence in which the customers are to be served, but also where and how much to charge the batteries in each route. The special features of the problem are that: 1) the function describing the relationship between the time spent charging the vehicle and the amount of charged energy is nonlinear and 2) a maximum number of EVs can simultaneously charge at each charging station (CS). We propose different MILP formulations for the E-VRP-NL-C and study the efficiency of these continuous-time models when running on a commercial solver. We also introduce a route first-assemble second approach to tackle the E-VRP-NL-C. In the routing phase the method uses an iterated local search embedding a variable neighborhood descent scheme. It combines simple components from the literature and components specifically designed to consider charging decisions and the limited number of chargers available at each CS. In the assembling phase the method builds the best possible solution from the routes that are part of the local optima found during the first stage. We adopt a decomposition method to exactly solve this phase