The Research Of Path Planning Problem Based On Ant Colony Optimization Algorithm

IVLNS (Intelligent Vehicle Location and Navigation System) is the high-techintegrated system of applying auto-vehicle location technology, GIS (GeographicalInformation System), database technology, computer technology, multimediatechnology and contemporary communications technology. Path Planning Problem isthe problem of searching an optimal steering route from starting point to destinationin the given city road network. It is a basic problem in IVLNS, and a precondition ofrealizing navigation. This thesis puts forward a new method and implementation for the Path PlanningProblem based on ACOA (Ant Colony Optimization Algorithm). ACOA is asimulated evolutionary algorithm of simulating to seek food of ants in nature. It hasseveral primary characteristics such as positive feedback and parallelism. Positivefeedback makes it faster to find better solutions. Parallelism makes it easier to realizeparallel computing. Although ACOA is not as good as conventional algorithm on thecomplexity of time, studies on the theory demonstrate that it is a robust simulatedevolutionary algorithm based on population. Ant colony in nature is a CAS (ComplexAdaptive System). CAS theory is one of the newest developments in the systemscience area. As the third generation of the system thinking, it has provided a newconcept, the adaptive agent, and provided a new perspective to investigate complexsystem, which views the behavior of the complex system as a result of theinteroperation between the adaptive agent and the environment, and inaugurated anew view in system study. This thesis describes ant colony as CAS, and expatiates fundamental of ACOA,and makes simulation experimentation to actual Beijing city road network.Experimentation demonstrates that it is feasible and applied to solve the Path PlanningProblem based onACOA.