上海理工大学管理学院，上海

收稿日期：2022年1月14日；录用日期：2022年2月10日；发布日期：2022年2月17日

摘要

尽管利用无人驾驶车辆在停车过程中可灵活移位的特征能有效提升共享泊位的利用率，但是停车过程中频繁地调换泊位势必增加用车成本和事故风险。为化解上述矛盾，构建了以移车次数和移车距离最小为优化目标，以满足可接受的停车需求为约束的无人驾驶条件下共享停车供需匹配优化模型。新模型具有纯整数二次规划特征，可视为一类特殊的二次分配问题。考虑到问题的NP-hard特性，设计了一种带有个体自主优化能力的改进遗传算法对其加以求解。数值实验分析验证了新模型和算法的有效性。本研究为利用无人驾驶提升共享停车服务水平提供了新思路和新方法。

关键词

共享停车，无人驾驶车辆，二次分配，遗传算法

Parking Space Sharing Supply-Demand Matching Model and the Designated Genetic Algorithm Based on Autonomous Vehicles

Yunting Cui, Shengxue He^*

Business School, University of Shanghai for Science and Technology, Shanghai

Received: Jan. 14^th, 2022; accepted: Feb. 10^th, 2022; published: Feb. 17^th, 2022

ABSTRACT

Though making use of the feature of autonomous vehicle that is changing parking spaces freely during parking can effectively improve the utilization of shared parking spaces, the frequently changing parking spaces during parking will surely increase the cost of using car and the risk of accidents. To solve the above conflict, the paper proposed a supply-demand matching optimization model for driverless vehicles with minimizing the total number and distance of changing the parking space as objective and satisfying the acceptable parking demand as constraints. The new model has the feature of a pure integer quadratic programming and is a special type of quadratic assignment problem. In view of the NP-hard characteristic of the problem, this paper designed a modified genetic algorithm with an individual’s self-improvement to solve the new model. Numerical experiments verified the effectiveness of the new model and the new algorithm. This research offers a new idea and a new method for improving the service level of shared parking with autonomous driving.

Keywords:Parking Space Sharing, Autonomous Vehicle, Quadratic Assignment, Genetic Algorithm

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

针对如何减少无人驾驶车辆在停车过程中总的移车次数和如何降低车辆移位过程中的事故风险，本文构建了对应的车辆与泊位时空匹配优化模型，并设计了带有个体自主优化的遗传算法对其加以求解。共享停车为有效利用现有的泊位资源提供了新思路，而无人驾驶车辆可以在无驾驶员条件下在泊位间自由移位的特点更进一步为充分利用停车资源提供了契机。在充分利用无人驾驶车辆上述特点的同时，如何避免由于频繁移位而产生新费用和引发事故风险是一个亟待解决的现实问题。考虑到车辆移位过程中的风险和费用与移位次数和移位距离正相关，因此我们将满足停车需求条件下减少移位次数和距离作为本研究的优化目标。本文研究是对现有众多关注停车场选择和有人驾驶车辆泊位匹配研究的一个拓展，也可进一步推进城市智慧停车的管理实践。

本研究特色可归纳如下：a. 与现有涉及无人驾驶的停车研究主要关注路线规划与停车场选择的整合优化不同，本文关注车辆在停车场内或在设定的停车区域内的移车费用和风险。b. 考虑到在停车场或设定停车区域内无人车在无驾驶员条件下可自由移位的特征，本文将停车需求时段和泊位共享时段分划为小的分割时段，从而为后续有效地构建供需匹配模型创造了条件。c. 针对所建二次分配模型具有的NP-hard特征，本文利用可行匹配所具有的时空结构特征设计了求解该模型的带有个体自主优化的改进遗传算法。

2. 现有文献综述

