Research On Multi-Compartment Electric Vehicle Routing Problem Based On Improved Estimation Of Distribution Algorithm

The multi-compartment vehicle routing problem(MCVRP)in which multiple products can be delivered at the same time,exists widely in real logistics.Meanwhile,pure electric vehicles have been becoming popular logistic tools due to their excellent characteristics such as energy saving and environmental protection.Therefore,after introducing electric vehicles to the MCVRP,this paper established a mixed integer programming model for the multi-compartment electric vehicle routing problem with soft time windows and multiple charging types(MCEVRP-STW&MCT),with the objective of minimizing the function composed of vehicle cost,distribution cost,time window penalty cost and charging service cost firstly.Then,an improved estimation of distribution algorithm based on Lévy Flight optimization(EDA-LF)is proposed to solve the model.The EDA-LF algorithm adopts the representation with permutation,uses the probability matrix as the probability model and updates it through an adaptive update strategy.At the same time,to enhance the ability of the EDA algorithm to jump out of the local optimum,the EDA-LF performs the local search operation based on Lévy Flight several times at the optimal solution of each generation.Finally,after using the Taguchi orthogonal experiment design of experiment(DOE)to set the algorithm parameters of the EDA-LF,a series of simulation calculations and comparisons of different algorithms are carried out and the experimental results verify the effectiveness of the model and EDA-LF algorithm.In addition,since the outbreak of the novel coronavirus in 2019,people have responded to the state’s call to stay at home to reduce the possibility of being infected.At the same time,the safe supply of daily life for people living at home or in isolation has become a major livelihood issue.It also puts forward new requirements for cold chain logistics which can provide high-quality transportation at the required temperature for all kinds of fresh food,such as the higher delivery timeliness caused by food shortage and the strict duration restrictions caused by the limited effectiveness of the protective clothing worn by driver.Therefore,this paper considers the constraints of power,compartment capacity,hard time windows and maximum vehicle delivery time as well as some factors such as partial charging strategy and the situation that power consumption while charging,then proposes a multi-compartment electric cold-chain vehicle routing problem with hard time windows and partial recharging strategy(MCECVRP-HTW&PR)and establishes its mathematical model with the objective of minimizing the function composed of vehicle cost,distribution cost,loss cost,refrigeration cost and charging service cost.After that,considering that the representation with permutation is simple and easy to construct solution but it’s often difficult to get the best partition because of its high dependence on the sequence of nodes in the path,while the representation with delimiter can solve this defect properly,an improved estimation of distribution algorithm based on multi-neighborhood search operator(EDA-MN)is proposed after combining with this representation with delimiter.The EDA-MN algorithm designs the probability model,sampling strategy and update strategy specifically based on this representation after constructing a new decoding scheme.At the same time,in order to overcome the shortcomings of the EDA algorithms that it is easy to fall into the local optimum and enhance the fine search ability,the EDA-MN performs the local search operation based on multi-neighborhood search operator at the optimal solution of each generation.Finally,after selecting the best charging strategy from the six partial charging strategies,the DOE is used to set the algorithm parameters of EDA-MN.Then,a series of comparison experiments among the EDA-MN and other algorithms are carried out,and the results verify the effectiveness of the EDA-LF algorithm.In addition,sensitivity analysis and some other comparative experiments related to the problem are also carried out.