路揚(yáng),何勝學(xué),王冬冬

?

共享停車泊位供需匹配優(yōu)化模型

路揚(yáng),何勝學(xué)*,王冬冬

上海理工大學(xué) 管理學(xué)院, 上海 200093

針對(duì)城市停車資源的有限性以及城市停車難問題，提出了一種基于共享停車?yán)砟畹墓蚕硗＼嚥次还┬杵ヅ鋬?yōu)化模型。首先對(duì)共享停車供需問題進(jìn)行分析，提出了虛擬泊位的概念，使多種泊位狀態(tài)下的時(shí)間窗實(shí)現(xiàn)并行分配；其次，基于整數(shù)規(guī)劃邏輯判斷理論，以提高泊位利用率為主要目標(biāo)，建立了泊位供需匹配優(yōu)化模型；最后，設(shè)計(jì)共享停車匹配仿真實(shí)驗(yàn)，并與“優(yōu)先長(zhǎng)時(shí)停車”的分配方法進(jìn)行對(duì)比。模擬算例表明：經(jīng)模型優(yōu)化后的匹配方案共享泊位總體利用效率高達(dá)85.31%，較優(yōu)化前利用效率提高了10.74%。

共享停車; 優(yōu)化模型

停車難是城市面臨的普遍問題。近年來隨著個(gè)人購(gòu)車水平的不斷提高，機(jī)動(dòng)車保有量驟然增加，城市停車問題受到巨大挑戰(zhàn)[1]。面對(duì)龐大的停車需求，城市中有限的停車資源已無(wú)法跟上其日益增長(zhǎng)的步伐，同時(shí)由于城市空間及建設(shè)資金的約束，憑借配建大量停車場(chǎng)來解決泊位匱乏問題并不切實(shí)際。城市中居民區(qū)與公共建筑區(qū)域停車泊位的使用情況存在長(zhǎng)時(shí)間的閑置狀態(tài)，這使城市中泊位擁有巨大的錯(cuò)時(shí)共享潛力[2]。共享停車概念[3]的提出為人們提供一個(gè)解決停車問題的新思路，并在一定程度上緩解了停車供需矛盾，對(duì)挖掘現(xiàn)有泊位潛力，盤活閑置停車資源有較強(qiáng)的理論及現(xiàn)實(shí)意義。

近年來越來越多的學(xué)者開始關(guān)注共享停車的相關(guān)問題，研究主要集中于共享停車的供需預(yù)測(cè)及供需匹配兩個(gè)方面。由于共享停車的匹配受到嚴(yán)格的時(shí)間限制，在共享時(shí)間窗預(yù)測(cè)方面，陳愷[4]、劉志廣[5]等利用時(shí)間序列分析法分別對(duì)不同場(chǎng)所的共享時(shí)間窗進(jìn)行預(yù)測(cè)，不僅確定了共享停車的開放條件，同時(shí)可較為準(zhǔn)確地預(yù)測(cè)出共享時(shí)間窗，但由于研究對(duì)象均為單一建筑，其廣泛適用性有待改善。王浩[6]鑒于停車行為選擇特性，成功將分時(shí)段停車需求預(yù)測(cè)模型優(yōu)化并應(yīng)用到實(shí)際預(yù)測(cè)中。在共享泊位匹配方面，不少學(xué)者借助了雙層規(guī)劃模型對(duì)車輛的匹配進(jìn)行優(yōu)化[7-10]，如段滿珍等[9]綜合考慮了高峰供應(yīng)限制及步行距離，利用雙層規(guī)劃模型有效解決了停車分配產(chǎn)生的局部擁堵問題，但未細(xì)致考慮到泊位層面。陳峻等[10]充分考慮了需求的時(shí)變狀態(tài)，對(duì)共享泊位開放條件以及供需特性進(jìn)行了透徹的分析，但仍局限于以泊位數(shù)作為研究對(duì)象。

