Abstract:

This study presents an Electric Vehicle Production Routing Problem (EVPRP) to achieve optimal decisions. In the proposed problem, the limitation of battery capacity and charging facilities is incorporated. In addition, partial charging is considered using both Heterogeneous (HT), and Homogeneous (HM) fleets to address the issue of long charging. The authors propose a mixed-integer linear programming model for the EVPRP, which is mathematically validated by solving (via CPLEX) the new instances generated compatible with the EVPRP. Due to the NP-hardness of the EVPRP model, which cannot solve large-scale instances by a commercial solver, they developed two types of exact algorithms named, Logic-Based Benders Decomposition (LBBD) algorithms. The first one is based on each vehicle in each period (LBBDvt), and the second algorithm is applied for each period (LBBDt). The proposed model's and LBBD algorithms' performance is validated through the computational experiments on the HM and HT EVPRP data sets. The computational results show that the proposed exact algorithms clearly outperform the MIP formulation solved by Cplex and demonstrate both algorithms' efficiency in finding high-quality solutions.