共享车位服务网络动态停放调度算法与仿真研究

闵慧

摘 要：城市停车难问题越来越严重。将可共享停车位资源合理调度，有利用缓解城市交通问题。研究了一种优化调度算法，以提升共享车位动态调度效率，缩短车辆与车位匹配停放后的周转作业时间，使车位空闲间隔时间更小。以每个停车请求的目的地区域中心点作为标记点，将周边可用于服务的车位网点建立停车服务网络，并据此建立多车位网点停放调度服务模型。基于102组实例数据，运用系统仿真技术，将模型优化运算出的调度方案与不经过模型优化的调度方案进行对比分析，驗证了模型的可靠性和适配性。

关键词：共享车位；动态调度；停车服务网络；周转作业；系统仿真

DOI：10.11907/rjdk.171215

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2017）009-0090-05

Abstract：Parking problems for the city has become very difficult to solve， and how to use the sharing parking resource of the city reasonably seems significant. In this paper， an optimal scheduling algorithm was proposed to improve the overall efficiency of the dynamic scheduling for parking in a macro level. The algorithm can reduce the overall job turnaround time that vehicle will take to go to the match parking spaces greatly， it also can small the idle interval of the parking spaces， at the same time， make the using of parking spaces more rational and effective. In this paper， the center of each parking request destination area was the mark point which can be used by the parking spaces surrounding to establish a parking service network， and accordingly the establishment of multi-parking spaces outlets of scheduling service model. Finally， based on 102 kinds of instance data， the use of system simulation model to optimize the operation of the scheme and scheduling model without optimization of stochastic simulation scheduling scheme sets out a comparative analysis， in order to verify the reliability and suitability of model.

Key Words：sharing parking spaces； dynamic dispatching； parking service network； recycling work； system simulation

0 引言

随着社会经济水平的提高，机动车保有量和停车位需求不断增加，而与之相适应的城市交通规划和停车位建设发展却相对缓慢，极大制约了人们的交通出行，快速准确地为车辆找到合适的车位停靠网点成为保证城市交通静态平衡的关键[1-2]。对司机而言，其目的地区域附近的停车位服务网点构成了其停放车辆的目的地停车服务网络。对于负责调度分配的系统而言，需要考虑并分配每辆车停放在哪个车位网点以及具体到达时间，从而达到整体停放车辆效率最优化。实际场景中，构成停车服务网络的各个停车网点分布在二维平面上，本文所述的停车服务网络面向车主用户并以车主目的地为服务散射中心，可以根据车位网点的位置与目的地距离的远近，以及车位网点停放车辆服务能力，将其抽象成如图1所示的停车服务能力分布网络。

学者对停车需求预测方法进行了大量研究，主要包括停车生成率模型、用地与交通影响分析模型、出行吸引模型、交通量-停车需求模型及多元回归模型等[3-5]。文献[6]在停车生成率模型基础上考虑价格因素、服务水平等对停车需求量的影响，提出“停车需求-供应模型”。文献[7]考虑不同用地泊位共享对停车需求总量的折减对停车生成率模型进行优化。文献[8]采用交通影响函数分析了路网流量增长率和停车率对停车需求的影响，在此基础上建立了停车需求预测模型。文献[9]针对现有模型在停车预测时存在的不足，综合考虑新城区CBD 区域用地特征及交通特性，根据出行吸引强度及交通方式划分，构建适用于新城区CBD 区域的停车需求预测模型。虽然现有的停车需求预测方法取得了很多研究成果，但由于受到城市规划动态变化和车辆停放时间不固定等因素影响，已有的预测模型在使用时可行性受到限制，预测结果的可靠性难以保证。为此，本文提出一种改进的共享车位服务网络动态停放调度算法，并通过实例数据验证该算法的有效性。

1 目的地停车服务网络车位动态调度模型

1.1 相关符号定义

为了便于描述，首先给出文中相关定义及含义：endprint

xi：第i辆车停放地点距目的地标点的位置距离（m），i∈S，xi∈M；

ti：第i辆车到达车位网点的停放时刻（小时：分），i∈S，ti∈R+；

P：车辆接受停放服务的顺序集合，P={1，2，…，s}；

L：车位网点网络等价的服务流线长度（m）；

li： 第i辆车类型，i∈S；

Ci：第i辆停放车辆的预计停放时长，i∈S；

ai：第i辆车到达目的地標点的预计时刻（小时：分），i∈S；

di：第i辆车离开目的地标点的预计时刻（小时：分），i∈S；

M：车位网点与目的地标点距离集合（m），M={m|m∈[0，L]∩RB）}；

