AVP条件下的共享停车供需匹配模型及自适应演化算法

何胜学

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

0 引言

传统的自动代客泊车(Autonomous Valet Parking,AVP)研究更多关注无人驾驶车辆如何合理规划行车路线和选择停车场，从而减少乘客的总的乘车时间和步行时间。也有一些研究考虑无人驾驶对共享停车供需量的影响，但是很少有研究涉及无人驾驶在共享停车中如何通过变换泊位进一步发掘有限的共享泊位资源。一方面，在泊车过程中通过变换泊位可以减少共享泊位空闲的碎片时间，满足更多的停车需求；另一方面，如果频繁进行泊位变换势必增加车辆的运行成本，同时提高发生事故的风险。为了化解上述矛盾，有必要对共享停车的需求和供给加以合理的匹配优化。针对上述问题，本研究将尝试建立在满足预约停车需求条件下最小化无人车变换泊位次数与移车总距离的匹配优化模型，并给出模型的有效算法，从而为AVP在共享停车中的进一步应用提供理论支持。

在共享停车需求分析方面，研究者分别从预约时间段的重要性、平台收益与步行距离平衡、停车需求分布与路径选择的关联性、泊位拥有者参与共享停车的意愿、共享无人车对泊位需求量的影响、基于个人信用等级减少泊车违约风险和停车需求信息的准确性等多个方面进行了深入分析[1-7]。在共享停车匹配优化模型构建和平台设计方面，研究者也进行了大量研究。通过定义虚拟泊位概念和考虑停车需求的优先级别差异，文献[8-9]建立了共享停车泊位匹配的优化模型。文献[10]在综合租用车位成本、提供停车服务收入和拒绝潜在用户的损失基础上，以平台收益最大化为目标，构建了车位租用和停车需求分配的统一决策模型。文献[11]以步行距离的差异定义共享车位的异质性，构建了跨区域泊位分配的随机动态规划模型。文献[12]利用滚动时域方法对实时获得的共享停车供给与需求进行滚动式动态匹配。文献[13]以最大化泊位利用率和减少步行距离为目标，建立了共享停车的泊位分配模型。文献[14]通过分析停车需求的到达时间和停泊时长分布，构建模型来优化共享停车收益，确定最佳共享泊位与保留非共享泊位的数量。文献[15]提出了一种基于序列拍卖的共享停车泊位分配和定价方法。从参与各方经济利益最大化角度出发，文献[16]构建了基于拍卖机制的共享停车泊位分配、定价和收益机制。文献[17-20]也对共享停车平台收益、泊位分配和平台构建进行了深入分析。研究者也针对无人驾驶对停车供需匹配的影响进行了研究。文献[21]分析了无人车市场占有率、燃油费和停车费对无人车在完成载客后选择停车场的影响。文献[22]分析了在不同的停车能力限制条件下共享无人车的市场占有率对早上通勤出行的影响。文献[23]利用仿真模型对共享无人车、私有无人车、共享有人车和非共享有人车共存情况下的停车需求变化进行分析，发现共享车辆的存在可降低总体停车需求，但也会增加部分敏感区域的停车需求。文献[24]分析了停车管理策略对需求响应式共享无人车的规模、服务效率和公平性的影响。

与现有研究相比，本研究的特色表现在：(1) 在共享停车中考虑无人驾驶车辆的特征，在提高泊位利用率的同时最小化无人车进行泊位变换所带来的风险与成本。(2)利用可行匹配图的结构特征，分析得出对可行解实施持续改进的直接方法。(3) 通过引入变异操作，使得新算法在求解具有NP-hard特征的匹配模型过程中不会过早地局部收敛。

1 匹配模型

1.1 问题引入

共享停车的实施需要多方的参与，包括具有停车需求的车主、共享泊位的所有人、共享停车服务平台、政府相关管理部门、停车区域的服务管理者等。其中，具有共享停车需求的车主向服务平台提供停车的具体时间信息；共享泊位所有人提供泊位可供利用的空闲时间信息；共享停车服务平台在汇总上述信息后，对停车需求与泊位供给加以合理匹配，并通知各方完成后续的停车服务。当然，服务平台需要事先与停车区域的其他服务管理者和政府相关部门协调，明确相关的法律、法规、制度和规则，并对利益的分配达成一致意见。停车需求者需为所享受的停车服务支付停车费，而服务平台需要与其他各方协调各自的利益所得。由于共享停车主要关注从长期来看可重现的停车需求和泊位供给，因此目前的共享停车以预约式为主，即停车的需求与供给是事先已知的。本研究将以预约式共享停车中的停车需求与泊位供给匹配对研究对象。

