考虑用户成本和泊位利用率的停车预约分配模型

Reservation and allocation model considering user cost and utilization of parking space

摘要

为提高停车资源利用率以缓解停车供需失衡问题，考虑停车分配过程中用户利益与系统效益间的博弈关系，建立了预约模式下停车泊位利用率最大和用户成本最小的联合优化目标函数；构建了融合用户偏好特性的最优停车分配整数规划模型（OPA），并设计了增广拉格朗日-交替乘子算法进行预约泊位分配方案求解。为检验模型的有效性，在不同停车供需情况下将本文模型与多种经典停车分配模型对比，结果表明：本文OPA模型在泊位利用率、用户平均成本和请求接收率3个评价指标上的表现均明显优于经典分配模型，本文研究成果可为停车预约平台的决策管理提供理论参考。

Abstract

In order to alleviate the problem of imbalance between parking supply and demand by improving the utilization rate of parking resources， and considering the game relationship between user benefits and system benefits in parking allocation， the optimization objective function of maximum parking space utilization and minimum user cost in parking reservation mode is established from the two aspects which are system optimization and user optimization respectively. Then， the optimal parking allocation integer programming model（OPA） considering users' preferences is established. An Augmented Lagrangian-Alternating Direction Method of Multipliers Algorithm is designed to solve the optimal solution of the model. Finally， in order to test the validity of the model， the proposed model and the classical distribution model are compared and analyzed under different supply and demand conditions. The results show that the performance of the proposed model in three performance metrics which are parking utilization， average user cost and request acceptance rate is significantly better than that of the classical allocation model. The research results of this paper can provide theoretical reference for the management of parking reservation platform.

Graphical abstract

关键词

交通运输系统工程 / 停车分配 / 整数规划模型 / 增广拉格朗日-交替乘子算法

Key words

engineering of communication and transportation / parking allocation / integer programming model / augmented Lagrangian-alternating direction method of multipliers algorithm

0 引　言

随着城市化进程的加快，大城市的汽车保有量也迅速增加，导致大城市的停车资源供需矛盾日益严重。驾驶员在出行时常常耗费大量时间去寻找能满足自身需求的泊位，因此导致的泊位争夺与巡泊交通不仅会造成市区交通的长期拥堵、驾驶员出行成本的增加，还会加重由尾气排放引起的环境污染问题^［1］。受到城市用地规划的限制，这一问题难以通过不断增设停车设施的传统方法解决，因此，能有效提升停车效率、减少巡泊交通的停车预约系统成为缓解停车问题的有效手段^［2］。

合理的停车分配可以有效提升停车资源的利用率与停车场的运行效率，因此，许多有关停车预约的研究集中于如何合理进行停车分配。为了提供最合适的停车设施，He等^［3］考虑了驾驶距离和步行距离等因素并制定了一个混合整数规划模型，以实现最小化所有用户的总出行成本。Said等^［4］进一步考虑了驾驶员在寻找可用泊位时面临的停车费、步行距离、停车时长等因素，以用户成本最低为目标，构建了预约模式下基于博弈论的停车分配模型。宁瑞昌^［2］对目前研究较少的停车场预约可靠性因素进行了重点分析和研究，根据停车场选择决策的特点采用了灰熵决策方法为用户推荐最优停车场。盖松雪等^［5］将用户停车时长定义为由入口到小区中心的车辆行驶时间和在停车位上的停车时间之和，并以用户平均停车时长最小为目标构建了模型，以实现每个停车者的利益最大化。

