Parking Guidance Algorithm Based on Time-dependent Shortest Path

李　伟1　余　森1　王　伟2

(河南工业职业技术学院计算机工程系1，河南 南阳　473000；西安电子科技大学通信工程学院2，陕西 西安　710071)

基于时间最短路径的停车场车位引导算法

Parking Guidance Algorithm Based on Time-dependent Shortest Path

李伟1余森1王伟2

(河南工业职业技术学院计算机工程系1，河南 南阳473000；西安电子科技大学通信工程学院2，陕西 西安710071)

摘要：针对停车场管理系统中存在的车位引导问题，在研究场内道路网络特征的基础上建立加权网络模型；以停车时间最短的路径作为最佳车位确定准则，结合Dijkstra算法改进停车引导模型，对系统进行寻优。仿真结果表明，基于时间最短路径的引导算法所选的最优车位更符合实际，停车平均时间最短，是一种寻求最优路径的有效算法。

关键词：车位引导时间最短路径Dijkstra算法智能交通系统停车管理静态交通

Abstract：Aiming at the parking guidance issue existing in parking lot management system, on the basis of the network features of the site road of parking lot, the weighted network model is established. With the time-dependent shortest path as the determine criterion for the best parking space, the parking guidance model is improved by combining Dijkstra algorithm, the system is optimized. The simulation results indicate that the best parking space selected by the guidance algorithm based on time-dependent shortest path is more realistic, the average parking time is shortest; this is an effective algorithm for finding the optimal path.

Keywords：Parking guidanceTime-dependent shortest pathDijkstra algorithmIntelligent transportation systemParking managementStatic traffic

0引言

近年来,随着机动车数量的井喷式增长，交通情况急剧恶化，停车位日益紧缺的问题在大中城市尤为严重。交通管理部门纷纷采取措施，新建地下停车场、立体式车库，开辟道路两侧夜间停车位，意图构造全方位停车设施，减缓部分停车难的问题。然而据统计,在已经投入使用的停车设施中，还存在效率低下的现象[1]。如何运用科技手段对停车场加以改进,使其充分发挥停车潜力，已成为交通管理部门和科研工作者关心的问题。车位引导系统就是其中重要的一项技术，它通过向驾驶员提供到达目标车位的最优路径来引导车辆行驶，缩短车辆在停车场内的寻泊时间，减少交通拥堵，提高停车效率。

1停车场车位引导系统

停车场车位引导系统本质上是图论中的求解最优路径问题。目前对最优路径问题的研究有很多，Dijkstra算法[2]是其中的经典方法，国内外学者对此进行了很多的研究和改进。张渭军[3]提出了从起点和终点分别用二叉树按其方向性进行搜索的双向Dijkstra算法，以此节省计算时间。文献[4]对Dijkstra算法的存储结构进行改进，采用多重邻接表来构建无向图，优化构建无向图和求解最短路径问题的时间复杂度。彭红星[5]根据停车场路网的实际情况，将车位节点和路口节点区分开,采用双层搜索方法，减少搜索点个数。

通过实地调查研究发现，提高停车场效率的关键，在于每一辆车都能够以最短的时间停泊，即寻找停车时间最短的车位要比停车距离最短的车位更为重要。基于上述考虑，本文设计了一种基于时间最短路径(time-dependent shortest paths,TSP)的停车场车位引导系统。结合Dijkstra算法进行车位诱导，系统能够减少车辆寻泊时间，提高停车泊位利用率，促使停车设施利用平衡化。

2时间最短路径的内涵

停车最短路径，最直观的是从停车场入口位置到目标车位距离最短的路径，一旦停车场建好，这种路径就是静态不可变的。然而现实生活中，由于停车场内道路交通强度是时变的，不同时间段行驶在道路上的车辆数目可变，两点间距离最短并不代表行驶时间最短。当最短路径车辆较多、出现拥堵时，路程长的路径反而可能耗时较短，因此最优路径必须考虑到实时的交通信息[6]。综合上述两个方面的因素选择的时间最短路径，才是满足实际需要的最佳路径。所以设计停车引导系统时还要考虑到车辆分流问题，在进出停车场的车流高峰时期对车辆进行分流，能够极大地提高停车场效率。

