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

周玉陶，张正华，朱尔立，金志琦，戚义盛，苏 权

(1.扬州大学 图书馆，江苏 扬州 225009；2.扬州大学 信息工程学院，江苏 扬州 225009；3.扬州大学 建筑工程学院，江苏 扬州 225009；4.扬州国脉通信发展有限责任公司，江苏 扬州 225009)

0 引言

随着城市汽车数量的日益增加,“停车难”问题日益凸显。目前大部分城市是单独的停车场[1]和路边的临时占道停车互补,虽然引入了“互联网+”模式[2-3],但并未把整个城市停车数据进行综合运用。因此,综合考虑公共停车域和私人停车域的停车位资源,研究共享停车优化分配策略对于改善城市交通局部拥堵、提高市民日常出行效率和停车区域综合利用率具有重要意义[4]。

迄今为止,国内外关于车位预测的方法主要有2个方面,基于数据分析的基础拟合模型方法和基于机器学习算法[5-6]的空闲预测方法。二者均存在一些难点和未解决的问题,具体如下:

(1)停车位的分配与选择[7-8]:① 只考虑降低停车成本,未考虑停车效益,没有平衡好各区域的停车利用率,从根本上并未解决资源的合理分配问题;② 多停车区域停车资源优化分配问题其实是多维优化问题,目前没有针对交通变量细化的求解方法。

(2)共享预约理念[9-10]:① 现有的预约方式基本都将静态预约和动态预约单独讨论;② 目前停车预约模型中的费用基本都是固定单价,不体现时效性。

(3)最优化算法以及车位预测算法[11-12]:① 输入数据的规模较大时,模型结构的调试量大,收敛速度慢;② 需要大量调试来确定算法中的关键权重参数,算法的收敛精度受影响[7];③ 无法针对具体的停车预约问题建模,再利用最优化算法求解模型达到全局最优。

针对城市中心停车高峰期“停车难”且停车利用率不均衡的问题,基于交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)[13-14]建立了优化的共享停车位分配模型,提出了基于ADMM优化的求解算法。

1 问题描述及模型建立

如图1所示,构建一个多类型停车场的分配系统。假设该相邻区域内有4个停车区域,分别为区域1～区域4,成本各不相同,且利用率有的过高有的过低[15]。

图1 停车位分配Fig.1 Parking space allocation

基于ADMM优化的共享停车位分配模型,在上述模拟现实情况下,需要有效降低车辆停车成本,合理引导达到平衡停车利用率作用。由此对模型提出如下假设:

① 假设平衡停车区停车位的使用率是市场管理者的最大目标。

② 假设用户对所有停车场中的任何停车位都没有特殊偏好。

③ 假设停车供应用户和停车需求用户都严格遵守系统提交的时间信息。

④ 假设停车需求的用户必须接受系统的分配结果。

⑤ 假设停车场和目的地之间的距离是用户的步行距离。

⑥ 假设用户会根据自己的实际需求如实向系统提交个人属性信息。

将停车场统一分为2种:公共停车域和私人停车域。为了使表达更加清晰,用C={1,2,…,|C|}表示一组寻找车位的车辆,用S={1,2,…,|S|}表示一组停车区域,其中包含了公共停车域和私人停车域。每个停车域的总容量用qj表示,其中j∈S。表1是该共享停车模型的2个目标类型。

表1 模型目标Tab.1 Model objectives

对于车辆所有者来说,每一辆车i∈C在停车时都应该考虑行程时间、搜索停车位所需时间、步行到达目的地所需时间、停车费用以及个人停车偏好等因素[15],这些都是车主在进行停车时需要关注的重要因素;对管理者来说,综合停车利用率是核心关注点,即停车成本和停车效益2个问题是研究的关键[16]。

2 模型建立与参数变量定义

2.1 停车分配中的成本问题

停车成本分为行程时间成本和停车费用成本两部分[17]。