作为一种颇具潜力的停车资源开发思想，研究者对共享停车进行了较为广泛和深入的研究。下面首先简单介绍以共享停车需求分析为主的现有研究。文献 [1] 通过时间序列预测时间重要度，在匹配时从车辆停车需求与共享泊位供给的区间重叠度和灰距离熵出发尽量减少热点时间的预约，从而减少泊位空闲时间碎片，提高泊位利用率。文献 [2] 以共享停车平台收益及用户从停车场至目的地步行距离为优化目标，构建了预约请求下共享泊位分配模型，提出利用蒙特卡洛法对模型进行求解。文献 [3] 提出停车设施的选择概率不仅依赖于设施的停车吸引力系数, 也与设施处的停车收费价格、停车相关步行时间和生成点与设施间的实际行程时间相关。文献 [4] 将停车需求分布与路径选择结合，构建了双层规划决策模型。文献 [5] 分析了不同情境下泊位拥有者参与共享泊位的意愿。文献 [6] 实证分析共享无人车的使用对停车泊位需求的影响，表明随着共享无人车比例的上升，一些特定泊位的需求会明显下降。文献 [7] 提出基于停车需求者的个人信用风险等级来匹配泊位，从而降低违约风险。文献 [8] 分析了共享停车供给与需求存在的不准时特征，发现给定时段最佳的预约泊位数不仅与该时段的停车需求的不准时相关，也与邻近时段的停车需求量相关。文献 [9] 分析了提高泊位利用率和停车需求者满意度两个方面对共享泊位的匹配的影响。

下面简单介绍在共享停车匹配优化模型构建和平台设计方面的现有研究。从参与各方经济利益最大化角度出发，文献 [10] 构建了基于拍卖机制的共享停车泊位分配、定价和收益机制。文献 [11] 通过定义虚拟泊位概念建立了共享停车泊位匹配的优化模型，在时间窗约束条件下实现共享泊位的最大利用率。文献 [12] 考虑停车需求的优先级别差异，针对多个停车场的共享停车泊位匹配问题建立了对应优化模型。文献 [13] 在综合租用车位成本、提供停车服务收入和拒绝潜在用户的损失基础上，以平台收益最大化为目标，构建了车位租用和停车需求分配的统一决策模型。文献 [14] 以步行距离的差异定义共享车位的异质性，构建了跨区域泊位分配的随机动态规划模型。文献 [15] 利用滚动时域方法对实时获得的共享停车供需进行滚动式动态匹配，研究表明超额的泊位供给或需求均不能提升系统的表现，而为需求增加一定的时间冗余将有利于系统的健康运行。文献 [16] 以最大化泊位利用率和减少步行距离为双目标，建立的共享停车的泊位分配模型，并利用粒子群算法对模型进行求解。文献 [17] 通过分析停车需求的到达时间和停泊时长分布，建立模型来优化共享停车收益，确定最佳共享泊位与保留非共享泊位的数量。文献 [18] 提出了一种基于序列拍卖的共享停车泊位分配和定价方法。文献 [19] 通过建立平衡优化模型，从共享停车平台定价的角度分析了租用泊位价格和停车服务费用对停车需求选择行为(如泊位类型选择和泊位位置选择)的影响。在包含损益中性、损失厌恶和收益喜好三种参拍者类型条件下，文献 [20] 基于拍卖机制在对预约式停车泊位分配进行了分析。文献 [21] 分析了共享停车服务平台预先租用一定量的泊位提供给共享车辆的可行性，发现将共享用车与专门的共享车辆预租泊位结合不仅可增加平台收益，也有利于社会的整体福利。在综合考虑租用车位费用、出售共享停车服务的收益和客户需求无法满足的损失条件下，文献 [22] 从平台收益角度建立了预约式泊位分配模型。