鑒于以共享停車場(chǎng)的開放泊位數(shù)作為研究對(duì)象的局限性，本文擬建立可針對(duì)每個(gè)具體泊位進(jìn)行 細(xì)致分析的共享停車泊位供需匹配優(yōu)化模型，通過虛擬泊位轉(zhuǎn)換實(shí)現(xiàn)匹配并行處理，并借助整數(shù)規(guī)劃邏輯判斷理論使運(yùn)算更加高效、準(zhǔn)確。考慮到“優(yōu)先長(zhǎng)時(shí)停車”的匹配方法以單泊位使用效率作為目標(biāo)函數(shù)，具有一定的優(yōu)化效果，因此本文設(shè)計(jì)了仿真算例，將通過模型優(yōu)化后的效果與“優(yōu)先長(zhǎng)時(shí)停車”的匹配方法進(jìn)行對(duì)比，進(jìn)一步證明模型的可行性、合理性。

1 共享停車供需描述

共享停車泊位的匹配問題就是將閑置時(shí)段的私有泊位利用起來，最大化滿足司機(jī)用戶的停車需求。為更好地研究泊位的匹配問題，充分發(fā)揮城市停車資源的最大價(jià)值，本文將分別從共享泊位的供給及需求兩個(gè)方面進(jìn)行分析并闡述二者之間的關(guān)系[11,12]。

1.1 共享泊位供給

通常共享停車的泊位狀態(tài)可以分為三種：泊位處于所有者使用狀態(tài)；泊位已被預(yù)約用戶占用或處于周轉(zhuǎn)間隔期；泊位處于閑置狀態(tài)。同時(shí)考慮到同一共享泊位在一天內(nèi)會(huì)存在多次開放服務(wù)的可能性，為了體現(xiàn)各自之間的獨(dú)立性，本文提出了虛擬泊位的概念。虛擬泊位，就是將同一泊位的多個(gè)不連續(xù)共享時(shí)間窗分解轉(zhuǎn)化，用相同數(shù)量的虛擬泊位代替，使每個(gè)虛擬泊位有且僅有一個(gè)共享泊位開放時(shí)段，其轉(zhuǎn)化過程如圖1所示。圖中陰影部分表示泊位處于泊位所有者自用狀態(tài)，白色方框表示區(qū)域?yàn)橐驯黄溆嘬囕v預(yù)定的狀態(tài)。1號(hào)泊位的對(duì)外出租時(shí)間為1至4時(shí)段，其中2至3時(shí)段已被其余車輛預(yù)定，即1號(hào)泊位的共享時(shí)間窗等價(jià)于1至2時(shí)段以及3至4時(shí)段。而等價(jià)泊位則在一天中存在兩個(gè)共享時(shí)間窗，將1號(hào)泊位進(jìn)行轉(zhuǎn)化得到虛擬泊位1及2。

圖1 虛擬泊位轉(zhuǎn)換示意圖

假設(shè)已知“共享停車場(chǎng)”所有共享泊位在一天中的開放時(shí)間及結(jié)束時(shí)間，建立關(guān)于共享開放時(shí)間、開放時(shí)長(zhǎng)、供給泊位的三維圖（圖2），直觀的展現(xiàn)出各虛擬泊位的供給時(shí)間窗以及總體開放趨勢(shì)。由圖可知，在1至6時(shí)間內(nèi)共設(shè)置了6個(gè)虛擬泊位提供共享停車服務(wù)，通過三維柱狀圖可以得到各虛擬泊位的開放時(shí)刻、開放時(shí)長(zhǎng)，由此可確定各泊位要求預(yù)約車輛離開的最晚時(shí)間。

圖2 共享泊位開放時(shí)間示意圖

圖 3 預(yù)約用戶停放時(shí)間示意圖

Fig.3 Parking time of the reserved user

1.2 停車需求

泊位共享的運(yùn)行模式要求司機(jī)在接受停車服務(wù)前進(jìn)行提前預(yù)約，并向系統(tǒng)提供其到達(dá)時(shí)間及停放時(shí)長(zhǎng)[13]，圖3所示示意圖提供了共享停車預(yù)約用戶的相關(guān)停放數(shù)據(jù)。系統(tǒng)將根據(jù)用戶停放數(shù)據(jù)及停車意愿，在一定的步行距離允許范圍內(nèi)確定最佳的共享停車場(chǎng)，并根據(jù)停車場(chǎng)各泊位的共享時(shí)間窗，選擇滿足用戶要求的泊位與其匹配。本文假設(shè)已知停車需求車輛的到達(dá)時(shí)間及停放時(shí)長(zhǎng)，且所有車輛能可在規(guī)定的時(shí)間內(nèi)離開，以保證泊位所有者自身使用不受影響。

