详情

原文传递并行K最短路径搜索算法研究

论文题名：	并行K最短路径搜索算法研究
关键词：	智能交通;路径搜索;并行技术;城市路网;交通流分配
摘要：	最短路径搜索不仅在城市交通路网规划和人工智能等领域被广泛应用，而且是现阶段智能交通行业研究的焦点。城市的发展使得城市规模不断扩大，城市路网变得越来越复杂，路网节点数目也迅速增加，从时间代价和计算量等多方面因素考虑，传统串行算法无法达到期望的求解结果。因此，伴随着并行技术发展，并行算法出现能够有效减少最短路径搜索时间，方便我们在大规模路网中求解最短路径。　　一般求解最短路径的算法存在一些问题，例如，采用Dijkstra算法在大规模城市交通路网中搜索最短路径，面对用户并发的出行请求，容易造成交通拥堵，降低了城市交通的运行效率。K最短路径(KSP)算法是路径搜索算法的另一个应用形式，区别于其他算法的是它可以搜索出路网中两点间的最短路径集合，能够尽可能的满足出行者的需求。实际中，路网规模越复杂，KSP算法需要计算的数据量就越大，占用计算机存储空间也就越多。文中提到的KSP算法具有O(n2+n+m)的时间复杂度，程序执行消耗时间较长，导致算法效率和实时性不高。　　本文从最短路径问题入手，结合城市路网交通流状况，分析了城市交通网络中最短路径算法发展现状，重点描述了KSP算法。针对传统算法存在的问题，本文提出将KSP算法并行化的思想来搜索最短路径。首先，分析城市道路网络的拓扑结构，根据路网的网络结构特点，确定网络分解的基本要求、网络划分方法以及交通网络分割算法。其次，本文以方格式路网模型为基础进行研究，按照网络分割原则划分网络，选择路径的源点和终点，运用并行K最短路径(PKSP)算法搜索路径，能够得到一个最短路径集合。最后，对PKSP算法的指标体系进行了评估，运用PKSP算法既降低了搜索路径的时间，提高了算法的搜索效率，又能获得较好的加速比。同时，将PKSP算法在城市路网交通流分配方面做了应用，结果证明：在大规模路网中，如果同时出现多个出行请求，PKSP算法能够搜索出多条符合K最短路径集合选择要求的最短路径，扩大了路段交通流的分布范围，降低了发生交通堵塞的频率。
作者：	李莹
专业：	信息与通信工程
导师：	段宗涛
授予学位：	硕士
授予学位单位：	长安大学
学位年度：	2015
正文语种：	中文