① 行程时间成本问题:首先明确车辆i的起始位置、车辆i的目的地位置和目的地附近停车区域的位置,假设位置信息已知,用dhi和dti分别表示车辆i的起始位置和目的位置,目的附近每个停车区域j的位置用dj表示,所有位置在二维欧几里德平面2上定义。每一辆车i的行程时间成本包含驾驶时间成本和步行时间成本,其中驾驶时间成本指到达停车区域j的时间成本,步行时间成本指从停车区域步行至目的地的时间成本。总行程时间成本定义为:

(1)

② 停车费用成本问题:假设某个停车区域j单位时间内的费用为φj,则费用成本sij可以表示为:

sij=γφjti,∀i∈C,j∈S,

(2)

式中:γ表示费用单位与时间单位统一起来的进率权重,ti表示寻找停车位的车辆i的总停车时间;各区域单位费用φj可以不一样,但同区域的单位费用一致。为符合竞争意义,私人停车域的单位费用小于公共停车域。即车辆i的到达目的地的停车总体成本可以表示为:

mij=θigij+(1-θi)sij,∀i∈C,j∈S,

(3)

式中:θi是行程时间成本和费用成本的权重参数,且θi∈[0,1]。一般情况下,θi取值为0.5,表明行程时间成本和费用成本在系统中的权重等价。这里定义一个总成本矩阵M=|C|×|S|,mij即为这个总成本矩阵里的每个元素。

2.2 停车分配中的效益问题

停车效益分为偏好、安全和利用率三部分[18]。

① 偏好问题:将用户停车偏好定义为司机选择某停车区域的概率Ri→j=P[i→j]。

② 安全问题:安全性为定性指标,用pj来表示每个区域指标。如表2所示,对常见城市停车区域进行量化安全性取值,值越大,越安全。

表2 安全性量化取值Tab.2 Quantitative values of safety

③ 综合利用率:引入二进制变量xij表示停车利用率:

(4)

式中:xij值为1时,表示车辆i分配区域j;xij值为0时,表示未成功分配。t时刻区域j的已占用数量zj(t)可以表示为:

(5)

则t时刻区域j的利用率可以表示为:

(6)

式中:qj是区域j的总车位数,记录在行矩阵Q1×|S|中。相邻两区域同时刻的利用率差值为:

ΔUj(t)=Uj(t)-Uj-1(t)。

(7)

相邻范围Ω={S1,S2,…,|S|}内同时刻所有区域的综合平均利用率记为:

(8)

3 模型构建

3.1 时空相关性

在停车分配模型构建之前,先分析相邻区域利用率的时间和空间特征。通过历史数据分析研究相邻区域时空相关性,作为目标函数的约束条件之一。

相邻区域利用率的时间特征用区域j在某时刻不同时间的利用率相关性表达。例如区域j在上午9:00和上午8:59、8:58、8:57…利用率时间相关性计算公式为:

时间相关性函数式(9)受多种因素影响,利用率在时滞情况下有强时间相关性。相邻区域利用率空间特征以同一时刻不同区域利用率间相关性表达。通过历史数据分析,某区域需求变化会对附近区域需求产生影响,空间相关性公式为:

s(t,d)=

(10)

式中:Ωd≜{(ja,jb)|ja,jb∈S,distance(ja,jb)≤d}指距离小于d的多对区域集合,d=0.16、0.32 km…。

可以看出,除同地点利用率存在时间相关性外,相邻区域在一定时间内也存在空间相关性。

3.2 目标函数与约束条件

本模型主要考虑成本和效益目标,分配策略总目标是在成本最小化基础上的多区域利用率最大化平衡,即最小化利用率差值,且最大化综合利用率。

根据上述多目标决策问题分析,首先将最小化成本的目标函数定义为:

定义目标函数F1为:

(11)

约束条件定义为:

(12)