除了上述的针对一般性共享停车的匹配研究，也有不少学者对共享停车供需匹配的某些特定场景进行了相关研究。文献 [23] 对居住区与毗邻商务区的夜间车辆停车需求规律进行了分析，给出了对应的停车泊位共享配置模型。文献 [24] 在考虑步行距离条件下分析了毗邻私有停车场设置共享停车位的利弊，得出设置共享停车位可以有效降低出行成本和缓解交通拥堵，但是过多地建设反而会降低系统的出行效率，造成新的拥堵的研究结论。文献 [25] 提出停车管理公司可通过回购部分私有车位用于共享停车的方式来化解停车难题。文献 [26] 给出了一种区分用户类别(如大楼住户和社会用户)的楼宇附属停车场的共享停车资源分配方法。

最后简单介绍现有的与停车供需匹配相关的无人驾驶车辆相关研究。文献 [27] 分析了无人车市场占有率、燃油费和停车费对无人车在完成载客后的选择停车场的影响，建议通过差异化的区域收费引导无人车的停车场选择，从而在整体上实现停车的供需平衡，减少交通拥堵。文献 [28] 分析了在不同的停车能力限制条件下共享无人车的市场占有率对早上通勤出行的影响。文献 [29] 利用仿真模型对共享无人车、私有无人车、共享有人车和非共享有人车共存情况下的停车需求变化进行分析，发现共享车辆的存在可降低总体停车需求，但也会增加部分敏感区域的停车需求。文献 [30] 分析了停车管理策略对需求响应式共享无人车的规模、服务效率和公平性，以及相关的外部性影响。文献 [31] 对智慧停车和自动代客泊车理论发展与相关实践进行了系统梳理，明确了当前相关领域需要关注和解决的主要问题。

3. 问题介绍

本文研究问题的提出基于两大背景，一是错时共享停车的研究与实践，二是无人驾驶技术的不断发展完善与实践。错时共享停车利用停车泊位供给与停车需求的时空分布特征，将一些在特定时间内空闲的私有停车位出租，从而满足该时间内的部分停车需求。一个典型例子就是居民小区白天上班期间会存在一定量的空闲车位可提供给在附近上班的司机；而晚间一些商业中心的停车场比较空闲，可以提供给附近有停车困难的居民。错时共享停车不仅解决了部分停车难题，而且有效盘活了现有泊位资源，并为泊位拥有者带来收益。无人驾驶是人工智能和信息通信技术发展的产物。无人驾驶从最初的车辆行驶辅助功能，如自动巡航和自动停车，发展到自主的路线规划和物联网层面的自动代客泊车，为实现信息时代的智慧出行保驾护航。将共享停车与无人驾驶结合，将促使以往的停车运营模式发生质的改变。

无人驾驶条件下，车辆不必在整个停车期间只停泊在一个给定车位。无人驾驶车辆可以在无驾驶员条件下，根据停车场或停车区域内共享泊位的占用和开放信息自主地进行移位，从而有效利用泊位资源，减少泊位的无停车时间碎片数量。当然无人驾驶带来上述便利的同时也会增加一定的车辆移位成本和风险，因此如何在满足停车需求条件下减少车辆移位成本和费用就成为一个亟待解答的问题。本文将关注如何在车辆停车需求时间和泊位共享开放时间给定，且已知各个泊位间的移车距离条件下，有效减少车辆移位次数与总的车辆移位距离，从而降低无人驾驶车辆在泊车过程中的移车成本与风险。

上述问题具有如下特征：a. 鉴于错时共享停车的理念，无人驾驶的停车需求和共享泊位的开放时间事先已知；b. 无人驾驶车辆可以在所有共享泊位之间实现灵活的移位；c. 泊位间移位的距离已知，且通过给定线路进行移车的风险可预估；d. 由于是预约式停车，可假设任意时刻的泊位供给大于实际可接受的预约需求。上述的问题特征使得我们可以将停车需求时间段和泊位的可共享时间段加以分割，形成一些相互关联的小的分割时间段；进一步将车辆和泊位的匹配问题转换为对一些供需分割时段的匹配，从而简化建模过程，实现对问题的细致刻画。

4. 模型

4.1. 主要参变量介绍

