考慮多方利益的大規(guī)模共享停車匹配優(yōu)化策略

王震邦 宋運忠

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

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

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

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

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

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

通信作者： 宋運忠（1968-），男，河南民權(quá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)計，截止到2021年3月，中國機動車保有量達(dá)3.7億輛。在人口密集的城市里找到停車位是個不小的挑戰(zhàn)。此外，30%的交通擁堵是由于停車巡游引起的，不僅會造成交通擁堵，而且會產(chǎn)生額外的燃油消耗與空氣污染［13］。

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

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

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

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

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

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

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

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

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

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

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

1.2.1 模型假設(shè)

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

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

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

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

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

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

4 算例分析

本文在2 000 m×2 000 m的毗鄰區(qū)域，設(shè)計了一種網(wǎng)格式路網(wǎng)［9］。路網(wǎng)中隨機生成1 000輛平均行駛速度為40 km/h、停放時間服從平均值為2 h的指數(shù)分布的待匹配車輛，為保證實驗結(jié)果具有代表性，將待匹配車輛的起點與目的地位置都隨機設(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)化：對式（18）進(jìn)行分布式求解，各子問題通過調(diào)用GUROBI求解器進(jìn)行求解，收斂精度為10-4；3）匹配博弈算法：考慮車主與停車場供應(yīng)商的偏好，得到一個穩(wěn)定雙邊匹配；4）貪心算法：為停車場就近匹配車輛，直到滿足其可服務(wù)車輛上限。本文的算例均在CPU為AMD Ryzen7 4 800H、主頻2.9 GHz、內(nèi)存為16G的計算機上采用MATLAB R2019a實現(xiàn)建模。

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

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

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

4.2 模型可行性分析

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

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

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

為分析權(quán)重系數(shù)對計算結(jié)果的影響，表6對比了7組不同權(quán)重系數(shù)的計算結(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)對計算結(jié)果會造成一定的影響，不可避免地?fù)p害了其他目標(biāo)的利益；觀察權(quán)重系數(shù)組5～7可知，如若少考慮一方利益，將嚴(yán)重?fù)p害被忽略方的利益。因此，在實際應(yīng)用中，需合理地選擇權(quán)重系數(shù)，使得各目標(biāo)均衡。

5 結(jié)論

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

參考文獻(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］盧凱， 林茂偉， 鄧興棟， 等. 停車總成本最小的停車位動態(tài)匹配與誘導(dǎo)模型［J］. 華南理工大學(xué)學(xué)報（自然科學(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)的車位動態(tài)預(yù)約與分配［J］. 系統(tǒng)工程理論與實踐， 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ī)模電動汽車分布式實時協(xié)同優(yōu)化［J］. 中國電機工程學(xué)報， 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)）