閔慧

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

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

DOI：10.11907/rjdk.171215

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

隨著社會(huì)經(jīng)濟(jì)水平的提高，機(jī)動(dòng)車保有量和停車位需求不斷增加，而與之相適應(yīng)的城市交通規(guī)劃和停車位建設(shè)發(fā)展卻相對(duì)緩慢，極大制約了人們的交通出行，快速準(zhǔn)確地為車輛找到合適的車位停靠網(wǎng)點(diǎn)成為保證城市交通靜態(tài)平衡的關(guān)鍵[1-2]。對(duì)司機(jī)而言，其目的地區(qū)域附近的停車位服務(wù)網(wǎng)點(diǎn)構(gòu)成了其停放車輛的目的地停車服務(wù)網(wǎng)絡(luò)。對(duì)于負(fù)責(zé)調(diào)度分配的系統(tǒng)而言，需要考慮并分配每輛車停放在哪個(gè)車位網(wǎng)點(diǎn)以及具體到達(dá)時(shí)間，從而達(dá)到整體停放車輛效率最優(yōu)化。實(shí)際場(chǎng)景中，構(gòu)成停車服務(wù)網(wǎng)絡(luò)的各個(gè)停車網(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é)者對(duì)停車需求預(yù)測(cè)方法進(jìn)行了大量研究，主要包括停車生成率模型、用地與交通影響分析模型、出行吸引模型、交通量-停車需求模型及多元回歸模型等[3-5]。文獻(xiàn)[6]在停車生成率模型基礎(chǔ)上考慮價(jià)格因素、服務(wù)水平等對(duì)停車需求量的影響，提出“停車需求-供應(yīng)模型”。文獻(xiàn)[7]考慮不同用地泊位共享對(duì)停車需求總量的折減對(duì)停車生成率模型進(jìn)行優(yōu)化。文獻(xiàn)[8]采用交通影響函數(shù)分析了路網(wǎng)流量增長(zhǎng)率和停車率對(duì)停車需求的影響，在此基礎(chǔ)上建立了停車需求預(yù)測(cè)模型。文獻(xiàn)[9]針對(duì)現(xiàn)有模型在停車預(yù)測(cè)時(shí)存在的不足，綜合考慮新城區(qū)CBD 區(qū)域用地特征及交通特性，根據(jù)出行吸引強(qiáng)度及交通方式劃分，構(gòu)建適用于新城區(qū)CBD 區(qū)域的停車需求預(yù)測(cè)模型。雖然現(xiàn)有的停車需求預(yù)測(cè)方法取得了很多研究成果，但由于受到城市規(guī)劃動(dòng)態(tài)變化和車輛停放時(shí)間不固定等因素影響，已有的預(yù)測(cè)模型在使用時(shí)可行性受到限制，預(yù)測(cè)結(jié)果的可靠性難以保證。為此，本文提出一種改進(jìn)的共享車位服務(wù)網(wǎng)絡(luò)動(dòng)態(tài)停放調(diào)度算法，并通過(guò)實(shí)例數(shù)據(jù)驗(yàn)證該算法的有效性。

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

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

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

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

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

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

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

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

Ci：第i輛停放車輛的預(yù)計(jì)停放時(shí)長(zhǎng)，i∈S；

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

di：第i輛車離開(kāi)目的地標(biāo)點(diǎn)的預(yù)計(jì)時(shí)刻（小時(shí)：分），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：時(shí)間窗下第i輛車最多可得的車位網(wǎng)點(diǎn)數(shù)，使第i輛車在調(diào)度時(shí)優(yōu)先遵循相鄰規(guī)則，i∈S，j∈P；

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

Tjj：時(shí)間窗的時(shí)間，為第j順序停放車輛與第j+1順序停放車輛間的間隔時(shí)間（分鐘），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)對(duì)停放時(shí)長(zhǎng)為Ci的第i輛車的周轉(zhuǎn)服務(wù)作業(yè)時(shí)間（分鐘），ti，ci，1=Ci/η，η為車位網(wǎng)點(diǎn)的車位利用率，i∈S；

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

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

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

1.2 問(wèn)題建模

目的地停車服務(wù)網(wǎng)絡(luò)車位網(wǎng)點(diǎn)動(dòng)態(tài)調(diào)度模型可描述為：首先根據(jù)xi將前往目的地標(biāo)點(diǎn)所屬區(qū)域的車輛停放服務(wù)請(qǐng)求分配到具體的車位服務(wù)網(wǎng)點(diǎn)，然后根據(jù)ti為車輛安排停放服務(wù)次序并按停放次序編排動(dòng)態(tài)時(shí)間窗，在各時(shí)間窗內(nèi)為待停放車輛的服務(wù)請(qǐng)求動(dòng)態(tài)分配區(qū)域內(nèi)車位網(wǎng)點(diǎn)對(duì)應(yīng)的決策支點(diǎn)，并保證該時(shí)間窗內(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ù)期離開(kāi)車位網(wǎng)點(diǎn)時(shí)間di內(nèi)離開(kāi)車位網(wǎng)點(diǎn)，最后使目的地所在區(qū)域所有車輛在車位網(wǎng)點(diǎn)的停放周轉(zhuǎn)時(shí)間之和最小。

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

2 調(diào)度算法

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

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

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

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

（3） k=k+1，當(dāng)前時(shí)間窗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ù)期離開(kāi)時(shí)刻不大于期望離開(kāi)時(shí)刻（ti+ti，Ci，1/qi，pi）≤di，車輛 i 的作業(yè)時(shí)間為ti，xi，ti=ti，Ci1/qi，pi；如果車輛 i 的預(yù)期離開(kāi)時(shí)刻大于其期望離開(kāi)時(shí)刻，即（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時(shí)間窗的初始時(shí)刻計(jì)入到Tpi，令T=T+Tpi，如果當(dāng)前pi時(shí)間窗內(nèi)沒(méi)有完成車位 i 的作業(yè)C′i-Tpi·qi，pi/（ti，Ci，1/Ci）>0，則剩余作業(yè)時(shí)間為C′i=C′i-Tpi·qi，pi/（ti，Ci，1/Ci），轉(zhuǎn)步驟（6）；否則pi時(shí)間窗內(nèi)分配給車輛 i 的車位網(wǎng)點(diǎn)數(shù)為qi，pi=min{qmaxi，pi，Qmaxi}，車輛 i的作業(yè)時(shí)間為ti，Ci，1=T-Tpi+Ci·（ti，Ci，1/Ci）/qi，pi。

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

本文提出了以建立每個(gè)停放請(qǐng)求目的地中心為標(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ū)域的車輛從整體上滿足車輛停放的同時(shí)最快停放，從而得到整體上最優(yōu)化的停放調(diào)度方案。本文基于實(shí)例數(shù)據(jù)，借助系統(tǒng)仿真手段，將模型優(yōu)化后運(yùn)算出的調(diào)度方案與不經(jīng)過(guò)模型優(yōu)化的隨機(jī)模擬出的若干組調(diào)度方案進(jìn)行對(duì)比分析，結(jié)果顯示經(jīng)過(guò)模型優(yōu)化后的調(diào)度方案，在保證車輛整體滿足停放需求條件下所消耗的停放周轉(zhuǎn)作業(yè)時(shí)間大幅減少，證明該動(dòng)態(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ù)測(cè)方法研究[J].北京工業(yè)大學(xué)學(xué)報(bào)，2012，32（7）：600-604.

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

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

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

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