2 共享停車匹配模型

2.1 模型基本符號(hào)及說明

d——代表第個(gè)停車需求車輛；S——代表第個(gè)虛擬泊位；td——代表車輛d的停放起始時(shí)間；d——代表需求車輛d在該停車場(chǎng)停泊的時(shí)長(zhǎng)，因此車輛d將要停泊的時(shí)間區(qū)間可以表示為(td,td+d)；t——代表停車泊位共享開放起始時(shí)間；——代表共享泊位開放時(shí)長(zhǎng)；ds?{0.1}——代表供需停車匹配參數(shù)，當(dāng)ds=1時(shí)，車輛d與泊位s成功匹配，否則ds=0；(d,s)——代表停車需求d與共享泊位s的一種匹配；——代表所有的需求車輛的總數(shù)；——代表所有虛擬泊位的總數(shù)。

2.2 目標(biāo)函數(shù)的建立

為體現(xiàn)分配結(jié)果的合理性及科學(xué)性，本文建立了以ds為核心的供需匹配數(shù)學(xué)優(yōu)化模型，對(duì)預(yù)約停車車輛進(jìn)行分配，并以停車泊位利用率作為目標(biāo)函數(shù)[14]，構(gòu)建共享停車泊位供需匹配優(yōu)化模型：

2.3 約束條件的建立

為了更好地將約束條件與目標(biāo)函數(shù)聯(lián)系起來，提高程序運(yùn)行效率，本文以整數(shù)規(guī)劃邏輯判斷理論為基礎(chǔ)，建立停車匹配約束條件。在共享停車匹配系統(tǒng)調(diào)配過程中，停車需求車輛d與虛擬泊位S能夠成功匹配的前提不僅需要車輛的停放時(shí)長(zhǎng)d小于、等于共享泊位的開放時(shí)長(zhǎng)，同時(shí)需滿足停車需求車輛到達(dá)與離開“共享停車場(chǎng)”的時(shí)間td、td+d均處于虛擬泊位S共享時(shí)間窗的范圍內(nèi)。若(td,td+d)/(t,t+)=?，說明供需雙方在時(shí)間上發(fā)生沖突，彼此匹配成功的條件不成立，因此停車需求車輛d不能與共享泊位S匹配，此時(shí)ds必定不為1。

對(duì)于某一輛待停車輛d來說，共有種不同的停車匹配組合供選擇，即(d,1)、(d,2)…(d,S)。同時(shí)對(duì)于任意一輛機(jī)動(dòng)車，同一時(shí)刻所有供給泊位只能有一個(gè)可以與之匹配。為確保供需雙方的一一對(duì)應(yīng)關(guān)系，避免同一時(shí)刻多輛機(jī)動(dòng)車被分配到同一泊位，建立了約束表達(dá)式（6）。

3 案例分析

首先采用一個(gè)簡(jiǎn)單的共享停車匹配系統(tǒng)為案例對(duì)系統(tǒng)的分配原則及過程進(jìn)行說明，以證明本文所建模型的合理性。圖4給出4個(gè)停車泊位1至4的共享時(shí)間窗，其中陰影部分包括泊位所有者自用時(shí)間及以被其他車輛預(yù)約的時(shí)間，將圖4的實(shí)際泊位轉(zhuǎn)化為虛擬泊位（圖5）。

圖 4 泊位共享時(shí)間窗

圖 5 虛擬泊位共享時(shí)間窗

圖6 需求車輛編號(hào)示意圖

圖7 供需匹配關(guān)系示意圖