$v\in V$ 表示具有共享停车需求的一辆无人车，而 $V$ 为所有具有共享停车需求车辆的集合；

$p\in P$ 表示可提供共享停车时段的一个具体泊位，而 $P$ 为所有可共享泊位构成的集合；

$t_{v,\text{start}}$ 表示无人车 $v$ 的停车需求的起始时刻；

$t_{v,\text{end}}$ 表示无人车 $v$ 的停车需求的终止时刻；

$t_{p,\text{start}}$ 表示停车泊位 $p$ 的共享停车时段的起始时刻；

$t_{p,\text{end}}$ 表示停车泊位 $p$ 的共享停车时段的结束时刻；

$t_{\text{start}}$ 表示共享停车开始时间，等于 ${\min }_{p\in P}\left\{t_{p\text{,start}}\right\}$ ；

$t_{\text{end}}$ 表示共享停车终止时间，等于 ${\max }_{p\in P}\left\{t_{p,\text{end}}\right\}$ ；

$t\in \left[t_{\text{start}},t_{\text{end}}\right]$ 表示可共享停车的总时段 $\left[t_{\text{start}},t_{\text{end}}\right]$ 中的一个时刻；

$i\in \left\{1,2,3,\cdots ,I\right\}$ 表示将 $\left[t_{\text{start}},t_{\text{end}}\right]$ 划分为 $I$ 个相继的小时段中的一个典型时段；

$\Delta t_i$ 表示第 $i$ 时段的实际时长；

$d_v^i\in \left\{0,1\right\}$ 指示车辆 $v$ 在第 $i$ 时段是否有停车需求，等于1时表示有停车需求，否则无；

$s_p^i\in \left\{0,1\right\}$ 指示泊位 $p$ 在第 $i$ 时段是否可用于共享停车，等于1时表示可共享，否则不可；

$x_{v,p}^i\in \left\{0,1\right\}$ 为匹配决策变量，等于1表示车辆 $v$ 在第 $i$ 时段停泊 $p$ 车位，否则为0；

$l_{p,q}$ 表示泊位 $p$ 与 $q$ 间的移车距离；

$w_v$ 表示车辆 $v$ 在共享停车过程中，发生一次移车的惩罚性成本，假设其单位与距离相同。

4.2. 分割时段

将一天中每个小时以固定时长分割为不同的小段。如以5分钟为间隔，8:00~9:00间的分割时间点包括{8:00, 8:05, 8:10, 8:15, 8:20, …, 9:00}。我们假设所有车辆的共享停车需求起止时间和共享停车泊位的可共享时段的起止时间都落在上述时间点上。基于上述假设，可以将停车需求时间和泊位共享时间加以有效分割。如果以上述给定固定时长作为所有分割时段的时长，可以得到等时长的分割时段。这种方法操作简单，在此不作详述。

虽然等时长的时段划分操作简单，但是得到的划分时段数量一般较大，因此会增加后续模型的求解时间。有鉴于此，下面我们考虑如何进行非等长的时段划分。具体步骤如下：

步骤1：将所有车辆的共享停车需求起止时间和共享泊位的可共享时段的起止时间放入一个集合，并去掉重复的值；

步骤2：按照从小到大的顺序对上述集合内的元素加以排序；

步骤3：比照上述时间序列，对所有车辆的停车需求时间加以分割；

步骤4：比照上述时间序列，对所有共享泊位的可共享时段加以分割。

一般而言，非等长的分割时段划分可以减少总的时段数量，从而降低后续模型的计算时间。但是非等长的时段划分降低了车辆与泊位匹配的灵活性，因此得到的最终解可能劣于在等长时段情景下得到的最终解。

4.3. 目标函数与约束

共享泊位与无人驾驶车辆的匹配优化模型如下：

