论文部分内容阅读
针对城市汽车导航中的车辆路径规划问题,借助返回思想,提出有返回的改进蚁群算法,通过返回策略解决了搜索中的“死胡同”问题。细致研究了汽车导航中城市路网的基本特征,受几何学中“两点之间线段最短”的启发,提出动态有限区域搜索策略,减小了搜索范围,提高了搜索效率。鉴于A*算法搜索时间短的优势,将其与有返回的改进蚁群算法相结合,提出基于动态区域规划的分层蚁群算法(DHACO),利用A*算法和有返回的蚁群算法进行两次路径优化,提高了搜索效率和可行解的质量。在宣城市市区的网络交通图上对改进算法进行实例验证,与A*算法和有返回的改进蚁群算法相比,DHACO算法在更短的时间内搜索到了更短的路径,实验结果验证了其在工程实践中的可行性和有效性。
Aiming at the problem of vehicle routing in urban car navigation system, an improved improved ant colony algorithm is proposed based on the idea of return, which solves the problem of “dead end ” in search through the return strategy. The basic characteristics of urban road network in car navigation system are studied carefully. Inspired by “the shortest line segment between two points” in geometry, a dynamic limited area search strategy is proposed to reduce the search range and improve the search efficiency. In view of the advantage of short searching time of A * algorithm, a DHACO algorithm based on dynamic region planning is proposed by combining it with the improved ant colony algorithm with backtracking. Using A * algorithm and returned ant colony algorithm Two path optimization, improve the search efficiency and the quality of feasible solution. An example is given to verify the improved algorithm in the network traffic map of Xuancheng city. Compared with the A * algorithm and the improved ant colony algorithm with return, the DHACO algorithm searches a shorter path in a shorter time, and the experimental result verifies Its feasibility and effectiveness in engineering practice.