On tackling non-linear charging functions in the electric vehicle routing problem

Abstract The increasing integration of electric vehicles into transportation fleets poses new challenges in the classical Vehicle Routing Problem, primarily due to the nonlinearity of the battery charging process. In the literature, the piecewise linear approximation and a formulation based on paths of charging stations are established approaches to deal with this complex function. In this paper, we address the Electric Vehicle Routing Problem using a realistic non-linear charging function, and we present an alternative exact method of linearising it by using Perspective Cuts. Additionally, we present a preprocessing algorithm for the elimination of dominated paths, i.e., paths that cannot be present in an optimal solution. The logic of our preprocessing, unlike previous methods, does not depend on the piecewise linear approximation. The proposed methods are validated through computational experiments on benchmark instances, demonstrating their effectiveness in improving model accuracy while maintaining computational tractability.