The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows

With the increase of public programs to encourage the use of electric vehicles and the shift of social reception towards so called energy efficient solutions the research in the field of vehicle routing using low-emission vehicles has increased as well. We therefore introduce a new problem, the so-called Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows (EFSMVRPTW). The problem covers real world applications where an optimal mix of different available battery powered (and conventional) vehicles has to be found. The EFSMVRPTW can be seen as a generalization of two other VRPs: On the one hand, the Electric Vehicle Routing Problem with Time Windows (EVRPTW) introduced by Schneider et al. (2012), where the goal is to find optimal tours from a single depot to customers using a homogeneous fleet under consideration of a distance dependent energy resource, which can be replenished in optional recharging stations. On the other hand, the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW) introduced by Liu and Shen (1999), where a heterogeneous fleet of different vehicles (with different load capacities and acquisition costs) has to be used to serve all customers, minimizing not only the distance and waiting time, but also the acquisition cost of the vehicles used. In the EFSMVRPTW we search for the optimal mix of different electric vehicle types minimizing the overall distance and acquisition costs while satisfying time window and energy resource constraints. As in the EVRPTW we can use a set of intermediate facilities to recharge the vehicles, implying a recharge time relative to the distance travelled since the last recharging station or the depot. In this work we generate a new benchmark set based on the existing FSMVRPTW and EVRPTW instances, which are both modifications of the well known Solomon instances with 100 customers, 21 recharge stations and three to six vehicle types. Additionally, we generated a set of smaller instances (with 5 to 15 customers). We propose a mixed integer programming model for the problem and are able to solve some of the smaller instances using CPLEX. Furthermore we implemented a heuristic approach based on the ALNS framework described by Pisinger and Ropke (2007) and use it to solve the EFSMVRPTW instances. In addition we tested our approach on the EVRPTW and FSMVRPTW instances in order to compare it with the state-of-the-art methods for those problems. Preliminary computational results on the smaller instances as well as the comparison with existing methods for similar problems show that good quality solutions for the EFSMVRPTW can be expected