以上文献均从用户的角度考虑问题，建立了停车分配模型，然而，在停车供给资源紧张的条件下，用户最优通常会对预约的效益产生巨大影响。因此，许多学者从预约系统的角度制定了停车分配策略。Liu等^［6］考虑了预约系统的收入和支出，以平台收益最大化建立了停车分配模型。Zhang等^［7］也以平台收益最大化为目标，考虑了预约系统的收入和支出，建立了停车分配模型。另外，Zhang等^［7］还对社会成本最小化目标下的停车分配进行了研究，并对两种目标下的分配方案进行了对比分析。Shao^［8］、Xie^［9］和孙会君^［10］等均考虑了拒绝请求对平台的负面影响，在构建收益最大化的目标函数时加入了拒绝惩罚因子以防止一味追求收益而导致过高的拒绝率。不同的是，Shao^［8］和Xie^［9］等的惩罚函数中只考虑了分配时的拒绝惩罚，而孙会君^［10］还考虑了提交请求时的拒绝惩罚。Zhao等^［11］将泊位利用率定义为泊位被占用时长与可用时长总和的比值，并以泊位利用率最大化为目标建立了停车预约分配模型。相似地，Wang等^［12］以停车泊位的总占用时长最大化为目标建立了目标函数，以追求停车分配时泊位利用率的最大化。为缓解多停车场间停车需求不平衡导致的停车过载问题，Kim^［13］和戴静^［14］等均以多停车场间的利用率差异最小化为目标建立了停车分配模型。不同的是，Kim等^［13］考虑实现所有时刻下的多停车场利用率均衡，戴静^［14］则深入分析了高峰与平峰下的停车供需规律差异，建模时加入了高峰判别值，以实现停车高峰期的多停车场利用率均衡，减少高峰期停车拥堵。相似地，考虑到停车需求的动态性与驾驶员对停车场的选择概率，Wang等^［15］建立了动态停车收费下的停车预约分配模型，以追求多停车场的利用率平衡。

综上，现有研究从用户成本、运营商收益、泊位资源利用率等角度构建了相应停车分配模型。但在面对个体用户的停车需求偏好不同时，如何保证分配结果满足用户需求偏好，降低预约取消率，同时确保泊位资源的有效利用，保证平台长久发展，是现有停车预约模式下泊位资源分配优化领域亟待解决的问题。基于以上问题，本文分别从系统最优和用户最优两方面出发，考虑了平台泊位利用率和用户停车所花费的金钱成本与其停车后步行前往目的地花费的时间成本，融合了用户偏好特征，构建了停车最优分配整数规划模型（Integer programming model， OPA）。考虑到多目的地多停车场环境下停车分配问题的运算规模，设计了增广拉格朗日-交替乘子算法来求解模型以实现高效率、低误差地求解分配方案，并利用数值仿真对模型有效性进行了检验。

1 停车预约分配模型

1.1　停车预约分配机制

假设停车预约平台在出行区域内的多个停车场内租用了一定数量具有相同可用时段的泊位。停车用户根据实际需求通过地图平台支持的停车预订平台在指定时段内提前提交停车请求，用户在提交请求时可以选择他们的目的地并提交停车需求偏好（见图1）。系统收到请求后首先判断能否满足用户需求偏好，若无法满足，则在用户界面告知无满足条件的泊位；若可以满足，则告知用户申请成功，并将请求重新编号后放入分配池，同时通知用户请求下发时段。最后平台综合考虑泊位利用率与用户成本，对收到的请求进行统一分配，并在规定时段内将分配结果下发至用户。

1.2　最优分配模型

本文提出的模型基于以下假设：

（1） 假设用户根据平台给出的单位时段提交停车申请，并严格遵守提交的到达和离开时间。

（2） 假设用户不会因行程改变等自身因素而取消预约。

变量、参数定义如表1所示。

1.2.1　用户需求偏好约束

由于用户在停车需求偏好上存在个体差异，因此，为防止过高的预约取消率导致系统运算资源和车位资源的浪费，需将用户需求偏好作为停车分配的条件约束。选择步行距离和停车费率两个最受用户关注的因素作为用户需求偏好^［2］。为简单起见，使用停车场到目的地的直线距离表示其步行距离l_{m^{\mathrm{*}}j}，因此，用户基本需求约束可表示为式（1）（2）：

l_{m^{\mathrm{*}}j}\le l_{m^{\mathrm{*}}}^{\mathrm{m}\mathrm{a}\mathrm{x}}（1）

f_j\le f_{m^{\mathrm{*}}}^{\mathrm{m}\mathrm{a}\mathrm{x}}（2）

式中：

l_{m^{\mathrm{*}}j}=\sqrt[]{{\left(x_{m^{\mathrm{*}}}-x_j\right)}^{\mathrm{2}}+{\left(y_{m^{\mathrm{*}}}-y_j\right)}^{\mathrm{2}}}（3）

