共享車位服務網絡動態停放調度算法與仿真研究

閔慧

摘 要：城市停車難問題越來越嚴重。將可共享停車位資源合理調度，有利用緩解城市交通問題。研究了一種優化調度算法，以提升共享車位動態調度效率，縮短車輛與車位匹配停放后的周轉作業時間，使車位空閑間隔時間更小。以每個停車請求的目的地區域中心點作為標記點，將周邊可用于服務的車位網點建立停車服務網絡，并據此建立多車位網點停放調度服務模型。基于102組實例數據，運用系統仿真技術，將模型優化運算出的調度方案與不經過模型優化的調度方案進行對比分析，驗證了模型的可靠性和適配性。

關鍵詞：共享車位；動態調度；停車服務網絡；周轉作業；系統仿真

DOI：10.11907/rjdk.171215

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2017）009-0090-05

Abstract：Parking problems for the city has become very difficult to solve， and how to use the sharing parking resource of the city reasonably seems significant. In this paper， an optimal scheduling algorithm was proposed to improve the overall efficiency of the dynamic scheduling for parking in a macro level. The algorithm can reduce the overall job turnaround time that vehicle will take to go to the match parking spaces greatly， it also can small the idle interval of the parking spaces， at the same time， make the using of parking spaces more rational and effective. In this paper， the center of each parking request destination area was the mark point which can be used by the parking spaces surrounding to establish a parking service network， and accordingly the establishment of multi-parking spaces outlets of scheduling service model. Finally， based on 102 kinds of instance data， the use of system simulation model to optimize the operation of the scheme and scheduling model without optimization of stochastic simulation scheduling scheme sets out a comparative analysis， in order to verify the reliability and suitability of model.

Key Words：sharing parking spaces； dynamic dispatching； parking service network； recycling work； system simulation

0 引言

隨著社會經濟水平的提高，機動車保有量和停車位需求不斷增加，而與之相適應的城市交通規劃和停車位建設發展卻相對緩慢，極大制約了人們的交通出行，快速準確地為車輛找到合適的車位停靠網點成為保證城市交通靜態平衡的關鍵[1-2]。對司機而言，其目的地區域附近的停車位服務網點構成了其停放車輛的目的地停車服務網絡。對于負責調度分配的系統而言，需要考慮并分配每輛車停放在哪個車位網點以及具體到達時間，從而達到整體停放車輛效率最優化。實際場景中，構成停車服務網絡的各個停車網點分布在二維平面上，本文所述的停車服務網絡面向車主用戶并以車主目的地為服務散射中心，可以根據車位網點的位置與目的地距離的遠近，以及車位網點停放車輛服務能力，將其抽象成如圖1所示的停車服務能力分布網絡。

學者對停車需求預測方法進行了大量研究，主要包括停車生成率模型、用地與交通影響分析模型、出行吸引模型、交通量-停車需求模型及多元回歸模型等[3-5]。文獻[6]在停車生成率模型基礎上考慮價格因素、服務水平等對停車需求量的影響，提出“停車需求-供應模型”。文獻[7]考慮不同用地泊位共享對停車需求總量的折減對停車生成率模型進行優化。文獻[8]采用交通影響函數分析了路網流量增長率和停車率對停車需求的影響，在此基礎上建立了停車需求預測模型。文獻[9]針對現有模型在停車預測時存在的不足，綜合考慮新城區CBD 區域用地特征及交通特性，根據出行吸引強度及交通方式劃分，構建適用于新城區CBD 區域的停車需求預測模型。雖然現有的停車需求預測方法取得了很多研究成果，但由于受到城市規劃動態變化和車輛停放時間不固定等因素影響，已有的預測模型在使用時可行性受到限制，預測結果的可靠性難以保證。為此，本文提出一種改進的共享車位服務網絡動態停放調度算法，并通過實例數據驗證該算法的有效性。

1 目的地停車服務網絡車位動態調度模型

1.1 相關符號定義

為了便于描述，首先給出文中相關定義及含義：endprint

xi：第i輛車停放地點距目的地標點的位置距離（m），i∈S，xi∈M；

ti：第i輛車到達車位網點的停放時刻（小時：分），i∈S，ti∈R+；

P：車輛接受停放服務的順序集合，P={1，2，…，s}；

L：車位網點網絡等價的服務流線長度（m）；

li： 第i輛車類型，i∈S；

Ci：第i輛停放車輛的預計停放時長，i∈S；

ai：第i輛車到達目的地標點的預計時刻（小時：分），i∈S；

di：第i輛車離開目的地標點的預計時刻（小時：分），i∈S；

M：車位網點與目的地標點距離集合（m），M={m|m∈[0，L]∩RB）}；