$\min z\left(x\right)=\underset{v\in V}{{\displaystyle \sum }}\underset{p\in P}{{\displaystyle \sum }}\underset{q\in P}{{\displaystyle \sum }}{\displaystyle \underset{i=1}{\overset{I-1}{\sum }}{l}_{p,q}{x}_{v,p}^i{x}_{v,q}^{i+1}}+\underset{v\in V}{{\displaystyle \sum }}\underset{p\in P}{{\displaystyle \sum }}\underset{q\in P/\left\{p\right\}}{{\displaystyle \sum }}{\displaystyle \underset{i=1}{\overset{I-1}{\sum }}{w}_v{x}_{v,p}^i{x}_{v,q}^{i+1}}$ (1)

$\underset{v}{{\displaystyle \sum }}{x}_{v,p}^i\le s_p^i,\forall p,i$ (2)

$\underset{p}{{\displaystyle \sum }}{x}_{v,p}^i=d_v^i,\forall i,v$ (3)

$x_{v,p}^i\in \left\{0,1\right\},\forall i,v,p$ (4)

目标函数式(1)的第一个加和项表示如果车辆在两个相邻时段停泊于不同泊位时需要移车的距离之和；而第二个加和项表示如果车辆在两个相邻时段停泊于不同泊位时需要移车所引发的惩罚成本。目标函数是以最小化上述两项的加和为目标。约束(2)表示在给定时段停泊在给定泊位的车辆数应小于该泊位在该时段最大的可停泊数量，即在可共享时段小于1，而在非共享时段小于0。约束(3)表示在任意给定时段车辆的可接受停车需求必须满足。约束(4)是对决策变量取值范围的限定。由约束(2)和(3)可推出下面的隐含约束：

$\underset{v}{{\displaystyle \sum }}{d}_v^i=\underset{v}{{\displaystyle \sum }}\underset{p}{{\displaystyle \sum }}{x}_{v,p}^i\le \underset{p}{{\displaystyle \sum }}{s}_p^i,\forall i$ (5)

隐含约束(5)表明在任意给定时段，车辆的停车需求小于泊位的供给。满足约束(5)的停车需求被称为可接受停车需求。

模型(1-4)属于纯整数二次规划(Pure Integer Quadratic Programming-PIQP)。现有研究已经证实上述类型的问题属于NP-hard问题，也是NP-Complete问题 [32]。针对较大规模的NP-hard问题，如本例中当有停车需求的车辆数大于20，目前不存在有效的精确最优解求解算法 [32]。因此只能通过设计有针对性的启发式算法加以求解。

5. 算法设计

5.1. 算法中的个体优化

只有当同一辆车在相邻的两个时间段停放在不同泊位时，才会产生移车的风险和成本。因此，如果能够直接减少车辆在停车过程中的实际移车次数和距离，就可以实现对目标函数(1)的优化。如图1所示，车辆 $v$ 在时间段 $i-1$ 和 $i$ 停放于泊位 $p$ ，而在时间段 $i+1$ 和 $i+2$ 则停放于泊位 $q$ 。为了简化计算，在这里忽略了移车的耗时，假设实际的移车时间已经包含在移车前后车辆所处的两个时间段内。如图1中，车辆在时刻t完成从泊位p到q的移动。

图1. 泊位上车辆位置示意图

定义1 (移位成本)：给定车辆与泊位的一个匹配方案，在任意给定的两个连续时段之间存在的所有移车成本称为该方案下两个分割时段间的移位成本。而多个连续时段的移位成本等于其中包含的所有相继两个分割时间段的移位成本之和。泊位与车辆的一个可行匹配由多个连续的分割时间段组成，其包含的所有相继分割时间段间的移位成本之和称为该匹配的移位成本。 □

定义2 (交换操作)：交换操作 $Swap\left[i,p\left(v\right),q\left(k\right)\right]$ 表示将 时段的泊位 $p$ 上的车辆 $v$ 与泊位 $q$ 上的车辆 $k$ 互换位置。互换后在 $i$ 时段车辆 $v$ 将停于泊位 $q$ 上，而车辆k将停在泊位 $p$ 上。显然，交换操作 $Swap\left[i,p\left(v\right),q\left(k\right)\right]$ 与 $Swap\left[i,q\left(k\right),p\left(v\right)\right]$ 是等价的。 □