通過圖6給出的預(yù)約車輛停放時(shí)間與共享時(shí)間窗對(duì)比分析，將虛擬泊位與需求車輛的匹配關(guān)系用圖7表示。由圖7發(fā)現(xiàn)，共享停車供需匹配可以有多種組合，如停車泊位4轉(zhuǎn)換得到的虛擬泊位5在滿足時(shí)間約束的前提下共有4種匹配組合，分別為(3,5)、(4,5)、(5,5)、(6,5)。本文建立了關(guān)于共享停車匹配的非線性規(guī)劃模型，求解該類問題可以使用一些經(jīng)典的算法求解，如分支定界法和模板模型法等，也可以使用一些經(jīng)典啟發(fā)式算法，如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法等。其中部分較成熟的算法已經(jīng)應(yīng)用到了一些商業(yè)軟件當(dāng)中，因此使用商用軟件Lingo可以較好地求解模型。將供需數(shù)據(jù)輸入Lingo程序中進(jìn)行匹配運(yùn)算整理結(jié)果得到虛擬泊位優(yōu)化分配結(jié)果示意圖，如圖8所示。結(jié)果發(fā)現(xiàn)，所有停車需求均得到滿足，各虛擬泊位共享時(shí)間窗內(nèi)被匹配到1或2個(gè)車輛，泊位利用較為充分，通過匹配優(yōu)化模型處理后的匹配組合避免了車輛未找到車位的現(xiàn)象。將圖8虛擬泊位的分配結(jié)果進(jìn)行還原，最終得到經(jīng)模型優(yōu)化后的實(shí)際泊位匹配結(jié)果，詳見圖9。

圖8 虛擬泊位優(yōu)化匹配結(jié)果示意圖

圖9 實(shí)際泊位優(yōu)化匹配結(jié)果示意圖

為了證明模型普適性及數(shù)據(jù)的全面性，設(shè)計(jì)了虛擬泊位多達(dá)31個(gè)的仿真實(shí)驗(yàn)，并與“優(yōu)先長(zhǎng)時(shí)停車”的分配方法進(jìn)行對(duì)比。算例選取早6點(diǎn)至晚8點(diǎn)時(shí)段為研究時(shí)段，并將早6點(diǎn)作為參考0點(diǎn)，以10 min為一個(gè)匹配步長(zhǎng)，共劃分了84步。

圖 10 虛擬泊位開放時(shí)間窗

Fig.10 Opening time window of virtual berths

圖 11 需求車輛停放時(shí)間窗

Fig.11 Parking time window of vehicle demand

通過圖10、11所示三維圖柱狀圖發(fā)現(xiàn)，在某“共享停車場(chǎng)”共設(shè)有31個(gè)共享虛擬泊位，有55個(gè)預(yù)約停車用戶希望通過系統(tǒng)獲得停車泊位。將上述數(shù)據(jù)輸入經(jīng)編制的泊位分配程序計(jì)算得到，經(jīng)模型優(yōu)化后的匹配方法實(shí)現(xiàn)55輛需求車輛全部匹配，共享泊位出租總時(shí)長(zhǎng)達(dá)181.7 h，占泊位總開放時(shí)長(zhǎng)的85.31%。而“優(yōu)先長(zhǎng)時(shí)停車”的匹配方法有10輛需求車輛未成功分配到停車泊位，19.5 h的出租時(shí)長(zhǎng)未得到充分利用，泊位使用率僅為74.57%。

表1 優(yōu)先長(zhǎng)時(shí)停車分配結(jié)果

表2 優(yōu)化后分配結(jié)果

仿真案例結(jié)果表明：相同的供需條件下，經(jīng)模型優(yōu)化后的共享泊位匹配方案有著更理想的匹配效果，泊位總體使用效率提高了10.74%，遠(yuǎn)大于以優(yōu)先停車時(shí)長(zhǎng)進(jìn)行分配的匹配方法。

4 結(jié)論

本文在分析共享停車供需關(guān)系的基礎(chǔ)上，基于共享停車?yán)砟?，以提升泊位利用率為目?biāo)，建立了共享停車匹配模型。通過模擬仿真實(shí)驗(yàn)證明經(jīng)模型優(yōu)化后的匹配方案能夠大大地提升泊位使用效率，在一定程度上緩解了城市停車供需之間的矛盾，為城市共享停車的推廣提供了一定的理論支撐。

