王震邦 宋運(yùn)忠

摘要： 為有效緩解大規(guī)模停車時(shí)的停車亂、停車難問題，圍繞停車費(fèi)用、排隊(duì)時(shí)間以及均衡多個(gè)停車場之間的停車需求，構(gòu)建兼顧多方利益凸優(yōu)化模型。首先，利用匹配博弈推導(dǎo)出最小化停車費(fèi)用的穩(wěn)定雙邊匹配；然后，同時(shí)考慮多方利益來擴(kuò)展研究，構(gòu)建的數(shù)學(xué)模型為凸優(yōu)化問題，使用交替方向乘子法（ADMM）分布式求解；最后，仿真結(jié)果表明基于ADMM分布式優(yōu)化模型與匹配博弈算法和貪心算法相比，可以滿足多方利益，從隱私保護(hù)、計(jì)算時(shí)間與數(shù)據(jù)傳遞量等方面分析驗(yàn)證了ADMM分布式優(yōu)化模型比集中式優(yōu)化模型更適用于大規(guī)模共享停車匹配，并分析驗(yàn)證了考慮多方利益的必要性與權(quán)重系數(shù)對(duì)計(jì)算結(jié)果的影響。

關(guān)鍵詞： 大規(guī)模停車匹配；多方利益；匹配博弈；交替方向乘子法

中圖分類號(hào)： TP273.1;U491.7文獻(xiàn)標(biāo)識(shí)碼： A

收稿日期： 2021-09-27；修回日期：2022-02-28

基金項(xiàng)目： 國家自然科學(xué)基金（61340041，61374079）;河南省自然科學(xué)基金（182300410112）

第一作者： 王震邦（1997-），男，河南鄭州人，碩士研究生，主要研究方向?yàn)閺?fù)雜系統(tǒng)建模與控制。

通信作者： 宋運(yùn)忠（1968-），男，河南民權(quán)人，博士，教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)的分析與控制。

A Massive Shared Parking Matching Optimization Strategy Considering the Interests of Multiple Parties

WANG Zhenbang， SONG Yunzhong

（School of Electrical Engineering and Automation， Henan Polytechnic University， Jiaozuo 454003， China）

Abstract：In order to effectively alleviate the problem of parking chaos and difficult parking during massive parking， this paper builds a convex optimization model that takes into account the interests of multiple parties， focusing on parking costs， queuing time and balancing the parking demand among multiple parking lots. First， a stable bilateral matching that minimizes parking fees is derived by using a matching game; then， the research is extended considering the interests of multiple parties at the same time， and the mathematical model constructed is a convex optimization problem， which is solved by the alternating direction multiplier method （ADMM） distributed solution. Finally， the simulation results show that the distributed optimization model based on ADMM can meet the interests of multiple parties compared with the matching game algorithm and the greedy algorithm. It is verified that the ADMM distributed optimization model is more efficient than the centralized optimization model from the aspects of privacy protection， computing time and data transfer volume. It is suitable for massive shared parking matching， and the necessity of considering the interests of multiple parties and the influence of weight coefficients on the calculation results are analyzed and verified.

Key words： massive parking matching; multi-party interests; matching game; alternating direction multiplier method

0 引言

據(jù)公安部統(tǒng)計(jì)，截止到2021年3月，中國機(jī)動(dòng)車保有量達(dá)3.7億輛。在人口密集的城市里找到停車位是個(gè)不小的挑戰(zhàn)。此外，30%的交通擁堵是由于停車巡游引起的，不僅會(huì)造成交通擁堵，而且會(huì)產(chǎn)生額外的燃油消耗與空氣污染［13］。

