Branch-Price-and-Cut for the Electric Vehicle Routing Problem
with Nonlinear Charging Function
G. M. Nafstada,∗ , G. Desaulniersb and M. Stålhaneaa Norwegian University of Science and Technology, Trondheim, Norway

gaute.m.nafstad@ntnu.no, magnus.staalhane@ntnu.no
b Polytechnique Montreal and GERAD, Montreal, Canada

guy.desaulniers@gerad.ca∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: (Branch-Price-and-Cut, E-VRP-NL, Resource constrained shortest path problem)

1Introduction

The world’s fleet of vehicles powered by electricity is growing. Important actors, such as theEuropean Union, have indicated that they will start to phase out petrol vehicles in order tocontribute to less greenhouse gas emissions. Several countries signed an agreement to stop salesof new emitting cars by 2040 during the 2021 United Nations Climate Change Conference.
Most of the electric vehicles today store energy in batteries. Battery and battery recharging
technology are in rapid development, but driving range and recharging times remain well known
drawbacks of electric vehicles. Route planning for electric vehicles introduces the need to accountfor a limited driving range and the possibility of recharging during a route. Petrol vehicles also
have limited driving range, however, as time needed to refuel a petrol vehicle is negligible andthe availability of gas stations is usually very high, it can be excluded from the route planning.
The classical problem of routing petrol vehicles falls in the category of vehicle routing problems(VRP), while route planning with electric vehicles are referred to as the electric vehicle routing
problem (E-VRP). The VRP is the problem of routing an unlimited fleet of homogeneous vehicles
to visit a set of customers. Each customer must be visited exactly once by a vehicle. The vehicles
start and end their route at a central depot. The objective is to minimize the distance traveledby the vehicles. In E-VRP, the vehicles have a given battery capacity which gives a limited
range before having to either recharge or end the route. The objective is to minimize the total
time spent on the routes, including travel time and recharging time. In addition to the depot
and the customer nodes, the E-VRP has dedicated recharging nodes. The recharging process
can be modelled in various ways, which is the main difference in several versions of the E-VRP.
The goal of this paper is to present a Branch-Price-and-Cut (BP&C) solution method for the EVRP with nonlinear charging functions (E-VRP-NL). The novelty of the method lies in the way
recharging is handled in the pricing problem. The method is tested on the benchmark instancesfrom Montoya et al. (2017) and solves several previously unsolved instances to optimality.
The E-VRP has received increasing attention in the last decade. The green vehicle routing problem, introduced by Erdoğan & Miller-Hooks (2012), was among the first to consider dedicated
TRISTAN XI Symposium

Original abstract submittal

G. M. Nafstad, G. Desaulniers and M. Stålhane2Figure 1 – The recharging functions are the ones used in the Montoya benchmark instances(Montoya et al., 2017).

recharging locations into the VRP. In subsequent years, many extensions of the problem withdifferent attributes have been contributed to the E-VRP literature. A survey by Erdelić & Carić(2019) presents many of these extensions and the tailored solution methods used, both exact
methods and heuristics. Multiple of these variations relate to the modeling of the recharging
procedure. Early works modelled the recharging process as a constant time procedure, similar tothe process of battery swapping. In the works of Conrad & Figliozzi (2011), vehicles can charge afixed percentage during a fixed recharging time at certain customer nodes. Later, other recharging modelling alternatives have been developed to better mimic the real recharging possibilities
and the related recharging times.
One of these modelling possibilities is to allow for partial recharging of the vehicle, contrary to
full recharging. This feature will increase the solution space, and hence might give improved
solutions. Another feature that affects the size of the solution space is the limit on the number ofvisits to recharging nodes for a route. Some limit recharging to maximum once per route, whileothers have no upper limit. A discussion related to this potential limit, its importance whenmodelling, and its effect on the optimal solution is presented by Montoya et al. (2017).
Desaulniers et al. (2016) present a BC&P method for the E-VRP with time windows and linear
charging, first introduced by Schneider et al. (2014). The method presented handles all fourcombinations that can be made by having full or partial recharging and one or multiple recharge
operations for a route. The recharging function that describes the state of charge (SoC) as afunction of time is linear in their case. In reality, the recharging function is a nonlinear concave
function. The recharging function is known to be close to linear on the interval from 0 % SoC toabout 80 %, and then the recharging rate decreases exponentially the remaining 20 % (Montoyaet al., 2017). Montoya et al. (2017) argue that a piecewise linear function with three segments is asufficiently good approximation. They introduce the E-VRP with nonlinear charging function (EVRP-NL). An additional feature in that problem is that the recharging nodes might have different
recharging technologies, meaning that they do not necessarily have the same recharging function.
The work also presents a set of benchmark instances for the problem. In these instances there
are three types of recharging nodes; Fast, Normal and Slow. The piecewise linear approximations
are shown in Figure 1 for a vehicle with a battery capacity of 16 kWh.
Montoya et al. (2017) solved the E-VRP-NL with a hybrid metaheuristic and presented a mixedinteger linear programming (MILP) formulation for the problem. Two tighter MILP formulations,
one based on arc flow and another on path flow, are presented by Froger et al. (2019). That is,TRISTAN XI Symposium

Original abstract submittal

G. M. Nafstad, G. Desaulniers and M. Stålhane3