1.2.2　最大化泊位利用率

由于停车资源的有限性，在满足用户基本需求的情况下最大限度地利用停车资源有利于使平台获取更多收入，同时缓解停车问题。因此，从系统最优的角度以泊位资源的时间利用率最大化为目标，建立目标函数如下：

\mathrm{m}\mathrm{a}\mathrm{x}{\omega }_{\mathrm{1}}=\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}（4）

1.2.3　最小化用户成本

从用户角度出发，用户通常对停车场的费率和停车后的步行距离最关注。因此，将用户的步行距离转化为时间成本，与其停车付费（金钱成本）一起作为用户m的停车成本{\pi }_m，以用户停车总成本最小化为目标，建立目标函数如下：

\mathrm{m}\mathrm{i}\mathrm{n}{\omega }_{\mathrm{2}}={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\pi }_m\right)（5）

式中：

{\pi }_m={\displaystyle \sum _{j=\mathrm{1}}^J}\left[a_{nj}·\left(\frac{l_{mj}}{\overline{v}}·\frac{\mathrm{G}\mathrm{D}\mathrm{P}}{Q·H}+f_j·du{r}_m\right)\right]（6）

式中：\overline{v}为用户平均步行速度；\frac{\mathrm{G}\mathrm{D}\mathrm{P}}{Q·H}为经济学生产法中计算的用户单位时间成本，元/小时^［16］；\mathrm{G}\mathrm{D}\mathrm{P}为国民生产总值；Q为年均就业人数；H为个人年均工作小时数。

式（6）为用户m的成本函数，其第1项表示用户停车后步行前往目的地所耗费的时间成本，第2项表示用户停车所耗费的金钱成本。

1.2.4　最优停车分配整数规划模型

本文追求预约系统与用户的综合最优，因此，引入权重系数\delta将上述两个目标函数进行组合，得到最优分配模型如下：

\mathrm{m}\mathrm{i}\mathrm{n}\omega ={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\pi }_m\right)·\delta -\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}·\left(\mathrm{1}-\delta \right)（7）

约束方程：

x_{mn}·l_{mj}\le l_m^{\mathrm{m}\mathrm{a}\mathrm{x}}（8）

x_{mn}·f_j\le f_m^{\mathrm{m}\mathrm{a}\mathrm{x}}（9）

\left[t_m^{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}},t_m^{\mathrm{e}\mathrm{n}\mathrm{d}}\right]\in \left[\mathrm{1},K\right]（10）

{\displaystyle \sum _{n=\mathrm{1}}^N}{x}_{mn}\le \mathrm{1}（11）

x_{nm}·d_{mk}\le s_{nk}（12）

{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{k=\mathrm{1}}^K}\left(x_{nm}·d_{mk}\right)={\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}（13）

{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}\le N（14）

x_{mn},d_{mk},s_{nk},a_{nj}\in \left\{\mathrm{0,1}\right\}（15）

式中：约束（8）和（9）为用户需求偏好约束；约束（10）表示用户的停车时段必须在系统泊位可用时段之内；约束（11）保证了一个请求最多只能被分配一个泊位；约束（12）保证了一个泊位在在同一时段只能分配给一位用户；约束（13）为任意泊位被占用情况的等式约束；约束（14）表示任意一个时间间隔内接收的请求总数不能超过系统提供的泊位总数；约束（13）表示x_{mn}等变量为0-1二进制变量。

2 增广拉格朗日-交替乘子求解算法

为求解所提出的二进制整数规划问题，首先通过将决策变量x_{mn}松弛为一个［0，1］内的连续变量使原问题转化为一个线性规划问题。由于转化后的问题是一个具有耦合线性等式约束（约束（13））的凸问题，因此，选用交替乘子算法求解该凸问题^［17］，使两个目标函数可以得到单独优化。

定义{\displaystyle \sum _{k=\mathrm{1}}^k}{z}_{nk}=z_n、{\displaystyle \sum _{k=\mathrm{1}}^k}{d}_{mk}=d_m，则与线性规划问题对应的增广拉格朗日函数定义如下：