在图1中其它三个与车辆 $v$ 相关的可能交换操作包括 $Swap\left[i-1,p\left(v\right),q\left(k\right)\right]$ 、 $Swap\left[i+1,p\left(n\right),q\left(v\right)\right]$ 和 $Swap\left[i+2,p\left(n\right),q\left(v\right)\right]$ 。单一的交换操作只能在同一分割时间段内进行。有时我们会同时实施几个不同的交换操作，如图1中可将 $Swap\left[i+1,p\left(n\right),q\left(v\right)\right]$ 和 $Swap\left[i+2,p\left(n\right),q\left(v\right)\right]$ 同时实施从而减少车辆 $v$ 的总体移位成本。

定义3 (有益与无益交换)：给定一个泊位与车辆的匹配，设 $E$ 为一组可行的交换操作， $\Delta c\left(E\right)$ 表示实施 $E$ 后，新得到的泊位与车辆的匹配的移位成本减去原匹配移位成本得到差值。如果 $\Delta c\left(E\right)$ 小于零，我们称 为有益交换；否则，称 $E$ 为无益交换。 □

在遗传算法里，我们称优化问题解的一个表达式为一个个体。在本文中，我们将泊位与车辆的一个可行匹配称为一个个体。下面给出个体自主优化的过程：

步骤1：从所有车辆任选一辆车 $v$ 。

步骤2：从车辆 $v$ 最早的分割时间段开始，依次判断在该分割时段与紧邻的后续分割时间段上车辆 $v$ 是否停放于同一泊位；如果车辆 $v$ 的所有分割时段已经判断完成，转步骤4。

步骤3：如果停放于同一泊位，则转步骤2进行下一时段的分析判断；否则实施如下操作：

步骤3.1：确定 $v$ 停放的两个泊位；

步骤3.2：分别以当前的两个相邻分割时间段为起始时段，分别向前和向后在两个泊位搜索停放 $v$ 的相邻时间段，构成两个集合；

步骤3.3：分别以两个集合和两个泊位为交换操作的内容与位置，确定有益交换中 $\Delta c\left(E\right)$ 最小的交换组合。

步骤3.4：如存在最佳的有益交换，则实施该交换。

步骤3.5：转步骤2，对新的相邻分割时段加以判断。

步骤4：从车辆集合里选择一辆未被选择过的车辆，转步骤2；如果所有车辆均已被选择，个体的自主优化过程结束。

5.2. 遗传算法流程

通过将共享停车时间分割为小的时间段，不仅可以有效地刻画无人驾驶车辆的特征和泊车优势，也为我们设计相关的遗传算法提供了便利。在一个给定的分割时间段内，泊位与相关的车辆形成一个匹配关系。如果我们将对应一个分割时间段的匹配看作一个基因点，那么所有分割时段对应的匹配合成一个染色体，即一个个体。这里的一个基因代表一个复杂的单时段匹配。算法中一个基因的变异可以用对应时段的一个随机生成的匹配表示。而遗传算法的交叉算子可以通过交换两个个体包含的对应同一分割时段的车辆与泊位匹配来实现。

下面给出对应的带有个体自主优化的遗传算法步骤：

步骤0：初始化。设定种群每代包含的个体总数 $n_{\mathrm{pop}}$ ，每代复制到下一代的个体总数 $n_{\text{copy}}$ ，通过交叉操作得到的新个体数目 $n_{\text{cross}}$ ；给定交叉系数 $r_C$ 、变异系数 $r_M$ 、锦标赛的规模 $n_T$ ，最大的遗传代数 $n_{GA}$ 和最大的分割时段序数 $I$ 。