Q： 車位網點集合，Q={1，2，…，q}，q=|Q|；

S： 待服務停放車輛集合，S={1，2，…，s}，s=|S|；

qmaxi，jj：時間窗下第i輛車最多可得的車位網點數，使第i輛車在調度時優先遵循相鄰規則，i∈S，j∈P；

qi，jj：時間窗下第i輛車可用于調度的車位網點數，i∈S，j∈P；

Tjj：時間窗的時間，為第j順序停放車輛與第j+1順序停放車輛間的間隔時間（分鐘），j∈P；

Qmaxi：第i輛車最多可接受的車位網點數目，i∈S；

Qmini：第i輛車最少可接受的車位網點數目，i∈S；

ti，ci，1：車位網點對停放時長為Ci的第i輛車的周轉服務作業時間（分鐘），ti，ci，1=Ci/η，η為車位網點的車位利用率，i∈S；

ti，xi，ti：時刻ti第i輛車在車位網點的周轉停放時間（小時），i∈S；

Zi，xi，ti：時刻ti第i輛車在車位網點停放，為1；否則，為0；i∈S；

Yi，jj：時間窗下第i輛車停放服務，為1；否則，為0；i∈S，j∈P。

1.2 問題建模

目的地停車服務網絡車位網點動態調度模型可描述為：首先根據xi將前往目的地標點所屬區域的車輛停放服務請求分配到具體的車位服務網點，然后根據ti為車輛安排停放服務次序并按停放次序編排動態時間窗，在各時間窗內為待停放車輛的服務請求動態分配區域內車位網點對應的決策支點，并保證該時間窗內所有停放車輛分配的車位網點總數不能大于區域內車位網點總數q，且停放車輛所分配的車位網點總數不能大于其最大可接受的車位網點數Qmaxi，分配的車位網點數應盡量保證車輛在預期離開車位網點時間di內離開車位網點，最后使目的地所在區域所有車輛在車位網點的停放周轉時間之和最小。

公式（1）為優化目標，要求所有車輛在車位網點的總計前往停放周轉時間之和最小：min∑si=1|ti，xiti+ti-ai|+

2 調度算法

車位實時動態共享的運行模式決定了司機用戶在接受停車服務前務必提前預約（即便是實時預定下單也意味著提前預約，因為下單與到達車位網點之間的最小時間窗一定大于0），預約時間越早意味在系統調度鏈條中越靠前，被排隊服務的概率越大。系統設定的輪詢檢測時間戳間隔可自定義，系統并行地計算出每個車位服務點的決策支持方案，考慮不同停放時間長短從而進行統籌調度。對于位于決策周期邊際閾值點的用戶，系統在進行調度配置停放方案時，在不影響排隊的待服務對象停放條件下，進行排隊命令穿插，否則將其預定需求自動排至下一次決策判斷周期進行配置。

根據以上規則確定車輛i的Qmaxi和 Qmini，則停放車輛的具體車位網點分配和其前往停放周轉作業時間確定如下：

（1）為停放車輛i分配Qmini車位服務網點，目的地停放區域隨機獲取相鄰Qmini車位服務網點，確定車輛i的到達順序為pi∈P，當前時間窗為pi，設中間變量C′i=C，k=0，T=0。

（2）如果車輛i的預計到達時刻不大于期望離開時刻，即（ti+ti，Ci，1/Qmint）≤di，車輛i的前往停放周轉作業時間為ti，xi，ti=ti，Ci，1/Qmini；否則，轉步驟（3）。

（3） k=k+1，當前時間窗pi內能夠分配給車輛i作為候選的車位網點數為qi，pi=min{（Qmini+k），qmaxi，pi，Qmaxi}，目的地停放區域隨機獲取相鄰qi，pi車位網點， 轉步驟（4）。

（4）如果車輛i的預期離開時刻不大于期望離開時刻（ti+ti，Ci，1/qi，pi）≤di，車輛 i 的作業時間為ti，xi，ti=ti，Ci1/qi，pi；如果車輛 i 的預期離開時刻大于其期望離開時刻，即（ti+ti，Ci，1/qi，pi）≤di，且車輛 i 當前可得最大車位網點數qmaxi，pi和允許的最大車位網點數Qmaxi的最小值大于當前分配車位網點數，即（Qmini+k）

（5）將pi時間窗的初始時刻計入到Tpi，令T=T+Tpi，如果當前pi時間窗內沒有完成車位 i 的作業C′i-Tpi·qi，pi/（ti，Ci，1/Ci）>0，則剩余作業時間為C′i=C′i-Tpi·qi，pi/（ti，Ci，1/Ci），轉步驟（6）；否則pi時間窗內分配給車輛 i 的車位網點數為qi，pi=min{qmaxi，pi，Qmaxi}，車輛 i的作業時間為ti，Ci，1=T-Tpi+Ci·（ti，Ci，1/Ci）/qi，pi。