式中:∑j∈Sxij=1表示车辆和区域的唯一化匹配,约束条件∑i∈Cxij≤qj表示区域分配量不大于总容量,约束条件xij={0,1}表示xij为二进制变量,0或1表示i是否被分配到区域j。可知以上是混合整数线性规划(Mixed Integer Linear Programming,MILP)问题,但大量的i和j数据会使求解难度增加。因此,将形成一个利用匹配理论优化ADMM的分配算法,以适用巨量数据。

图2为平衡成本和效益分配问题。

图2 成本最小和效益平衡示意Fig.2 Schematic diagram of cost minimization and benefit balance

为此引入利用率差值ΔUj(t):

(13)

定义目标函数F2为:

(14)

约束条件定义为:

(15)

为解决资源分配问题,首先放宽分配指标xij,其次将xij转化为[0,1]连续实变量,定义目标函数F3为:

(16)

约束条件定义为:

(17)

3.3 车位分配模型算法与求解

3.3.1 算法设计

假设在起始时间点所有需求都能分配并满足,则先构建偏好模型,详细算法流程如下。

算法1: 停车者的偏好1:初始化,输入集合S={1,2,…,S}中所有停车区域j。2:根据式(3)计算每辆车i分配到停车区域j的停车成本,并按照停车成本的计算结果,将所有停车区域i按升序排序。3:将停车区域j的排序集合添加到车辆i的偏好集合,车辆i的偏好即为停车者的偏好。4:输出停车者的偏好集合Γ(i),∀i∈C。

从成本角度考虑,可得到偏好集合Γ(i),∀i∈C。停车区域的资源分配偏好如算法2所示。

算法2: 停车区域的资源分配偏好1:初始化,输入集合C={1,2,…,C}中所有车辆i。2:根据F2中的F=∑i∈C∑j∈Sδmijxij+∑j∈S(1-δ)ΔUj(t),按照计算结果,将所有车辆i按升序排序。3:判断如果len(2中的排序列表) ≤qj,则将此排序列表中的所有车辆i添加到停车区域j的偏好集合中;否则,将此排序列表中最前面的qj个车辆添加到停车区域i的偏好集合中。4:输出停车者的偏好集合Γ(j),∀j∈S。

从利用率角度考虑,可得偏好集合Γ(j),∀j∈S。本模型目标为通过一种匹配博弈的方法找到一个稳定的匹配方式,如算法3所示。

算法3: 共享停车匹配博弈1:输入:Γ(i),Γ(j),H=[qj]1×S,∀i∈C,j∈S。2:输出:匹配系数μ。3:初始化:接受矩阵χ=[0]C×S,临时拒绝列表=⌀。4:for i∈C do5: j←Γ(i)j,在Γ(i)中j是最优先的。6: if qj>0 then7: χ[i,j]=1;qj=qj-1。8: else9: =∪i;Γ(i)=Γ(i)j10:while≠⌀or H ≠[0]C×S do11: i←i;j←Γ(i)j,Γ(i)中j是最优先的。12: if qj>0 then13: χ[i,j]=1;qj=qj-1。14: else15: i′←i。16: Kj={k/χ[k,j]=1&i′≻jk}.i′≻jk表示停车区域j更偏好i′而不是k。17: for k∈Kj do18: =∪k;χ[k,j]=0;qj=qj+1;Γ(j)=Γ(j)k;Γ(k)=Γ(k)j;19:Return μ←χ20:end

算法3得到收敛稳定的匹配系数μ所需的决策矩阵数量较大。在每次迭代过程中,由车辆个体根据偏好选择区域后,区域选择接受或者拒绝,使算法3在|C|×|S|范围内迭代收敛,得到趋于稳定的匹配系数μ,|C|为停车数量,|S|为停车区域的数量。

3.3.2 ADMM模型求解

算法3中匹配理论结合MILP求解器可以有效解决问题F1,然而F1中没有考虑效益问题,无法平衡资源分配。因此,综合考虑所有因素,得到目标函数F2,为了更好求解将其转换为问题F3。问题F1是单变量优化问题,形如:

(18)

如式(18),定义其增广拉格朗日函数为:

(19)

使用对偶上升法求解,即:

