Research On Ant Colony Optimization Algorithms In Routing Planning Problems

The routing planning problems (RPP) have a significant practical applications, suchas designing flight course, lying tract and improving city traffic. By differentconstraints and demands, RPP problem can be divided into several sub-problems——Optimal Path Problems（OPP）、Travelling Salesman Problem（TSP）、TravellingSalesman Problem with Time Windows（TSPTW）and so on. But the RPP problem isa typical NP-HARD problem, so it’s difficult to use precise algorithm to get thesolution. Swarm intelligence search algorithm with strong robustness, easy to obtainthe global solution. Therefore, the swarm intelligence search algorithm, such as antcolony algorithm, began to being used in the RPP problem, and had achieved goodresults. But in the use of ant colony algorithm, there are still easy to fall into localoptimal solution, slow speed of convergence, the final solution quality and otherproblems to be improved. Therefore, this article studied on the ant colony algorithmfor RPP problem in detail, and the main work includes:(1) A highly efficient ACO for OPP problems is proposed. In this algorithm,first we make destination emit fragrance information which could attract ants close tothe destination, and it also could make the search of ants have directivity. Secondly,we classify the route in road networks, and combine dynamic classification strategyto avoid the shortcoming such as stagnation. The experiment result shows, newalgorithm are both better than ant colony optimization in the stability and the qualityof optimum solution.(2) TSPTW problems need minimize the total travel time and satisfy the timeconstraints, so we proposed a novel TSPTW model based on magnetic fieldrepresentation to satisfy the requirement of time constraints, which could also avoidstagnation. After that, when initializing solutions are formed, mutation strategy willbe used to create feasible solutions for the un-served clients. The experiment resultsshow that the new algorithm is effective and efficient.By combining ant colony algorithm, biological discovery and magnetic fieldtheory, the above-mentioned studies are new achievement in the research of antcolony algorithm for RPP problems. Not only provide a effective method to RPP, butalso enrich the ant colony algorithm.