何胜学，马思涵，程朝中，崔允汀，郁奇凡

(上海理工大学，管理学院，上海200093)

0 引言

共享停车在城市停车难问题日益严峻的今天受到越来越多的关注。各种共享停车平台纷纷涌现，预约式共享停车实践也在许多城市出现。共享停车中泊位拥有者将空闲时段的泊位通过共享平台出租以获取收益，而其他车辆使用者向平台预约特定区域内一定时段的共享泊位以便停车。在最大化满足停车需求，并提高泊位利用率的条件下，如何将上述具有差异化时间窗限制的需求与供给加以合理匹配就成为共享停车实践的首要问题。

与此同时，无人驾驶技术日益成熟，以无人公交、无人出租车和无人清扫车为先导的无人驾驶实践纷纷涌现。无人驾驶对共享停车也带来了诸多影响。一方面，无人驾驶需要更多通信和AI 技术的支持，因此有必要进一步提升现有停车设施；另一方面，无人驾驶车辆在泊车过程中可自主改变泊位的特征也为提高泊位的利用率带来了新契机。如果是有人驾驶车辆，当车辆的停车需求时间段与泊位的开放时间段不匹配时，两者的共享停车匹配不能成立；如果是无人驾驶车辆，只要停车需求与泊位供给在时间上有交集，两者间的匹配就有可能成立。因为无人驾驶车辆可以在该时间交集上停放在该泊位，而在其他时间段通过自主移动停放到其他泊位。无人驾驶车辆的上述优势，为充分利用有限的共享泊位资源提供了条件，但是不合理的匹配也可能造成无人车的频繁移位，增加用车成本，并引发交通事故。

为在利用无人驾驶特征提升泊位利用率的同时减少无人车频繁改变泊位带来的用车成本和潜在交通事故风险，本文以泊车过程中的车辆移位次数和距离最小化作为优化目标建立相应的车辆与泊位时空匹配优化模型，并设计有效的求解方法。

在共享停车需求分析方面，研究者分别从平台收益与步行距离平衡[1]、停车需求分布与路径选择的关联性[2]、泊位拥有者参与共享停车的意愿[3]和共享无人车对泊位需求的影响[4]等角度进行了深入分析。文献[5]在综合租用车位成本、提供停车服务收入和拒绝潜在用户损失的基础上，以平台收益最大化为目标，构建了车位租用和停车需求分配的统一决策模型。文献[6]以步行距离的差异定义共享车位的异质性，构建了跨区域泊位分配的随机动态规划模型。文献[7]利用滚动时域方法对实时获得的共享停车供需进行滚动式动态匹配。文献[8]以最大化泊位利用率和减少步行距离为目标，建立共享停车的泊位分配模型。文献[9]通过分析停车需求的到达时间和停泊时长分布，确定最佳共享泊位和保留非共享泊位的数量。文献[10]提出了一种基于序列拍卖的共享停车泊位分配和定价方法。文献[11]构建了基于拍卖机制的共享停车泊位分配、定价和收益机制。针对无人驾驶对停车供需匹配的影响，文献[12]分析了无人车市场占有率、燃油费和停车费对无人车在完成载客后选择停车场的影响。文献[13]分析了在不同的停车能力限制条件下共享无人车的市场占有率对早上通勤出行的影响。文献[14]利用仿真模型对共享无人车、私有无人车、共享有人车和非共享有人车共存情况下的停车需求变化进行分析，发现共享车辆的存在可降低总体停车需求，但也会增加部分敏感区域的停车需求。文献[15]分析了停车管理策略对需求响应式共享无人车规模、服务效率和公平性的影响。对于无人驾驶条件下的共享停车，现有研究多关注无人车的市场占有率和其影响，对停车期间无人车在停车区域内可灵活移位特征的应用与影响缺乏研究。本研究将关注无人车这一具体特征对共享停车匹配的影响，通过构建优化模型，并给出有效算法，以期实现泊位资源的进一步优化匹配。

与现有研究相比，本文的特色表现为：与现有无人驾驶研究多关注车辆的路线选择、停车目的地选择和停车自动缴费技术不同，本文关注无人驾驶特征对停车服务的影响，并以优化泊车中的车辆移位为重点；通过分析车辆与泊位的时空匹配结构特征，合理定义可行匹配的邻域，从而实现利用模拟退火算法对匹配模型的有效求解。

1 匹配模型

1.1 参变量介绍

V——具有共享停车需求的无人车集合，v为其中的一辆无人车，v∈V；

P——提供可共享服务的泊位集合，p为其中的一个泊位，p∈P；

