Optimization Models And Algorithms Of Vehicle Routing Problem Under Uncertain Demands

Traffic and logistics are essential industries to support the development of social economy,and the vehicle routing problem as a classical and hot issue in combinatorial optimization and operations research,is mainly to arrange the route and scheduling of vehicles reasonably under certain constraints to optimize the overall distribution service cost.In real life,some unknow information often appear in distribution system,the distribution system with unknow information belong to the uncertain problem.Since it has a great wide application background in the fields of material dispatching,electronic commerce,railway civil aviation,bus line and so on,it is of significant theoretical and practical significance to study and optimize the uncertain vehicle routing problem which closed to the actual production operation link.Based on the review of the corresponding uncertain programming theory,VRP research progress and heuristic algorithm,the paper firstly analyzes the classical CVRP.A hybrid heuristic algorithm combining variable neighborhood search and biological symbiotic search is also designed which adopts the sequential coding method.The comparison and analysis of the literature examples show that the hybrid algorithm and the model are effective to CVRP.Based on the two-stage optimization strategy of pre-optimization and rescheduling,the thesis firstly analyzes and deals with the fuzzy demand variables in CVRPFD.By introducing the fuzzy credibility theory and combining with the preset risk preference level of the decision-maker,the fuzzy variable can participate in the follow-up optimization step by fuzzy chance constraint.According to the constructed fuzzy opportunity programming model of the CVRPFD,a two-stage hybrid variable neighborhood tabu search algorithm is designed.And the paper proposes a new client-point rescheduling strategy which can solve the problem of poor return at previous failure points and difficulty in selecting appropriate return points.All the incomplete service sub paths will be rescheduled according to the rescheduling strategy when the path fails,which can reduce the additional cost of distribution and ensure that all the clients receive the service.For CVRPSD,the paper firstly analyzes the random demand variables at the customer point,and a stochastic chance constraint is set to deal with random variables.According to the central limit theorem for the stochastic chance constraint,the deterministic equivalent processing can obtain for random variables.Due to the influence of stochastic demand variables,CVRPSD has the characteristic of two stages optimization in the process,and the optimization stage first obtains the path scheme with stochastic chance constraint programming model,then adjusts the scheme according to the proposed failure point rescheduling strategy when the path failure occurs.A hybrid algorithm combining variable neighborhood search and scatter search is designed to solve the two-stage optimization of CVRPSD.Through the analysis of time complexity and comparison of corresponding CVRP and CVRPSD instances,it shows that the stochastic chance constraint programming model and hybrid algorithm are effective.The results of instances show that the new failure point rescheduling strategy can effectively reduce the overall distribution cost.Based on the research of UVRP under the influence of fuzzy and stochastic factors,the paper studies the CVRPDR which is different from the two-stage optimization features of the first two problems.The characteristic of dynamic customer demand makes the CVRPDR has to realize the solution through periodic multistage optimization.And the optimization strategy has great influence on the total cost of the final scheme.The paper firstly analyzes the dynamic characteristic of the new customers appear after the optimization is begin,and then puts forward a periodic real-time reset strategy based on time slice partition to matter the need of dynamic customers.And the vehicle delay service mechanism can balance the service demand of new and old customers which will reduce the cost of vehicle delivery.According to the above strategy,the hybrid variable neighborhood artificial colony algorithm is designed to solve the CVRPDR and it allows the sub path of vehicle routing scheme to be changed dynamically between time slices which is more suitable for dynamic problem solving.