因此，學(xué)術(shù)界和工業(yè)界關(guān)于停車匹配問題的研究主要集中在如何將車輛匹配給最接近目的地的可用停車場，從而最大限度減少停車匹配的成本。譬如：Wu等［4］為自動(dòng)駕駛車輛尋找最短路徑，最小化停車成本；Kotb等［5］的目標(biāo)是同時(shí)提高停車資源利用率、增加停車場收入與減少停車成本。Xu等［6］利用最小化停車場到車輛目的地的最大距離，實(shí)現(xiàn)公平停車分配。以上的文獻(xiàn)都只解決了單個(gè)停車場的分配問題，忽視了多個(gè)停車場之間的潛在合作。盧凱等［7］在考慮司機(jī)個(gè)體對(duì)于步行距離與停車場收費(fèi)的心理意愿的前提下，實(shí)現(xiàn)了停車誘導(dǎo)系統(tǒng)虛擬總成本最小化；Lin等［8］旨在保證停車服務(wù)質(zhì)量的同時(shí)，最大化停車場的效益；Schlote等［9］提出了一種負(fù)載平衡算法來平衡多個(gè)停車場的需求；Kim等［10］利用分布式算法在均衡多個(gè)停車場之間停車需求的前提下，降低停車費(fèi)用。當(dāng)前工作暫無同時(shí)考慮多方停車?yán)娴难芯浚疚膶⒖紤]多方利益以使系統(tǒng)更高效。

目前，關(guān)于停車誘導(dǎo)系統(tǒng)的研究主要分為兩類：基于傳感器的方法和基于路邊單元（Road Side Units， RSUs）的方法。在基于傳感器的方法中［1112］，用戶必須把注意力分散給移動(dòng)設(shè)備，具有嚴(yán)重的交通隱患。基于RSUs的車載自組織網(wǎng)絡(luò)可以提高道路安全，并帶來更好的駕駛體驗(yàn)［1314］，但不同停車場之間的交流是由多個(gè)RSUs來共同完成的，則多個(gè)RSUs必須使用同步機(jī)制［15］，此機(jī)制成本較為昂貴。關(guān)于共享停車場的匹配策略，必須考慮所有可用資源。當(dāng)許多地區(qū)具有大規(guī)模的空閑車位時(shí)，以上方法就暴露了缺點(diǎn)。因此，本文提出了一種基于霧服務(wù)器和路邊云的停車誘導(dǎo)系統(tǒng)，低成本地、高效地進(jìn)行停車匹配。

本文針對(duì)大規(guī)模共享停車匹配問題，采用匹配博弈算法實(shí)現(xiàn)最小化停車費(fèi)用的穩(wěn)定雙邊匹配，采用交替方向乘子法（Alternating direction method of multipliers， ADMM）來實(shí)現(xiàn)多方利益。最后利用Matlab進(jìn)行仿真與分析，證明了所提方案的有效性與可行性，同時(shí)對(duì)比分析了集中式優(yōu)化算法、匹配博弈算法與貪心算法，證明了基于ADMM的算法的優(yōu)勢。

1 系統(tǒng)模型與模型構(gòu)建

1.1 系統(tǒng)組件及其原理

如圖1所示，在智能城市中，一個(gè)停車誘導(dǎo)系統(tǒng)可以控制多個(gè)共享停車場系統(tǒng)。

1）停車場與車輛：系統(tǒng)考慮大規(guī)模車輛與多個(gè)停車場的停車資源共享。停車場向霧服務(wù)器提供每個(gè)停車位的狀態(tài)（占用或空閑）。車輛包括共享汽車與私人車主。私人停車場與私人車主將被激勵(lì)參與有序停車，停車場與車主都將獲得經(jīng)濟(jì)利益。

2）霧服務(wù)器：扮演著停車場與RSUs之間信息交換的角色。通過WIFI和Zigbee等無線網(wǎng)絡(luò)收集全部停車位的狀態(tài)，將信息傳輸至RSUs。

3）RSUs：主要負(fù)責(zé)與車輛進(jìn)行交互，連接其通訊范圍內(nèi)車輛，向司機(jī)廣播停車位數(shù)據(jù)，為它們找到最佳停車位置。一方面，RSUs需要跟蹤有限的空閑車位，另一方面還需要優(yōu)化控制。因此，這部分可以充當(dāng)模型的控制中心。

4）路邊云：路邊云在RSUs之間起到中間層的作用，交換不同停車位的信息。由于RSUs的通信范圍有限，路邊云幫助兩個(gè)RSUs進(jìn)行信息交換。路邊云的存在，使司機(jī)可以隨時(shí)隨地向RSUs發(fā)送自己的停車需求。

1.2 構(gòu)建數(shù)學(xué)模型

1.2.1 模型假設(shè)

在模型構(gòu)建中，對(duì)停車匹配問題進(jìn)行適當(dāng)?shù)暮喕?，作以下假設(shè)：

