一种基于单元格的密集停车策略：最小化移库的停车-取车调度设计与高效数学启发式方法

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：A novel cell-based dense parking strategy: Design and relocation-minimizing parking-retrieval scheduling with an efficient matheuristic

　　

• 引入一种新颖的基于单元格的密集停车系统，以解决城市停车供应短缺的挑战。
• 提出一种新颖的数学启发式算法，以便在合理时间内快速找到高质量的可行解。
• 基于真实停车数据进行广泛的数值实验，以证明所提数学启发式算法的优越性。
• 所提出的数学启发式算法可扩展到解决具有两种或更多替代公式的广泛优化问题。

引言

由于私家车拥有量的大幅上升（中华人民共和国公安部，2024年；INRIX研究，2017年），停车难题在各大都市区日益成为关键问题。为解决停车短缺问题，停车服务提供商、城市规划者和研究人员探索了一系列解决方案，涉及建筑改进和技术创新。在建筑方面，建造多层停车设施已被确认为扩展停车容量和提高停车可用性的有效方法（Goel等，2012年）。技术解决方案，如紧凑自动化停车系统（Wu等，2019年）和自动立体车库（Li和Miao，2020年），通过采用垂直停车设计和自动化来提高停车效率。这些系统通过显著提高垂直空间的利用率，为应对城市环境的停车需求提供了有用途径。然而，它们的实用性往往受到高建设成本、对现有停车设施进行大量重新设计的需要，以及购买新型先进设备的高成本所限制，在许多城市地区，从财务上看是不可行的。

本研究引入了一种新颖的基于单元格的密集停车系统，作为传统稀疏停车布局的一种具有成本效益和可扩展性的替代方案。该系统不单纯依赖固定的行车道和标准车位，而是通过将部分机动通道重新配置为额外的停车位，实现更高的密度，创建称为密集停车单元格的标准化模块单元。每个密集停车单元格结合了（i）传统布局中的原始标准车位和（ii）由通道空间改造而成的新增加阻挡车位。这种安排更高效地利用了可用的闲置空间，允许在同一物理空间内容纳额外的车辆，而无需新建建筑。对于某些停车设施布局，所提出的配置可将有效停车容量提高至少30%，使其成为空间受限城市地区的实用解决方案。此外，单元格结构的模块化特性使其能够通过调整包含的行车道长度灵活适应不同的停车布局。

密集停车单元格设计可以仅通过布局修改无缝集成到传统停车场中。图1通过一系列示意图比较展示了这种转变：图1(a)展示了一个真实的停车设施，其中停车位沿行车道两侧垂直排列，并由承重柱界定。图1(b)显示了传统停车场配置的俯视图，中心区域包含369个标准车位。放大视图突出显示了一个完全由标准车位组成的12车位单元（使用12车位案例进行说明；该方法可扩展到其他大小和布局，详见3.1节密集停车单元格的配置结构和动态开启机制，图2）。图1(c)说明了在提出的密集停车系统下重新配置的布局。在此，密集停车单元格随着传统车位的填满而逐步激活。每个18车位单元格由12个标准车位和6个阻挡车位组成。图1(d)展示了一种极端利用场景，其中所有密集停车单元格完全激活，达到系统的最大静态容量，共491个车位（345个标准车位和146个阻挡车位）。这种设置仅在高度饱和的需求条件下启动，作为静态占用率的上限。

一旦标准化的基于单元格的密集停车布局就位，首要的实际问题是如何实施单元格内的车辆重新定位。在实践中，这些任务可以通过几种新兴技术或服务模式之一来实现：i) 代客泊车服务（JONES，2022年；The Parking Spot，2020年），由人工驾驶员手动重新定位车辆；ii) 自动驾驶系统（Banzhaf等，2017年；Ferreira等，2014年；Nourinejad等，2018年；Siddique等，2021年），使用传感器和算法进行自动导航；以及iii) 自动导引车系统，自动引导车辆驶入或驶出停车位（PARKPLUS，2016年；Yeefung，2016年）。

阻挡车位的使用显著增加了停车和检索操作调度的计算难度。真实数据集显示每个车位每天有两到三次周转；因此，一个18车位单元格预计每天要处理大约36-54个预约请求。在这些吞吐量下，我们的实验表明，最先进的求解器Gurobi（Gurobi Optimization, LLC, 2022年）通常在合理的求解时间内无法产生令人满意的解，对于许多实例，即使经过8小时的计算也找不到可行解。

为应对这一挑战，我们首先提出了针对基于单元格的密集停车优化问题的两种替代整数规划（IP）模型。基于这些模型，我们开发了一种高效、可扩展的数学启发式算法，以显著提升解的质量。我们的工作做出以下贡献：

