基于ADMM優(yōu)化的停車位分配模型與求解

周玉陶，張正華，朱爾立，金志琦，戚義盛，蘇 權(quán)

(1.揚(yáng)州大學(xué) 圖書館，江蘇 揚(yáng)州 225009；2.揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225009；3.揚(yáng)州大學(xué) 建筑工程學(xué)院，江蘇 揚(yáng)州 225009；4.揚(yáng)州國(guó)脈通信發(fā)展有限責(zé)任公司，江蘇 揚(yáng)州 225009)

0 引言

隨著城市汽車數(shù)量的日益增加,“停車難”問題日益凸顯。目前大部分城市是單獨(dú)的停車場(chǎng)[1]和路邊的臨時(shí)占道停車互補(bǔ),雖然引入了“互聯(lián)網(wǎng)+”模式[2-3],但并未把整個(gè)城市停車數(shù)據(jù)進(jìn)行綜合運(yùn)用。因此,綜合考慮公共停車域和私人停車域的停車位資源,研究共享停車優(yōu)化分配策略對(duì)于改善城市交通局部擁堵、提高市民日常出行效率和停車區(qū)域綜合利用率具有重要意義[4]。

迄今為止,國(guó)內(nèi)外關(guān)于車位預(yù)測(cè)的方法主要有2個(gè)方面,基于數(shù)據(jù)分析的基礎(chǔ)擬合模型方法和基于機(jī)器學(xué)習(xí)算法[5-6]的空閑預(yù)測(cè)方法。二者均存在一些難點(diǎn)和未解決的問題,具體如下:

(1)停車位的分配與選擇[7-8]:① 只考慮降低停車成本,未考慮停車效益,沒有平衡好各區(qū)域的停車?yán)寐?從根本上并未解決資源的合理分配問題;② 多停車區(qū)域停車資源優(yōu)化分配問題其實(shí)是多維優(yōu)化問題,目前沒有針對(duì)交通變量細(xì)化的求解方法。

(2)共享預(yù)約理念[9-10]:① 現(xiàn)有的預(yù)約方式基本都將靜態(tài)預(yù)約和動(dòng)態(tài)預(yù)約單獨(dú)討論;② 目前停車預(yù)約模型中的費(fèi)用基本都是固定單價(jià),不體現(xiàn)時(shí)效性。

(3)最優(yōu)化算法以及車位預(yù)測(cè)算法[11-12]:① 輸入數(shù)據(jù)的規(guī)模較大時(shí),模型結(jié)構(gòu)的調(diào)試量大,收斂速度慢;② 需要大量調(diào)試來確定算法中的關(guān)鍵權(quán)重參數(shù),算法的收斂精度受影響[7];③ 無法針對(duì)具體的停車預(yù)約問題建模,再利用最優(yōu)化算法求解模型達(dá)到全局最優(yōu)。

針對(duì)城市中心停車高峰期“停車難”且停車?yán)寐什痪獾膯栴},基于交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)[13-14]建立了優(yōu)化的共享停車位分配模型,提出了基于ADMM優(yōu)化的求解算法。

1 問題描述及模型建立

如圖1所示,構(gòu)建一個(gè)多類型停車場(chǎng)的分配系統(tǒng)。假設(shè)該相鄰區(qū)域內(nèi)有4個(gè)停車區(qū)域,分別為區(qū)域1～區(qū)域4,成本各不相同,且利用率有的過高有的過低[15]。

圖1 停車位分配Fig.1 Parking space allocation

基于ADMM優(yōu)化的共享停車位分配模型,在上述模擬現(xiàn)實(shí)情況下,需要有效降低車輛停車成本,合理引導(dǎo)達(dá)到平衡停車?yán)寐首饔?。由此?duì)模型提出如下假設(shè):

① 假設(shè)平衡停車區(qū)停車位的使用率是市場(chǎng)管理者的最大目標(biāo)。

② 假設(shè)用戶對(duì)所有停車場(chǎng)中的任何停車位都沒有特殊偏好。

