Research On Distribution Routing Optimization Problems With Uncertain Factor

As one important part of modern logistics,logistics distribution routing optimization is an important means to reduce the cost of distribution and improve the efficiency of distribution process.This thesis studies two-point distribution routing problem and multi-point distribution vehicle routing problem in distribution routing optimization.On the basis of reviewing the research status of routing optimization,this thesis focuses on the solution method of route optimization,multi-point distribution vehicle routing problem considering stochastic customer demand and load change,and two-point distribution route choice with multiple uncertain factors,and the corresponding solutions are proposed.The main contributions of this thesis include the following three aspects:(1)To solve the Capacitated Vehicle Routing Problem(CVRP)with capacity constraints,a hybrid simulated annealing algorithm(HSAA)based on tabu-search is proposed.Compared with the conventional Simulated Annealing Algorithms(SAA),the HSAA algorithm proposed in this thesis has the following improvements:different from the conventional random initialization method,the k-means clustering algorithm is used to partition clusters and the insertion method is used to adjust clusters to obtain the initial feasible solution,which is helpful to take account of the geographical distribution of customers;Tabu Search(TS)algorithm is used for the neighborhood searching process.The idea of the method is to use K-nearest neighbor algorithm to generate tabu-search tables.Four neighborhood searching methods are used to traverse the tabu tables in a global step-by-step search mode,which enhances the effectiveness of the neighborhood search process while expanding the scope of the neighborhood search.To verify the performance of HSAA algorithm,20 CVRP benchmark datasets are tested,and comparison results with the existing SAA algorithm with restart strategy is provided.The experimental results show that the optimization ability of the proposed HSAA algorithm and the convergence speed under the same temperature attenuation times are better than the existing SARS algorithm.(2)To solve the green VRP(GVRP),a multi-point vehicle routing optimization model considering both stochastic demand and load variation is proposed,and the corresponding solution method is developed by using the proposed HSAA algorithm.In the real-world logistic distribution scenario,the energy consumption rate of a vehicle is proportional to its workload.Conventional vehicle routing optimization model only considers the shortest travelling distance,but ignores the impact of vehicle load on energy consumption,and the obtained optimal route is not the one with lowest energy consumption.On the other hand,existing work only considers the average customer demands,but ignores its randomness.In order to minimize energy consumption at the same time considering the impact of stochastic demand on vehicle load,this thesis proposes a risk probability constraint to describe the probability of overloading caused by stochastic demand,and proposes a simplified strategy of risk probability to reduce the complexity of the algorithm.The experimental results show that,compared with conventional routing models,considering the variation of vehicle load and the randomness of customer demands can effectively avoid vehicle overload and reduce transportation energy consumption,thereby improving the practicability of the optimization results and reducing the cost of logistics distribution.(3)To solve the two-point distribution route choice problem with multiple uncertain factors,an evidence reasoning based route choice method is proposed.Most of the existing research on route choice focuses on static traffic network,which is not consistent to the dynamic stochastic nature of transportation networks in real-world scenarios.In addition,in real-world scenarios,the results of vehicle routing choices are often influenced by multiple factors,and the decision results are often uncertain.Therefore,it is difficult to obtain a reasonable and satisfactory result by only considering a single factor for routing optimization in a transport network.This thesis considers the route choice problem with multi-candidate paths in real-world dynamic transportation network,and a multi-factor evidence reasoning based route choice method is proposed.Firstly,simple supporting evidence is constructed by membership function that transform the factor data into membership values.Next,the Dempster combination rule is used to fuse the basic belief functions(BBAs)of all factors to obtain the global BBA.At last,the path with the largest belief degree is selected as the optimal result.The validity of the proposed method is verified by the actual distribution scenario in Beijing,and the detailed results are provided.The results show that,compared with the Fuzzy Analytic Hierarchy Process(FAHP),the decision results obtained by the proposed method have a higher degree of discrimination,thereby prove that the proposed method has better performance in eliminating the uncertainty of decision results.