Research On Capacitated Vehicle Routing Optimization Under Uncertain Demands

With the rapid development of digital economy and information technology,logistics industry has entered a rapid development period and has become an important driving force of the development of our society.Vehicle Routing Problem(VRP)widely exists in the field of logistics transportation scheduling.A reasonable vehicle distribution scheme is a key factor to improve the transportation efficiency of logistics enterprises and reduce the distribution cost.Therefore,in recent years,the research on vehicle routing optimization has gradually become a hot topic both in academia and industry.The Capacitated Vehicle Routing Problem with Uncertain Demands(CVRPUD)is a special extension form of VRP and belongs to NP-hard Problem.Different from the traditional VRP,the uncertainty of customer demands tends to make the single optimal solution unfeasible or non-optimal.Under the condition of vehicle load restrains,it requires managers to arrange the distribution order of customer reasonably,so as to avoid or reduce the loss brought by uncertainty,achieving distribution costs minimized or the shortest distance.However,most of the existing research on CVRP is based on the deterministic demand,which can not fit the actual vehicle scheduling application well.This thesis mainly constructs an optimization model of CVRPUD,aiming at the uncertainty of customer demands.Firstly,in view of the sufficient historical customer information,this thesis adopts the random variable following Poisson distribution to model,and the problem is solved by stochastic optimization method.Secondly,in view of the lack of historical customer information,this thesis introduces triangular fuzzy number as a fuzzy variable to describe customer demands,and adopts fuzzy optimization method to solve the problem.Finally,in view of the special situation of temporary increase or decrease of customer points,based on the perspective of multimodal optimization,this thesis obtains multiple vehicle alternatives simultaneously,and the vehicle distribution scheme can be flexibly adjusted according to the relative coordinates of changing customer points,so as to better cope with the impact of uncertain customer demands.At present,the research on CVRPUD is still in the initial stage.This thesis designs optimization algorithms for three optimization models,aiming at providing robust scheduling schemes for enterprise managers,and further enriching and deepening the vehicle scheduling theory and method.The main research achievements and innovation of this thesis can be summarized as follows:(1)A capacitated vehicle routing optimization model under uncertain demands based on stochastic optimization method and solution algorithm are proposed.The model characterizes customer demands through Poisson distribution,and equivalently replaces random chance constraint with deterministic constraint,thus constructing corresponding random optimization model.To solve this problem,a solution coding scheme based on segmentation points is proposed under the framework of Jaya algorithm,and a repair strategy is incorporated to deal with the infeasible solution.On this basis,a hybrid Jaya(HJaya)algorithm is proposed to solve CVRPUD by combining three local search strategies.The experimental results verify the effectiveness of the proposed encoding and decoding scheme and the superiority of HJaya algorithm.(2)A capacitated vehicle routing optimization model under uncertain demands based on fuzzy optimization method and solution algorithm are proposed.It is difficult for decision makers to predict future information when past experience with customer demands is unreliable or missing.In this regard,this thesis takes customer demands as fuzzy variable through triangular fuzzy number,and establishes a fuzzy optimization model based on credibility theory.On this basis,combining with the framework of hyper-heuristic algorithm,by introducing the mechanism of reinforcement learning,taking Q-learning algorithm as the high-level heuristic strategy(HLH)and combining with the problem characteristics to design seven low-level heuristic rules(LLH)as the selectable action set,through the reward and punishment mechanism of Q learning algorithm to realize the choice and acceptance of actions,this thesis proposes a Qlearning based hyper-heuristic(QHH)algorithm,so as to achieve the optimization of the problem.In the experimental part,simulation analysis is carried out based on the fuzzy improved instance set,and the results verify the effectiveness and robustness of the proposed QHH algorithm to solve the CVRPUD.(3)A capacitated vehicle routing optimization model under uncertain demands based on multi-modal optimization method and solution algorithm are proposed.In view of the demand changes caused by the temporary increase or decrease of customer points,based on the perspective of multimodal optimization and the framework of Differential Evolution(DE)algorithm,the multimodal optimization of the problem is realized by improving the operators such as selection and crossover,and combining with the elite archiving strategy.The experimental results show that the proposed Multimodal Differential Evolution(MDE)algorithm can effectively obtain multiple vehicle distribution schemes,and can effectively cope with the impact of demand adjustment caused by temporary increase or decrease of customer points.To sum up,the research on CVRPUD in this thesis can provide a more robust vehicle distribution scheme,help enterprises reduce transportation costs,improve management efficiency,and enhance the intelligent level of logistics distribution,which has important theoretical value and practical significance.