基于馬爾科夫鏈的停車尋位模型與仿真

田 瓊，楊 麗，羅 婷

（北京航空航天大學 經濟管理學院，北京100191）

基于馬爾科夫鏈的停車尋位模型與仿真

田 瓊*，楊 麗，羅 婷

（北京航空航天大學 經濟管理學院，北京100191）

本文在經典的環(huán)形城市模型上，基于馬爾科夫鏈建立解析的路邊停車尋位模型.分別從系統(tǒng)和駕駛者兩個角度，對尋位競爭隊列進行描述，依據(jù)其馬爾科夫特性，推導出停車尋位距離概率密度函數(shù)，發(fā)現(xiàn)傳統(tǒng)的二項分布假設不能反映尋位車輛間的競爭車位行為，揭示了尋位車輛間的競爭是已有理論低估了停車難的原因之一.在數(shù)理分析基礎上，提出環(huán)形城市路邊停車仿真模型及算法，仿真結果驗證了理論模型的結論，并發(fā)現(xiàn)車位被連續(xù)占用也是低估停車難問題的另一個主要原因.研究結果有助于加深對路邊停車行為的認識，為制定相關車輛停車政策提供依據(jù).

城市交通；路邊停車；馬爾科夫鏈；尋位行為；環(huán)型城市

1 引 言

停車的混亂無序，增加了停車成本，也加劇了城市中心區(qū)的交通擁堵，路邊停車問題在交通系統(tǒng)中扮演著越來越重要的角色[1].據(jù)北京市政府披露，截至2013年底，北京機動車保有量已超540萬輛，而政府公布的正規(guī)停車位僅有276萬個，北京市實際非正規(guī)停車比例超過80%.

上世紀中期，Vickrey[2]對路邊停車問題進行了早期研究，認為停車應該同其他商品一樣，按照它的邊際社會成本定價.沿著他的思路，國內外學者對路邊停車定價及對周邊交通的影響進行了廣泛的研究[3-6]，他們的共同觀點認為由于路邊停車引發(fā)的車輛尋位是資源配置無效率的，應該通過提高路邊停車收費來消除.但是由于系統(tǒng)的隨機特性，路邊尋位很難徹底消除.實際應用中，Shoup就建議路內停車收費應該使得平均車位占有率維持在85%的水平[7].

在上述理論研究中，往往把停車尋位過程假設為以車位空置率為成功概率的二項分布.近期，Levy等的仿真研究也在建立車輛巡游模型時特別關注了車位占有率與車輛巡游數(shù)量間的非線性關系[8]，發(fā)現(xiàn)以往對停車尋位采用二項分布存在偏差，低估了停車尋位的困難度.但是Levy等的工作是建立在格子網絡模型上的，很難解析分析.

本文基于馬爾科夫鏈，解析地推導得到了停車尋位距離概率密度函數(shù)，發(fā)現(xiàn)以往對停車時尋位概率采用二項分布的確存在理論偏差.之后提出了仿真模型及算法，分析了車位占有率變化規(guī)律及停車尋位距離概率分布函數(shù)的理論結果與仿真結果的差異，發(fā)現(xiàn)尋位駕車者之間的競爭行為和路邊連續(xù)成段的車位被占用是增加停車尋位難度的兩個重要因素.本文對路邊停車的研究能夠更好地理解、刻畫駕駛者停車行為，為制定相關車輛停車政策提供依據(jù).

2 環(huán)形城市路邊停車尋位模型描述

在路邊停車研究中鮮有能夠進行解析分析的模型，Arnott等提出的環(huán)形城市模型[4]是其中引用最為廣泛的.如圖1所示，該模型假設在一個環(huán)形城市內，停車位均勻分布路邊，同質的出行需求隨機分布在環(huán)形城市沿線，他們都是要從出發(fā)點沿環(huán)形道路去目的地.比如用O點代表某個人的出發(fā)點，R點代表目的地，從O點出發(fā)，行駛一段時間后，從Q點開始巡游尋找停車位，發(fā)現(xiàn)空的停車位后停車，并將車停在此處（即S點），停車一段時間后，駕車離開系統(tǒng).圖中標記出發(fā)點O和目的地R之間的距離為x，出行者提前找車位的距離為d，開車巡游的距離為y.設每一點處的出行需求相互獨立，且均服從參數(shù)為λ的泊松分布，停車時長服從參數(shù)為 μ的負指數(shù)分布.

圖1 環(huán)形城市路邊停車過程Fig.1 The curbside parking process of circular city

