基于AHP与Bellman—Ford算法的停车规划方法

王超+高武奇

摘要：为解决现代城市停车车位信息不透明、缺乏诱导信息等原因导致的停车难等问题，提出了一种车位引导算法。该算法根据各停车场、路段的静态信息和采集来的实时信息，建立相应的指标体系，采用层次分析法，计算各指标权值系数，得出区位排序，并给出基于改进Bellman-Ford算法的最短车位引导路径。

关键词：车位引导；层次分析法；指标体系；Bellman-Ford算法

中图分类号：U495 文献标识码：A 文章编号：1007-9416（2017）07-0142-02

近年来，随着国家经济的高速发展和人民生活水平的快速提高，城市化进程伴随着汽车的广泛普及。由于机动车的增长，车辆使用强度增加，对停车产业而言，是一种最好的机遇，多种停车场设备相继出现[1]。为了停车管理更加方便快捷，智能停车系统中已经开始采用停车诱导手段。这样，不仅可以使驾驶者能更加快捷地找到车位，提高停车场车位利用率，而且可以提高停车场的管理效率，大大缓解城市交通压力，为城市交通建设带来更多效益[2]。因而，在考虑实现怎样的停车诱导时，如何选择合理的车位和最便捷的路径，保证驾驶者顺利找到车位并停入已经成为现今停车诱导研究领域所要解决的重要问题。

1 问题分析

目前国内外公认的较好最短路径算法是Dijkstra算法[3]，其本质是基于静态网络的最短路径搜索算法[4]。由于交通路网的复杂性和不确定性，与静态环境下的最短路径相比，动态条件下最短路径的选择更有现实意义[5]。路径最短不一定时间最短，而且不同类型的停车场对应不同的停车环境，不同的驾驶者有不同的停车意愿，所以车位的选择也不能一概而论。目前停车场管理系统所能提供的信息主要还是静态的路径诱导，缺乏對交通情况变化的掌握，很容易造成拥堵现象[6]。对于停车场或者是车位的选择，已有的方法大多是基于最短路径得出的，忽视了驾驶者的特殊要求。

因而，在本文中提出一种普遍适用的区位选择方法，无论是对于停车场外引导还是停车场内引导[7]，该方法都可以在在保证及时获取车位信息的前提下，可以根据层次分析法以及该时段的实时车位信息给出合适的停车区位排序，并考虑实时路况信息给出最佳停车路径，有效提高停车效率。

2 基本原理

2.1 指标体系的建立

停车场的类型有很多，有地下停车场、露天室外停车场、路内停车场以及住宿小区/校园传统停车场等，其停车设施、周围环境、车辆进出情况、收费情况等不尽相同。 在经过多个停车场的问卷调查及数据采集后，综合得出费用、可达性、流量、环境、空余车位数量等多个影响驾驶者选择停车区位的指标，这里选取影响最为重要的4个指标（费用、可达性、流量、环境），综合分析这些指标要素，建立评价各停车区位的指标体系及衡量尺度。

2.2 最佳车位的选择

2.2.1 AHP基本原理

层次分析法（AHP）可以将定性和定量的方法结合起来，处理许多用传统的最优化技术无法着手的实际问题，在最大程度克服主观因素的条件下，尽可能全面地考虑所有的影响因素，得出比较准确、科学的结论。同时，层次分析法比较简单易行，成本也比较低，不会造成过重的财务负担。

首先将复杂问题分成若干层次，以同一层次的各要素按照上一层要素为准则进行两两判断，比较其重要性，以此计算各层要素的权重，最后根据组合权重并按最大权重原则确定最优方案。

2.2.2 AHP选最佳车位

（1）选择评价指标，建立层次结构模型。将决策的目标——确定最佳车位、考虑的因素——选取的指标要素和决策对象——各个停车区位按它们之间的相互关系分为目标层、准则层和方案层，绘制层次结构图。

（2）构造指标判断矩阵并比较。在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容易被别人接受，因而提出：一致矩阵法，即：不把所有因素放在一起比较，而是两两相互比较。对比时采用相对尺度，以尽可能减少性质不同因素相互比较的困难，以提高准确度。层次分析法中通常采用9级标度法来给判断矩阵的元素赋值[8][9]，这里需要根据依据经验值及专家打分法，将各准则要素的相对权重定量化，并运用加权平均，利用上一步的结果计算每个方案下每个指标的相对权数。

