Research On Model And Algorithm Of Electric Vehicle Routing Problem

In recent years,the state has vigorously supported pure electric vehicles.Compared with traditional logistics and distribution,the electric vehicles have many advantages such as saving fuel and protecting the environment.Inspired by national policies,many logistics companies have used electric vehicles as distribution tools,and electric logistics vehicles have grown substantially in China.In actual logistics operations,the companies usually consider recharging costs,waiting time costs,vehicle fixed costs,and transportation costs into the total operating costs.From the perspective of enterprises,compared with gasoline vehicles,pure electric vehicles face problems such as excessive purchase costs,longer charging times,and shorter cruising range.Therefore,studying the electric vehicle routing problem has a non-negligible influence on enterprises to reduce logistics costs and increase economic benefits.It is important to organize suitable vehicle distribution paths when dealing with thousands of customers and complex reality constraints.In addition,the electric vehicle routing problem belongs to the NP-Hard problem in the field of mathematics.In 2000,it was listed as one of Millennium Prize Problems which selected by the Clay Mathematical Research of the United States.This problem has quickly attracted great attention in the fields of operations research,applied mathematics,combinatorial mathematics,graph theory and network analysis,and computer applications.In this case,this paper studies the following three types of electric vehicle routing problems from easy to difficult based on the current real logistics environment,and has achieved innovative results in mathematical models and heuristic algorithms.This paper first studies the electric vehicle routing problem with time windows and capacity constraints.The problem includes time window constraints,mileage constraints and capacity constraints.Its objective functions are to minimize the number of transport vehicles and minimize the total mileage.To solve this problem,this paper first established a path-based mixed integer linear programming model to accurately solve the problem of small-scale instances,and then proposed a hybrid heuristic search algorithm to solve large-scale instances and find high-quality local optimal solutions in short reasonable time.We conduct experiments on the instances of Schneider et al.In the test of small-scale instances,the proposed mathematical model can be solved in a very short time,and its performance is better than that of other literature models.In the test of large-scale instances,compared with the state-of-the-art algorithms in other literature,our heuristic algorithm found several better local optimal solutions,which shows the effectiveness of the algorithm.In addition,this paper tests and analyzes different recharging strategies and different objective functions.The results show that allowing partial recharging can further reduce costs but the complexity of the problem is higher.Considering the problem of minimizing the number of vehicles is more complicated than just minimizing the mileage.Next,this paper studies the Heterogeneous-Fleet electric vehicles with time windows and capacity constraints.This problem considers a variety of electric models with different maximum capacity,maximum driving range,recharging speed and fixed cost,and the objective function is to minimize the sum of the total driving cost and the total fixed cost.Compared with the electric vehicle routing problem with time windows and capacity constraints,we not only need to determine each distribution route,but also need to arrange the optimal vehicle type for each distribution route.To solve this problem,this paper extends the path-based model,and enumerates the paths that can be visited by each vehicle type.Our model removes infeasible paths according to the time window and capacity constraints,and removes the dominated paths that through dominated recharging stations.Then,our heuristic algorithm relaxes the time window constraint and mileage constraint and allows infeasible solutions.A dynamic penalty coefficient is introduced into the objective function to search between the infeasible solution area and the feasible solution area.In addition,this paper proposes a labeling algorithm to solve the fixed route vehicle recharging problem exactly.Our model and algorithm are tested on the instances of Hiermann et al.The model of Hiermann et al.is almost impossible to solve for small-scale instances,and they proposed a branch and price algorithm to solve all small-scale cases.Our path-based model can solve most small-scale instances,and can find high-quality upper bound solutions for the rest small-scale instances.Our heuristic algorithm can find the optimal solution for all small-scale instances in a very short time.Since the recharging strategy of Hiermann et al.is to force the vehicle to be fully recharged,we allow partial recharging to further reduce the total costs.Our algorithm is tested on the large-scale instances and this research is an extension of the research work of Hiermann et al.Finally,this paper studies a Multi-trip and Heterogeneous-Fleet Electric Vehicle Routing Problem with Time Windows and Partial Recharging(MTHF-EVRP)based on real business practice in green logistics.This problem stems from the real logistics problems of many logistics companies.We use the instances come from the real business practice of JD.com,one of the largest ecommerce businesses in China.This company accumulates delivery needs for thousands of delivery stations in large cities,such as Beijing.A fleet of heterogeneous electric vehicles can perform multiple trips at the depot center for reloading goods,and can be partially recharged at recharging stations or at depot center.This problem combines the features of multi-trip VRP,heterogeneous-fleet VRP and partial recharging.We expand on the basis of the above research,and consider the recharging costs and waiting costs simultaneously.The objective function of this problem is to minimize the sum of mileage cost,waiting time cost,recharging cost and vehicle fixed cost.Our mathematical model can solve all the 15 customer instances within a limited time,and solve most of the 20 customer instances.We propose a hybrid variable neighborhood search algorithm(Hybrid VNS).Hybrid VNS contains a new problem-specific neighborhood operation,a proposed two-layer exact labeling algorithm and a restart mechanism.The proposed labeling algorithm can make optimal decisions regarding recharging,reloading and selecting vehicle types simultaneously for a fixed route.For small-scale instances(random subsets of JD.com data set),by comparing to our MILP optimal solutions,our Hybrid VNS algorithm is shown to be quite efficient which finds optimal solutions for most cases quickly.In addition,we test Hybrid VNS algorithm on 6 large-scale instances which contain 1000,1100,1200,1300,1400,and 1500 customers.The number of recharging stations in the first instance is 100,and the number of recharging stations in the rest instances is 200.Compared with the state-of-the-art algorithm on the large-scale instances,our algorithm can significantly reduce the logistics cost in the same time,which shows that the great competitiveness of Hybrid VNS algorithm.Besides,we conduct experiments on large-scale instances with four different cases to investigate the benefits of multi-trip,heterogeneous-fleet and partial recharging.The results can provide a basis for decision-making of real logistics companies.This article has innovative results in both mathematical models and heuristic algorithms.Compared with the traditional node-based replica model,the path-based mixed integer linear programming model established in this paper does not need to replicate any recharging station nodes or depot nodes.The hybrid heuristic algorithm proposed in this paper combines the variable neighborhood search algorithm and the label algorithm.Compared with state-of-the-art algorithms,the results on large-scale instances show the great competitiveness of our algorithm.It converges to a high-quality local optimal solution in a short reasonable time.This algorithm can be widely used to deal with large-scale logistics data sets in real scenarios.