1）假設(shè)有停車需求的車主對(duì)所有停車場與停車位都沒有特殊的偏好；

2）假設(shè)單個(gè)停車場的所有車位屬性與費(fèi)用相同，且僅考慮按照時(shí)長收費(fèi)；

3）假設(shè)停車場供應(yīng)商與車主都嚴(yán)格遵守系統(tǒng)規(guī)則與停車時(shí)間；

4）假設(shè)車輛的當(dāng)前位置、目的地位置以及停車場的位置都是二維歐幾里得空間，R2；

5）假設(shè)車主會(huì)根據(jù)實(shí)際需求提交相關(guān)屬性信息，且一定會(huì)接受匹配結(jié)果。

4 算例分析

本文在2 000 m×2 000 m的毗鄰區(qū)域，設(shè)計(jì)了一種網(wǎng)格式路網(wǎng)［9］。路網(wǎng)中隨機(jī)生成1 000輛平均行駛速度為40 km/h、停放時(shí)間服從平均值為2 h的指數(shù)分布的待匹配車輛，為保證實(shí)驗(yàn)結(jié)果具有代表性，將待匹配車輛的起點(diǎn)與目的地位置都隨機(jī)設(shè)置在區(qū)域中，停車場的位置也均勻分布在區(qū)域中，且數(shù)據(jù)均不同，如表3所示。為兼顧多方主體的目標(biāo)，權(quán)重系數(shù)δ1，δ2與δ3分別為5×10-4，1×10-4與1×10-4。

本文涉及的算法主要有：1）集中式優(yōu)化：本文調(diào)用GUROBI來獲得最優(yōu)解，考慮了系統(tǒng)的整體效率；2）ADMM分布式優(yōu)化：對(duì)式（18）進(jìn)行分布式求解，各子問題通過調(diào)用GUROBI求解器進(jìn)行求解，收斂精度為10-4；3）匹配博弈算法：考慮車主與停車場供應(yīng)商的偏好，得到一個(gè)穩(wěn)定雙邊匹配；4）貪心算法：為停車場就近匹配車輛，直到滿足其可服務(wù)車輛上限。本文的算例均在CPU為AMD Ryzen7 4 800H、主頻2.9 GHz、內(nèi)存為16G的計(jì)算機(jī)上采用MATLAB R2019a實(shí)現(xiàn)建模。

4.1 各算法的優(yōu)化結(jié)果性能對(duì)比

各算法的加權(quán)平均總成本比較如圖4所示，優(yōu)化結(jié)果對(duì)比數(shù)據(jù)如表4所示。

可以觀察到，由于集中式優(yōu)化是最優(yōu)結(jié)果，因此得到的總成本最低。ADMM分布式優(yōu)化的初始狀態(tài)與最優(yōu)結(jié)果的差距較大，然而，當(dāng)算法滿足收斂，ADMM分布式優(yōu)化得到了近似最優(yōu)解，計(jì)算結(jié)果基本吻合，說明在誤差允許的范圍內(nèi)，二者模型可以看作等價(jià)。間隙是由于松弛投影二進(jìn)制變量x產(chǎn)生的誤差，可忽略不計(jì)。因此ADMM分布式優(yōu)化優(yōu)于匹配博弈算法與貪心算法。匹配博弈算法降低車主停車費(fèi)用方面的性能較強(qiáng)，由于貪心算法為車輛匹配較近的停車場，最小化停車場排隊(duì)時(shí)間的性能較強(qiáng)。

4.2 模型可行性分析

分布式模型是否能夠應(yīng)用于工程實(shí)際應(yīng)用，取決于算法的收斂性能。圖5、圖6給出了分布式優(yōu)化下的殘差變化曲線，由于本文模型考慮兩個(gè)線性等式耦合，故存在兩組對(duì)偶更新。所有殘差均可以在迭代40次收斂，根據(jù)測試分析，每次子問題的迭代時(shí)間不超過0.5 s。在實(shí)際應(yīng)用中，通訊時(shí)延0.1 s后，可在30 s內(nèi)達(dá)到收斂。與此同時(shí)，與集中式優(yōu)化相比，ADMM分布式優(yōu)化對(duì)子問題的計(jì)算量和內(nèi)存占用量大大減小。通信數(shù)據(jù)僅包括分配策略、拉格朗日乘子等信息，通信負(fù)載很小，且不含任何私密信息，有利于保護(hù)用戶的隱私［20］。因此，本文的模型適合于未來大規(guī)模共享停車匹配。

