  This paper outlines an exact and a heuristic algorithm for the electric
vehicle routing problem with a nonlinear charging function (E-VRP-NL)
introduced by Montoya et al. (2017). The E-VRP-NL captures several realistic
features of electric vehicles including the battery limited driving range and
nonlinear charging process at the charging stations. We formulate this problem
as a set-partitioning and solve it using a column generation based algorithm.
The resulting pricing problem of the column generation is a complicated problem
as, next to the usual operational constraints e.g. time windows and vehicle
capacity, electric vehicle related features are also considered. In particular,
the nonlinear nature of the battery charging process requires the incorporation
of a set of sophisticated recursive functions in the pricing algorithm. We show
how these recursive functions allow for the simultaneous evaluation of the
routing and charging decisions. Moreover, we illustrate how they can
efficiently be embedded in the pricing algorithm. The column generation
algorithm is integrated in a branch and bound algorithm and cutting planes are
added resulting in a branch-and-price-and-cut algorithm for the E-VRP-NL. Next
to the exact algorithm, we also develop a tabu search based heuristic to solve
the problem quickly. To prove the efficiency of the proposed algorithms, their
performance is tested on benchmark instances from the literature. Our exact
algorithm can optimally solve instances with up to 40 customers, including
several instances previously unsolved to optimality. The tabu search heuristic
proves to be superior to state-of-the-art heuristics in the literature both on
solution quality and computation times.
