基于最短路径的停车场内部诱导系统设计方法研究

0前言 

    目前停车诱导系统研究主要是针对停车场外的停车诱导，对停车场内的诱导重视不足。驾驶员进入停车场后找寻停车位的过程主要是靠场内工作人员的引导或由驾驶员在场内四处寻找，这既浪费了人力资源，又降低停车效率，这种管理模式是不符合智能停车场的科学化和人性化管理的需要的。本文在对静态最短路径研究的基础上，对停车场内最优停车路径进行了研究，提出了停车场内部诱导系统的设计思路和方法。 

1静态最短路径分析 

1．1静态最短路径模型 

停车场内的车位网络可以画成带权的图，两者的概念对应如下： 

    结点(Node，记做N)：道路的交叉口或空闲停车位。 

    边(Edge，记做E)瓜(Arc，记做A)：两结点之间的路段称为边，若规定了路段的方向，则称为弧。 

    边(弧)的权(weight，记做w)：是路段某个或某些特征属性的量化表示。根据不同的最优目标，可以选择不同的路段属性，如路段长度、路段平均行程时间等作为该路段对应的边(弧)的权，或称为道路权重。 

    在规定了结点、边(弧)及其权值之后，便将路网抽象为一个赋权无向图或赋权有向图。从而确定停车场内停车位的最优路线便转化为图论中的最短路问题。其中有向图和无向图的区别在于前者虽然增大了路网的存储量，但适用于弧的两个方向权值大小不同的情况，由于停车过程是由人口到出口，应采用有向图表示停车路网。 

    一个停车场空闲车位网络可以用一个有向图G=(、／r，E，w)来表示。其中、／r为顶点集，V={ l i=1，2，⋯， }；E为边集E={e( ， )l∈、／r}，w 为权集，W={叫(vi)l∈ ， }。 

    道路权重的标定决定了 ， 最短路路径搜索的依据，也就是搜索指标。常用的路权指标有停车距离或停车时间。 

1．2典型静态最短路径算法实现及其复杂度分析 

1．2．1 I~kstra传统最短路径算法 

    传统的最短路径算法主要有Floyd算法和Di—jkstra算法等，其中Floyd算法是用于计算所有点对点之间的最短路径。Dijkstra算法用于计算一个源节点到其它节点的最短代价路径，有较高的应用价值。 

    1996年Zhan和Noon使用实际交通网络测试了17种算法中的15种，测试结果表明计算一点到所有其它点的最短路径最快的算法是Dijkstra算法。 

1．2．1．1 I~kstra算法的基本思想 

设从顶点、／rl出发，找从它到图中其它各顶点的最短路径。把图中的所有顶点分为两组，第一组包括己经确定最短路径的顶点，第二组包括尚未确定最短路径的顶点，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去，直到从、／rl出发可以到达的所有顶点都包括在第一组中。在此过程中，总保持从 到第一组的各顶点的最短路径长度，都不大于从、／rl到第二组的任何顶点的最短路径长度，另外，每一个顶点对应一个距离值，第一组的顶点对应的距离值就是从、／rl到此顶点的只包括第一组的顶点为中间顶点的最短路径长度。 

1．2．1．2 I~kstra算法实现 

    一开始第一组只包括顶点Vl，第二组包括其它所有顶点，Vl对应的距离值为0，第二组的顶点对应的距离值是这样确定的：若图中有边< vl， >，则 的距离值为此边所带的权值，否则的距离为一个很大的数(大于所有顶点的路径长度)，然后每次从第二组的顶点中选一个距离值为最小的V_m加人到第一组中去。每往第一组加人一个顶点Vrm，就要对第二组的各个顶点的距离值进行一次修正。若加进Vm做中间顶点，使从Vl到Vj的最短路径比不加、rm的路径短，则要修正 的距离值.改后再选距离最小的顶点加到第一组中去。如此进行下去，直到图中所有顶点都包括在第一组中，或再也没有加人到第一组的顶点存在为止。 

    该算法的时间复杂度为o(n2)。 

2停车场内部诱导系统设计方案研究 

2．1停车场内部诱导系统的功能需求 

    结合停车场内部停车诱导系统的意义，要求系统满足如下功能： 

    (1)实时准确地采集停车场内空车位信息，并及时向停车场管理中心输送。 
    (2)采用信息发布屏方式对进人停车场的车辆提供停车场内不同区段空车位的数目及行车路线导行。 
    (3)向驾驶员提供最优的停车路线选择。 
    (4)实现停车场的自动化管理，包括收费系统、计算机化管理以及数据的快速查询、统计和分析。 
    (5)管理中心具有较强的数据处理功能，包括停车场管理信息的整合、数据发布信息可靠性的处理。 
    (6)管理中心的车位信息查询，包括停车场的车位利用信息，LED显示牌的实时车位信息以及停车场车次El流量变化图等。 
    (7)设备监控：监控、显示各显示牌运行状态。 
    (8)报表设计：包括车辆流量报表统计、停车场内部车辆信息统计等。 
    (9)系统管理：包括停车场内部车辆信息及权限、操作员管理权限及系统审计权限(监控操作员工工作过程)。 

2．2停车场内部诱导系统的组成与结构 

    停车场内部诱导系统的直接功能就是给停车场管理人员及有停车需求的司机提供停车信息。这就要求系统必须从停车场获得信息，然后通过显示装置发布出去，供需求者使用。因此系统必须具备信息采集和信息发布的功能。采集设备得到的信息必须经过处理，才能转换成有用的信息，并经过合理的控制，才能正确地发布出去，因此，系统应具备信息处理功能。从采集设备得到信息到信息发布出去，必须要经过一定的传播方式使信息到达目的地，所以系统还应具备信息传输(通讯)的功能。由此可以看出，停车场内部诱导系统的组成一般包括信息采集、信息处理、信息传输和信息发布等。系统的四个模块相互依赖、共同作用，从而实现停车诱导系统的功能。