（6）進入下一個時間窗即pi=pi+1進行車位網點分配，車輛 i 在當前時間窗 pi 下分配的車位網點數為qi，pi=min{qmaxi，pi，Qmaxi}，如果車輛i 的預期離開時刻不大于期望離開時刻，即[ti+T+C′i·（ti，Ci，1/Ci）/qi，pi]≤di，則車輛i前往停放周轉作業時間為ti，xi，ti=T+C′i·（ti，Ci，1/Ci）/qi，pi；否則，轉步驟（5）。

3 仿真實驗

將本文算法模型用Python語言封裝成一個模型訓練庫，并通過總計102次差異性較大的實例數據序列測試模型的優化性能，圖2列出了總周轉作業時間這一指標項的優化后，每輛車的平均周轉作業時間結果與原始隨機模擬調度結果平均值的對比擬合曲線。

本文以車位服務能力比較緊張的第23組實例數據序列中南方向的車輛和車位網點數據信息為例（車位網絡服務能力越緊張越能測試出模型的適配性能），列出具體的相關仿真過程和對比結果。第23組實例數據序列中，南方方向車輛信息如表1所示。

根據上述數據，采用MATLAB結合Python封裝好的模型訓練庫，模擬車輛向目的區域的自然遷移過程，如圖3所示。

第23組實例數據序列中，南方方向的車位網點數據信息如表2所示。

根據表2的數據，用MATLAB結合Python封裝好的模型訓練庫，模擬車位網點停車服務網絡在目的地區域的停放服務能力分布，如圖4所示。

為了驗證上述模型的優化效果，用Python封裝好的模型訓練庫隨機模擬車位的匹配停放，模擬運算10次的隨機調度結果與本文模型調度優化效果進行對比分析，結果見圖5。

從圖5曲線關系可以看出，本文所提模型優化后的停放作業周轉時間與不經過優化隨機產生的調度方案所耗費的停放作業周轉時間相比處于低耗損值，這意味著本文提出的調度優化模型取得了較好的優化效果，在車位網點的實時調度中耗損成本最小，所有待服務車輛均得到了合理停放。

4 結語

本文提出了以建立每個停放請求目的地中心為標點、搜索周邊可用于服務的車位網點構成停車服務網絡的理念，并據此建立了多車位網點停放調度服務模型，將車輛的停放需求在停車服務網絡上遍歷搜索，使到達該區域的車輛從整體上滿足車輛停放的同時最快停放，從而得到整體上最優化的停放調度方案。本文基于實例數據，借助系統仿真手段，將模型優化后運算出的調度方案與不經過模型優化的隨機模擬出的若干組調度方案進行對比分析，結果顯示經過模型優化后的調度方案，在保證車輛整體滿足停放需求條件下所消耗的停放周轉作業時間大幅減少，證明該動態調度模型優化效果很好。

參考文獻：

[1] LEVY N， RENDER M， BENENSON I. Spatially explicit modeling of parking search as a tool for urban parking facilities and policy assessment [J]. Transport Policy，2015，39（11）：9-20.

[2] WU E H K， SAHOO J， LIU C Y， et al. Agile urban parking recommendation service for intelligent vehicular guiding system [J]. IEEE Intelligent Transportation Systems Magazine，2014，6（1）：35-49.

[3] LEVY N， BENENSON I. GIS-based method for assessing city parking patterns[J]. Journal of Transport Geography，2015，46（3）：220-231.

[4] TASSERON G， MARTENS K， VAN DER HEIJDEN R. The potential impact of vehicle-to-vehicle and sensor-to-vehicle communication in urban parking[J]. IEEE Intelligent Transportation Systems Magazine， 2015，7（2）：22-33.

[5] ZHANG W， GUHATHAKURTA S， FANG J， et al. Exploring the impact of shared autonomous vehicles on urban parking demand： an agent-based simulation approach[J]. Sustainable Cities and Society，2015，19（5）：34-45.

[6] 關宏志，王鑫，王雪.停車需求預測方法研究[J].北京工業大學學報，2012，32（7）：600-604.

[7] 薛行健，歐心泉，晏克非.基于泊位共享的新城區停車需求預測[J].城市交通，2010，11（5）： 2-56.

[8] 王豐元，鄒旭東，閻巖，等.基于用地和交通特征的停車需求預測模型[J].交通運輸工程學報，2010，7（2）：84-88.

[9] 張飛飛，吳兵，李林波.新城區CBD區域停車需求預測方法[J].重慶交通大學學報：自然科學版，2012，31（5）：1018-1022.

（責任編輯：杜能鋼）endprint