3 基于馬爾科夫鏈的停車尋位模型

3.1 “垂直隊列”狀態(tài)分析

在車輛尋找路邊停車位的過程中，車輛也在不斷行進，當一個空位出現(xiàn)后，不會因為某一車輛尋位時間更長，就讓其優(yōu)先停入，這樣路邊停車尋位車輛就可能出現(xiàn)“后尋位先入位”的情況，即不服從傳統(tǒng)道路交通中的“先進先出”準則.這一方面是路邊停車問題的特殊之處，另一方面也成了研究的困難點.本文針對尋位過程中可能出現(xiàn)的多輛車輛并排行駛競爭一個可能的空車位的情況，將這些在道路上空間相鄰共同巡游的車輛看做一個虛擬隊列，稱為路邊“垂直隊列”.當有空車位出現(xiàn)在該組車隊位置時，在該隊列中的車輛共同競爭車位，不因在隊列時間長而特別優(yōu)先.用i表示垂直隊列中的車輛數(shù)，則i的狀態(tài)集為I={0,1,2,…} ，0表示當前位置沒有尋位車輛，1表示僅有一個尋位車輛，2表示有兩個車輛共同尋位，競爭隨時可能出現(xiàn)的車位，其他以此類推.用相等的時間間隔t來計量時間，t足夠小以使得一個停車位在這個時間間隔中新產生的停車需求不可能超過一個.由于每個點上新產生的停車需求相互獨立，服從參數(shù)為λ的泊松分布，相應的，尋位車輛隊列中的車輛數(shù)隨時間變化是一個馬爾可夫過程.用P={pik}來表示馬爾可夫狀態(tài)轉移矩陣，其中pik=p{t+1時刻尋位車數(shù)為k|t時刻尋位車數(shù)為i}.

為了簡化分析，我們假設各個停車位空閑的概率相互獨立且服從參數(shù)為V的泊松過程.同時V也是路邊停車泊位的空置率.即

因為假設停車后的逗留時間服從期望為μ的負指數(shù)分布，則空置率、出行需求和逗留時間的相互關系可以表示為V=1-λμ.

顯然該馬爾科夫鏈是全連通的.用Π=[π0,π1,π2,…,πi,…]表示系統(tǒng)內尋位車輛各隊列長度的穩(wěn)態(tài)概率，其中πi表示狀態(tài)i發(fā)生的絕對概率.平穩(wěn)狀態(tài)下，應該滿足式（2）條件.

3.2尋位車輛狀態(tài)分析

當一個司機開始尋找路邊停車位，成功找到停車位的概率不僅取決于是否有空置的停車位，也取決于他有多大幾率優(yōu)先于其他一起尋位車輛獲得該位置.本節(jié)從一個尋位車輛司機的角度來分析路邊垂直隊列，即用 j表示已經在垂直隊列中的車輛數(shù)，J={0,1,2,…} 是 j的狀態(tài)集.與i=0表示的是垂直隊列中沒有車輛不同，j=0表示成功找到停車位的狀態(tài).用表示在司機開始找尋停車位的第l個時間間隔后的 j的概率分布向量.sl的推導可以分為兩個階段.

第一階段是車輛剛開始進入到尋位系統(tǒng)中，由于泊松過程的性質，一個時間間隔內最多出現(xiàn)一輛新進入的車輛與其他已有車輛競爭路外停車位.圖2描述了第一階段的狀態(tài)轉移關系.

這時有s0=Π?S0，其中Π 是由3.1節(jié)推導得到，具體表達形式同式.而S0是第一階段的狀態(tài)轉移矩陣為

將Π、S0帶入s0=Π?S0，可以得到

這是尋位車輛在第一個時間間隔內，即剛開始尋位后立刻就能找到停車位的概率.

圖2 尋位車輛第一階段的狀態(tài)轉移Fig.2 The state transmission of cruising on the first stage.

第二階段是基于新進入路邊垂直隊列的車輛并沒有在第一個時間間隔內停車的假設下，對其在之后的時間間隔內與其他車輛競爭路外停車位的狀態(tài)進行研究，此時在新的時間間隔中可能有另外的新車輛進入原有的路邊垂直隊列.圖3描述了第二階段的狀態(tài)轉移關系.

圖3 尋位車輛第二階段的狀態(tài)轉移Fig.3 The state transmission of cruising on the second stage

由于λt和V都與時間無關，第二階段是另外一個馬爾可夫鏈.與i的所有狀態(tài)都是常態(tài)不同，j的狀態(tài)除了 j=0是吸收態(tài)，其他狀態(tài)都是瞬時狀態(tài).

