基于权值的Dijkstra停车路径规划算法的优化与实现
2017-05-11袁琳王渊孙建芸王新生湖北大学资源环境学院湖北武汉430062农业部遥感应用中心武汉分中心湖北武汉430062
袁琳,王渊,孙建芸，王新生,2(.湖北大学资源环境学院，湖北 武汉 430062；2.农业部遥感应用中心武汉分中心，湖北 武汉 430062)
基于权值的Dijkstra停车路径规划算法的优化与实现
袁琳1,王渊1,孙建芸1，王新生1,2
(1.湖北大学资源环境学院，湖北 武汉 430062；2.农业部遥感应用中心武汉分中心，湖北 武汉 430062)
基于用户自由选择车位，以停车时间最短为准则，结合权值的计算方法及停车场的内部结构特点，对Dijkstra算法进行改进，设计并实现符合实际的最优停车路径规划算法，并对武汉某公园的大型停车场进行应用验证.结果表明，相对于传统算法，改进后的Dijkstra算法降低时间的复杂度，减少节点的搜索量，提高搜索效率，在停车场引导系统中有一定的实际应用价值.关键词：停车场；权值；Dijkstra算法；最优停车路径
0 引言
随着经济的发展，人民生活水平的不断提高，汽车普遍存在于生活之中，自驾出行的频率也随之增高，于是出现了城市“停车难”现象.早在1971年，国外就有了停车场引导系统，我国也于2001年开始建立停车引导系统[1-2]，但多数停车引导系统只能提示停车场的出入口位置以及当前剩余停车位数量，对于车位的分配是随机的，用户进入停车场后只能盲目地寻找空车位，因此满意度不高.这说明现有的停车引导系统没有起到相应的引导作用，用户寻找空闲车位的时间仍较长，停车效率低，常常造成停车场的拥堵.
针对以上问题，本文中从用户角度出发，基于用户自由选择车位，以停车时间最短为准则，采用Dijkstra算法，结合停车场的内部结构特点，采用分层的方法对Dijkstra算法进行改进，设计并实现适用于手机Android系统的最优停车路径规划算法，应用于停车场停车引导应用程序中，提供最优停车路径，使用户可以快速到达空闲车位，提高停车效率，最后用Java对改进的算法进行应用仿真.
1 停车场模型构建
为了研究大型停车场的最优停车路线规划问题,需根据实际停车场的车位与道路布局建立抽象数学模型.图1是武汉某公园停车场平面示意图.Dijkstra算法基于有向(无向)带权图，因此将停车场内部的车位网络转化成为有向(无向)带权图结构，转化后的效果如图2所示.道路的交叉口、转弯处、停车位以及停车场出入口均代表一个节点，其中R表示停车场的入口，E表示停车场的出口，本文中引用的停车场的出口与入口在同一位置.道路交叉处定义为道路节点，分别用n1、n2、……n12表示，Pi(i=1,2,3,…)表示车位节点，C
图1 武汉某公园停车场平面示意图
图2 停车场无向带权结构图
2 方法描述
2.1 Dijkstra最短路径算法 路径规划的核心就是最短路径算法，研究最短路径的方法很多，如凸轮基本方法、启发式搜索方法、动态规划方法、神经网络方法等.传统的最短路径算法主要有Floyd算法、矩阵算法和Dijkstra算法等.其中Floyd算法用于计算网络中每次段路径；Dijkstra算法用于计算一个源节点到其他节点的最短代价路径.Dijkstra算法由于适应网络拓扑的变化，其性能稳定，因而在计算机网络拓扑路径选择以及GIS中得到广泛应用[3].
Dijkstra算法由荷兰计算机科学家迪克斯特拉提出的[4].Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直至扩展到终点，是有代表性的最短路径算法，有较高的应用价值[4].1996年Zhan等[5]使用实际交通网络测试了17种最短路径算法的15种，结果表明，计算一点到其他点的最短路径的最快的方法是Dijkstra算法.
2.2 道路权值设定 权值是道路某个或某些特征属性的量化表示，如道路长度、路段车流量等属性都可以被量化为路段相对应的权值.权值是Dijkstra算法计算最短路径的依据，寻找最短路径即起点到终点之间的消耗最低，所以权值的确定是算法精确度的关键.由于在停车场内部驾车行驶的无方向性特性，本文中设定每个路段来回方向上对应的边权值相等，即每条边都有且仅有一个权值.
在传统的Dijkstra算法中，权值仅表示2个节点之间的距离.由于停车场车流量的不确定性，即道路畅通性是无法确定的，所以通过距离长短来判断是否是最优路径的方法不准确.本文中对权值的设定进行改进，以用户的停车时间最短为准则，在考虑最优路径时，结合道路长度以及道路上的实时车流量信息来计算权值.随着图像射频技术和射频技术的快速发展，已能准确采集停车场道路实时车流量信息[6-7].
设定D
(1)
(2)
其中，β的值由实地统计得到[7].权值计算公式为：
(3)
2.3 Dijkstra算法的改进 传统的Dijkstra最短路径算法在确定某一起点到任一节点的最短路径时，会遍历计算所有的节点，本文中针对的是节点较多的停车场，传统的Dijkstra算法计算慢，效率低.针对这一缺陷，本文中对传统的Dijkstra算法进行改进.
由于停车场的节点数较多，如图2所示，所以将道路节点和车位节点区分开.采用分层搜索方法，把路径搜索过程化，对每个过程进行求解，得到全局较优解[8-9].具体操作为：把停车场中的所有节点分为2层，车位节点Pi(i=1,2,3,…)属于第一层，入口节点R、出口节点E和交叉口的道路节点C
改进后的Dijkstra算法的实现步骤如下：
1) 根据用户选择的车位结点，查询车位节点所在路段两端的道路节点，记录节点名称，分别计算车位节点到两端道路节点的距离；
2) 判断距离长度，确定目标道路节点；
3) 初始化道路节点集合T，T集合中只包含入口节点以及到其本身的最小权值，令T={S(0)}，初始化集合U，U集合包含除入口节点R外的其余道路节点以及边相对应的最小权值(与入口节点相邻的则记录权值，不相邻的权值则为∞)；
4) 从U集合中选出权值最小的节点，并加入到T集合中，同时从U集合中移除该节点；
5) 更新U集合中各个节点到入口节点R的权值；
6) 重复步骤4)和5)，直到捕捉到目标节点；
7) 将入口节点与通过的节点和最终的车位节点连接起来，则为最终的最优路径.
3 实例与分析
为验证算法的正确性与有效性，采用上述算法步骤，在Eclipse环境下通过Java语言实现改进后的Dijkstra算法.以图1所示的停车场为实验场景，假设某一时刻停车场内剩余27个空闲车位，其余车位均已被占用.P1为用户所选择的空闲车位，表1为图1停车场在某一时刻的道路权值属性表，表中记录停车场内17条路段的属性信息.道路长度固定不变，且停车场限速5km/h(约为2m/s)，录入每条路段实时车流量，根据(1)式、(2)式计算相应每条路段的行驶速度，根据(3)式计算每条路段相对应的权值D
表1 停车场道路权值属性表(一)
由表1可以清楚看到每条道路的权值属性，道路C
更改每条道路的实时车辆数，重新计算权值，更改后的道路权值属性表如表2所示.根据以上停车场各路段的属性值，运行最优停车路径算法，得到的最优路径为n4→n5→n6→n9→n12→P1，最小权值为52.56，最优路径如图4所示.
图3 最优路线规划(一
图4 最优路线规划(二
由图4可知，在规划最优路径时有效地避开了较为拥堵的C
分别保持停车场道路权值属性表(表1和表2)的状态，更改用户所选车位为P2，运行程序，分别得到以下2种最优路径规划为：n4→n7→n8→P2，最小权值为22.5，如图5所示；n4→n5→n8→P2，最小权值为33.84，如图 6所示.规划行车路线时，有效地避开较为拥堵的C
图5 最优路线规划(三
表2 停车场道路权值属性表(二)
道路属性Vk/(m/s)M
针对以上实验例证，本文中对传统的Dijkstra算法和改进后的Dijkstra算法在2种不同道路权值属性下，规划入口到车位P1的行车路线，将程序所需运行时间进行比对，如表3所示.
表3 传统的Dijkstra算法和改进后的Dijkstra算法运行时间对比
从表3中可以看出，改进后的Dijkstra算法在运行时间上有很大的提高，运行时间大约是传统的Dijkstra算法的1/40，基本达到预期目标.
由以上实例验证，可以看到改变实时车流量信息的同时，权值也随之变化.运行程序后，在规划路径时，改进的最优路径算法可以有效地引导用户通过权值较小的路段,避开权值较大的路段即拥堵路段，为用户节省停车所需时间.如果仅仅考虑道路距离判断权值大小，将导致用户无法准确避免拥堵道路，增加用户停车所用时间，降低停车场的使用效率.本文中结合道路距离及道路的实时车流量信息计算权值，提高用户的停车效率及停车场的运行效率.
4 结论
针对停车场的车位引导问题,本文中建立停车场数学模型，引入时间权值和节点分层的方法对传统的Dijkstra算法进行改进,并利用改进后的算法结合实例验证，规划出入口到目标车位之间的最优停车路径.相比于传统的Dijkstra算法，改进后的最优停车路径算法能够引导用户通过路况通畅的路段，避开通行质量不佳的路段，使用户可以快速、安全地完成停车行为，减少用户停车时间，避免停车场内部的道路拥挤，有利于停车场内部的管理，对于多车位、路线复杂的停车场具有一定的实用价值.
[1] 彭红星,解凤玲.改进Dijkstra算法在停车诱导系统中的应用与仿真[J].计算机应用，2011，31(12):63-66.
[2] 于德新,杨兆升,刘雪杰.基于停车场选择的停车诱导路径优化方法研究[J].交通运输系统工程与信息，2006，6(12):41-48.
[3] 程丽平,谭永海.改进的分层A*算法在停车场路径寻优中的应用[J].计算机测量与控制，2015，23(1):183-186.
[4] 王梅梅.基于GIS的最优路径算法研究与实现[D]. 南京：南京理工大学，2008.
[5] 许增昭,许伦辉.Dijkstra改进算法在泊位诱导系统中的应用与仿真[J].科学技术与工程，2009，23(12):7226-7229.
[6] 吴若伟,楼佩煌.基于Dijkstra算法的大型停车场最优泊车路径规划[J].工业控制计算机，2013，26(5):93-95.
[7] James D T. A Dijkstra’s algorithm shortest path assignment using the Google Maps API: poster session[J].Journal of Computing Sciences in Colleges，2010,25(6):253-255.
[8] 张玉杰,田硕.Dijkstra优化算法在停车场车位引导系统中的应用[J]. 计算机测量与控制，2014，22(1):191-193.
[9] 钱红昇,葛文锋,钟鸣,等.基于分层的改进A算法在路径规划中的应用[J].计算机工程与应用，2014，50(7):225-229.
(责任编辑 郭定和)
Optimizing Dijkstra algorithm design and accomplishment for parkingroutine programming based on weight caculation
YUAN Lin1, WANG Yuan1, SUN Jianyun1, WANG Xinsheng1,2
(1.Faculty of Resources and Environmental Science, Hubei University, Wuhan 430062, China；2.Wuhan Branch of Remote Sensing Application Center, Ministry of Agriculture, Wuhan 430062, China)
Relying on the principle that the user self-defined routine, and shortest parking time purpose, we associate with combining the weight calculation algorithm and parking lot internal structure to optimize the Dijkstra algorithm and accomplished the algorithm for the best parking routine design. The research result has been successfully tested in one selected large parking garage in Wuhan Park, and proved to be a great improvement in reducing time complication, node searching times, and improved the searching efficiency. The improved parking guide system has some practical value.Key words:parking garage;weight calculation;Dijkstra algorithm;parking routine optimization
2016-10-24
袁琳(1992-)，女，硕士生；王新生，通信作者，教授，E-mail:443941982@qq.com
1000-2375(2017)03-0279-06
TP301.6
A
10.3969/j.issn.1000-2375.2017.03.012