图1为某停车场车位分布图，其中，点P0、E分别为停车场入口和出口，C1~C8为交叉路口节点，P1~P12为空闲车位。

当某一较短时间段内驶入停车场的车辆较多时，车位引导算法如果仅考虑选择距离入口最近的车位，车辆将会在图中C5-C1、C5-C6区间形成排队现象，而其他区域出现无车的状况。这种场内相关道路局部拥堵的情况是停车场要极力避免的，因此需要根据停车场内部交通组织布局，合理分散交通流。以图1为例，某时刻同时驶入的车辆可以分别按照C5-C1-C2-C3-C4、C5-C6-C2-C3-C4、C5-C6-C7-C3-C4、C5-C6-C7-C8-C4四条路径行驶，充分利用停车场的所有停车位，避免车辆刮蹭等交通事故的出现。

另外，某一时间段内不但有车辆驶入停车场，同时也有车辆驶离，但是大多数停车场出口和入口是分离的，双向行驶的车辆互不干扰，且驾驶人员根据经验很容易找到出口，所以不需要对出场车辆进行引导。

3停车场通行规则模型

交通网络分析往往要建立抽象的计算机图论模型，该模型中最短路径的查找就是在两个指定网络节点间找到一个权重最小的路径。这里的权重不仅可以是距离，还可以是时间、费用、容量等其他因素[7]。

停车场路网相对较为简单，主要由环路、交叉路口及停车位等节点组成，可以抽象为一个加权有向图G(P,C,T)，如图2所示。在G(P,C,T)中，P表示停车场路网中的节点，C表示场内有向路段，T是权重，其值为车辆在道路节点i和j之间的行驶时间：

(1)

式中：c(i,j)和v(i,j)分别为节点i到j之间的距离和行驶速度。

图2　目标停车位加权有向图

4Dijkstra时间最短路径算法

4.1　权重的计算

由式(1)可知，图2中两个相邻节点之间的权重即车辆在该路段行驶所需要的时间。一般情况下，道路的行驶速度v(i,j)比较稳定，且与道路上的机动车数成反比。车辆数量越多，道路越拥挤，行驶速度越慢。

设定车辆在场内道路上行驶单位长度需要的时间为Δt，考虑到同一路径上多个车辆之间的相互影响，定义延迟系数K。经现场实地统计，当一条路径上有2辆车时，单位长度行驶时间延长至1.9Δt；当一条路径上有3辆车时，单位长度行驶时间延长至2.7Δt；当一条路径上的车辆大于4辆时，单位长度行驶时间延长至3.1Δt。即：

(2)

其中：

(3)

4.2　引导算法

基于时间最短路径的停车场车位引导算法，输入一个以空闲停车位为节点的邻接矩阵AMcost，在邻接矩阵中以停车场入口P0作为源顶点。用P表示所有空闲停车位节点集合，邻接矩阵AMcost中的每一个元素AMcost[i][j]表示有序节点对(Pi,Pj)之间的权重。本算法以两点之间的车辆行驶时间作为权重，不同于经典Dijkstra算法，该权重是随着同一时间场内环路上车辆的数目而时变的[8]，具体变化关系如式(2)、式(3)所示。若Pi、Pj不相邻，则将元素AMcost[i][j]置为∞。设S为已经查找到的从P0出发的最短路径的节点集合，任意两节点之间的总开销就是最短路径经过的所有边的权重总和。用T表示这些最短路径的花费值，T[i]表示从源节点P0出发到终点Pi的最短路径的开销。

算法具体步骤如下。

① 初始化最短路径集合S及其开销T，即T[j]=AMcost[0][j]，S={P0}。

