閔慧

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

關鍵詞：共享車位；動態(tài)調度；停車服務網(wǎng)絡；周轉作業(yè)；系統(tǒng)仿真

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 引言

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

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

1 目的地停車服務網(wǎng)絡車位動態(tài)調度模型

1.1 相關符號定義

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

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

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

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

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

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

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

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

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

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

Q： 車位網(wǎng)點集合，Q={1，2，…，q}，q=|Q|；

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

qmaxi，jj：時間窗下第i輛車最多可得的車位網(wǎng)點數(shù)，使第i輛車在調度時優(yōu)先遵循相鄰規(guī)則，i∈S，j∈P；

qi，jj：時間窗下第i輛車可用于調度的車位網(wǎng)點數(shù)，i∈S，j∈P；

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

Qmaxi：第i輛車最多可接受的車位網(wǎng)點數(shù)目，i∈S；

Qmini：第i輛車最少可接受的車位網(wǎng)點數(shù)目，i∈S；

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

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

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

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

1.2 問題建模

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

公式（1）為優(yōu)化目標，要求所有車輛在車位網(wǎng)點的總計前往停放周轉時間之和最?。簃in∑si=1|ti，xiti+ti-ai|+

2 調度算法

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

根據(jù)以上規(guī)則確定車輛i的Qmaxi和 Qmini，則停放車輛的具體車位網(wǎng)點分配和其前往停放周轉作業(yè)時間確定如下：

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

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

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

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

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

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

3 仿真實驗

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

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

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

第23組實例數(shù)據(jù)序列中，南方方向的車位網(wǎng)點數(shù)據(jù)信息如表2所示。

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

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

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

4 結語

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

參考文獻：

[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].北京工業(yè)大學學報，2012，32（7）：600-604.

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

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

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

（責任編輯：杜能鋼）endprint