（3）一致性检验。为了确保判断矩阵能科学地评价各个指标的相对重要性以及评价结果的有效性[10]，AHP提供了一致性程度要求来检验成对比较的一致性，若该一致性检验符合要求，则继续下面的运算；否则重新审核并做出相应修改。

（4）确定最佳车位。通过层次总排序确定准则层所有因素对于总目标相对重要性的排序权值。将不同方案各准则要素的权重矩阵与准则要素的相对权重矩阵相乘，得到各区位的层次排序，进而选出最佳区位。

2.2.3 路径选择

本文将Bellman-Ford算法改进，提出了静态/动态最优路径算法。动态最优路径算法是在已有路径权值的基础上，通过在路段增加附加权值来映射路况等因素对路径的影响，根据实际路况选择相应的附加权值[5]，最后由Bellman-Ford算法得出实时的动态最优路径。无附加权值或附加权值均为零时的情况为静态最优路径算法。

附加权值的选取需要综合各种环境因素（能见度、路面湿滑度、交通密集度等）对路径的影响并根据其影响程度匹配不同等级的权值。这里的附加权值不是单一的，可以有多个。如果在车辆行驶途中有停车需求，则根据one-step-look-ahead的策略，将所处位置作为动态最优路径算法的源点，同时对交通网络的附加权重进行匹配赋值[11]，从而实现了最优路径的实时动态选择。当路况突然发生变化时，只需要及时更新各路径的权值即可[12]，不会影响算法的运行。

通过采用限制搜索范围、分解搜索目标等策略减少迭代次数，以降低算法的时间复杂度。endprint

3 结语

应用层次分析法确定最佳停车区位，可以将定性的区位分析根据民意调查转化为定量的权值大小，进而将停车区位选择变为停车区位的单一指标/综合排序问题。在一定程度上，将现有的停车资源充分整合[13]，为有停车意愿的驾驶者提供了最佳停车区位，满足了驾驶员的特殊要求。在Bellman-Ford算法中引入附加权值计算得出的最佳路径综合考虑了静/动态交通和环境变化等因素，具有全局优化性、实时性和应变性。

参考文献

[1]杨晓光，薛昆，白玉.城市停车诱导信息系统设计[J].交通运输系统工程与信息，2004，（1）：93-96.

[2]刘姣，葛召炎，谢静，吴轩.停车场泊车问题的研究与仿真[J].计算机仿真，2011，（7）：340-344.

[3]王防修，周康.基于回溯法的Dijkstra算法改进及仿真[J].计算机仿真，2013，（11）：352-355.

[4]何建国，张文胜，赵根庄.智能泊车引导方法的研究与实现[J].地理空间信息，2007，（2）：3-5.

[5]宫恩超，李鲁群.基于Bellman-Ford算法的动态最优路径算法设计[J].测绘通报，2011，（8）：26-28+41.

[6]李坤.智能停车场车位检测与泊位诱导系统研究与设计[D].中国科学院大学（工程管理与信息技术学院），2013.

[7]刘媛媛.大型停车场内车位诱导系统研究[D].长安大学，2010.

[8]刘江.基于层次分析法的企业运输方式的选择[D].对外经济贸易大学，2006.

[9]汪少勇，李建忠，郭秋麟，李登華.层次分析法在致密油有利区优选中的应用——以川中侏罗系大安寨段为例[J].地球科学进展，2015，（6）：715-723.

[10]魏晓玲.在Matlab平台上用AHP对高职院校毕业生综合素质的评价[J].计算机与数字工程，2016，（11）：2288-2292.

[11]董芳.弯道驾驶行为研究及无人驾驶车辆智能行为评价[D].北京理工大学，2016.

[12]张冲，朱凡.基于Bellman-Ford算法的无人机路径规划研究[J].弹箭与制导学，2007，（5）：249-251.

[13]周智勇，陈峻，王炜.城市停车诱导信息系统发展应用综述[J].交通运输系统工程与信息，2006，（2）：27-30.endprint