无人驾驶车辆的出现对共享停车服务提出了新的挑战与机遇。研究者和实践者都亟需回答：如何充分发挥无人车的特征优势进一步发掘有限的停车资源？可以从多个方面对上述问题加以回答，如考虑无人车的自主远程停车场搜索和停泊。本研究将从无人车可以自主移位的特点出发，通过无人车的移位改变过去在泊车需求时间段内普通有人驾驶车辆仅能停泊于一个固定车位的现状，增加供需匹配的可能性，从而提高泊位的利用率。

原则上讲，只要有空闲的共享泊位，无人车就可以随时自主移位，但是这种有可能造成车辆的频繁移位，进而增加车主的用车成本。为此本研究限定无人车仅可在停车需求与供给时间段的首末时间点进行移位。利用供需时间段的首末时间点可以将所有的停车需求与泊位供给划分为一些较短时间段上的需求与供给，从而方便后续的建模分析。下面给出具体的分割时段划分方法：

1.2 基本参变量介绍

v∈V为一辆具有共享停车需求的无人驾驶车辆，V为所有相关车辆的集合。

p∈P为一个提供共享停车服务的泊位，P为所有相关泊位的集合。

tv,start为车辆v的停车需求开始时刻。

tv,end为车辆v的停车需求结束时刻。

tp,start为泊位p提供的共享停车服务时段的开始时刻。

tp,end为泊位p可以被用于共享停车的结束时刻。

k∈K为一个分割时间段，集合K={1,2,3,...,nK}是所有分割时间段的集合。

lpi,pj为无人驾驶车辆从共享泊位pi移位至共享泊位pj所需要行驶的距离。

wv为对车辆v而言，在其泊车过程中一次泊位改变所带来的惩罚性成本，假设其计量单位与距离的计量单位一致。

1.3 共享泊位与车辆的匹配模型

利用前面给出的参变量和分割时段概念，构建满足停车需求条件下的车辆与泊位的匹配优化模型如下：

(1)

(2)

(3)

(4)

式(1)为目标函数，其构成的第1个加和项是给定供需匹配x后，无人驾驶车辆泊车过程中进行泊位变换总共需要的行驶距离；目标函数构成的第2个加和项是无人驾驶车辆总的泊位变换次数。式(2)为给定分割时段停泊在给定泊位的车辆数必须等于或少于该泊位在该给定分割时段的供给。式(3)为给定分割时段给定车辆的共享停车需求必须得到满足。约束式(4)是对匹配决策变量的取值范围约束。如果先对约束式(2)和(3)分别进行加和，然后加以比较，可以得到下面的隐含约束条件：

(5)

式(5)为模型的约束条件下，所有可接受的预约式共享停车需求都将得到满足。这里的“可接受”指的是在任意时刻的停车需求总量小于等于该时刻的泊位供给总量。

与现有的针对有人驾驶车辆的共享停车匹配模型相比，上述模型的约束条件更加简洁。由于本研究将共享停车的供需划分为统一的较小时间段上的停车供给与需求，因此避免了以往研究中各种繁复的与需求和供给的时间段的前后时间点匹配相关的约束。同时，新模型的目标函数式(1)以泊车中无人车的移位次数和移位距离最小化为目标，也与过去以最大化供需匹配数目或泊位利用率不同。式(5)表明新模型是对可接受的预约式共享停车需求的匹配，匹配结果必须满足所有可接受的停车需求。而可接受的预约式共享停车需求只要满足在任意时刻停车的供给大于等于该时刻停车的需求即可，而不必像处理有人驾驶车辆停车时需考虑车辆停车需求时间是否被泊位的供给时间所涵盖，因此易知新模型得到的泊位利用率将高于过去仅考虑有人驾驶车辆停车需求的情况。

匹配模型属于纯整数二次规划模型，由约束和目标函数的特殊形式，也可视为一类特殊的二次分配问题模型。现有研究证实二次分配问题是一类极难的NP-hard问题，目前还没有确定较大规模相关问题全局精确最优解的有效方法。一般的线性化技术方法只能提供问题较好的目标值下界，而启发式方法也只能保证给出问题的局部最优或近似最优解。

2 自适应演化算法

2.1 可行匹配结构分析

定义2 (匹配组)：令Vk和Pk分别为分割时间段k具有共享停车需求的无人驾驶车辆集合和在时间段k提供共享停车服务的泊位集合。如果为Vk中的每辆车在Pk中指定一个排他的独占泊位，就构成了在分割时间段k上的一个匹配组，简记为S(Vk,Pk)或Sk。