Q： 车位网点集合，Q={1，2，…，q}，q=|Q|；

S： 待服务停放车辆集合，S={1，2，…，s}，s=|S|；

qmaxi，jj：时间窗下第i辆车最多可得的车位网点数，使第i辆车在调度时优先遵循相邻规则，i∈S，j∈P；

qi，jj：时间窗下第i辆车可用于调度的车位网点数，i∈S，j∈P；

Tjj：时间窗的时间，为第j顺序停放车辆与第j+1顺序停放车辆间的间隔时间（分钟），j∈P；

Qmaxi：第i辆车最多可接受的车位网点数目，i∈S；

Qmini：第i辆车最少可接受的车位网点数目，i∈S；

ti，ci，1：车位网点对停放时长为Ci的第i辆车的周转服务作业时间（分钟），ti，ci，1=Ci/η，η为车位网点的车位利用率，i∈S；

ti，xi，ti：时刻ti第i辆车在车位网点的周转停放时间（小时），i∈S；

Zi，xi，ti：时刻ti第i辆车在车位网点停放，为1；否则，为0；i∈S；

Yi，jj：时间窗下第i辆车停放服务，为1；否则，为0；i∈S，j∈P。

1.2 问题建模

目的地停车服务网络车位网点动态调度模型可描述为：首先根据xi将前往目的地标点所属区域的车辆停放服务请求分配到具体的车位服务网点，然后根据ti为车辆安排停放服务次序并按停放次序编排动态时间窗，在各时间窗内为待停放车辆的服务请求动态分配区域内车位网点对应的决策支点，并保证该时间窗内所有停放车辆分配的车位网点总数不能大于区域内车位网点总数q，且停放车辆所分配的车位网点总数不能大于其最大可接受的车位网点数Qmaxi，分配的车位网点数应尽量保证车辆在预期离开车位网点时间di内离开车位网点，最后使目的地所在区域所有车辆在车位网点的停放周转时间之和最小。

公式（1）为优化目标，要求所有车辆在车位网点的总计前往停放周转时间之和最小：min∑si=1|ti，xiti+ti-ai|+

2 调度算法

车位实时动态共享的运行模式决定了司机用户在接受停车服务前务必提前预约（即便是实时预定下单也意味着提前预约，因为下单与到达车位网点之间的最小时间窗一定大于0），预约时间越早意味在系统调度链条中越靠前，被排队服务的概率越大。系统设定的轮询检测时间戳间隔可自定义，系统并行地计算出每个车位服务点的决策支持方案，考虑不同停放时间长短从而进行统筹调度。对于位于决策周期边际阈值点的用户，系统在进行调度配置停放方案时，在不影响排队的待服务对象停放条件下，进行排队命令穿插，否则将其预定需求自动排至下一次决策判断周期进行配置。

根据以上规则确定车辆i的Qmaxi和 Qmini，则停放车辆的具体车位网点分配和其前往停放周转作业时间确定如下：

（1）为停放车辆i分配Qmini车位服务网点，目的地停放区域随机获取相邻Qmini车位服务网点，确定车辆i的到达顺序为pi∈P，当前时间窗为pi，设中间变量C′i=C，k=0，T=0。

（2）如果车辆i的预计到达时刻不大于期望离开时刻，即（ti+ti，Ci，1/Qmint）≤di，车辆i的前往停放周转作业时间为ti，xi，ti=ti，Ci，1/Qmini；否则，转步骤（3）。

（3） k=k+1，当前时间窗pi内能够分配给车辆i作为候选的车位网点数为qi，pi=min{（Qmini+k），qmaxi，pi，Qmaxi}，目的地停放区域随机获取相邻qi，pi车位网点， 转步骤（4）。

（4）如果车辆i的预期离开时刻不大于期望离开时刻（ti+ti，Ci，1/qi，pi）≤di，车辆 i 的作业时间为ti，xi，ti=ti，Ci1/qi，pi；如果车辆 i 的预期离开时刻大于其期望离开时刻，即（ti+ti，Ci，1/qi，pi）≤di，且车辆 i 当前可得最大车位网点数qmaxi，pi和允许的最大车位网点数Qmaxi的最小值大于当前分配车位网点数，即（Qmini+k）

（5）将pi时间窗的初始时刻计入到Tpi，令T=T+Tpi，如果当前pi时间窗内没有完成车位 i 的作业C′i-Tpi·qi，pi/（ti，Ci，1/Ci）>0，则剩余作业时间为C′i=C′i-Tpi·qi，pi/（ti，Ci，1/Ci），转步骤（6）；否则pi时间窗内分配给车辆 i 的车位网点数为qi，pi=min{qmaxi，pi，Qmaxi}，车辆 i的作业时间为ti，Ci，1=T-Tpi+Ci·（ti，Ci，1/Ci）/qi，pi。