③ 假設(shè)停車供應(yīng)用戶和停車需求用戶都嚴(yán)格遵守系統(tǒng)提交的時(shí)間信息。

④ 假設(shè)停車需求的用戶必須接受系統(tǒng)的分配結(jié)果。

⑤ 假設(shè)停車場(chǎng)和目的地之間的距離是用戶的步行距離。

⑥ 假設(shè)用戶會(huì)根據(jù)自己的實(shí)際需求如實(shí)向系統(tǒng)提交個(gè)人屬性信息。

將停車場(chǎng)統(tǒng)一分為2種:公共停車域和私人停車域。為了使表達(dá)更加清晰,用C={1,2,…,|C|}表示一組尋找車位的車輛,用S={1,2,…,|S|}表示一組停車區(qū)域,其中包含了公共停車域和私人停車域。每個(gè)停車域的總?cè)萘坑胵j表示,其中j∈S。表1是該共享停車模型的2個(gè)目標(biāo)類型。

表1 模型目標(biāo)Tab.1 Model objectives

對(duì)于車輛所有者來說,每一輛車i∈C在停車時(shí)都應(yīng)該考慮行程時(shí)間、搜索停車位所需時(shí)間、步行到達(dá)目的地所需時(shí)間、停車費(fèi)用以及個(gè)人停車偏好等因素[15],這些都是車主在進(jìn)行停車時(shí)需要關(guān)注的重要因素;對(duì)管理者來說,綜合停車?yán)寐适呛诵年P(guān)注點(diǎn),即停車成本和停車效益2個(gè)問題是研究的關(guān)鍵[16]。

2 模型建立與參數(shù)變量定義

2.1 停車分配中的成本問題

停車成本分為行程時(shí)間成本和停車費(fèi)用成本兩部分[17]。

① 行程時(shí)間成本問題:首先明確車輛i的起始位置、車輛i的目的地位置和目的地附近停車區(qū)域的位置,假設(shè)位置信息已知,用dhi和dti分別表示車輛i的起始位置和目的位置,目的附近每個(gè)停車區(qū)域j的位置用dj表示,所有位置在二維歐幾里德平面2上定義。每一輛車i的行程時(shí)間成本包含駕駛時(shí)間成本和步行時(shí)間成本,其中駕駛時(shí)間成本指到達(dá)停車區(qū)域j的時(shí)間成本,步行時(shí)間成本指從停車區(qū)域步行至目的地的時(shí)間成本?？傂谐虝r(shí)間成本定義為:

(1)

② 停車費(fèi)用成本問題:假設(shè)某個(gè)停車區(qū)域j單位時(shí)間內(nèi)的費(fèi)用為φj,則費(fèi)用成本sij可以表示為:

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

(2)

式中:γ表示費(fèi)用單位與時(shí)間單位統(tǒng)一起來的進(jìn)率權(quán)重,ti表示尋找停車位的車輛i的總停車時(shí)間;各區(qū)域單位費(fèi)用φj可以不一樣,但同區(qū)域的單位費(fèi)用一致。為符合競(jìng)爭(zhēng)意義,私人停車域的單位費(fèi)用小于公共停車域。即車輛i的到達(dá)目的地的停車總體成本可以表示為:

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

(3)

式中:θi是行程時(shí)間成本和費(fèi)用成本的權(quán)重參數(shù),且θi∈[0,1]。一般情況下,θi取值為0.5,表明行程時(shí)間成本和費(fèi)用成本在系統(tǒng)中的權(quán)重等價(jià)。這里定義一個(gè)總成本矩陣M=|C|×|S|,mij即為這個(gè)總成本矩陣?yán)锏拿總€(gè)元素。

2.2 停車分配中的效益問題

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

① 偏好問題:將用戶停車偏好定義為司機(jī)選擇某停車區(qū)域的概率Ri→j=P[i→j]。

