Distribution Optimization With Stochastic Customers And Demands

Distribution model planning and distribution routing are two major problems of logistics distribution optimization and scheduling. In combinatorial optimization, these two problems are researched as clustering problem and routing problem. Both of the two problems have been proposed for decades. Researchers have already explored deep in these fields and acquired valuable results. In daily logistics distribution, the requirements of customers are not constant. On the contrary, mostly people have to complete the optimization with uncertainty before exact requirements and demands are available. But by now, researches on distribution optimization with uncertain customers and demands are still rare.Based on the existing researches on distribution optimization, especially on the certain clustering, certain traveling salesman problem and certain vehicle routing problem, this thesis focuses on three subproblems of uncertain distribution optimization, in which customers and demands are stochastic. These subproblems includ clustering problem with stochastic object existence, probabilistic traveling salesman problem, and vehicle routing problem with stochastic customers and demands. After problem formulation and modeling, some heuristic algorithms are proposed for each subproblem respectively.Firstly, a new uncertain clustering problem model with stochastic object existence named CPSE is proposed. Based on the K-means algorithm of classic certain clustering problem, a new heuristic algorithm named PK-means is proposed for CPSE. Since clustering results of K-means family algorithms depend on initial clustering centers strongly. To overcome this shortcoming, an improved initialization of clustering centers based on neighbor density is proposed, then it is used in both DK-means algorithm for certain clustering and DPK-means algorithm for CPSE. Experimental results show that, it is necessary to research CPSE separated from nomal certain clustering problme, and design particular algorithms for CPSE. In addition, the experimental results also prove the efficiency of DPK-means for CPSE and its improvement compared with DK-means.Secondly, this thesis considers customer requirements as random element, since in most logistics distribution application, customer requirements are uncertain when people scheduling routes. An uncertain routing problem named probabilistic traveling salesman problem (PTSP) is proposed. Compared with nomal classic traveling salesman problem (TSP), PTSP is much more difficult to solve. After problem formulation and modeling, author found the bottleneck of PTSP solving is complex and costly object function computing. Samilar to the neighborhood search idea of TSP, two neighborhood search methods for PTSP is proposed. With derivation of cost change evaluation, the compute complexity of PTSP's neighborhood search is efficiently decressed from O(n4) to O(n2). Moreover, for common algorithms designing, two approximate evaluations for expected tour length are proposed, and their parameters are analysised with experiments. After discuss the relationship between PTSP solutions and TSP solutions, a new global optimization algorithm named HGSA is proposed. Experimental results indicate that HGSA is more efficient to solve PTSP.Finally, considering the uncertainty of customers and demands in actual logistics distribution, with the capacity restriction of vehicles, an vehicle routing problem with stochastic customers and demands (VRPSCD) is discussed. VRPSCD is much more difficult than classic capacitated vehicle routing problem (CVRP) to solve. After problem formulation and modeling, it is found that the bottleneck to solve VRPSCD is high compute complexition of object value eveluation. Based on neighborhood search idea of CVRP, an approximated evaluation method to compute the change of expected object function value in VRPSCD neighborhood search is proposed. To fit more algorithms designing, sampling approximation for VRPSCD's expected object value is proposed, and the relationship between sampling scale and approximation precision is discussed with experiments. At last, with different customer requirement probabilistic distributions, VRPSCD solutions and CVRP solution with historic average demands are compared with experiments.