1. 我们引入了一种新颖的、可扩展的、实用的、标准化的基于单元格的密集停车布局，并研究了该系统中停车和检索过程的联合优化。我们将问题表述为IP模型，并将其扩展为两种变体，以解决现实问题设置，包括多个输入/输出点和动态停车需求。在真实世界数据集上的实验证明了预约考虑在减少车辆重新定位方面的显著效益，显示重新定位努力可以节省40%～73%。通过定量分析确定的效益，连同实用的标准化布局设计和设置，有效地说服现有停车场采用所提出的停车服务。

2. 我们提出了一种新颖的、通用的、高效的替代模型诱导的交互式邻域搜索（AMIINS）数学启发式算法，以在规模各异的实例（尤其是实际规模的实例）上显著提升计算效率。该方法充分整合了两种模型的优势，通过由两种替代公式和强路径固定程序驱动的模型诱导交互式邻域搜索机制，有效生成改进解。超越本文范围，我们强调所提出的AMIINS数学启发式算法具有通用性，并有可能进一步扩展以解决可从替代角度公式化的一系列优化问题。

3. 对于零重新定位的特殊情况（即不需要重新定位的情况），我们开发了一种基于零重新定位路径公式（ZRTS-PF）和定理1的快速精确求解方法。此外，该方法连同问题的固有属性（观察1和定理2），可用于快速提高需要重新定位的情况的全局下界。

4. 我们基于真实世界停车数据集进行了广泛的数值实验，以验证所提出的AMIINS数学启发式算法的性能。结果表明，与基线方法相比，AMIINS在测试实例上的解质量、计算时间和收敛速度方面均显著优于基线方法。此外，关于初始解和相关关键算法参数的全面敏感性分析进一步证明了AMIINS的鲁棒性，并提供了有用的调优建议。

本文其余部分结构如下。第2节回顾相关文献并确定研究空白。第3节详细描述了基于单元格的密集停车优化问题，包括布局设计、相关概念和假设、预约机制以及运营过程细节。第4节介绍了用于解决所研究问题的两种替代数学规划模型，分析其属性并讨论现实扩展。第5节详细介绍了所提出的数学启发式方法，阐述核心思想，描述其框架并解释其组件。第6节报告了基于真实数据的数值实验结果，并提供了全面的分析。最后，第7节总结本工作并讨论潜在的未来研究方向。

相关工作片段

我们的工作与三个研究领域相关：停车预约、基于拼图存储系统中的物品检索和高密度停车。具体而言，停车预约方面与本研究中基于预约的停车服务设置直接相关。基于拼图存储系统中的物品检索与我们解决的车辆停车和检索操作非常相似，因为两者都需要处理目标对象与其他物品之间的阻挡约束。最后，

问题描述片段

本节全面描述了基于单元格的密集停车系统的布局结构和运营逻辑。我们从单元格的停车系统布局和预约机制开始。然后，我们介绍合法的车辆移动和相关的阻挡动力学，接着是车辆停车和检索过程的基于轮次的表示。一个示例说明结束本节。

数学公式片段

本节从两个角度公式化所研究的问题，并呈现相应的整数规划模型，即基于轮次的整数规划公式（第4.1节）和基于时空路径的公式（第4.2.2节）。前者基于车辆停车和检索过程的逐轮表示（详见第3.4.1节），而后者从时空网络表示角度公式化所研究的问题。两者...

求解方法片段

由于计算复杂性，使用最先进的求解器（如Gurobi）求解RbF模型是耗时的。此外，如附录B中所述，尽管开发了基于TS-PF的分支定价和切割算法，但生成高质量解所需的计算时间仍然过长，需要进一步改善。为解决计算挑战，我们提出了一种高效和通用的替代模型诱导的邻域交互式搜索（AMIINS）...

数值实验片段

本节使用真实世界停车数据集进行广泛的数值实验，以验证纳入预约机制的效益，并评估与基线方法相比所提出的AMIINS数学启发式算法的性能。首先，我们在第6.1节中描述数据集、实例生成和参数设置。接下来，第6.2节简要解释了用于比较的基线方法。在第6.3节中，我们探索如何...

结论片段

本文引入了一种新颖的基于单元格的密集停车系统，以解决城市停车供应短缺的严峻挑战。为了提高可扩展性和实用性，我们设计了标准化的密集停车单元格结构，使整个停车场由一组这样的单元格组成。在这个密集停车系统中，客户需要在计划时段前通过指定进入和离开时间来预约他们的停车需求，使停车服务运营商能够整体...

CRediT作者贡献声明

吉子淳：写作 – 审阅与编辑，写作 – 原稿撰写，可视化，验证，软件，方法论，调查，形式化分析，数据管理，概念化。刘兴鲁：写作 – 审阅与编辑，写作 – 原稿撰写，可视化，验证，软件，资源，方法论，调查，形式化分析，数据管理，概念化。赖凯帆：写作 – 审阅与编辑，调查。康月鑫：写作 – 审阅与编辑，验证。吉凯丰：

吉子淳|刘兴鲁|赖凯帆|康月鑫|吉凯丰|杨鹏