② 安全問題:安全性為定性指標(biāo),用pj來表示每個(gè)區(qū)域指標(biāo)。如表2所示,對(duì)常見城市停車區(qū)域進(jìn)行量化安全性取值,值越大,越安全。

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

③ 綜合利用率:引入二進(jìn)制變量xij表示停車?yán)寐?

(4)

式中:xij值為1時(shí),表示車輛i分配區(qū)域j;xij值為0時(shí),表示未成功分配。t時(shí)刻區(qū)域j的已占用數(shù)量zj(t)可以表示為:

(5)

則t時(shí)刻區(qū)域j的利用率可以表示為:

(6)

式中:qj是區(qū)域j的總車位數(shù),記錄在行矩陣Q1×|S|中。相鄰兩區(qū)域同時(shí)刻的利用率差值為:

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

(7)

相鄰范圍Ω={S1,S2,…,|S|}內(nèi)同時(shí)刻所有區(qū)域的綜合平均利用率記為:

(8)

3 模型構(gòu)建

3.1 時(shí)空相關(guān)性

在停車分配模型構(gòu)建之前,先分析相鄰區(qū)域利用率的時(shí)間和空間特征。通過歷史數(shù)據(jù)分析研究相鄰區(qū)域時(shí)空相關(guān)性,作為目標(biāo)函數(shù)的約束條件之一。

相鄰區(qū)域利用率的時(shí)間特征用區(qū)域j在某時(shí)刻不同時(shí)間的利用率相關(guān)性表達(dá)。例如區(qū)域j在上午9:00和上午8:59、8:58、8:57…利用率時(shí)間相關(guān)性計(jì)算公式為:

時(shí)間相關(guān)性函數(shù)式(9)受多種因素影響,利用率在時(shí)滯情況下有強(qiáng)時(shí)間相關(guān)性。相鄰區(qū)域利用率空間特征以同一時(shí)刻不同區(qū)域利用率間相關(guān)性表達(dá)。通過歷史數(shù)據(jù)分析,某區(qū)域需求變化會(huì)對(duì)附近區(qū)域需求產(chǎn)生影響,空間相關(guān)性公式為:

s(t,d)=

(10)

式中:Ωd?{(ja,jb)|ja,jb∈S,distance(ja,jb)≤d}指距離小于d的多對(duì)區(qū)域集合,d=0.16、0.32 km…。

可以看出,除同地點(diǎn)利用率存在時(shí)間相關(guān)性外,相鄰區(qū)域在一定時(shí)間內(nèi)也存在空間相關(guān)性。

3.2 目標(biāo)函數(shù)與約束條件

本模型主要考慮成本和效益目標(biāo),分配策略總目標(biāo)是在成本最小化基礎(chǔ)上的多區(qū)域利用率最大化平衡,即最小化利用率差值,且最大化綜合利用率。

根據(jù)上述多目標(biāo)決策問題分析,首先將最小化成本的目標(biāo)函數(shù)定義為:

定義目標(biāo)函數(shù)F1為:

(11)

約束條件定義為:

(12)

式中:∑j∈Sxij=1表示車輛和區(qū)域的唯一化匹配,約束條件∑i∈Cxij≤qj表示區(qū)域分配量不大于總?cè)萘?約束條件xij={0,1}表示xij為二進(jìn)制變量,0或1表示i是否被分配到區(qū)域j?？芍陨鲜腔旌险麛?shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)問題,但大量的i和j數(shù)據(jù)會(huì)使求解難度增加。因此,將形成一個(gè)利用匹配理論優(yōu)化ADMM的分配算法,以適用巨量數(shù)據(jù)。

圖2為平衡成本和效益分配問題。

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

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

(13)

定義目標(biāo)函數(shù)F2為:

(14)

約束條件定義為:

(15)

為解決資源分配問題,首先放寬分配指標(biāo)xij,其次將xij轉(zhuǎn)化為[0,1]連續(xù)實(shí)變量,定義目標(biāo)函數(shù)F3為:

(16)

約束條件定義為:

(17)

3.3 車位分配模型算法與求解

3.3.1 算法設(shè)計(jì)

假設(shè)在起始時(shí)間點(diǎn)所有需求都能分配并滿足,則先構(gòu)建偏好模型,詳細(xì)算法流程如下。

算法1: 停車者的偏好1:初始化,輸入集合S={1,2,…,S}中所有停車區(qū)域j。2:根據(jù)式(3)計(jì)算每輛車i分配到停車區(qū)域j的停車成本,并按照停車成本的計(jì)算結(jié)果,將所有停車區(qū)域i按升序排序。3:將停車區(qū)域j的排序集合添加到車輛i的偏好集合,車輛i的偏好即為停車者的偏好。4:輸出停車者的偏好集合Γ(i),?i∈C。

從成本角度考慮,可得到偏好集合Γ(i),?i∈C。停車區(qū)域的資源分配偏好如算法2所示。

算法2: 停車區(qū)域的資源分配偏好1:初始化,輸入集合C={1,2,…,C}中所有車輛i。2:根據(jù)F2中的F=∑i∈C∑j∈Sδmijxij+∑j∈S(1-δ)ΔUj(t),按照計(jì)算結(jié)果,將所有車輛i按升序排序。3:判斷如果len(2中的排序列表) ≤qj,則將此排序列表中的所有車輛i添加到停車區(qū)域j的偏好集合中;否則,將此排序列表中最前面的qj個(gè)車輛添加到停車區(qū)域i的偏好集合中。4:輸出停車者的偏好集合Γ(j),?j∈S。

從利用率角度考慮,可得偏好集合Γ(j),?j∈S。本模型目標(biāo)為通過一種匹配博弈的方法找到一個(gè)穩(wěn)定的匹配方式,如算法3所示。

算法3: 共享停車匹配博弈1:輸入:Γ(i),Γ(j),H=[qj]1×S,?i∈C,j∈S。2:輸出:匹配系數(shù)μ。3:初始化:接受矩陣χ=[0]C×S,臨時(shí)拒絕列表=?。4:for i∈C do5: j←Γ(i)j,在Γ(i)中j是最優(yōu)先的。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是最優(yōu)先的。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表示停車區(qū)域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得到收斂穩(wěn)定的匹配系數(shù)μ所需的決策矩陣數(shù)量較大。在每次迭代過程中,由車輛個(gè)體根據(jù)偏好選擇區(qū)域后,區(qū)域選擇接受或者拒絕,使算法3在|C|×|S|范圍內(nèi)迭代收斂,得到趨于穩(wěn)定的匹配系數(shù)μ,|C|為停車數(shù)量,|S|為停車區(qū)域的數(shù)量。

3.3.2 ADMM模型求解

算法3中匹配理論結(jié)合MILP求解器可以有效解決問題F1,然而F1中沒有考慮效益問題,無法平衡資源分配。因此,綜合考慮所有因素,得到目標(biāo)函數(shù)F2,為了更好求解將其轉(zhuǎn)換為問題F3。問題F1是單變量?jī)?yōu)化問題,形如:

(18)

如式(18),定義其增廣拉格朗日函數(shù)為:

(19)

使用對(duì)偶上升法求解,即:

(20)

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

(21)

由于F3是一個(gè)耦合線性等式約束的凸問題,形如式(21)所示:

(22)

為高效解決問題F3,采用ADMM法,通過分布式計(jì)算方式求解。通過上述分析,定義問題F3增廣拉格朗日函數(shù)如下:

(23)

對(duì)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)

最后,綜合推導(dǎo)出變量為:

(30)

得到相鄰?fù)＼噮^(qū)域停車?yán)寐手?

(31)

在以上基礎(chǔ)上,基于ADMM優(yōu)化提出算法4,詳細(xì)步驟如圖3所示。

圖3 基于ADMM優(yōu)化的停車算法流程Fig.3 Flowchart of parking algorithm based on ADMM optimization