(20)

vk+1=vk+c(axk+1+b)。

(21)

由于F3是一个耦合线性等式约束的凸问题,形如式(21)所示:

(22)

为高效解决问题F3,采用ADMM法,通过分布式计算方式求解。通过上述分析,定义问题F3增广拉格朗日函数如下:

(23)

对x=[xij]|C|×|S|、z=[zj(t)]1×|S|和λ=[λj]1×|S|三种变量,通过以下迭代过程得到。首先,通过式(25)求得x(k+1):

约束条件定义为:

(26)

接下来,求解z(t+1)j:

(27)

约束条件定义为:

s.t.0≤zj(t)≤qj,∀j∈S。

(28)

每次迭代更新变量λ如下:

(29)

最后,综合推导出变量为:

(30)

得到相邻停车区域停车利用率之差:

(31)

在以上基础上,基于ADMM优化提出算法4,详细步骤如图3所示。

图3 基于ADMM优化的停车算法流程Fig.3 Flowchart of parking algorithm based on ADMM optimization

由图3可以看出,算法4开始时,初始化k=0、匹配控制变量x和拉格朗日乘子λ。然后通过收集到的数据,根据式(23)～式(26)更新,并赋值k←k+1,不断迭代,将收敛性作为判断条件,通过梯度下降法证明其收敛性。

4 性能分析

通过模拟停车数据,求解最优δ值,比较不同权重因子δ对收敛性的影响,以及同情况不同算法的收敛特性。

4.1 仿真假设

假设半径为1 000 m的4个停车区域,需求车辆为2 000辆,在Matlab 2018b上进行仿真。首先对比不同权重因子成本和效益间变化,测得平衡点;其次,固定权重因子δ,对比不同算法的收敛性;最后,以ADMM求解算法对比δ对算法收敛性的影响。

4.2 结果分析

通过仿真,得到如下结果,图4为权重因子δ影响分析,图5为ADMM、混合整数二阶锥优化(Mixed Integer Second-Order Cone Optimization,MSO)、增广拉格朗日方法(Augmented Lagrangian Method,ALM)三种算法收敛性比较,图6为不同权重因子δ收敛性对比,表3为性能对比分析。

图4 权重因子δ影响Fig.4 Influence of weight factor δ

如图4所示,随着权重因子δ的增加而成本增大,而效益没有变化。可看出,成本和效益在δ= 1.42×10-3的时候相交于点(0.142,4)。当1.42×10-3<δ<1时,社会效益低于个体成本;当0<δ<1.42×10-3时,社会效益高于个体成本;当δ=1.42×10-3时,二者相等,达到平衡。

如图5所示,当δ=1.42×10-3时,对ADMM、MSO和ALM三种方法收敛性进行比较。ALM法迭代20次达到最优,MSO法13次达到最优,ADMM法迭代8次达到最优。ADMM法收敛性更好、运算更快。

图5 各算法收敛性对比Fig.5 Comparison of convergence of various algorithms

如图6所示,在ADMM法下,虽然δ=1.42×10-2和δ=1.42×10-4时收敛速度快,但当δ= 1.42×10-3时,结果更优。

图6 不同权重因子δ收敛性对比Fig.6 Comparison of convergence of different weight factor δ

表3 性能对比Tab.3 Performance comparison

对实验数据总结可得,当δ=1.42×10-3时,采用ADMM优化算法,模型收敛性最优,高于MSO算法9.18%,高于ALM算法15.94%。

5 结束语

本文从考虑成本和效益两方面综合构建了停车位分配模型。从资源高效利用角度出发,研究了多停车区域分配问题。提出了分配问题的主要目标:成本最低和需求最平衡,并通过构造混合整数优化问题来解决这2个目标。研究了基于ADMM优化的分配算法并论证了可行性,通过Matlab进行仿真得出,在收敛性能上,对比得出ADMM优化算法较MSO算法提高9.18%,较ALM算法提高15.94%,结果更接近最优。