基于Dijkstra算法的车位引导路径
来源:用户上传
作者:
【摘要】 随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广.最短路径分析是GIS地理网络分析功能中的一个关键性的问题.计算最短路径的经典算法之一就是Dijkstra算法.传统的Dijkstra算法是将所有可能路径都加进去，计算量较大、效率低。本文在分析停车场内部结构的基础上，运用广义DEA模型结合影响驾驶员泊车心理的制约因素，进行有效性分析，采用改进的Dijkstra算法来优化、引导数据模型找出最优泊车路径。
【关键字】 Dijkstra算法 路径规划 广义DEA模型
一、绪论
1.1研究背景
由国家统计局公布的信息，1997年至2016年的20年间，私人汽车拥有量已由358.36万辆增长为16330.20万辆。据行内人士预测，在2020年中国私人汽车拥有量将达到2亿辆。“一位难求”的现象越发普遍，这给停车场管理及其管理系统带来新的挑战。目前的智能化停车场管理系统是通过计算机、网络设备、车道管理设备共同搭建的一套管理系统。系统包括车辆人员身份识别、车辆资料管理、车辆出入情况、位置跟踪和收费管理等。为解决以上问题，有效利用时间，车位引导系统显得尤为重要。
1.2研究意義
车位引导最短路径规划，实质上是通过引导驾驶员在最短时间内到达距离目的地最近的空车位。对Dijkstra算法的技术可行性、区域适应性和实施可能性进行最优化选择。力求时间消耗最少的情况下，找到最优空车位。研究Dijkstra优化算法是提高效率的最佳方法，探求驾驶员泊车心理制约因素对车位引导系统的影响，抑制“粗放型”治理模式，追求“多快好省”的引导方案，以实现边际效益的最大化。
二、名词解释及模型假设
2.1名词解释
（1）Dijkstra算法：是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
（2）遗传算法：遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。按照适者生存和优胜劣汰的原理，逐渐演化产生出越来越好的近似解。种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。
（3）A*算法：A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。
2.2模型假设
（1）假设每个停车场分布均匀不影响评估结果。
（2）假设每个停车场地势无显著差异且对评估结果无影响。
（3）假设各个区域存在微小差异，故不影响评估结果。
（4）假设各个决策单元之间相互独立。
三、广义DEA模型的建立与求解
3.1.3广义DEA有效性含义分析
为了进一步确认每个决策单元较优秀的样本单元更高效，或是与之持平，亦或是不如它，同时，也为了确认具体差距和量化后的排名，下文建立了满足生产可能集公理的条件下的样本单元确定可能集T（1），以及样本可能集T（1）的有效面L，同时，确立前沿有效面L∩T（1），经由G-BCC模型将样本单元和被评价单元代入，得出对应取值，以做出比较。
3.2模型的求解
通过调查发现驾驶员在停车过程中存在短暂的决策过程，停车位置的选择主要受到以下因素的影响：目的地位置、停车区域位置、步行距离、行驶路线时间以及车位信息。将此信息作为偏好投入指标。将路线、车位信息作为产出。
四、Dijkstra算法与其他主流算法的比较
4.1搜索速度比较
以16、32、43、62、78五个节点为例分别采用Dijkstra算法、A*算法、遗传算法进行路径规划，他们各自花费的时间如表4-1所示。
由上表可看出：当节点个数比较少时，三种算法所花费的时间差不多，当节点个数比较多时，A*算法最快，Dijkstra算法最慢，而且这种差距将随节点数量的增加而变得更明显。对于实际地图而言，由于节点与道路的数量一般都很的大，Dijkstra算法在搜索速度方面弱势明显。
4.2搜索成功率比较
对上述五个节点分别采用三种算法进行路径规划，三者各自搜索到最短路径的情况如表4-2所示.
由表4-2可以看出：当节点个数和弧数量比较多时，Dijkstra算法是一种遍历算法，每次能保证100%搜索到最短路径，遗传算法搜索到最短路径的成功率比Dijkstra算法低一些， 算法最低，且这种差距在节点数和弧数量越大时更加明显。
五、Dijkstra算法的优缺点
（1）从全局出发，算法稳定性强，理论上最完备，实际应用广泛。
（2）该算法具有鲁棒性，全局搜索可行解的能力强。
（3）易于其他方法相结合来改善算法。
（4）只适用于非负权值网络的最短路问题。
参 考 文 献
[1]李宗正，张民，张炜，秦玉莲，刁少文.基于停车时间最短的车位引导系统设计[J].工业控制计算机，2017
[2]蔡佳.基于Dijkstra算法的停车场车位引导系统[J].电子技术与软件工程，2014
转载注明来源:https://www.xzbu.com/1/view-15135068.htm