\begin{array}{l}{L}_c={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\pi }_m\right)·\delta -\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}·\left(\mathrm{1}-\delta \right)+\\ {\displaystyle \sum _{n=\mathrm{1}}^N}\left[{\lambda }_n·{\displaystyle \sum _{m=\mathrm{1}}^M}\left(d_m·x_{mn}-z_n\right)\right]+\end{array}

{\displaystyle \sum _{n=\mathrm{1}}^N}\left[\frac{\rho }{\mathrm{2}}·\left({\displaystyle \sum _{m=\mathrm{1}}^M}{d}_m·x_{mn}-z_n\right)\right]（16）

式中：{\lambda }_n为约束（13）对应的拉格朗日乘子；\rho为标量参数。

显然，式（16）中存在x={\left[x_{mn}\right]}_{M\times N}、z={\left[z_n\right]}_{\mathrm{1}\times N}以及\lambda ={\left[{\lambda }_n\right]}_{\mathrm{1}\times N}这3种变量，通过使用交替乘子算法，可以分别求解变量x和z的最小值，并对拉格朗日乘子\lambda进行更新。基于交替乘子算法的迭代过程如式（17）~（19）所示：

\underset{x_{mn}}{\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\pi }_m\right)·\delta +{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\lambda }_n^{\left(r\right)}\right)+

{\displaystyle \sum _{n=\mathrm{1}}^N}\left[\frac{\rho }{\mathrm{2}}·\left({\displaystyle \sum _{m=\mathrm{1}}^M}{d}_m·x_{mn}-z_n^{\left(r\right)}\right)\right]（17）

\underset{z_n}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}·\left(\delta -\mathrm{1}\right)-{\displaystyle \sum _{n=\mathrm{2}}^N}\left(z_n·{\lambda }_n^{\left(r\right)}\right)+

{\displaystyle \sum _{n=\mathrm{1}}^N}\left[\frac{\rho }{\mathrm{2}}·\left({\displaystyle \sum _{m=\mathrm{1}}^M}{d}_m·x_{mn}^{\left(r+\mathrm{1}\right)}-z_n\right)\right]（18）

{\lambda }_n^{\left(r+\mathrm{1}\right)}={\lambda }_n^{\left(r\right)}+\rho ·\left({\displaystyle \sum _{m=\mathrm{1}}^M}{d}_m·x_{mn}^{\left(r+\mathrm{1}\right)}-z_n^{\left(r+\mathrm{1}\right)}\right)（19）

对于每次迭代r，给定{\lambda }_n^{\left(r\right)}和z_n^{\left(r\right)}，可以通过求解式（17）求得x_{mn}^{\left(r+\mathrm{1}\right)}的值。而由x_{mn}^{\left(r+\mathrm{1}\right)}和{\lambda }_n^{\left(r\right)}的值，可以通过求解式（18）求得z_n^{\left(r+\mathrm{1}\right)}的值。最后，由x_{mn}^{\left(r+\mathrm{1}\right)}和z_n^{\left(r+\mathrm{1}\right)}的值，可以通过求解式（19）求得{\lambda }_n^{\left(r+\mathrm{1}\right)}的值。

因此，根据以上分析设计的增广拉格朗日-交替乘子求解算法的基本求解流程伪代码如算法1所示。

算法1　增广拉格朗日-交替乘子算法伪代码

1: 初始化环境:r=\mathrm{0}, \rho, {\lambda }_n^{\left(\mathrm{0}\right)}, z_n^{\left(\mathrm{0}\right)}。

2: repeat

3: \mathrm{r}\leftarrow \mathrm{r}+\mathrm{1}

4: \forall \mathrm{m}\in \left[\mathrm{1},\mathrm{M}\right], \mathrm{n}\in \left[\mathrm{1},\mathrm{N}\right], do:

5: 求解式(17)更新{\mathrm{x}}_{\mathrm{m}\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)};

6: 将{\mathrm{x}}_{\mathrm{m}\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)}和{\mathrm{\lambda }}_{\mathrm{n}}^{\left(\mathrm{r}\right)}代入求解式(18)更新{\mathrm{z}}_{\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)};