4.3 單目標(biāo)與權(quán)重系數(shù)對(duì)計(jì)算結(jié)果的影響

為驗(yàn)證考慮多方利益的必要性，利用ADMM分布式優(yōu)化將本文模型與3種單目標(biāo)模型進(jìn)行對(duì)比。目標(biāo)1：本文模型；目標(biāo)2：僅考慮最小化車主的停車費(fèi)用；目標(biāo)3：僅考慮最小化停車場的排隊(duì)時(shí)間；目標(biāo)4：僅考慮均衡多個(gè)停車場的停車需求。表5列出了3種不同匹配目標(biāo)下的計(jì)算結(jié)果，考慮多方利益匹配方案的加權(quán)平均總成本最低。目標(biāo)2～4沒有兼顧到全局的利益，無法實(shí)現(xiàn)長久互利共贏。因此，考慮綜合效益的模型十分必要。

為分析權(quán)重系數(shù)對(duì)計(jì)算結(jié)果的影響，表6對(duì)比了7組不同權(quán)重系數(shù)的計(jì)算結(jié)果。各組中δ1的取值分別為5×10-3，5×10-4，5×10-4，0，5×10-4與5×10-4，δ2的取值分別為1×10-4，1×10-3，1×10-4，1×10-4，0與1×10-4，δ3的取值分別為1×10-4，1×10-4，1×10-3，1×10-4，1×10-4與0。觀察權(quán)重系數(shù)組1～3可知，過于偏重某一目標(biāo)對(duì)計(jì)算結(jié)果會(huì)造成一定的影響，不可避免地?fù)p害了其他目標(biāo)的利益；觀察權(quán)重系數(shù)組5～7可知，如若少考慮一方利益，將嚴(yán)重?fù)p害被忽略方的利益。因此，在實(shí)際應(yīng)用中，需合理地選擇權(quán)重系數(shù)，使得各目標(biāo)均衡。

5 結(jié)論

針對(duì)大規(guī)模共享停車匹配問題，為了有效利用資源，整合公共和私人停車場，目標(biāo)是在均衡多個(gè)停車場之間的停車需求的條件下，降低停車費(fèi)用與停車排隊(duì)時(shí)間。首先，基于匹配博弈得到最小化停車費(fèi)用穩(wěn)定雙邊匹配。然后，考慮多方利益構(gòu)造了一個(gè)凸優(yōu)化問題，利用ADMM算法進(jìn)行分布式優(yōu)化。仿真算例表明：匹配博弈算法可以更有效地降低停車費(fèi)用，滿足停車場與車輛的偏好的同時(shí)，得到穩(wěn)定雙邊匹配；ADMM分布式優(yōu)化同時(shí)均衡多個(gè)停車場之間的停車需求、降低停車費(fèi)用與排隊(duì)時(shí)間，且分布式優(yōu)化注重個(gè)體獨(dú)立性與隱私保護(hù)，更適合于大規(guī)模共享停車匹配問題的工程實(shí)際應(yīng)用。隨著道路上電動(dòng)汽車的劇增，車主、充電站和電網(wǎng)三方利益的充電問題將是未來研究的重點(diǎn)。

參考文獻(xiàn)：

［1］SHOUP D C. Cruising for parking［J］. Transport Policy， 2006， 13（6）： 479-486.

［2］KONG T R， XU S， CHENG M， et al. Iot-enabled parking space sharing and allocation mechanisms［J］. IEEE Transactions on Automation Science and Engineering， 2018， 15（4）： 1654-1664.

［3］BOCK F， MARTINO S D， ORIGLIA A. Smart parking： using a crowd of taxis to sense on-street parking space availability［J］. IEEE Transactions on Intelligent Transportation Systems， 2020， 21（2）： 496-508.

［4］WU M， JIANG H， TAN C A. Automated parking space allocation during transition with both human-operated and autonomous vehicles［J］. Applied Sciences， 2021， 11（2）： 855.