步骤1：生成初始种群。依次生成各分割时段所包含的需求车辆和可共享泊位的一个随机匹配，并组合形成一个新个体；同理，连续生成 $n_{\mathrm{pop}}$ 个新个体，形成初始种群。

步骤2：个体自主优化后的复制。对当前种群的个体实施4.1节的个体优化操作，并记录当前最优的个体；然后利用规模为 $n_T$ 的锦标赛算法从当前种群中选出 $n_{\text{copy}}$ 个个体作为复制到下一代的个体群。

步骤3：交叉操作。利用规模为 $n_T$ 的锦标赛算法从当前种群中选出2个个体进行交叉。本文随机从基因序列里选择两个基因位置作为交叉位，实施两点的错位交叉，从得到的两个交叉个体中随机选择一个作为下一代的新个体加以保留。同理，连续交叉生成 $n_{\text{cross}}$ 个新个体。

步骤4：变异操作。对步骤3得到个体逐一进行变异操作。按照变异系数 $r_M$ 逐一判断每个基因位上的基因是否需要进行变异。如果需要变异，则生成一个对应分割时间段的随机匹配加以替换。

步骤5：新种群构成。将步骤2和步骤4得到的新个体，以及当前记录的最优个体，合并形成新一代种群。如果达到了最大遗传代数 $n_{GA}$ ，算法终止，输出最优个体信息；否则，转步骤2。

6. 算例分析

算例分析的基本参数设定如下：每次移车的惩罚成本为100公里(km)；任意两个相异泊位间的距离为在0.01公里(km)到0.1 km之间的服从均匀分布的一个随机生成数；遗传的总代数为500；种群规模为40；变异系数0.05；每代复制个体数10；交叉变异得到新个体数30；基因的随机交叉点位数为2；锦标赛选择个体数目为5。利用Java语言实现本文算法，并在NetBeans IDE8.1平台运行，所用计算机处理器为Intel® Core i3-3120M CPU。对于下面将分析的两个问题，算法执行500迭代的计算时间均小于千分之一秒(即0.001 s)。

首先以一个简单算例来验证本文模型与算法的有效性。该算例数据来自文献 [9]。表1和表2分别给出了车辆的停车需求和泊位的供给。该算例的特殊性在于该问题存在无需移车的匹配方案，因此可以验证本文模型是否也可以对有人驾驶的情景加以处理。

表1. 车辆停车需求

表2. 泊位共享开放时间

表3给出了利用本文遗传算法得到3组最优解，即无需移车的泊位与车辆匹配。其中一组与文献 [9] 给出的最优解相同。表3列出了每个车位以时间顺序停泊的车辆集合。经多次计算表明：得到该问题最优解的遗传算法迭代次数一般不超过5次。

表3. 最优匹配结果

我们也利用商业优化软件Lingo对上述问题的优化模型进行了直接求解。Lingo需约15秒得到一个全局最优解。该解与文献 [9] 给出的已知最优解一致。尽管Lingo可以处理较小规模的问题，但对于稍大规模的问题就无法在可接受的时间范围内给出结果。例如我们利用Lingo求解下面将要分析的具有10个泊位、14辆车和23个分割时段的匹配问题，经数小时运算仍无法得到一个可行解，更不用说最优解。而本文算法可在千分之一秒内给出一个近似最优解。第二个规模稍大的问题的车辆停车需求和泊位供给信息分别在表4和表5中给出。泊位间车辆移位的线路长度在矩阵 $L$ 中给出。矩阵 $L$ 的第 $i$ 行第 $j$ 列的元素值表示车辆从第i个泊位移位到第 $j$ 个泊位所需行驶的距离(km)。

表4. 算例2的车辆停车需求

表5. 算例2的泊位共享开放时间