7: 将{\mathrm{x}}_{\mathrm{m}\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)}和{\mathrm{z}}_{\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)}代入式(19)更新{\mathrm{\lambda }}_{\mathrm{n}}^{\left(\mathrm{r}+\mathrm{1}\right)};

8: until 符合终止迭代的条件。

由于求解算法求得的模型解x={\left[x_{mn}\right]}_{M\times N}为［0，1］内的连续变量，因此，本文选取投影法将其还原回0-1二进制变量来代表泊位分配结果。用集合B=\left\{\mathrm{0,1}\right\}表示二进制集合，x_{mn}\in \left[\mathrm{0,1}\right]在集合B上的投影就可以由{\Phi }_B=\underset{b\in B}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\parallel x_{mn}-b\parallel求得。

3 仿真实验

3.1　评价指标

为衡量本文提出的最优分配模型的有效性，选取了泊位利用率、平均用户成本、请求接受率、时间停车强度和平台收益5个指标对模型进行评价。

泊位利用率是衡量系统中泊位是否得到充分利用的重要指标，其含义为系统中泊位被占用的总时长与泊位总可用时长的比值，可以通过式（20）计算：

U=\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}（20）

平均用户成本用于衡量用户的利益是否得到充分的考虑，其含义为被接受请求的停车成本之和与被接受的请求总数的比值，即：