設g(i)是尋位車輛在第i個時間間隔內成功停車的概率.由于是車輛在第i個時間間隔前到達成功停車狀態(tài) j=0狀態(tài)的概率，這時有

由此，可以得到g(i)的公式為

檢查g(1)，g(2)得到

4 停車尋位數(shù)值仿真

4.1 模型參數(shù)與算法

依據(jù)環(huán)形城市尋車找位模型，我們建立了如下的仿真模型.如圖4所示，假設一個環(huán)形城市共有N個停車位離散地均勻分布在一個環(huán)形城市內，每個停車位產生的停車車輛在該車位被占用時會向下尋找下一空車位，直到找到空的車位為止，車輛找到車位后會占據(jù)該車位一段時間，該時間也就是出行者的逗留時間，出行者的逗留時間服從負指數(shù)分布.隨著停車需求的產生，每一個停車位上都可能有多車并排競爭尋找路內停車空位，所以每個車位都存在排隊的現(xiàn)象，圖4中的虛線格子表示尋車排隊隊列，車位允許的最大排隊數(shù)為Q，為避免排隊車輛溢出，設Q=∞.

圖5所示，為仿真算法的實現(xiàn)步驟.在仿真實驗中，環(huán)形城市周長3 km，每個路邊停車位長6 m，可劃分為500個車位.設單位時間為t=3 s，即每3 s系統(tǒng)的車位信息更新一次，總仿真時間為10 h，即12 000個時間單位.逗留時間服從參數(shù) μ=1/3(h)的負指數(shù)分布.

圖4 尋車找位仿真模型Fig.4 Cruising simulation model

4.2 仿真結果

仿真中多次更改λ的值，發(fā)現(xiàn)系統(tǒng)占有率均是在2 000個時間單位前增長迅速，2 000個時間單位后基本達到穩(wěn)定狀態(tài).圖6是λ=2.4時仿真中系統(tǒng)占有率隨時間變化情況.

選取2 000–12 000時間區(qū)間內的停車數(shù)據(jù)，計算平均占有率，然后帶入式(6)，得到車輛尋位距離概率分布，如圖7中實線所示.然后提取該區(qū)間實際成功停車數(shù)據(jù)，統(tǒng)計出尋位距離分布，如圖7中點線所示.可以看出二者雖然十分接近，但還有一定距離，馬氏模型內的尋車距離成功概率要高于實際仿真的結果，或者說馬爾科夫模型低估了找車難度.

再次考察馬氏鏈理論模型，其中對車位占用分布存在其相互獨立的假設，但在仿真實驗中存在大量車位成段連續(xù)被占用的現(xiàn)象.尤其是高車位占有率條件下，尋位車輛車位競爭隊列較長，尋位車輛可能要經過連續(xù)幾個空余車位才能競爭到一個實際屬于自己的位置，往往導致車位被連續(xù)占用.因此，專門設立了仿真實驗，將車位占用與尋位行為獨立，假設被占用車位依照占用率，隨機分布，即圖7中的間斷線部分.可以看出，如果消除仿真中大量車位成段連續(xù)被占用這一因素，將仿真模型中的停車位占有完全設置為隨機，車輛尋位距離概率分布的理論結果與仿真結果基本重合.這說明造成車輛尋位難度低估的另一因素是存在大量車位成段連續(xù)被占用的現(xiàn)象.

圖5 路邊停車仿真算法Fig.5 The algorithm of simulating curbside parking

圖6 系統(tǒng)車位占有率隨時間變化圖Fig.6 The occupancy rate vary with time

圖7 不同機制下的尋位距離概率分布圖Fig.7 The probability distribution of searching distance under various schemes

那么系統(tǒng)中連續(xù)被占用的停車位數(shù)量這一隨機過程的概率分布情況是否具有一定的規(guī)律，值得探究.若系統(tǒng)的空置率為V，假設各個車位是否被占用是獨立分布的，則系統(tǒng)內連續(xù)k個車位被占用的條件是：有兩個車位為空，這兩個車位之間的k個車位不空，如圖8所示.

圖8 系統(tǒng)內車位被連續(xù)占用示意圖Fig.8 The continuously occupied positions

系統(tǒng)內連續(xù)k個車位被占用的概率N(k)為