to the best of our knowledge, the only papers describing exact solution methods for the E-VRPNL. Froger et al. (2021) presents a matheuristic for the E-VRP-NL with capacitated charging
stations. They also test their algorithm on the benchmark instances presented by Montoya et al.
(2017), and currently have many of the best known solutions.
Lee (2021) presents a Branch-and-Price method for the E-VRP-NL. However, in their workthe recharging function is not linearized. This leads to a very complex pricing problem. The
columns generated with the pricing problem represent no-charge-segments. No-charge segments
are sequences of nodes, where the first and last nodes are either the depot or recharging nodes
and the remaining are customer nodes. The master problem is an arc flow formulation using
no-charge-segments as arcs.

2Solution method

The solution method used is based on BP&C, which is arguably the most successful method
for solving most extensions of the vehicle routing problem. For recent advances in BP&C forVRPs, see Costa et al. (2019). The master problem is a set partitioning problem and the pricing
problem is a shortest path problem with resource constraints (SPPRC). The advantage of using
a set partitioning formulation contrary to an arc flow formulation, as done by Lee (2021), is thatthe master problem formulation gives a tighter dual bound. In addition, in this case it results inthe need to solve a single pricing problem. Lee (2021) needs to solve a pricing problem for eachpair of start node, recharging node and end node. Its advantage is that each pricing problem
will be significantly faster than the one solved when using a set partitioning formulation.
The SPPRC is solved by dynamic programming with a labeling algorithm. An important factor
for a successful labeling algorithm, is the ability to identify and prune labels that are provably nota part of the optimal solution. Such pruning is called dominance. Pareto frontiers representing
the recharging potential for the labels are compared to conclude on dominance. This feature alsoenables partial dominance to increase the efficiency of the labeling algorithm. Then, a subset ofthe feasible extensions to the end node is pruned. Partial dominance can also lead to complete
dominance when several labels together dominate the entire pareto frontier of the dominatedlabel.
Several well known techniques are used to improve the overall efficiency of the algorithm. For
more information on the techniques see the survey by Costa et al. (2019). To speed up thepricing of columns, a bidirectional labeling algorithm has been implemented. NG-path is usedto strengthen the dominance of labels and improve the efficiency of the labeling algorithm. Thedrawback is a weakening of the master problem. Limited memory subset row cuts are used tostrengthen the dual bound.
The branching strategy is to first branch on the number of routes used, then the number of visits
to each recharging node and lastly on the flow on each edge.

3Preliminary results

The computational tests were run on a Lenovo ThinkSystem SD530, running CentOS 7.9.2009,
with 3.6GHz Intel Xeon Gold 6244 CPU and 384Gb RAM. The algorithm is implemented inC++ and compiled with GNU GCC 10.3.0. The linear models are solved using Gurobi 9.1. The
upper limit on the computation time was set to three hours. That is the same time limit as
being used when testing the MILPs by Froger et al. (2019).
Our BP&C method is tested on the Montoya benchmark instances (Montoya et al., 2017). Itsolves all 20 10-customer instances with an average computation time of about 13 seconds,
TRISTAN XI Symposium

Original abstract submittal

G. M. Nafstad, G. Desaulniers and M. Stålhane4compared to an average of about seven minutes for the path-flow model by Froger et al. (2019).
They solve 5 of the 20 20-customer instances while our method solves 16. In addition, the model
is able to solve 8 of the 20 40-customer instances, whereas Froger et al. (2019) solve none. Theseresults are preliminary as we are continuing to improve our BP&C algorithm. Updated results
will be presented at the conference.

References
Conrad, Ryan, & Figliozzi, Miguel. 2011. The Recharging Vehicle Routing Problem. Proc. of the 61st
Annual IIE Conference, 01.
Costa, Luciano, Contardo, Claudio, & Desaulniers, Guy. 2019. Exact Branch-Price-and-Cut Algorithms
for Vehicle Routing. Transportation Science, 53(4), 946–985.
Desaulniers, Guy, Errico, Fausto, Irnich, Stefan, & Schneider, Michael. 2016. Exact algorithms for electricvehicle-routing problems with time windows. Operations Research.
Erdelić, Tomislav, & Carić, Tonči. 2019. A Survey on the Electric Vehicle Routing Problem: Variants
and Solution Approaches. Journal of Advanced Transportation, 2019, 5075671.
Erdoğan, Sevgi, & Miller-Hooks, Elise. 2012. A Green Vehicle Routing Problem. Transportation ResearchPart E: Logistics and Transportation Review, 48(1), 100–114.
Froger, Aurélien, Mendoza, Jorge E., Jabali, Ola, & Laporte, Gilbert. 2019. Improved formulations andalgorithmic components for the electric vehicle routing problem with nonlinear charging functions.
Computers and Operations Research, 104(apr), 256–294.
Froger, Aurélien, Jabali, Ola, Mendoza, Jorge E., & Laporte, Gilbert. 2021 (Feb.). The electric vehicle
routing problem with capacitated charging stations. working paper or preprint.
Lee, Chungmok. 2021. An exact algorithm for the electric-vehicle routing problem with nonlinear charging
time. Journal of the Operational Research Society, 72(7), 1461–1485.
Montoya, Alejandro, Guéret, Christelle, Mendoza, Jorge E., & Villegas, Juan G. 2017. The electric vehicle
routing problem with nonlinear charging function. Transportation Research Part B: Methodological.
Schneider, Michael, Stenger, Andreas, & Goeke, Dominik. 2014. The electric vehicle-routing problem
with time windows and recharging stations. Transportation Science, 48(4), 500–520.

TRISTAN XI Symposium

Original abstract submittal