\overline{\mathrm{\pi }}=\frac{{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(x_{mn}·{\pi }_m\right)}{{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}{x}_{mn}}（21）

请求接受率是衡量平台服务水平和用户满意度的重要指标，其含义为接受的请求总数与分配池中请求数的比值，即

A=\frac{{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{n=\mathrm{1}}^N}{x}_{mn}}{M}（22）

时间停车强度是衡量停车需求与供给之间的时间匹配程度的指标，其含义为时间间隔内的停车请求总数与可租用泊位数的比值，即：

{\sigma }_k=\frac{D_k}{S_k}（23）

式中：D_k={\displaystyle \sum _{m=\mathrm{1}}^m}{d}_{mk}；S_k={\displaystyle \sum _{n=\mathrm{1}}^n}{s}_{nk}。{\sigma }_k的期望E\left(\sigma \right)=\frac{\mathrm{1}}{K}{\displaystyle \sum _{k=\mathrm{1}}^k}{\sigma }_k和方差\mathrm{V}\mathrm{A}\mathrm{R}\left(\sigma \right)=\sqrt[]{\frac{\mathrm{1}}{K}{{\displaystyle \sum _{k=\mathrm{1}}^k}\left({\sigma }_k-\overline{{\sigma }_k}\right)}^{\mathrm{2}}}可以用于度量停车需求与停车供给之间的匹配程度，E\left(\sigma \right)=\mathrm{1}和\mathrm{V}\mathrm{A}\mathrm{R}\left(\sigma \right)=\mathrm{0}代表停车供需间的完美匹配。

收益用于衡量停车预约平台的运营效益，其含义为平台从用户处获得的收益减去向停车场租用泊位支出的费用，即

\beta ={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{j=\mathrm{1}}^J}\left(f_j·c_{mj}·du{r}_m\right)-{\displaystyle \sum _{j=\mathrm{1}}^J}{\displaystyle \sum _{n=\mathrm{1}}^N}\left(p_j·a_{nj}\right)（24）

3.2　参数标定

假设系统提前收集当天的停车请求，并为分配池中的请求进行统一分配。假设一天的泊位可用时段为8：00~22：00，系统中单位时段为30 min（t=\mathrm{30}）^{［18，19］}，因此，系统中的时段总数为28（K=\mathrm{28}）。假设在二维平面第一象限内从（0，0）到（500，500）的500 m×500 m区域内进行研究，平台从该区域内的两个停车场内各租用25个泊位（J=\mathrm{2}，N=\mathrm{50}），停车场的位置随机分布。假设一天内收到了500个停车请求，其目的地随机分布在研究区域内；停车请求到达时间服从泊松分布，停车时长服从期望为3 h（\tau =\mathrm{3}）的负指数分布^［20］；用户需求偏好随机分配，其中最大可接受步行距离为300 m和500 m的用户各占一半，最高可接受停车费率为3元/h和5元/h的用户各占一半。使用Matlab R2016A生成到达时间、停车时长等实验数据如图2和图3所示。根据国内2022年的国民生成总值、年均就业人数等数据求得用户单位时间成本为\frac{\mathrm{G}\mathrm{D}\mathrm{P}}{Q·H}=\mathrm{68.74}元/h，用户平均步行速度取\overline{v}=5 km/h的经验值。

将权重系数\delta的值从10^-4开始以9×10^-3为步长渐增，对比加权下的泊位利用率和用户成本的值，多次实验去除异常值并取平均值后的实验结果如图4所示。

在图4中，对实验数据进行线性拟合，通过拟合函数求得交点值为\delta=7.48×10^-3。由图4可知，\delta>7.48×10^-3时，泊位利用率的值明显高于用户成本，反之亦然。由于本文的目标是追求系统与用户的综合最优，因此，取\delta=7.48×10^-3。

3.3　算例实验

本文选择先到先得（FCFS）、先预约先得（FBFS）和贪婪分配方法（GPA）3个经典停车分配模型作为对比对象^{［13，21］}。实验环境设置同参数标定部分，使用Matlab R2016A编程求解模型，算例结果如表2和图5所示。图5中x轴表示单位时段，y轴表示停车场与停车泊位编号，停车泊位的占用状态和时长通过有色色块表示，停车泊位的空闲状态和时长通过空白色块表示。

由图5可知，OPA模型的分配方案中车位的空闲率（图中空白部分）明显低于3个经典模型，车位资源在OPA模型下得到了充分利用。由表2可知，本文提出的OPA模型与FCFS方法相比，提升了11.84%的泊位利用率，降低了24.33%的平均用户成本，提升了18.84%的请求接受率；与FBFS方法相比，OPA模型提升了泊位利用率（16.44%）与请求接受率（14.76%），降低了平均用户成本（13.89%）；与GPA方法相比，OPA模型同样提升了泊位利用率（11.84%）与请求接受率（9.33%），降低了平均用户成本（9.21%）。由此可知，本文提出的OPA模型可以实现泊位利用率与用户成本的综合优化。

3.4　拓展实验

3.4.1　对比分析

为进一步研究OPA模型的优越性，将每个停车场内租用的泊位数增至50（即N=\mathrm{100}），并使请求数从0开始以50的步长渐增至2 000，其余设定与算例实验相同，对比结果如图6所示。

由图6可知，在100个停车泊位供给，停车需求从0渐增到2 000的情况下，4种分配方法在3个评价指标上的表现与算例实验基本一致。在泊位利用率和请求接受率方面，本文所提出的OPA模型的曲线始终明显位于3个经典停车分配模型之上，这是因为本文所提出的OPA模型以用户成本最小与泊位资源利用率最大为目标进行分配，但3个经典停车分配方法则按照用户到达顺序、提交申请顺序及距离停车场的距离进行分配，无法实现车位资源的充分利用，因此，也无法接受更多的请求；同理，与OPA模型相比，3个经典停车分配方法无法实现用户成本的降低，因此，在平均用户成本方面，OPA模型的曲线也始终明显位于3个经典停车分配模型之下。

3.4.2　灵敏度分析

请求数量、用户平均停车时长等因素是影响平台泊位利用率和运营商收益的重要因素，为探寻其对泊位利用率等指标的影响，对其进行灵敏度分析。

假设停车费率分别为6元/h和4元/h（f_{\mathrm{1}}=\mathrm{6}，f_{\mathrm{2}}=\mathrm{4}），每个泊位的购入价格分别为30元/d和20元/d（p_{\mathrm{1}}=\mathrm{30}，p_{\mathrm{2}}=\mathrm{20}）。其余参数设定与对比分析实验相同，时间停车强度的灵敏度分析如图7、图8和图9所示。

由图7、图8和图9可知，对于给定的停车供给，随着停车需求的增加，可以根据供需关系将利用率和收益曲线划分为3个区域：

（1）区域Ⅰ：需求不足。在此区域内，停车供给远大于停车需求，停车分配不受泊位数约束限制（约束（14）），请求接受率为100%，泊位利用率线性增长，但运营商呈负收益状态。

（2）区域Ⅱ：中等需求。在此区域内，停车需求与停车供给相匹配，随着需求的增加，泊位利用率保持上升，运营商也开始盈利。需求量的增加使系统可以根据分配目标制订合理的分配方案，泊位利用率也因此得到提升从而提高了运营商收益，然而，由于泊位数约束的限制，部分请求会被拒绝，因此，请求接受率也随之下降。

（3）区域Ⅲ：需求过剩。随着需求量的持续增加，停车需求远超过停车供给，多余的需求会被拒绝，因此，请求接受率持续下降。同时，由于所有泊位都得到充分利用，泊位利用率与收益变化趋于平稳，表明在该供求状态下，泊位利用率与收益已达到最优水平，难以进一步优化。

为研究用户平均停车时长\tau对泊位利用率的影响，使平均停车时长从1 h开始以1 h为步长逐渐增加到5 h进行实验，实验结果如图10所示。由图10可知，随着请求数的增加，不同平均停车时长下达到最大泊位利用率所需的请求数不同，平均停车时长越长，泊位利用率越早达到峰值。当平均停车时间较短时（如\tau =\mathrm{1}），2 000个请求不足以使其达到泊位利用率峰值。因此，对于停车时长特性不同的停车需求，平台应制订相应的请求接受策略。

3.4.3　利用率水平影响分析

引入最低泊位利用率阈值U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}衡量提升停车场效益对用户成本与服务水平的影响，如式（25）所示。参数取值同灵敏度分析实验，实验结果如图11所示。U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}约超过48%时，收益开始明显增长；约超过60%时，平均用户成本也迅速下降。说明随着泊位利用率阈值的增大，停车场效益和用户利益都得到了提升，但会导致请求接受率的明显下降。这是因为想要实现泊位利用率的提升必须接受更多的请求，从中择优形成更优的泊位分配方案，以使泊位得到充分利用，停车场收益也因此增加。同时，随着泊位分配方案的优化，用户的步行距离与停车费用也得以进一步优化，从而降低了用户成本。然而，被拒绝的请求数量也会随之增加，导致请求接受率（服务水平）下降。当U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}超过70%后收益增长速率明显下降，平均用户成本下降速率也明显减缓；当U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}超过80%时，由于停车场泊位资源已接近饱和，难以继续满足不断增长的停车需求，请求接受率急速下降。并且，相较服务水平下降的程度，停车场收益与用户利益提升的幅度明显更小。