tv,enter、tv,leave——无人驾驶车辆v共享停车需求的开始时刻、结束时刻；

tp,start、tp,end——共享泊位p提供共享停车服务的开始时刻、结束时刻；

k——将总的共享停车时间划分为K个连续分割时间段后其中的一段，；

wv——无人车v一次移位的惩罚性成本，假设其单位与相同；

1.2 优化模型

模型构建的基本假设条件包括：①在预约式共享停车服务中，已知停车需求的具体时间段和泊位供给的具体时间段；②为避免无法提供服务，假设任一时刻泊位的总供给大于该时刻总的停车需求；③共享停车中，有人车在停放后一般不会改变其泊车位置；④无人车可通过远程控制或自主与平台交互，在停放中自主调换其泊位，但仅在供需时段的首末时间点进行车辆移位。

为刻画无人车可自主变换泊位的特征，将每个泊位的共享时段和每辆车的停车需求时段按下述方法加以分割：将所有停车供需时段的首末时间点放入一个集合，并按升序对时间点排序；将所有车辆的共享需求时间与泊位的共享时间以上述时间序列的时刻为分割点加以划分，得到相应的分割时间段。如果无人车在两个连续的小时间段分别停放于不同的泊位，代表其进行了移位。而有人车则必须在其停车需求时间内停放在同一泊位上。

满足共享停车需求条件下，以最小化车辆移位距离和移位惩罚成本为目标的无人车与泊位时空匹配模型为

式(1)为目标函数，第1个加和项为共享泊车过程中车辆总的移位距离，第2个加和项是泊车过程中车辆移位的总惩罚成本。式(2)保证泊位在任一分割时段最多只能被1 辆车占用。式(3)表示无人车在任一时段的共享停车需求必须得到满足。式(4)是决策变量的0-1 特征约束。对式(2)和式(3)进行加和，可得

式(5)表明所有的可接受停车需求必须得到满足。这里的“可接受”是指任一时刻泊位的总供给大于该时刻的总停车需求。

匹配模型式(1)～式(4)属于纯整数二次规划模型，是一类特殊的二次分配模型。现有研究表明二次分配属于极难的NP-hard 问题，目前不存在可在现实可行时间内确定较大规模二次分配问题精确解的方法。因此，需利用式(1)～式(4)解的结构特征设计对应的启发式求解算法。

2 模拟退化算法

2.1 解的邻域

下面通过定义匹配图的邻域来确定对应可行解的邻域。

Mi的k时段邻域定义为

2.2 算法流程

模拟退火算法(Simulated Annealing Algorithm,SA)是一种通用的启发式算法。该算法具有跳出局部最优解，且在理论上以概率1渐进收敛于全局最优解的特征。下面给出针对模型式(1)～式(4)的SA具体操作步骤。

Step 1 初始化。给定初始温度Γ、最大邻域搜索次数β、降温系数ε。令当前温度G=Γ，当前迭代次数n=1，当前邻域搜索次数τ=0。

Step 2 生成初始匹配。由匹配图定义，随机生成一个匹配图。令当前匹配图和最优匹配均等于。

Step 3 生成M(n)的邻居。如果τ ＞β，转Step 5；否则，令τ:=τ+1，并执行如下操作，从所有分割时段中随机选择一个时段k，随机生成一个Sk，用Sk替代中时段k的匹配组，得到的一个邻居。

Step 4.2 生成在[0,1]区间内的均匀分布的一个随机数δ。

Step 4.3 如果δ≤Pr，用代替，并转Step 3；否则，直接转Step 3。

Step 6 终止判断。如果G≤1 或Mˉ对应的目标函数值为0，算法终止，输出Mˉ；否则，转Step 3。

3 算例分析

求解算法利用Java语言实现，执行程序的计算机处理器为Intel®Core i3-3120M CPU。为便于分析令所有车辆的惩罚性成本wv为100 km，而任意两个泊位间的移车距离均取自区间[0.010，0.100]km上服从均匀分布的随机数。上述假设将便于从最终匹配结果直接判断需要移车的次数和总距离。例如，最终目标函数值为200.142 km，则表明需要移车2次，移车的总距离为0.142 km。

首先分析一个有10个泊位和14辆车的共享停车匹配问题。该问题的停车需求和泊位开放时间如表1和表2所示。无人车在泊位间变换停放位置的行驶路线长度在矩阵E中给出。E中第i行第j列的元素值表示从第i个泊位移车到第j个泊位的无人车行驶路线长度。按式计算得到的名义泊位利用率φ=0.795。

表1 车辆停车需求Table 1 Parking demand of vehicles

表2 泊位共享开放时间Table 2 Opening times of sharing slots