［5］KOTB A， SHEN Y， ZHU X， et al.IParker—a new smart car-parking system based on dynamic resource allocation and pricing［J］. IEEE Transactions on Intelligent Transportation Systems， 2016， 17（9）： 2637-2647.

［6］XU Y， ALFONSETTI E， Weeraddana P C， et al. A semidistributed approach for the feasible min-max fair agent-assignment problem with privacy guarantees［J］. IEEE Transactions on Control of Network Systems， 2016， 5（1）： 333-344.

［7］盧凱， 林茂偉， 鄧興棟， 等. 停車總成本最小的停車位動(dòng)態(tài)匹配與誘導(dǎo)模型［J］. 華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 46（9）： 82-91，98.

LU K， LIN M W， DENG X D， et al. A dynamic allocation and guidance model for parking spaces with minimum total parking costs［J］. Journal of South China University of Technology（Natural Science Edition） ， 2018， 46（9）： 82-91，98.

［8］LIN J， CHEN S Y， CHANG C Y， et al. SPA： smart parking algorithm based on driver behavior and parking traffic predictions［J］. IEEE Access， 2019， 7， 34275-34288.

［9］SCHLOTE A， KING C， CRISOSTOMI E， et al. Delay-tolerant stochastic algorithms for parking space assignment［J］. IEEE Transactions on Intelligent Transportation Systems， 2014， 15（5）： 1922-1935.

［10］ KIM O T T， TRAN N H，PHAM C， et al. Parking assignment： minimizing parking expenses and balancing parking demand among multiple parking lots［J］. IEEE Transactions on Automation Science and Engineering， 2020， 17（3）： 1320-1331.

［11］ 林小圍， 周晶， 盧珂. 私家車位共享系統(tǒng)的車位動(dòng)態(tài)預(yù)約與分配［J］. 系統(tǒng)工程理論與實(shí)踐， 2018， 38（11）： 189-199.

LIN X W， ZHOU J， LU K. Dynamic reservation and allocation in private parking slot sharing system［J］. Systems Engineering-Theory & Practice， 2018， 38（11）： 189-199.

［12］ GARRA R， MARTNEZ S， SEB F. A privacy-preserving pay-by-phone parking system［J］. IEEE Transactions on Vehicular Technology， 2017， 66（7）： 5697-5706.

［13］ LIU P， XU B， DAI G， et al. MDP： minimum delay hot-spot parking［J］. Journal of Network and Computer Applications， 2017， 87： 210-222.

［14］ LIU H， QIU T， ZHOU X， et al. Parking-area-assisted spider-web routing protocol for emergency data in urbanVANET［J］. IEEE Transactions on Vehicular Technology， 2020， 69（1）： 971-982.

［15］ LU R， LIN X， ZHU H， et al. Spark： a new VANET-based smart parking scheme for large parking lots［C］// Rio de Janeiro， Brazil： IEEE Infocom， 2009，2009.

［16］ GALED， SHAPLEY L S. College admissions and the stability of marriage［J］. American Mathematical Monthly， 1962， 69（1）： 9-15.

［17］ ROTH A E. Deferred acceptance algorithms： history， theory， practice， and openquestions［J］. International Journal of Game Theory， 2008， 36（3）： 537-569.

［18］ 李偉鋼， 唐朝生， Antonio C de A Junior， 等. 航空交通協(xié)同決策方法研究［J］. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2015， 12（2）： 46-52.

LI W G， TANG C S， ANTONIO C DE A J， et al. A study on collaborative decision making in air transportation［J］. Complex Systems and Complexity Science， 2015， 12（2）： 46-52.

［19］ BOYD S， PARIKH N， CHU E， et al. Distributed optimization and statistical learning via the alternating direction method of multipliers［J］. Foundations & Trends in Machine Learning， 2010， 3（1）： 1-122.

［20］ 潘振寧， 余濤， 王克英. 考慮多方主體利益的大規(guī)模電動(dòng)汽車分布式實(shí)時(shí)協(xié)同優(yōu)化［J］. 中國電機(jī)工程學(xué)報(bào)， 2019， 39（12）： 3528-3541.

PAN Z N，YU T，WANG K Y. Decentralized coordinated dispatch for real-time optimization of massive electric vehicles considering various interests［J］. Proceedings of the CSEE， 2019， 39（12）： 3528-3541.

（責(zé)任編輯 李 進(jìn)）