\frac{{\displaystyle \sum _{n=\mathrm{1}}^N}{\displaystyle \sum _{k=\mathrm{1}}^K}{z}_{nk}}{N·K}\ge U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}（25）

综合来看，引入最低泊位利用率阈值可以在一定程度上优化停车资源的利用，改善用户体验，降低用户成本。然而，需要权衡好平台收益、用户成本以及服务水平之间的关系，找到一个平衡点，以达到最佳的停车场经营效果。因此，U_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}}设定在70%~80%较为合适。

4 结束语

本文考虑了停车预约平台效益与用户利益的博弈关系，提出了以泊位利用率最大和用户成本最小为目标的最优停车分配整数规划模型，并设计了增广拉格朗日-交替乘子算法实现高效率、低误差的求解。仿真实验结果表明：本文提出的OPA模型在泊位利用率、平均用户成本和请求接受率3个方面均明显优于经典停车分配模型，能有效提高停车预约平台的运营效益，且充分保障了停车用户的利益。

参考文献

[1] Shoup D. Cruising for parking[J]. Transport Policy, 2006, 13(6): 479-486.

[2] 宁瑞昌. 基于预约模式的停车选择模型研究[D]. 西安: 长安大学交通学院, 2017.

[3] Ning Rui-chang. Research on parking selection model based on reservation mode[D]. Xi´an: School of Transportation, Chang´an University, 2017.

[4] He H, Zhang Z X, Yan P Y. A real-time reservation service for smart parking system[C]∥The 15th International Conference on Service Systems and Service Management (ICSSSM), Hangzhou, China, 2018: 1-6.