由圖3可以看出,算法4開始時(shí),初始化k=0、匹配控制變量x和拉格朗日乘子λ。然后通過收集到的數(shù)據(jù),根據(jù)式(23)～式(26)更新,并賦值k←k+1,不斷迭代,將收斂性作為判斷條件,通過梯度下降法證明其收斂性。

4 性能分析

通過模擬停車數(shù)據(jù),求解最優(yōu)δ值,比較不同權(quán)重因子δ對(duì)收斂性的影響,以及同情況不同算法的收斂特性。

4.1 仿真假設(shè)

假設(shè)半徑為1 000 m的4個(gè)停車區(qū)域,需求車輛為2 000輛,在Matlab 2018b上進(jìn)行仿真。首先對(duì)比不同權(quán)重因子成本和效益間變化,測(cè)得平衡點(diǎn);其次,固定權(quán)重因子δ,對(duì)比不同算法的收斂性;最后,以ADMM求解算法對(duì)比δ對(duì)算法收斂性的影響。

4.2 結(jié)果分析

通過仿真,得到如下結(jié)果,圖4為權(quán)重因子δ影響分析,圖5為ADMM、混合整數(shù)二階錐優(yōu)化(Mixed Integer Second-Order Cone Optimization,MSO)、增廣拉格朗日方法(Augmented Lagrangian Method,ALM)三種算法收斂性比較,圖6為不同權(quán)重因子δ收斂性對(duì)比,表3為性能對(duì)比分析。

圖4 權(quán)重因子δ影響Fig.4 Influence of weight factor δ

如圖4所示,隨著權(quán)重因子δ的增加而成本增大,而效益沒有變化?？煽闯?成本和效益在δ= 1.42×10-3的時(shí)候相交于點(diǎn)(0.142,4)。當(dāng)1.42×10-3<δ<1時(shí),社會(huì)效益低于個(gè)體成本;當(dāng)0<δ<1.42×10-3時(shí),社會(huì)效益高于個(gè)體成本;當(dāng)δ=1.42×10-3時(shí),二者相等,達(dá)到平衡。

如圖5所示,當(dāng)δ=1.42×10-3時(shí),對(duì)ADMM、MSO和ALM三種方法收斂性進(jìn)行比較。ALM法迭代20次達(dá)到最優(yōu),MSO法13次達(dá)到最優(yōu),ADMM法迭代8次達(dá)到最優(yōu)。ADMM法收斂性更好、運(yùn)算更快。

圖5 各算法收斂性對(duì)比Fig.5 Comparison of convergence of various algorithms

如圖6所示,在ADMM法下,雖然δ=1.42×10-2和δ=1.42×10-4時(shí)收斂速度快,但當(dāng)δ= 1.42×10-3時(shí),結(jié)果更優(yōu)。

圖6 不同權(quán)重因子δ收斂性對(duì)比Fig.6 Comparison of convergence of different weight factor δ

表3 性能對(duì)比Tab.3 Performance comparison

對(duì)實(shí)驗(yàn)數(shù)據(jù)總結(jié)可得,當(dāng)δ=1.42×10-3時(shí),采用ADMM優(yōu)化算法,模型收斂性最優(yōu),高于MSO算法9.18%,高于ALM算法15.94%。

5 結(jié)束語

本文從考慮成本和效益兩方面綜合構(gòu)建了停車位分配模型。從資源高效利用角度出發(fā),研究了多停車區(qū)域分配問題。提出了分配問題的主要目標(biāo):成本最低和需求最平衡,并通過構(gòu)造混合整數(shù)優(yōu)化問題來解決這2個(gè)目標(biāo)。研究了基于ADMM優(yōu)化的分配算法并論證了可行性,通過Matlab進(jìn)行仿真得出,在收斂性能上,對(duì)比得出ADMM優(yōu)化算法較MSO算法提高9.18%,較ALM算法提高15.94%,結(jié)果更接近最優(yōu)。