② 比较集合S外部各节点Pi∈P-S，选取其中T[j]最小的节点Pk，则Pk就是目前求得的一条从P0出发的最短路径的终点，并将节点Pk加入集合S。

③ 更新从P0到Pk最短路径的开销值，令：

T[k]=min(T[k],AMcost[j][k])

(4)

④ 重复步骤②、③，直到有向图中各节点均加入集合S，即得出从P0到其余各节点的时间最短路径。

5实验仿真结果分析

为验证算法的正确性和有效性，在MicrosoftVisualC++ 6.0环境下，使用C语言开发仿真程序进行测试。以图1所示的停车场车位分布图为背景，在某一时刻，停车场内剩余12个空闲车位，其余车位均已被占用。车辆到达停车场的时间服从泊松分布，道路车流稳定，短时间内共有6辆机动车顺序进入停车场待分配车位。

停车场入口到每个空闲车位的行驶距离如表1所示。表1中，s表示单位长度。

表1　停车场内空闲车位与入口的距离

分别编程实现距离最短路径引导算法(distance-dependent shortest paths,DSP)和时间最短路径引导算法，这两种算法中车辆在停车场内的行驶距离和消耗时间统计如表2所示。表2中，s也表单位长度。

表2　路径长度及消耗时间测试数据

由表2可知，时间最短路径引导算法求出车辆行驶路径长度为64s，所需行驶时间合计为69.6Δt，而传统的距离最短路径引导算法求出的车辆行驶路径长度为53s，所需行驶时间合计为93.0Δt。实验数据表明，改进算法求得的总路径长度较传统算法稍远，但由于车辆分布较为合理，相互之间的延误时间少，导致路况良好，车流比较顺畅，所以所需行驶时间减少了许多。这种方案更能满足用户的实际需要，而且引导驾驶者避免拥挤的区域，选择车流相对顺畅的路段，更能解决停车场内交通拥堵问题。

6结束语

本文利用基于时间最短路径的Dijkstra算法对停车场车位分布加权有向图进行最短路径寻优，找到时间意义上的最优车位。该算法减少了驾驶员停车时间，降低了道路车流量，有利于停车场的内部管理，对于现代多车位、路线复杂的大型停车场具有实际意义。通过实验证明，其结果更符合实际需要。

参考文献

[1] 张玉杰,田硕.地下停车场智能化照明与停车引导系统设计[J].自动化仪表,2014,35(4):64-67.

[2] 齐悦,夏克俭,姚琳.数据结构算法与应用[M].北京:清华大学出版社,2015.

[3] 张渭军,王华.城市道路最短路径的Dijkstra算法优化[J].长安大学学报:自然科学版,2005,25(6):62-65.

[4] 黄震,薛文科,李鹏,等.Dijkstra算法在停车诱导系统中的应用[J].计算机时代,2013(12):38-41.

[5] 彭红星,解凤玲.改进Dijkstra算法在停车诱导系统中的应用与仿真[J].计算机应用,2011,31(S2):63-66.

[6] 李晓东,王东,曾凡智,等.城市交通时间最短路径计算模型及应用仿真[J].计算机仿真,2014,31(1):172-176.

[7] 冯璐璐.基于物联网的停车泊位诱导系统关键技术研究[D].长春:吉林大学,2013.

[8] 张玉杰,田硕.Dijkstra优化算法在停车场车位引导系统中的应用[J].计算机测量与控制,2014,22(1):191-193.

中图分类号：TH7;TP301+.6

文献标志码：A

DOI:10.16086/j.cnki.issn1000-0380.201508006

河南省科技攻关计划基金资助项目(编号：142102310225)。

修改稿收到日期：2015-05-07。

第一作者李伟(1982-)，男，2008年毕业于西安电子科技大学交通信息工程及控制专业，获硕士学位，助教；主要从事嵌入式及物联网技术、智能交通系统的研究。