（6）进入下一个时间窗即pi=pi+1进行车位网点分配，车辆 i 在当前时间窗 pi 下分配的车位网点数为qi，pi=min{qmaxi，pi，Qmaxi}，如果车辆i 的预期离开时刻不大于期望离开时刻，即[ti+T+C′i·（ti，Ci，1/Ci）/qi，pi]≤di，则车辆i前往停放周转作业时间为ti，xi，ti=T+C′i·（ti，Ci，1/Ci）/qi，pi；否则，转步骤（5）。

3 仿真实验

将本文算法模型用Python语言封装成一个模型训练库，并通过总计102次差异性较大的实例数据序列测试模型的优化性能，图2列出了总周转作业时间这一指标项的优化后，每辆车的平均周转作业时间结果与原始随机模拟调度结果平均值的对比拟合曲线。

本文以车位服务能力比较紧张的第23组实例数据序列中南方向的车辆和车位网点数据信息为例（车位网络服务能力越紧张越能测试出模型的适配性能），列出具体的相关仿真过程和对比结果。第23组实例数据序列中，南方方向车辆信息如表1所示。

根据上述数据，采用MATLAB结合Python封装好的模型训练库，模拟车辆向目的区域的自然迁移过程，如图3所示。

第23组实例数据序列中，南方方向的车位网点数据信息如表2所示。

根据表2的数据，用MATLAB结合Python封装好的模型训练库，模拟车位网点停车服务网络在目的地区域的停放服务能力分布，如图4所示。

为了验证上述模型的优化效果，用Python封装好的模型训练库随机模拟车位的匹配停放，模拟运算10次的随机调度结果与本文模型调度优化效果进行对比分析，结果见图5。

从图5曲线关系可以看出，本文所提模型优化后的停放作业周转时间与不经过优化随机产生的调度方案所耗费的停放作业周转时间相比处于低耗损值，这意味着本文提出的调度优化模型取得了较好的优化效果，在车位网点的实时调度中耗损成本最小，所有待服务车辆均得到了合理停放。

4 结语

本文提出了以建立每个停放请求目的地中心为标点、搜索周边可用于服务的车位网点构成停车服务网络的理念，并据此建立了多车位网点停放调度服务模型，将车辆的停放需求在停车服务网络上遍历搜索，使到达该区域的车辆从整体上满足车辆停放的同时最快停放，从而得到整体上最优化的停放调度方案。本文基于实例数据，借助系统仿真手段，将模型优化后运算出的调度方案与不经过模型优化的随机模拟出的若干组调度方案进行对比分析，结果显示经过模型优化后的调度方案，在保证车辆整体满足停放需求条件下所消耗的停放周转作业时间大幅减少，证明该动态调度模型优化效果很好。

参考文献：

[1] LEVY N， RENDER M， BENENSON I. Spatially explicit modeling of parking search as a tool for urban parking facilities and policy assessment [J]. Transport Policy，2015，39（11）：9-20.

[2] WU E H K， SAHOO J， LIU C Y， et al. Agile urban parking recommendation service for intelligent vehicular guiding system [J]. IEEE Intelligent Transportation Systems Magazine，2014，6（1）：35-49.

[3] LEVY N， BENENSON I. GIS-based method for assessing city parking patterns[J]. Journal of Transport Geography，2015，46（3）：220-231.

[4] TASSERON G， MARTENS K， VAN DER HEIJDEN R. The potential impact of vehicle-to-vehicle and sensor-to-vehicle communication in urban parking[J]. IEEE Intelligent Transportation Systems Magazine， 2015，7（2）：22-33.

[5] ZHANG W， GUHATHAKURTA S， FANG J， et al. Exploring the impact of shared autonomous vehicles on urban parking demand： an agent-based simulation approach[J]. Sustainable Cities and Society，2015，19（5）：34-45.

[6] 關宏志，王鑫，王雪.停车需求预测方法研究[J].北京工业大学学报，2012，32（7）：600-604.

[7] 薛行健，欧心泉，晏克非.基于泊位共享的新城区停车需求预测[J].城市交通，2010，11（5）： 2-56.

[8] 王丰元，邹旭东，阎岩，等.基于用地和交通特征的停车需求预测模型[J].交通运输工程学报，2010，7（2）：84-88.

[9] 张飞飞，吴兵，李林波.新城区CBD区域停车需求预测方法[J].重庆交通大学学报：自然科学版，2012，31（5）：1018-1022.

（责任编辑：杜能钢）endprint