Research On Vehicle Routing Problem With Grey Time Windows And Stochastic Travel Time Constraints

The logistics industry has become an important growth point for China’s economy.The vehicle routing problem(VRP)is the core problem of logistics distribution.Scholars have carried out extensive research on this problem and achieved fruitful results.The thesis introduced grey time windows constraints to describe and model the one-dimensional,two-dimensional and three-dimensional loading constraints respectively,and improved the quantum evolution algorithm to solve and analyze the model.The research content and contributions are as follows:1.Improved the quantum evolution algorithm,solve VRP based on the improved quantum evolution algorithm,and use the improved quantum evolution algorithm as the basic algorithm for subsequent chapters.In terms of the improvement of quantum evolution algorithm,the quantum cell body is defined,and a method to exchange the alpha and beta positions of quantum chromosomes under specific conditions is proposed,which reduces the loss of effective information in the evolution process.The full load rate and centripetal angle are defined,and the anthropomorphic greedy algorithm with return weights is designed to easily realize the diversity of initial solutions.2.Introduce the grey time windows to study a new type of VRP: VRP with grey time window constraints.Combining grey system theory and uncertain theory,a new model of VRP: grey constraint programming model is constructed.The grey time windows is used to describe the characteristic of clear upper and lower bounds of the expected and tolerable delivery time in actual delivery.Based on this feature,this thesis whitens the grey time windows in combination with the grey system theory to lay the foundation for the solution of the model.3.Different from the stochasticity of the delivery time of vehicles along the entire route in traditional research,it considers the travel time of vehicles between customers as stochastic,and sets the customer satisfaction threshold.Both the travel time between nodes and the threshold of customer satisfaction affect the vehicle’s choice of customer nodes.Synthesizing the grey time windows of customers,a complex opportunity constraint model is established: the grey opportunity constraint programming model.The grey chance constrained programming model cannot be solved directly by existing methods.After the model transformed,an algorithm is designed to solve the model.4.The two-dimensional loading VRP with grey time windows and stochastic travel time constraints is studied.A grey chance constrained programming model is established.A two-layer heuristic algorithm is designed to solve the problem after the model is transformed.The outer layer of the two-layer algorithm is based on the improved quantum evolution algorithm to optimize the route,and the inner layer algorithm checks the two-dimensional packing constraints.In the processing of the twodimensional packing strategy,a neighborhood search algorithm is constructed based on the bottom and left filling algorithm(BLF),and the compactness function is introduced to decide the selection problem of the packing posture of multiple items.The coloring method is used to easily handle the constraints of first-in-last-out,and solve the problem that the two-dimensional packing algorithm is frequently called and affects the overall efficiency of the algorithm.5.3L-MDCVRP with grey time windows and stochastic travel time constraints is studied.A grey chance constrained programming model is established.After the model is transformed,a two-layer/hybrid heuristic algorithm is designed to solve the model.In the processing of the three-dimensional packing strategy,a neighborhood search algorithm is constructed based on the key point update algorithm,the deepest position filling algorithm and the maximum contact surface filling algorithm.It is proposed that the condition for two objects in three-dimensional space not to overlap is that their projections to the x-axis,y-axis and z-axis have at least one disjoint conclusion,which converts the discrete judgment problem into a continuous numerical calculation problem.The method of coloring the rear of the outermost items is proposed to easily handle the first-in-last-out constraint.The application of the two methods improves the operating efficiency of the frequently called three-dimensional packing algorithm.The thesis comprehensively uses grey system theory,operations research and intelligent optimization algorithms to expand the vehicle problem,establishes a new grey opportunity constrained programming model,gives the model conversion method and designs the corresponding solution algorithm.This research expands the research direction of the vehicle routing problem,enriches related theoretical systems and solving methods,and at the same time provides references and solutions for logistics enterprises to optimize management processes and vehicle scheduling.