An Improved Tabu Search For Time-Dependent Electric Vehicle Routing Problem

In recent years,the rapid development of e-commerce has brought new opportunities and challenges to the development of logistics.The logistics industry combines big data,cloud computing,artificial intelligence and other technologies to transform into intelligent logistics.Intelligent vehicle scheduling is an important issue in intelligent logistics that has received extensive attention and research.At the same time,the increasingly frequent logistics transportation has caused adverse impacts on the environment and resources,so the state and logistics companies have begun to promote the use of electric vehicles in the transportation link,which meets the national energy conservation and emission reduction requirements and the development trend of green logistics.In addition,the increasing demand for travel has resulted in complex and diverse traffic conditions.Static models with constant travel time have been unable to meet actual needs,while time-dependent models that consider dynamically changing traffic conditions are more practical and executable.Based on the time-dependent vehicle routing problem and the green vehicle routing problem,this paper proposes a Time-Dependent Electric Vehicle Routing Problem with Heterogeneous Fleet,Multiple Trips,Recharging Stations and Time Windows(TD-EVRPTW),and then establishes a mixed integer programming model.The core of this model is to construct a travel time function to reflect the time dependence of travel time,and to consider the constraint of the battery capacity of the electric vehicle on the mileage.In this paper,an improved tabu search heuristic algorithm(Improved-TS)is designed to solve the TD-EVRPTW.The tabu search algorithm and dynamic planning based on label-setting algorithm are combined to design the customer movement operators between routes and the recharging station movement operator within the route,to optimize the distribution customers and charging decisions separately.Moreover,a shake method is added to the algorithm to jump out of the local optimal solution by randomly selecting the neighborhood of the operators.The algorithm is also optimized from an engineering perspective to improve the performance of the algorithm.Finally,computational experiments use JAVA and perform on test instances based on the actual enterprise data set,and computational results show that the Improved-TS solves all of the instances accurately.In contrast,experiments also use the CPLEX solver to build and solve the TD-EVRPTW on some instances,and the results including the quality of the solutions and the computational times of the two methods are compared to verify the effectiveness and practicability of the Improved-TS.