基于ADMM优化的停车位分配模型与求解.pdf

年 无线电工程 第 卷 第 期：引用格式：周玉陶，张正华，朱尔立，等基于优化的停车位分配模型与求解无线电工程，（）：，（）：基于优化的停车位分配模型与求解周玉陶，张正华，朱尔立，金志琦，戚义盛，苏权（扬州大学 图书馆，江苏 扬州；扬州大学 信息工程学院，江苏 扬州；扬州大学 建筑工程学院，江苏 扬州；扬州国脉通信发展有限责任公司，江苏 扬州）摘要：随着近几年我国城市机动车保有量的不断增加，停车设施配建不足，如何利用现有停车资源通过资源分配技术平衡各区域停车利用率被广泛关注和研究。因此，通过共享停车分配模式，高效利用现有停车位，对缓解停车难题具有重要意义。针对“停车难”和利用率不均衡问题，基于交替方向乘子法（，）建立了优化的车位分配模型，搭建了基于 的仿真系统。结果表明，基于优化的分配模型收敛性能更佳，较混合整数二阶锥优化（，）算法和增广拉格朗日方法（，）算法，所提算法结果更接近最优。关键词：共享停车分配；空闲预测；交替方向乘子法中图分类号：文献标志码：开放科学（资源服务）标识码（）：文 章 编 号：（），（，；，；，；，）：，（），（）（）：；收稿日期：基金项目：江苏省扬州市产业前瞻与共性关键技术产业前瞻研发重点资助项目（）；江苏省扬州市年市级计划市校合作专项资助项目（）：，（）；，（）信号与信息处理 引言随着城市汽车数量的日益增加，“停车难”问题日益凸显。目前大部分城市是单独的停车场和路边的临时占道停车互补，虽然引入了“互联网”模式，但并未把整个城市停车数据进行综合运用。因此，综合考虑公共停车域和私人停车域的停车位资源，研究共享停车优化分配策略对于改善城市交通局部拥堵、提高市民日常出行效率和停车区域综合利用率具有重要意义。迄今为止，国内外关于车位预测的方法主要有个方面，基于数据分析的基础拟合模型方法和基于机器学习算法的空闲预测方法。二者均存在一些难点和未解决的问题，具体如下：（）停车位的分配与选择：只考虑降低停车成本，未考虑停车效益，没有平衡好各区域的停车利用率，从根本上并未解决资源的合理分配问题；多停车区域停车资源优化分配问题其实是多维优化问题，目前没有针对交通变量细化的求解方法。（）共享预约理念：现有的预约方式基本都将静态预约和动态预约单独讨论；目前停车预约模型中的费用基本都是固定单价，不体现时效性。（）最优化算法以及车位预测算法：输入数据的规模较大时，模型结构的调试量大，收敛速度慢；需要大量调试来确定算法中的关键权重参数，算法的收敛精度受影响；无法针对具体的停车预约问题建模，再利用最优化算法求解模型达到全局最优。针对城市中心停车高峰期“停车难”且停车利用率不均衡的问题，基于交替方向乘子法（，）建立了优化的共享停车位分配模型，提出了基于优化的求解算法。问题描述及模型建立如图所示，构建一个多类型停车场的分配系统。假设该相邻区域内有个停车区域，分别为区域 区域，成本各不相同，且利用率有的过高有的过低。图停车位分配 基于优化的共享停车位分配模型，在上述模拟现实情况下，需要有效降低车辆停车成本，合理引导达到平衡停车利用率作用。由此对模型提出如下假设：假设平衡停车区停车位的使用率是市场管理者的最大目标。假设用户对所有停车场中的任何停车位都没有特殊偏好。假设停车供应用户和停车需求用户都严格遵守系统提交的时间信息。假设停车需求的用户必须接受系统的分配结果。假设停车场和目的地之间的距离是用户的步行距离。假设用户会根据自己的实际需求如实向系统提交个人属性信息。将停车场统一分为种：公共停车域和私人停车域。为了使表达更加清晰，用，表示一组寻找车位的车辆，用，表示一组停车区域，其中包含了公共停车域和私人停车域。每个停车域的总容量用表示，其中。表是该共享停车模型的个目标类型。表模型目标 评价内容评价指标指标类型停车便捷性、可达性行驶和步行距离停车成本型停车费用停车费率停车成本型停车安全性停车场设施类型停车效益型停车分配综合停车利用率停车效益型信号与信息处理 年 无线电工程 第 卷 第 期 对于车辆所有者来说，每一辆车在停车时都应该考虑行程时间、搜索停车位所需时间、步行到达目的地所需时间、停车费用以及个人停车偏好等因素，这些都是车主在进行停车时需要关注的重要因素；对管理者来说，综合停车利用率是核心关注点，即停车成本和停车效益个问题是研究的关键。模型建立与参数变量定义 停车分配中的成本问题停车成本分为行程时间成本和停车费用成本两部分。行程时间成本问题：首先明确车辆的起始位置、车辆的目的地位置和目的地附近停车区域的位置，假设位置信息已知，用和分别表示车辆的起始位置和目的位置，目的附近每个停车区域的位置用表示，所有位置在二维欧几里德平面 上定义。每一辆车的行程时间成本包含驾驶时间成本和步行时间成本，其中驾驶时间成本指到达停车区域的时间成本，步行时间成本指从停车区域步行至目的地的时间成本。总行程时间成本定义为：，（）式中：和是将行程时间单位与停车费用单位进行权衡的进率权重参数，和表示平均驾驶速度和平均步行速度。停车费用成本问题：假设某个停车区域单位时间内的费用为，则费用成本可以表示为：，（）式中：表示费用单位与时间单位统一起来的进率权重，表示寻找停车位的车辆的总停车时间；各区域单位费用可以不一样，但同区域的单位费用一致。为符合竞争意义，私人停车域的单位费用小于公共停车域。即车辆的到达目的地的停车总体成本可以表示为：（），（）式中：是行程时间成本和费用成本的权重参数，且，。一般情况下，取值为，表明行程时间成本和费用成本在系统中的权重等价。这里定义一个总成本矩阵 ，即为这个总成本矩阵里的每个元素。停车分配中的效益问题停车效益分为偏好、安全和利用率三部分。偏好问题：将用户停车偏好定义为司机选择某停车区域的概率。安全问题：安全性为定性指标，用来表示每个区域指标。如表所示，对常见城市停车区域进行量化安全性取值，值越大，越安全。表安全性量化取值 停车设施类型量化取值路边停车地面停车场地下停车场立体停车场机械式停车场综合利用率：引入二进制变量表示停车利用率：，（）式中：值为时，表示车辆分配区域；值为时，表示未成功分配。时刻区域的已占用数量（）可以表示为：（）。（）则时刻区域的利用率可以表示为：（）（），（）式中：是区域的总车位数，记录在行矩阵中。相邻两区域同时刻的利用率差值为：（）（）（）。（）相邻范围，内同时刻所有区域的综合平均利用率记为：，（）（），。（）模型构建 时空相关性在停车分配模型构建之前，先分析相邻区域利信号与信息处理 用率的时间和空间特征。通过历史数据分析研究相邻区域时空相关性，作为目标函数的约束条件之一。相邻区域利用率的时间特征用区域在某时刻不同时间的利用率相关性表达。例如区域在上午：和上午：、：、：利用率时间相关性计算公式为：（，）（），（）（），（）（），（）（），（）槡，（）式中：时刻和时刻利用率的相关系数为（，），区域在时刻利用率是（），时刻的综合利用率是，（）。时间相关性函数式（）受多种因素影响，利用率在时滞情况下有强时间相关性。相邻区域利用率空间特征以同一时刻不同区域利用率间相关性表达。通过历史数据分析，某区域需求变化会对附近区域需求产生影响，空间相关性公式为：（，）（，）（），（）（，）（），（）（，）（），（）槡，（）式中：（，），（，）指距离小于的多对区域集合，、。可以看出，除同地点利用率存在时间相关性外，相邻区域在一定时间内也存在空间相关性。目标函数与约束条件本模型主要考虑成本和效益目标，分配策略总目标是在成本最小化基础上的多区域利用率最大化平衡，即最小化利用率差值，且最大化综合利用率。根据上述多目标决策问题分析，首先将最小化成本的目标函数定义为：定义目标函数为：。（）约束条件定义为：，（）式中：表示车辆和区域的唯一化匹配，约束条件表示区域分配量不大于总容量，约束条件，表示为二进制变量，或表示是否被分配到区域。可知以上是混合整数线性规划（，）问题，但大量的和数据会使求解难度增加。因此，将形成一个利用匹配理论优化的分配算法，以适用巨量数据。图为平衡成本和效益分配问题。图成本最小和效益平衡示意 为此引入利用率差值（）：（）（）（）（）（）。（）定义目标函数为：（）（）。（）约束条件定义为：，（），（，），（，）（），（）式中：为权重因子，；约束条件（）和（）表示在同一时间内，区域空间量充足；信号与信息处理 年 无线电工程 第 卷 第 期 约束条件（，）和（，）表示相邻区域时空相关性在一定阈值范围内，和为常数。同样是问题，且（）随变化。针对此凸优化问题用构建求解算法。为解决资源分配问题，首先放宽分配指标，其次将转化为，连续实变量，定义目标函数为：（）（）。（）约束条件定义为：，（），（，），（，）（），。（）车位分配模型算法与求解 算法设计假设在起始时间点所有需求都能分配并满足，则先构建偏好模型，详细算法流程如下。算法：停车者的偏好：初始化，输入集合，中所有停车区域。：根据式（）计算每辆车分配到停车区域的停车成本，并按照停车成本的计算结果，将所有停车区域按升序排序。：将停车区域的排序集合添加到车辆的偏好集合，车辆的偏好即为停车者的偏好。：输出停车者的偏好集合（），。从成本角度考虑，可得到偏好集合（），。停车区域的资源分配偏好如算法所示。算法：停车区域的资源分配偏好：初始化，输入集合，中所有车辆。：根据中的（）（），按照计算结果，将所有车辆按升序排序。：判断如果（中的排序列表），则将此排序列表中的所有车辆添加到停车区域的偏好集合中；否则，将此排序列表中最前面的个车辆添加到停车区域的偏好集合中。：输出停车者的偏好集合（），。从利用率角度考虑，可得偏好集合（），。本模型目标为通过一种匹配博弈的方法找到一个稳定的匹配方式，如算法所示。算法：共享停车匹配博弈：输入：（），（），。：输出：匹配系数。：初始化：接受矩阵，临时拒绝列表。：（），在（）中是最优先的。：，；。：；（）（）：；（），（）中是最优先的。：，；。：。：，表示停车区域更偏好而不是。：；，；（）（）；（）（）；：算法得到收敛稳定的匹配系数所需的决策矩阵数量较大。在每次迭代过程中，由车辆个体根据偏好选择区域后，区域选择接受或者拒绝，使算法在 范围内迭代收敛，得到趋于稳定的匹配系数，为停车数量，为停车区域的数量。模型求解算法中匹配理论结合求解器可以有效解决问题，然而中没有考虑效益问题，无法平衡资源分配。因此，综合考虑所有因素，得到目标函数，为了更好求解将其转换为问题。问题是单变量优化问题，形如：（）。（）如式（），定义其增广拉格朗日函数为：（，）（）（）。（）使用对偶上升法求解，即：（，），（）（）。（）由于是一个耦合线性等式约束的凸问题，形如式（）所示：信号与信息处理 （）（）。（）为高效解决问题，采用法，通过分布式计算方式求解。通过上述分析，定义问题增广拉格朗日函数如下：（）（）（）（）()，（）式中：是耦合约束（）的拉格朗日乘子，是标量参数。将上式等价为：（）（）（）()（）。（）对 、（）和三种变量，通过以下迭代过程得到。首先，通过式（）求得（）：（）（）（）（）()。（）约束条件定义为：，。（）接下来，求解（）：（）（）（）（）（）（）（）()。（）约束条件定义为：（），。（）每次迭代更新变量如下：（）（）（）（）()。（）最后，综合推导出变量为：（）（）（）（）。（）得到相邻停车区域停车利用率之差：（）（）（）（）()。（）在以上基础上，基于优化提出算法，详细步骤如图所示。图基于优化的停车算法流程 由图可以看出，算法开始时，初始化 、匹配控制变量和拉格朗日乘子。然后通过收集到的数据，根据式（）式（）更新，并赋值，不断迭代，将收敛性作为判断条件，通过梯度下降法证明其收敛性。性能分析通过模拟停车数据，求解最优值，比较不同权重因子对收敛性的影响，以及同情况不同算法的收敛特性。仿真假设假设半径为 的个停车区域，需求车辆为 辆，在 上进行仿真。首先对比不同权重因子成本和效益间变化，测得平衡点；其次，固定权重因子，对比不同算法的收敛性；最后，以求解算法对比对算法收敛性的影响。结果分析通过仿真，得到如下结果，图为权重因子影信号与信息处理 年 无线电工程 第 卷 第 期 响分析，图为、混合整数二阶锥优化（，）、增广拉格朗日方法（，）三种算法收敛性比较，图为不同权重因子收敛性对比，表为性能对比分析。图权重因子影响 如图所示，随着权重因子的增加而成本增大，而效益没有变化。可看出，成本和效益在 的时候相交于点（，）。当 时，社会效益低于个体成本；当 时，社会效益高于个体成本；当 时，二者相等，达到平衡。如图所示，当 时，对、和三种方法收敛性进行比较。法迭代次达到最优，法次达到最优，法迭代次达到最优。法收敛性更好、运算更快。图各算法收敛性对比 如图所示，在法下，虽然 和时收敛速度快，但当 时，结果更优。图不同权重因子收敛性对比 表性能对比 性能对比综合停车效益标量化参数 性能对比综合停车效益标量化参数 性能对比综合停车效益标量化参数 对实验数据总结可得，当 时，采用优化算法，模型收敛性最优，高于算法，高于算法。结束语本文从考虑成本和效益两方面综合构建了停车信号与信息处理 位分配模型。从资源高效利用角度出发，研究了多停车区域分配问题。提出了分配问题的主要目标：成本最低和需求最平衡，并通过构造混合整数优化问题来解决这个目标。研究了基于优化的分配算法并论证了可行性，通过进行仿真得出，在收敛性能上，对比得出优化算法较算法提高，较算法提高，结果更接近最优。?参考文献王韩麒时间窗约束下的共享停车泊位动态分配模型武汉理工大学学报（交通科学与工程版），（）：，（）：平嘉蓉，张正华，沈逸，等基于轻量级神经网络的人群计数模型设计无线电工程，（）：姬杨蓓蓓，成枫，张小宁城市中心区域毗邻私有停车场的共享停车位优化设置研究系统工程理论与实践，（）：樊聪敏，张颖臖，袁晓军，等基于图形表示的异构超密集网络的机器学习技术研究电子科技大学学报，（）：江浩斌，叶浩，马世典，等基于多传感器数据融合的自动泊车系统高精度辨识车位的方法重庆理工大学学报（自然科学），（）：程浩，杨秀沙，黄恒东，等缓解城市停车难问题的分析和对策研究价值工程，（）：李云飞多维场景数据的共享存取优化模型山东农业大学学报（自然科学版），（）：路扬，何胜学，王冬冬共享停车泊位供需匹配优化模型山东农业大学学报（自然科学版），（）：，（）：，（）：，：罗森林，赵惟肖，潘丽敏结合加权和自适应牛顿法的稳健方法北京理工大学学报，（）：，：，（）：何明明，彭建文求解单调包含问题的惯性混合非精确邻近点算法应用数学学报，（）：王波面向实施的公共停车场用地规划方法研究 以广州为例城市规划，（）：段满珍基于博弈论的居住区共享停车理论与方法研究长春：吉林大学，孙会君，傅丹华，吕莹，等基于共享停车的车位租用与分配模型交通运输系统工程与信息，（）：丁敏，张正华，苏权，等基于的智慧停车管理系统设计无线电工程，（）：作者简介周玉陶男，（），硕士，副研究馆员，硕士生导师。主要研究方向：信息资源管理、信息网络及信息安全。（通信作者）张正华男，（），硕士，教授，硕士生导师。主要研究方向：实时信号处理、智能信号处理、嵌入式技术和物联网技术。朱尔立男，（），硕士，工程师。主要研究方向：电气自动化、信息网络及信息安全、物联网技术。金志琦男，（），硕士研究生。主要研究方向：强化学习、嵌入式技术。戚义盛男，（），硕士研究生。主要研究方向：智能信号与信息系统。苏权男，（），硕士，正高级工程师。主要研究方向：软件工程、大数据、人工智能和云计算。信号与信息处理