● 摘要
随着交通及旅游业的不断发展,对出行路径的合理规划就显得日益重要。在路径规划问题中,最常涉及得就是最短路径。由于路径规划中考虑的因素可以不同,如时间、费用、道路的容量等,最短路径问题就可以引申为最快、最低费用路径问题。不管选取哪种标准,路径规划中都是为了实现其路径最优。所以,最优路径规划最终都可以归结为在特定的道路网络中搜索总代价最小的目标路径问题。
最短路径问题一直是研究的热点,其中比较经典的算法是Dijkstra算法,此外还有Ford算法、A算法、A*算法、动态规划法等。为了提高搜索的效率,很多学者对Dijkstra算法进行了改进,它们在一定程度上能降低算法执行的时间复杂度或空间复杂度。此外,由于Dijkstra算法的时间复杂度为O(n2),当道路节点的数目很大的时候,它的执行效率就显得相对较差。为了克服这个问题,有的学者引入了限制搜索区域的思想,缩小搜索空间,比如椭圆限制、矩形限制等。遗传算法是一种基于生物进化论中的优胜劣汰、自然选择和适者生存原理以及生物遗传规律的智能搜索方法,具有较强的全局搜索能力、稳健性、并行性和启发式随机搜索特性,它通过维持一组可行解,并通过对可行解的重新组合,改进可行解在多维空间内的移动轨迹或趋向,最终走向最优解,克服了传统优化方法容易陷入局部极值的缺点。这使得在解决路径寻优问题中,遗传算法只需要对部分路径进行编码,再通过不断的进化操作,最终便可在整个搜索空间中获得最优或较优的解。而实际上,当解空间达到一定的规模时,单纯的遗传算法往往很难获得令人满意的解,这是因为遗传算法的搜索本身具有一定的盲目性和随机性,搜索空间越大,对其性能的影响就越大。在本文中,采用分层的思想,将整个解空间分解成两个或多个子空间,实现分级搜索,以提高遗传算法的路径寻优的效率和解的质量。与单纯的遗传算法相比,分层算法更倾向选择有利于行驶的高层路径,尽可能少的选择较差的低层路径,这种选择也符合出行者的决策心理,使路径的选择更加合理。
论文主要完成两部分的工作:第一是算法的研究,主要是遗传算法的研究。本文采用了改进的遗传算法用于路径的寻优,使用分层的思想提高求解的效率,最后并通过实验结果的比较,证明其可行性和有效性;第二是路径查询系统的设计,包括系统功能模块的设计、系统工作流程的设计和系统界面的设计,最后,基于Oracle数据库,通过Visual Studio 2005和MapXtreme 2005完成了路径查询系统的设计,使系统实现了路径查询功能和地理信息处理功能。