共享車位服務(wù)網(wǎng)絡(luò)動態(tài)停放調(diào)度算法與仿真研究

閔慧

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

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

DOI：10.11907/rjdk.171215

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

1.1 相關(guān)符號定義

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

xi：第i輛車停放地點(diǎn)距目的地標(biāo)點(diǎn)的位置距離（m），i∈S，xi∈M；

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

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

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

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

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

ai：第i輛車到達(dá)目的地標(biāo)點(diǎn)的預(yù)計時刻（小時：分），i∈S；

di：第i輛車離開目的地標(biāo)點(diǎn)的預(yù)計時刻（小時：分），i∈S；

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

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

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

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

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

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

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

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

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

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

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

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

1.2 問題建模

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

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

2 調(diào)度算法

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

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

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

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

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

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

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

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

3 仿真實(shí)驗

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

[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] 關(guān)宏志，王鑫，王雪.停車需求預(yù)測方法研究[J].北京工業(yè)大學(xué)學(xué)報，2012，32（7）：600-604.

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

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

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

（責(zé)任編輯：杜能鋼）endprint