# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
###### Abstract  
To develop a non-polluting and sustainable city, urban administrators encourage logistics companies to use electric vehicles instead of conventional (i.e., fuel-based) vehicles for transportation services. However, electric energy-based limitations pose a new challenge in designing reasonable visiting routes that are essential for the daily operations of companies. Therefore, this paper investigates a real-world electric vehicle routing problem (VRP) raised by a logistics company. The problem combines the features of the capacitated VRP, the VRP with time windows, the heterogeneous fleet VRP, the multi-trip VRP, and the electric VRP with charging stations. To solve such a complicated problem, a heuristic approach based on the adaptive large neighborhood search (ALNS) and integer programming is proposed in this paper. Specifically, a charging station adjustment heuristic and a departure time adjustment heuristic are devised to decrease the total operational cost. Furthermore, the best solution obtained by the ALNS is improved by integer programming. Twenty instances generated from real-world data were used to validate the effectiveness of the proposed algorithm. The results demonstrate that using our algorithm can save 7.52% of operational cost.  
t 1 2019  
A real-world EVRP proposed by a logistics company in Wuhan, China is presented in this paper. In the problem, a fleet of heterogeneous electric vehicles departs from the distribution center, delivers or picks up customer parcels within predefined time windows, and finishes at the center. While in transit, a vehicle can return to the center to load parcels to be delivered or unload collected parcels, and it can also go to charging stations as well as the distribution center to fully charge its battery in a fixed time (e.g., 30 min). The objective is to minimize the sum of the acquisition costs of used vehicles, the travel costs of vehicles, the waiting costs at customers and centers, and the charging costs. In Figure 1, two types of electric vehicles, i.e., Vehicle 1 and Vehicle 2, are used to fulfill delivery or pickup requests of customers; the lines having the same color denote a visiting route of a vehicle in the day. The red route does not need to charge; the purple route requires two charges at two different stations, one of which it shares with the black route; and the yellow route with two trips needs to go back to the distribution center. Obviously, the problem combines the features of the capacitated VRP [1], the VRP with time windows [2,3], the heterogeneous fleet VRP [4], the multi-trip VRP [5], and the EVRP with charging stations [6]. Considering its complexity, we must resort to meta-heuristics to efficiently solve the proposed problem.  
This paper focuses on developing a heuristic approach based on the adaptive large neighborhood search (ALNS) and integer programming (IP) to solve the proposed problem. In the algorithm, we devise a charging station adjustment heuristic based on labeling algorithm to obtain the optimal selection and location of charging stations in a given sequence of customers and a departure time adjustment heuristic to calculate the optimal departure time when vehicles should first leave from the distribution center. After the termination of the ALNS iterative process, the best solution is further improved by set-partitioning-based integer programming. In computational experiments, the effectiveness of the components of the proposed algorithm was validated by 20 instances generated from real-world data.  
The rest of this paper is organized as follows. Section 2 provides a brief review of the pertinent literature about the EVRP. Section 3 outlines a definition for the proposed problem. Section 4 presents the solution approach for the problem. Section 5 reports the computational results. Section 6 presents the conclusions and future research directions.