Research On Evolutionary Algorithms For Solving Two Logistics Planning Problems Under Uncertainty

Over the years,logistics planning has received extensive attention due to its wide application in real world.Recently,logistics planning under uncertainty has become a hot topic since there exist dynamic and stochastic changes in a large number of real world logistics planning problems.To address logistics planning problems under uncertainty,a large variety of evolutionary algorithms have been developed on account of their effectiveness in solving other logistics problems.Nevertheless,there still exist some difficulties for these algorithms to handle the uncertainty in logistics planning problems in terms of effectiveness and efficiency.To this end,this dissertation works on developing effective evolutionary algorithms to solve two typical logistics planning problems under uncertainty: shelter location problem under uncertainty of road networks(USLP)and dynamic vehicle routing problem with uncertain customer requests(DVRP).Specifically,the main contributions of this dissertation consist of the following four parts:(1)This dissertation proposes a clustering-based surrogate-assisted multi-objective evolutionary algorithm,termed AR-MOEA+SA,in the framework of a recently developed evolutionary algorithm AR-MOEA,to solve USLPs.In AR-MOEA+SA,a clustering based surrogate modeling method is suggested to approximately calculate the evacuation distance for individual evaluation with a small computational cost since calculating the evacuation distance for exact evaluation is very expensive.Moreover,due to the fact that there often exist a large number of communities needing to be considered in shelter location,a clustering strategy is suggested to convert the surrogate of high-dimensional problem into the one of low-dimensional problem in the proposed AR-MOEA+SA for efficiently building the surrogate model.Experimental results on a variety of test instances demonstrate the superiority of the proposed AR-MOEA+SA over state-of-the-art approaches to USLPs in terms of both computational efficiency and solution quality.(2)This dissertation proposes a demand coverage diversity based evolutionary algorithm,termed ACO-CD,in the framework of ant colony algorithm,to solve DVRPs.Despite that diversity based algorithms are typical methods for solving DVRPs,it is still difficult for most of them to include the newly appeared customers that are far from planned routes in route planning at a low traveling cost.Hence in ACO-CD,a demand coverage diversity adaptation method is suggested to maintain the diversity of covered customers in routes so that theoptimizer can effectively response to the new customers even when they get far from planned routes.Experimental results on 27 DVRP test instances demonstrate the effectiveness of the proposed demand coverage diversity adaptation method and the superiority of the proposed ACO-CD over four state-of-the-art DVRP algorithms in terms of solution quality.(3)This dissertation proposes a pairwise proximity learning-based ant colony algorithm,termed PPL-ACO,for efficiently solving DVRPs.Despite that ACO-CD can effectively tackle newly appeared customers in DVRPs,it is difficult for ACO-CD to efficiently track dynamically changed optimal routes in DVRPs.Hence,PPL-ACO is proposed to quickly track the optimal routes in DVRPs.In PPL-ACO,a pairwise proximity learning method is suggested to facilitate ACO efficiently track the optimal routes.Specifically,the pairwise proximity learning method first predicts the local visiting orders between customers in the optimal routes after the occurrence of changes,which is on the basis of learning from the optimal routes found before the changes occur.Then the local visiting orders predicted by the suggested learning method are incorporated into ACO to substantially reduce the search space of ACO,making ACO efficiently track the optimal routes.Experimental results on 27 popular DVRP instances with up to 1000 customers show that the proposed PPL-ACO significantly outperforms four state-of-the-art approaches to DVRPs in terms of both efficiency and effectiveness.The results on a real case of Nankai Strict,Tianjin,China also verify that the proposed PPL-ACO is more effective and efficient than the four compared approaches in solving real-world DVRPs.(4)This dissertation proposes a benchmark generator for online dynamic optimization problem(OL-DOP)and captures the characteristics of DVRPs,where the solutions found for a static problem in a previous environment will influence the problems in future environments.Despite that the OL-DOP is a widespread real-world dynamic optimization problem,there are lack of benchmarks that can reflect the influence of the solutions found for a static problem in a previous environment on the problems in future environments in OL-DOPs.Therefore,the proposed benchmark generator for OL-DOPs defines different types of influences of the solutions found in each environment on the problems in the next environment with different types of functions.Moreover,the dynamism degree can be tuned by a set of predefined parameters in these functions.Based on the proposed generator,we suggest a test suite consisting of ten continuous OL-DOPs and two discrete OL-DOPs.The empirical results demonstrate that the suggested OL-DOP test suite is characterized with time-deception in comparison with existing DOP benchmark test suites,and is able to analyze the ability of dynamic optimization algorithms in tackling the influence of the solutions found in eachenvironment on the problem in the next environment.