[5] Said A M, Kamal A, Afifi H. An intelligent parking sharing system for green and smart cities based IoT[J]. Computer Communications, 2021, 172: 10-18.

[6] 盖松雪, 曾小清, 岳晓园, 基于用户-系统双层优化算法的车位引导模型[J]. 吉林大学学报:工学版, 2022, 52(6): 1344-1352.

[7] Gai Song-xue, Zeng Xiao-qing, Yue Xiao-yuan, et al. Parking guidance model based on user and system bi⁃level optimization algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1344-1352.

[8] Liu W, Graham D J, Yang H, et al. Modeling and managing the joint equilibrium of destination and parking choices under hybrid supply of curbside and shared parking[J]. Transportation Research Part C—Emerging Technologies, 2021, 130: No. 103301.

[9] Zhang F N, Liu W, Wang X L, et al. Parking sharing problem with spatially distributed parking supplies[J]. Transportation Research Part C—Emerging Technologies, 2020, 117:No.102676.

[10] Shao C Y, Yang H, Zhang Y, et al. A simple reservation and allocation model of shared parking lots[J]. Transportation Research Part C—Emerging Technologies, 2016, 71: 303-312.

[11] Xie M H, Zhang X Y, Wu Z H, et al. A shared parking optimization framework based on dynamic resource allocation and path planning[J]. Physica D: Nonlinear Phenomena, 2023, 616: No.128649.

[12] 孙会君, 傅丹华, 吕莹, 基于共享停车的泊位租用与分配模型[J]. 交通运输系统工程与信息, 2020, 20(3): 130-136.

[13] Sun Hui-jun, Fu Dan-hua, Ying Lyu, et al. Parking spaces renting and allocation model for shared parking[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3): 130-136.

[14] Zhao P F, Guan H Z, Wei H, et al. Mathematical modeling and heuristic approaches to optimize shared parking resources: a case study of Beijing, China[J]. Transportation Research Interdisciplinary Perspectives, 2021, 9: 2590-1982.

[15] Wang S F, Li Z H, Xie N. A reservation and allocation model for shared-parking addressing the uncertainty in drivers' arrival/departure time[J]. Transportation Research Part C—Emerging Technologies, 2022, 135: No. 103484.

[16] Kim O T T, Tran N H, Pham C, et al. Parking assignment: minimizing parking expenses and balancing parking demand among multiple parking lots[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(3): 1320-1331.

[17] 戴静. 居住区共享停车泊位分配模型研究[D]. 哈尔滨: 东北林业大学交通学院, 2018.

[18] Dai Jing. Shared parking spaces induction model in residential areas[D]. Harbin: School of Transportation, Northeast Forestry University, 2018.

[19] Wang Y, Chen Q. Dynamic parking allocation model in a multidestination multiple parking lot system[J]. IEEE Intelligent Transportation Systems Magazine, 2022, 14(5): 195-208.

[20] 杨博. 基于时间窗约束的居住区共享停车泊位预订分配模型研究[D]. 北京:北京交通大学交通运输学院, 2018.

[21] Yang Bo. The study on shared parking slots allocation model for residential areas based on time window constraint[D]. Beijing: School of Transportation, Beijing Jiaotong University, 2018.

[22] Choi H G, Seiler P J, Dhople S V. Propagating uncertainty in power flow with the alternating direction method of multipliers[J]. IEEE Transactions on Power Systems, 2018, 33(4): 4124-4133.

[23] Jiang B W, Fan Z P. Optimal allocation of shared parking slots considering parking unpunctuality under a platform-based management approach[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 142:No. 102062.

[24] Xie M H, Lin S Y, Wu Z H, et al. Optimal allocation and adjustment mechanism of shared parking slots considering combined parking resources[J]. Transportation Letters, 2023,15(7): 730-741.

[25] Richardson A J. An improved parking duration study method[C]∥Proceedings of the 7th Australian Road Research Board Conference, Adelaide, Australia, 1974: 397-413.

[26] Xue Z J, Cheng J H, Ji K F. An allocation model of shared parking with continuous time windows[C]∥Conference on Industrial Electronics and Applications, Chengdu, China, 2021:253-258.

基金资助

国家自然科学基金项目(52131202)