[1] 段滿珍,楊兆升,張林,等.居住區(qū)泊位對(duì)外共享能力評(píng)估模型[J].交通運(yùn)輸系統(tǒng)工程與信息,2015,15(4):106-112

[2] 李濤,關(guān)宏志.考慮用戶時(shí)間沖突的停車共享方案優(yōu)化研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2017,17(5):144-150

[3] He P, Chen J, Zhen JH,. Parking Choice Behavior for Shared Parking Based on Parking Purposes[J]. Applied Mechanics & Materials, 2015,743:439-444

[4] 陳愷.城市中心區(qū)典型行政辦公配建泊位共享時(shí)間窗口劃分研究[D].南京:東南大學(xué),2016

[5] 劉志廣.城市中心區(qū)典型商場(chǎng)配建停車泊位共享時(shí)間窗口研究[D].南京:東南大學(xué),2016

[6] 王浩,胡江濤,晏秋.居住區(qū)共享泊位開放數(shù)量確定方法[J].西部交通科技,2016(12):70-73

[7] Ran J. Bi-level model for shared parking decision-making based on parking lot assignment simulation[J]. Journal of Southeast University (English Edition), 2011,27(3):322-327

[8] 冉江宇,過秀成.基于停車共享的已建成區(qū)停車需求分析方法[J].交通信息與安全,2015,33(3):9-15

[9] 段滿珍,楊兆升,張林,等.個(gè)性化誘導(dǎo)下的居住區(qū)共享停車泊位分配模型[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2017,38(2):174-179

[10] 陳峻,謝凱.中心城區(qū)高校停車泊位共享的動(dòng)態(tài)分配模型及效果評(píng)價(jià)[J].中國(guó)公路學(xué)報(bào),2015,28(11):104-111

[11] Mejri N, Ayari M, Kamoun F. An efficient cooperative parking slot assignment solution[C]. Porto, Portugal: The seventh international conference on mobile ubiquitous computing, systems, services and technologies, 2013:119-125

[12] Roca-Riu M, Fernández E, Estrada M. Parking slot assignment for urban distribution: Models and formulations[J]. Omega, 2015,57:157-175

[13] Shao C, Yang H, Zhang Y,. A simple reservation and allocation model of shared parking lots[J]. Transportation Research Part C Emerging Technologies, 2016,71(8):303-312

[14] 姚恩建,張正超,張嘉霖,等.居住區(qū)共享泊位資源優(yōu)化配置模型及算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2017,17(2):160-167

The Matching Optimization Model of Shared Parking Spaces between Supply and Demand

LU Yang, HE Sheng-xue*, WANG Dong-dong

200093,

The limited availability of parking resulting in traffic congestion is commonplace in most cities. This paper proposed a matching optimization model of urban shared parking between supply and demand based on shared parking theory by optimizing the Shared parking matching scheme. The concept of virtual berth is presented firstly according to Shared parking supply and demand analysis to realize parallel processing of time windows. To improve the utilization rate of berth, the matching optimization model of urban shared parking between supply and demand is established secondly based on the theory of integer programming logic judgment. Finally, the simulation of the model was carried out and compared with the "long-time parking priority” allocation method. The results indicated that the efficiency of the berth utilization by matching optimization model of urban shared parking up to 85.31% can be achieved, which is 10.74% higher than before optimization.

Shared parking; optimal model

F57

A

1000-2324(2018)06-0986-05

10.3969/j.issn.1000-2324.2018.06.016

2018-04-20

2018-04-30

上海理工大學(xué)人文社科攀登重點(diǎn)項(xiàng)目(SK17PA02);上海市一流學(xué)科建設(shè)項(xiàng)目(S1201YLXK);上海市自然科學(xué)基金項(xiàng)目(18ZR1426200)

路揚(yáng)(1991-),男,碩士研究生,主要研究方向?yàn)榻煌ňW(wǎng)絡(luò)建模、智能交通系統(tǒng). E-mail:nryl0627@163.com

Author for correspondence. E-mail:lovellhe@126.com