統(tǒng)計仿真實驗后2 000個時刻的連續(xù)車位占有分布情況，得出連續(xù)車輛數(shù)頻率分布的仿真結果，如圖9所示.將仿真得到的系統(tǒng)占有率帶入式(8)中得到連續(xù)車輛數(shù)頻率分布的理論結果.圖9中的曲線是當λ=2和λ=2.7，2 000個時間單位后平均占有率為66.91%和90.13%時理論與仿真的對比結果.發(fā)現(xiàn)當λ的值比較小時，連續(xù)車輛數(shù)頻率分布曲線比較穩(wěn)定，理論結果與仿真結果差異不大，但是當λ的值變大，車位占有率達到85%以上后，二者的差距就很明顯了.

圖9 連續(xù)占用車位數(shù)概率密度圖Fig.9 The probability density of continuously occupied positions under variousλ

比較圖9中(a)、(b)兩圖，發(fā)現(xiàn)隨λ的增大，連續(xù)停車數(shù)概率分布越不穩(wěn)定，且連續(xù)停車數(shù)較低的概率逐漸減小，連續(xù)停車數(shù)較高的概率逐漸增大.

5 研究結論

本文基于馬爾科夫鏈理論，在經典的環(huán)形城市模型上建立了路邊停車尋位模型，解析地得到了路邊尋位車輛隊列概率分布和車輛尋位距離分布，證明了路邊停車尋位距離概率分布非二項分布，這很好地解釋了實證中發(fā)現(xiàn)的路邊尋位難度往往高于理論估計的原因.在理論分析基礎上，提出環(huán)形城市路邊停車仿真模型及算法，仿真結果驗證了理論模型的結論，并發(fā)現(xiàn)車位被連續(xù)占用也是增加停車難度的另一個重要原因.

今后的研究將考慮將本文提出的模型應用到路邊定價策略的設定上，同時將道路擁擠與停車行為共同考慮也將很有理論價值.

[1]張國伍.停車系統(tǒng)在城市交通中的地位與作用[J].交通運輸系統(tǒng)工程與信息.2014，14(1):2-8.[ZHANG G W,The position and role of parking system in urban traffic[J].Journal of Transportation Systems Engineering and Information Technology,2014，14(1):2-8.]

[2]Vickrey W.The economizing of curb parking space[J]. Traffic Engineering,November,1954,29:62-67.

[3]Arnott R,De Palma A,Lindsey R.A temporal and spatial equilibrium analysis of commuter parking[J]. Journal of Public Economics,1992,45(3):301-335.

[4]Arnott R,Rowse J.Modeling parking[J].Journal of Urban Economics,1999,45(1):97-124.

[5]Anderson S P,de Palma A.The economics of pricing parking[J].Journal of Urban Economics,2004,55(1):1-20.

[6]郭宏偉,高自友,趙小梅,等.路內停車對非機動車交通行為影響研究[J].交通運輸系統(tǒng)工程與信息.2011, 11(1):79-84.[GUO H W,GAO Z Y,ZHAO X M, et al.Traffic behavior analysis of non-motorized vehicle under influence of curb parking[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(1):79-84.]

[7]Shoup D C.Cruising for parking[J].Transport Policy, 2006,13(6):479-486.

[8]Levy N,Martens K,Benenson I.Exploring cruising using agent-based and analytical models of parking[J]. Transportmetrica A:Transport Science,2012,9(9):773-797.

A Markov-based Curbside Parking Model and Simulations

TIAN Qiong,YANG Li,LUO Ting
(School of Economics and Management,Beihang University,Beijing 100191,China)

Referring to the classic circular city model,a curbside parking model based on the Markov chain theory is formulated.According to its Markov properties,the cruising competition queue is depicted through the viewpoints of the system and drivers,respectively.Consequently,the probability density function of the searching distance is derived,which proves that the traditional binomial distribution is limited in describing the competition behaviors between drivers.Then,a simulation algorithm is established to verify the theoretical results of the Markov model and find that besides the competition behavior,the continuouslyparking phenomenon is another major reason for difficult curbside parking.The finding extends our knowledge of curbside parking and can be helpful in designing the curbside parking policies.

urban traffic;curbside parking;Markov chain;cruising behavior;circular city

1009-6744（2015）01-0179-06

：U491

：A

2014-08-14

：2014-10-11錄用日期：2014-10-17

國家自然科學基金（71071011，71271017，71471010）；國家973重大基礎研究計劃項目（2012CB725401）；中央基本科研業(yè)務費（YMF-2014-JGXY-002）.

田瓊（1981-），男，河北廊坊人，博士，副教授. ＊

：tianqiong@buaa.edu.cn