定义3 (匹配图)：对应集合K={1,2,3,…,nK}中的各分割时间段，分别存在对应的匹配组S1,S2,S3,…,SnK。把上述nK个匹配组放入一个集合A={S1,S2,S3,…,SnK}，称该集合为一个匹配图。利用匹配和匹配组的概念可以推出任何一个匹配图都对应模型(1～4)的一个可行解。

2.2 有益交换操作

定义 4 (交换): 设存在两个匹配m(k,v,p)和m(k′,v′,p′)。将上述两个匹配包含的车辆进行交换，可得到两个新的匹配m(k,v′,p)和m(k,v,p′)。将上述操作称为匹配交换，简单为E[m(k,v,p),m(k,v′,p′)]。

按照上述交换定义，可得E[m(k,v,p),m(k,□,p′)]⟹m(k,□,p)和m(k,v,p′)。为了简化表达式，如果已知m(k,v′,p′)，则交换E[m(k,v,p),p′]⟹m(k,v′,p)和m(k,v,p′)。对交换E[m(k,v,p),p′]而言，我们称m(k,v,p)为其显式交换内容，p′为其目标交换泊位。 我们也用Ek为对应分割时间段k的一个交换操作。设M是一个由不同匹配构成的匹配集合，m∈M为M包含的一个匹配。则表达式E(M,p)为进行所有相关操作E(m,p),∀m∈M。在E(M,p)中，称M为其显式交换内容，称p为其目标交换泊位。

给定两个匹配组Sk和Sk+1，两者之间由于无人驾驶车辆变换泊位产生的移车距离与移车惩罚性成本之和记为c(Sk,Sk+1)或c(Sk+1,Sk)。由于车辆只能在相邻的两个分割时间段之间进行移位，因此规定c(Si,Sj)=0,∀|i-j|≠1。为了后续公式表达方便，规定：如果k<1或k+1>nK，则c(Sk,Sk+1)=0。c(Sk,Sk+1)的具体计算公式如下：

(6)

(7)

如果Δc(Ek)>0，我们称Ek为有益交换。如果Δc(Ek)≤0，我们称Ek为无益交换。

定义 6 (有益连续交换组): 将一组在时间上连续的交换操作{Ek,Ek+1,…,Ek+n}定义为连续交换Ek→(k+n)。与上述连续交换对应的匹配组集合为{Sk,Sk+1,…,Sk+n}。在未实施交换前，{Sk,Sk+1,…,Sk+n}在其内部和与外部紧邻的其他匹配组之间由于无人驾驶车辆的移位产生的移车距离与移车惩罚性成本之和计算公式如下：

(8)

而实施Ek→(k+n)带来的成本变化量Δc(Ek→(k+n))计算如下：

(9)

如果Δc(Ek→(k+n))>0，我们称Ek→(k+n)为有益连续交换组；否则，称Ek→(k+n)为无益连续交换组。

假设对于v∈V，其对应两个连续分割时间段的匹配分别为m(k,v,p)与m(k+1,v,p′)。如果p≠p′，可知车辆v在两个连续分割时间段之间需要进行泊位变换，对应的移车成本为cv(k,k+1)=lp,p′+wv；如果p=p′，则显然有cv(k,k+1)=0。在给定一个匹配图A的条件下，如果希望对其进行调整，从而减少对应的目标函数值z[x(A)]，就需要确定是否存在有益交换或有益连续交换组。而实施交换的触发条件是车辆在两个连续的分割时间段停泊在不同的泊位。如上面条件p≠p′成立时，可以通过尝试实施交换E[m(k,v,p),p′]或E[m(k+1,v,p′),p]来得到新的匹配图，从而减少总的移车成本。

2.3 自适应式优化的实现

利用上面2.1和2.2节给出的概念和定义，下面给出对一个给定匹配图进行一次自适应式优化的流程：

步骤2：如果k已经是车辆v的最晚的分割时间段，转步骤4；否则，依次确定对应当前分割时段k和后续分割时段k+1停放v的两个泊位p和q。

步骤3：如果p=q，则令k:=k+1，并转步骤2；否则实施下列操作：

步骤3.1：分别以k和k+1为起始时段，分别向前和向后在两个泊位p和q上搜索停放v的相邻时间段，并将分别得到的与v相关的匹配组成两个集合Mp和Mq。

