| Ant colony optimization(ACO)is an intelligent bionic algorithm which simulates the foraging behavior of ant colony.It uses special chemical substance called pheromone ants produce to communicate and exchange information between individuals and environment.Ants determine the forward path which to move via recognizing pheromone concentration.This behavior has inspired people to create artificial ants to solve combinatorial optimization problems and got significant results.Hence the various problems in the real world can be resolved orderly through their mutual cooperation.Nevertheless,the conventional ACO mainly deals with the static optimization problems.That is to say,the environment is invariant during the execution of algorithm.Due to the fixed environment,ACO can gradually converge and ultimately find an optimal solution.In fact,the most problems of reality are dynamic,namely the changing environments.It is complicated and difficult to handle these problems where the objective functions,constraints and control parameters may be variable over time.Thus,Taking advantage of effective information from the previous environment should be particularly emphasized.Even though there is much trouble in addressing dynamic problems,the ACO has some advantages in transmitting environmental information owing to their robustness and self-adaptability.They can quickly track the optimal solution when the environment changes according to the pheromone deposited on the path.In this thesis,the ACO is utilized to solve three dynamic optimization problems which contain dynamic travelling salesman problem(DTSP),dynamic vehicle routing problem(DVRP)and dynamic location routing problem(DLRP).The changing environments are composed of random and cyclic dynamic traffic factors,which can duly reflect the traffic jam.Meanwhile,new variants of ACO are proposed to cope with respective problems.Firstly,the ACO with neighborhood search(NS-ACO)is presented to address the DTSP with random changes.Since the solution of DTSP is a closed route,local optimization can enhance the quality of solution in dynamic environments.Neighborhood search is an effective method to optimize the framework of solutions.Three optimized strategies composed of swap,insertion and 2-opt operations are randomly selected to revise solutions.In this way,the diversity of solutions can be enhanced,implying it is a high probability to quickly find a better solution when the changing environment occurs.The experiment indicates NS-ACO is superior to conventional ACOs and the ACO with random immigrant.Secondly,the ACO with three immigrant schemes(i.e.,random immigrants,elitism-based immigrants and memory-based immigrants)is used to resolve the DVRP.The DVRP has several vehicle routes,and local optimization is very complicated and inefficient for handling this problem.Thus,immigrant schemes are used to improve the ACO's ability to track optimal solution in dynamic environments.Three immigrants play an important role and indicate distinctive results in different scales of DVRP.The comparative experiment demonstrates my proposed ACO is effective and efficient.Finally,the ACO with improved K-means clustering algorithm(KACO)which uses three immigrant schemes is put forward for DLRP.The clustering method is novel for selecting depots in DLRP.The improved K-means algorithm called distance cost function automatically determines the depot and its surrounding cities.Then,the KACO with three immigrants can effectively and efficiently handle the DVRP.The experiments illustrate the clustering algorithm optimizes the structure of solution to enhance the property of immigrants.Thus,KACO with three immigrants can perform much better than the ACO without K-means algorithm,traditional ACOs and other heuristic methods such as simulated annealing and genetic algorithm.Therefore,the whole experiments demonstrate my proposed ACOs are superior in three dynamic problems,suggesting they are the promising approaches for optimizing dynamic problems. |
PDF Full Text Request