基于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的時間成本,步行時間成本指從停車區域步行至目的地的時間成本?？傂谐虝r間成本定義為:

(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%,結果更接近最優。