步骤3.2：将集合Mp里的匹配作为显式交换内容，而将泊位q作为目标交换泊位，确定连续交换E(Mp,q)的成本Δc[E(Mp,q)]；同理确定Δc[E(Mq,p)]。

步骤3.3：如果Δc[E(Mp,q)]≥max{0,Δc[E(Mq,p)]}，实施交换操作E(Mp,q)。

步骤3.4：如果Δc[E(Mq,p)]>max{0,Δc[E(Mp,q)]}，实施交换操作E(Mq,p)。

步骤3.5：令k:=k+1，并转步骤2。

2.4 带有变异操作的自适应演化算法

下面给出带有变异操作的自适应演化算法的具体操作流程：

步骤 1：初始化。设定算法的最大执行次数Nout、对给定匹配图实施个体自适应式优化的最大次数Nin，以及变异操作系数α。令当前的迭代次数τ:=0。随机生成一个可行匹配图，并将其赋予当前匹配图Aτ和最优匹配图A*。

步骤 2：匹配图的自适应优化。令Aτ:=ENin(Aτ)。如果z[x(Aτ)]

步骤 4：终止条件判断。如果z[x(A*)]=0或τ=Nout，算法终止，输出最优匹配图A*；否则，令Aτ:=Aτ-1，转步骤2。

3 算例分析

下面分析一个具有20辆车和12个泊位的共享停车匹配问题。该问题的车辆停车需求信息和共享泊位的共享时间信息分别在表1和表2中给出。假设最早提供共享停车服务的泊位开放时间是0，而其他的时间以分钟作为时间计量单位。表格1和2中的时刻表达方式是将实际时刻以共享停车的开始时刻为基准转化为以分钟为单位后得到的数值。泊位间的移车距离矩阵在矩阵L中给出。矩阵L中的第i行第j列元素的值表示从第i个泊位移车到第j个泊位车辆需要行驶的距离(单位:km)。

表1 车辆停车需求

表2 泊位共享开放时间

算法运行所需的参数设定如下：Nout=200，Nin=100 和α=0.015。设无人车移位1次的惩罚性成本为10 km。图1给出了典型的3次程序运行结果。3次运行结果具有相似的算法收敛特征，即在算法迭代的初期，最优目标函数值会出现一个突降，随后最优目标函数值的降低速度明显减缓，而在算法迭代的后期，最优目标函数值的改变很少。基本相似的收敛特征说明了新提出的自适应演化算法具有较强的稳定性和可靠性。对应3次程序运行的最终目标函数值分别为50.20,60.27和60.21。图2给出了对应图1中数据系列1的最佳匹配图的矩阵图。该图中第1列第1行的“sn”为第1列为泊位的序号。图2的矩阵图的第1行的数字为分割时段的序号。矩阵图中其他元素的意义规定如下：“/”为对应泊位在对应分割时段不开放；“—”为对应泊位在对应分割时段为共享停车开放，但是没有被占用；数字“n” 为对应泊位在对应分割时段被序号为n的车辆占用。图2给出的结果并非问题2的全局最优解，通过多次尝试算法可以将目标函数值降低到40.20左右。如需进一步优化结果，需要调整算法的参数，并增大算法允许的最大迭代次数。鉴于启发式算法本身的近似最优解求解特征，在此不再进行更深入的分析。

图1 随迭代次数增加，最优目标函数值的变化

图2 对应系列1的最佳匹配图的矩阵图

从图2的结果可知，车辆1,8,9,11和12各需移位1次，移位的总距离为0.2 km。而进一步分析可知，假设车辆1和8为有人驾驶车辆，即通常情况下两辆车只能各选择一个固定车位停放时，现有的共享泊位供给将不能满足两车的停车需求；而在两辆车为无人车时，通过自动代客泊车技术，可以合理有效化解上述停车困境，在满足上述停车需求条件下，增加泊位的利用率。

表3 不同泊位数、车辆数和泊位利用率组合下算法的计算结果比较

4 结论

以AVP为背景，给出了预约式共享停车供需匹配的二次分配模型，并利用可行匹配图的结构特征设计了带有变异操作的自适应式演化算法。通过定义匹配、匹配组、匹配图、交换、交换成本、有益连续交换组等概念，明确了对给定匹配图进行合理调整的方法步骤，从而实现了对模型可行解的持续改进。引入变异操作可以有效避免过早的算法局部收敛。数值算例表明新算法不仅计算效率高，而且具有较高的可靠性。考虑到模型本身的NP-hard特征，算法极短的计算时间说明新算法具有处理实际规模问题的能力。本研究的结果可以有力推进智慧停车理论在未来更广泛深入的实践。