Research On Routing Similarity Based Bi-level Heuristic Algorithm For The Electric Vehicle Routing Problem

Transportation is one of the major sources of air pollutants and greenhouse gas emissions.Vehicle routing problems(VRPs)are concerned with the scheduling of vehicles in the transportation and have received much attention form many scholars for its great economic and environmental benefits.In recent years,the development of electric vehicle technology provides an alternative to conventional fuel vehicles for logistics companies.Electric vehicles have the merits of less pollution and low noise,but the characteristics of limited cruising range and limited number of charging stations bring new challenges.The electric vehicle routing problems are thus proposed.They have been widely used in transportation,logistics and other fields,and have received much attention from many scholars.The capacitated vehicle routing problem(CVRP)is a classical problem in VRPs.To tackle the insufficient convergence and exploration capability and time-consuming in its solving,an adaptive large neighborhood search based artificial bee colony algorithm for CVRP is proposed.In this algorithm,five removal operators and two insertion operators were designed.Moreover,a distinct operator-using strategy,a careful scouter strategy and a loose update strategy are incorporated into the proposed method to improve its performance.As a result,the proposed algorithm can search efficiently for acceptable solutions,as it is able to converge to most of the best known solutions on the experimental datasets,and four best known exact solutions are updated.The results show that the proposed approach have excellent comprehensive performance and all three optimization strategies are effective.For EVRP,A kind of pseudo node is added to its model under the assumption that any vehicle passes through at most one recharging station between two customers,and its realistic rationality is analyzed.Thus,the electric vehicle routing problem with a kind of pseudo node(EVRPPN)is proposed.The EVRPPN puts additional constraints on the charging timing of vehicles,which reduces the solving difficulty of the problem.Then,a bi-level heuristic(BH)for EVRPPN is given.Following the idea of bi-level solving of EVRP,the problem is decomposed into two sub-problems,CVRP and Fixed Route Vehicle Charging Problem(FRVCP).A simulated driving(SD)algorithm and a customer order adjustment strategy are given to solve CVRP,and a roulette random removal-heuristic(RRH)algorithm to solve FRVCP.In addition,a variable extent shaking strategy(VES)is designed to jump out of the local optimum.Finally,a similarity-based framework for combinatorial optimization problems(COPSF)is proposed to improve the search breadth of its incorporated algorithm.First,a general definition of similarity for COPs is given,and a framework for maintaining a population of local optima in which any two solutions are dissimilar is designed.Then,the route division strategy of BH is improved,and a route combination algorithm is designed to optimize high-quality solutions based on the COPSF.The presented algorithm achieves state-of-the-art results on the small and mediumscale EVRP benchmark dataset and updated one best known solution.The experimental results show that BH has advanced performance,and both COPSF and the proposed strategies can effectively improve the algorithm’s performance.