# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 2 Literature Review  
Research on the VRP and its variants is increasing tremendously in the literature [7, 8, 9]. [PERSON] et al. [10] presented a survey of the existing research in the goods distribution with electric vehicles. This section mainly reviews the very recent developments of the EVRP and its variants.  
Figure 1: Illustration for the proposed problem.  
[PERSON] et al. [11] introduced the EVRP with time windows which considers the possibility of partial recharges at any station. They proposed a hybrid heuristic based on a variable neighborhood search (VNS) algorithm and a tabu search (TS) heuristic. [PERSON] et al. [12] exploited constructive and local search heuristics within a non-deterministic simulated annealing framework to solve an EVRP with multiple technologies and partial recharges. [PERSON] et al. [13] proposed an iterated TS for the mix fleet VRP with heterogeneous electric vehicles. [PERSON] and [PERSON] [14] presented an electric vehicle battery swap location routing problem that determines the location of battery swap stations and the routing of electric vehicles under battery driving range limitations. In the problem, vehicles can stop at battery swap stations to swap their battery for a fully charged battery. They proposed a four-phase heuristic called SIGALNS (Sweep heuristic, Iterated Greedy, Adaptive Large Neighborhood Search) and a two-phase TS-modified Clarke and Wright Savings heuristic to solve the problem. [PERSON] et al. [15] addressed the electric vehicle scheduling problem in which a set of timetabled bus trips should be carried out by a set of electric vehicles. The vehicles can be recharged fully or partially at any recharging station. They proposed an ALNS algorithm to solve it. [PERSON] and [PERSON] [16] studied the EVRP with time windows and partial recharging and design an ALNS algorithm to solve it. [PERSON] et al. [6] introduced the electric fleet size and mix VRP with time windows in which the vehicle is assumed to recharge to full capacity on visit of a recharging station. They solved the problem using the branch-and-price algorithm and the enhanced ALNS algorithm. [PERSON] et al. [17] presented four variants of the EVRP based on the allowable times of recharges per route and partial or full recharges. For each variant, they proposed the branch-price-and-cut algorithm with customized mono-directional and bidirectional labeling algorithms to solve it. [PERSON] et al. [18] considered the EVRP with a nonlinear charging function, which assumes that the battery-charge level is not a linear function of the charging time. They developed a hybrid meta-heuristic combining an iterated local search (ILS) and a heuristic concentration method to solve the problem. [PERSON] and [PERSON] [19] introduced a location-routing problem that considers routing of electric vehicles and positioning decisions for charging stations. Partial recharges are allowed in the problem. They presented an ALNS, which is improved by local search and labeling algorithms, and devised new penalty functions for neighborhood evaluation. [PERSON] et al. [20] designed an adaptive VNS algorithm to solve the battery swap station location-routing problem proposed by [PERSON] and [PERSON] [14]. [PERSON] et al. [21] devised an ant colony algorithm to solve the EVRP with recharging stations to minimize energy consumption. [PERSON] et al. [22] proposed an ILS heuristic to the mixed fleet vehicle routing problem with partial battery recharging and time windows in which the fleet is composed of electric and conventional vehicles. [PERSON] et al. [23] proposed a new model, a heuristic, and an exact labeling algorithm for the EVRP with nonlinear charging functions.  
From the literature review, we can find that differing charge strategies and objectives make the solution approaches not interchangeable and that problem-specific optimization components must be designed to accommodate the features of our problem, which motivates us to design a sophisticated heuristic for solving it.