Electric vehicle routing problem with non-linear charging and load-dependent discharging

We propose a three-index formulation for E-VRP with Non-Linear charging and Load-Dependent discharging (E-VRP-NL-LD), and an Adaptive Large Neighborhood Search (ALNS) algorithm to solve the E-VRP-NLLD and E-VRP-NL-LD with Capacitated Charging Stations (E-VRP-NL-LD-CCS). Existing implementations of EVRP duplicate charging station nodes which enables the modelling of EVRP using extended VRP formulations. Two limitations of such an approach are: (i) the number of such duplications is not known a priori, and (ii) the size of the problem increases. In our formulation, we allow multiple visits to a charging station without duplicating nodes. We propose five new operators for ALNS which are tested on 120 instances each of E-VRP-NL and E-VRP-NL-LD, and 80 instances of E-VRP-NL-LD-CCS. Results show that our ALNS outperforms the existing algorithms improving the solution in 63% of the instances and matching the best known solution in 31% of the instances. Results also show that considering load-dependent discharge is critical to optimally solve E-VRP. (C) 2020 Elsevier Ltd. All rights reserved.