GIS路径寻优中的蚁群算法研究

最短路径问题是交通网络分析中的一个重要问题,也是资源分配、路线设计等优化问题的基础。多年来,最短路径算法一直是运筹学、地理信息科学等学科的研究热点,由此出现了大量研究成果。纵观这些成果,主要还是集中在以经典Diikstra算法为基础的各类改进算法的研究和应用方面。蚁群算法是近年来迅速发展起来的一种全局性优化算法,但这种基于生物进化原理的算法还没有形成系统的、成熟的算法理论体系,提高搜索速度,克服过早收敛仍然是算法研究的方向。论文以提高算法效率为出发点,对基于道路网络的蚁群算法搜索策略进行了研究。论文还对时变道路网络的最短路径问题进行了探讨。 论文的研究成果主要包括: 1)基于泰州市电子地图道路信息,通过道路的提取,拓扑网络的构建,生成了适于最短路径问题分析的道路网络平台。 2)基于上述平台,设计并实现了道路网络寻优中的蚁群算法,具体包括:分析蚂蚁搜寻过程,设计算法流程,编写代码并实现。 3)对上述蚁群算法进行改进,研究了矩形限制搜索区域的蚁群算法,实验结果表明:矩形限制搜索区域的蚁群算法较传统的蚁群算法在节点搜索数目及运算时间方面有较大改善。 4)利用蚁群算法多解性,通过调整蚂蚁信息素释放标准,保证蚂蚁得到的次优解质量,结果表明,在最短路径不可行的情况下,蚂蚁能够迅速地收敛到最理想的替代路径上来。 5)在对时变网络分析的基础上,建立了一个时变道路网模型。对道路交通网络的道路通行时间进行区域简化,并基于该简化网络实现了时变的最短时间路径算法。