Electric Vehicle Routing Problem Based On Logistics Distribution System

With the rapid economic development,the problem of energy crisis,environmental pollution and greenhouse effect are becoming increasingly severe.The quantity of gasoline vehicles and diesel vehicles retain sustained growth and their exhaust gas comprises an important part of urban air pollution.These put forward the higher request of energy conservation and emission reduction to the auto industry,which makes developing new energy vehicles based on electric vehicle(EV)an inevitable trend.At present,countries and societies are starting to focus on EV applications,and give subsidies and preferential tax policies to EV purchasing.In order to keep up with the pace of development and respond the call of government,logistics enterprise put more and more emphasis on the applications of EV.How to improve the deliver efficiency,make the most of battery recharging stations and battery swapping stations,take advantage of EV in the environmental protection and minimize the logistics cost,have become the current urgent problems.In this background,this thesis studys electric vehicle routing problem based on logistics distribution system,and obtained some innovative achievements.In order to conform to this development tendency of electric vehicles in logistics distribution system,this dissertation studies the electric vehicle routing problem with time windows,and takes limited battery capacities,recharging time and travel time of electric vehicles of the practical application into account.Aims at minimizing the total distance of logistics distribution system,a corresponding mixed integer programming model is established.In order to obtain the optimal solution,a modified branch-and-price algorithm is designed to solve the problem.In the experiment part,the accuracy of model and algorithm are validated by the improved Solomon instances,and the sensitivity analysis of battery driving range and battery recharging rate are also conducted,demonstrate the proposed algorithm has a certain application value.Subsequently,this dissertation studies the heterogeneous electric vehicle routing problem with time windows,considering that the logistics enterprises usually adopt different types of vehicles to provide service for customers.The types of vehicles differ with respect to battery capacity,battery charge rate,battery consumption rate,load capacity,fixed cost and variable cost.The problem is formulated as a mixed integer programming model,which aims at minimizing the total cost of logistics distribution system.The optimal solution is obtained by a branch-and-price algorithm,and two strategies to improve lower bound and upper bound of the solution are added to the algorithm.In the experiment part,the computational results based on several groups of benchmark instances show the accuracy and efficiency of the model,and prove the effctiveness of the two accelerating strategies.In addition,the effect of variable cost is analyzed based on different sized examples.With progress of sustainable development of city logistics,solving the common problems in city logistics appears especially important.This dissertation studies the two-echelon capacitated electric vehicle routing problem.In this distribution mode,goods first are deliveried from distribution center to satellites(transfer station)by large electric vehicles,then are deliveried from satellites to customers by small electric vehicles.An integer programming formulation of the problem is proposed,and a hybrid algorithm that combines a column generation and an adaptive large neighborhood search(CG-ALNS)is designed to solve the problem.Extensive computational experiments of the two-echelon capacitated(electric)vehicle routing problem are conducted to demonstrate the applicability of the proposed model and the efficiency of the CG-ALNS.In addition,the sensitivity analysis of battery driving range in both echelons and the effect of the distribution mode to the emissions reduction efficiency are conducted.