图1 用矩阵形式给出算法得到的最佳匹配结果，矩阵中第1列第1行的“sn”表示第1列为泊位的序号，矩阵的第1行数字表示分割时段的序号。矩阵图中其他元素的定义如下：“/”表示对应泊位在对应分割时段不开放；“__”表示对应泊位在对应分割时段为共享停车开放，但没有被占用；数字“n”表示对应泊位在对应分割时段被序号为n的车辆占用。图1 数据表明：无人车1 和4 各需移车1 次，利用E的数据可知，2 次移车的距离分别为0.064 km 和0.078 km；对应最优目标函数值，存在多个可行匹配图，如无人车11 除现在的泊位6，还可选择停放在泊位3；无人车4 的需求无法被任何单一的开放共享泊位满足，若将无人车4转化为有人车，其需求将无法得到满足；无人车1的需求，在无人车4的停车需求被拒时，可被泊位1满足。

图1 最佳匹配的矩阵图Fig.1 Matrix of the best matches

表3 为在8 种车辆数、泊位数和名义泊位占用率组合条件下，匹配优化的部分结果。表中，CT表示计算时间，φ为名义泊位利用率，和分别表示算法迭代过程中最优目标函数的初值和终值。从表3 的结果可知：随问题规模增大，计算耗时增加，目标函数值也显著增加；同一情景下最终的目标值可缩小到不到初值的5%，在问题规模较小时甚至接近2.5%；从计算耗时来看，新算法可应用于求解实际规模的共享匹配问题。

表3 不同情境下算法的计算结果Table 3 Results from different scenarios

从表3最后一列数据可知，最终匹配的车辆移位次数和总的移车距离。例如情景4 对应的的值为1400.69 km，表示需移车14次，而总的移车距离为690 m。由于在生成算例时限定任意两个车位间的移车距离小于100 m，因此每次移车的车辆行驶时间较小，对车辆和泊位的供需时段匹配影响较小。但是当两个车位间距离较大时，移车时间可能较长，会对上述的匹配产生影响。考虑到现实中每个停车需求和每个供给的时间跨度一般都在几十分钟以上，而移车的时间一般不超过几分钟，上述较短的移车时间一般对实际的匹配影响甚微，因此，在构建本文优化模型时忽略了上述可能的影响。

另一方面，考虑到启发式方法一般只能给出问题的一个局部最优解，且每次执行可能给出不同的解，要得到一个较好的匹配结果，有必要多次运行算法，比较后确定一个满意的最终结果。从表3给出的程序运行时间数据可知，模拟退火算法运行一次的时间很短，故在多次反复执行的要求下，也可满足实际的运行需要。

上述计算所设初始温度Γ=1000，邻域搜索次数β=2，降温系数ε=0.03。假设温度低于1 时，算法终止。为验证算法的有效性，以匹配问题1为基础对算法的两个主要参数β和ε进行灵敏度分析。图2 为邻域搜索次数β分别为1，2，4 和6 时，目标函数随迭代次数增加的变化情况。图1 数据显示4 种情况下目标函数均随迭代增加而降低，β值越大，算法前期的收敛越快，最终的目标函数值也较优。但4种情况的收敛趋势一致，说明算法具有较高的可靠性。当邻域搜索次数较大时，算法在迭代初期可能得到较好的初始目标函数值。

图2 邻域搜索次数β 对算法迭代的影响Fig.2 Impact of search number β in neighborhood on algorithm

图3 为当降温系数分别为0.100、0.075、0.050和0.025时算法的收敛表现。在初始温度相同条件下，随着降温系数减小，算法的迭代次数增加。数据显示，降温速度慢会增加迭代次数，但也会改善算法得到的最终优化目标。降温系数较大时算法在前期的表现较差。尽管降温系数差异较大，算法的收敛表现一致，说明算法的鲁棒性较强。

图3 降温系数ε 对算法的影响Fig.3 Impact of temperature reduce rate ε of on algorithm

4 结论

本文主要结论如下：

(1)利用无人车灵活移位特征可以有效提升共享泊位利用率，减少可接受停车需求的拒绝率。从算例1的分析结果可知，共享泊位的利用时间增加了415 min，可接受的停车需求拒绝率由14.3%降为0。

(2)将停车需求和泊位供给在时间上加以分割来反映无人车泊车中灵活移位的特征，进而实现基于解的时空特征定义匹配图和匹配图邻域。

(3)经模型求解优化，无人车的移位次数可减少到不足初值的5%，实现降低移车成本和风险的目的。

(4)随着问题规模增大，求解模型的耗时有所增加，但是求解时间均小于1 s，可保证算法的实用性。