The Research On Multi-Objective Routing Problems Based On Ant Colony Optimization Algorithm

Routing problems, such as the traveling salesman problem and the vehicle routing problem are widely studied both because of their classic academic appeal and their numerous real-life applications. Similarly, the field of multi-objective optimization is attracting more and more attention, notably because it offers new opportunities for defining problems. Focusing on ant colony optimization algorithms for solving multi-objective routing problems which is closer to real-life applications than routing problems, the main achievements of this thesis can be summarized as follows:Firstly, aiming to the key issue of how to keep the balance between the exploration in search space regions and the exploitation of the search experience gathered so far, and by introducing cloud model which is a model of the uncertainty transition between a linguistic term of a qualitative concept and its numerical representation, a novel cloud-based fuzzy ant colony algorithm (CFACA for short) is proposed in this thesis. By using half-cloud model as the fuzzy membership function for the suboptimal solutions'pheromone updating and the mechanism of self-adaptive, the CFACA algorithm can avoid the premature convergence effectively and improve the performance of the algorithm on solving routing problems.Secondly, we analyzed the convergence of the CFACA algorithm in this thesis. By analyzing the probability model of the CFACA algorithm, we proved that the new algorithm is convergent. And the simulation results on solving traveling salesman problem show that the CFACA algorithm is superior to the two most successful ant algorithms ACS and MMAS on the convergence speed and stability.And thirdly, based on the CFACA algorithm and integrated the characteristic of multi-objective routing problems, a novel cloud-based multi-objective ant colony algorithm (CMACA for short) is proposed in this thesis. With constructing heuristic information and pheromone trails to each objective of multi-objective routing problems and processing the pheromone trails fuzzily through cloud model, the CMACA updating the sub-dominated solutions'pheromone as well as non-dominated solutions. By evaluating the states of pheromone, CMACA construct a multi-objective self-adaptive mechanism, and make the algorithm explore the Pareto front as much as possible. The simulation results on solving multi-objective traveling salesman problem show that CMACA is superior to the NSGA-II and SPEA2.