$L=\left[\begin{array}{c}0.0000.0850.0400.0690.0790.0830.0850.0200.0290.064\\ 0.0950.0000.0330.0350.0150.0180.0360.0750.0920.046\\ 0.0900.0980.0000.0400.0510.0380.0880.0740.0100.087\\ 0.0770.0600.0530.0000.0320.0300.0390.0190.0680.035\\ 0.0310.0890.0920.0930.0000.0410.0290.0660.0140.023\\ 0.0450.0620.0900.0750.0390.0000.0680.0960.0720.059\\ 0.0340.0500.0420.0800.0650.0180.0000.0840.0710.073\\ 0.0900.0690.0700.0510.0200.0780.0530.0000.0690.089\\ 0.0990.0790.0150.0320.0840.0900.0250.0510.0000.094\\ 0.0440.0970.0180.0370.0360.0890.0270.0850.0690.000\end{array}\right]$ (8)

图2用矩阵的形式给出了三次对问题二求解的最终匹配结果。图2所示矩阵图中第一列第一行的“sn”表示第一列为泊位的序号。该矩阵图的第一行的数字表示分割时段的序号。矩阵图中其它元素的意义规定如下：“/”表示对应泊位在对应分割时段不开放；“__”表示对应泊位在对应分割时段为共享停车开放，但是没有被占用；数字“n”表示对应泊位在对应分割时段被序号为 $n$ 的车辆占用。三次计算的最终目标函数值均为200.142，表示三个结果中各存在2次移车操作。注意三次的最终匹配结果是不同的。我们将三次运算的目标函数值随遗传代数增加而变化的情况在图3中给出。三次运算的目标函数初值分别为6503.379、6103.578和6003.613。三次运算收敛于最终匹配解的遗传代数分别为80、490和118。

图2. 最佳匹配的矩阵

图3. 随遗传代数增加，最佳个体对应的目标函数值变化

上面对两个算例的计算分析表明：本文给出的模型不仅可以处理无人驾驶车辆的共享停车供需匹配问题，而且也可以对小规模的常见普通车辆的共享停车供需匹配问题进行处理；改进后的遗传算法可以高效的求解本文建立的具有NP-hard特征的匹配优化模型，在极短时间内给出问题的近似最优解。

7. 结论

考虑到无人车可以在无驾驶员情况下在停车场内自主移位的特征，本文构建了最小化移车距离和次数的无人车与共享泊位之间的时空匹配优化模型，并给出了一个具有个体自主优化特点的改进遗传算法对模型加以求解。通过数值算例验证说明了模型和算法的有效性。研究表明在利用有限泊位资源有效满足停车需求的同时，合理的匹配也可以大幅减少无人车的不必要频繁移位。本研究可以为“如何在无人驾驶环境下通过共享和合理配置充分利用有限的共享停车泊位”提供解决方案，也为解决目前大城市停车难问题提供了一种新的思路。

由于目前尚缺乏无人驾驶环境下实际的停车需求与共享泊位数据，因此本文仅对一些仿真数据进行了验证分析，后续研究将对这方面数据的获取与分析进行深入探索。尽管本文模型可以处理有人驾驶的共享停车匹配，但是由于遗传算法一般只能提供次优解，因此得到的结果往往存在车辆在停泊过程中需要进行移位的情况，因此还无法满足实际的有人车与泊位的匹配优化需要。关于在有人驾驶和无人驾驶混合情况下如何得到实际可行的匹配结果将是我们下一步研究的重点。

基金项目

国家自然科学基金资助项目/National Natural Science Foundation of China (71801153, 71871144)；上海市自然科学基金项目/Natural Science Foundation of Shanghai (18ZR1426200)。

文章引用

崔允汀,何胜学. 无人驾驶条件下的共享停车供需匹配模型及其对应遗传算法
Parking Space Sharing Supply-Demand Matching Model and the Designated Genetic Algorithm Based on Autonomous Vehicles[J]. 应用数学进展, 2022, 11(02): 756-768. https://doi.org/10.12677/AAM.2022.112081

参考文献