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

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

?

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

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

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

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

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

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

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

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

1 共享停車供需描述

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

1.1 共享泊位供給

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

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

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

圖2 共享泊位開放時間示意圖

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

Fig.3 Parking time of the reserved user

1.2 停車需求

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

2 共享停車匹配模型

2.1 模型基本符號及說明

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

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

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

2.3 約束條件的建立

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

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

3 案例分析

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

圖 4 泊位共享時間窗

圖 5 虛擬泊位共享時間窗

圖6 需求車輛編號示意圖

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

通過圖6給出的預(yù)約車輛停放時間與共享時間窗對比分析，將虛擬泊位與需求車輛的匹配關(guān)系用圖7表示。由圖7發(fā)現(xiàn)，共享停車供需匹配可以有多種組合，如停車泊位4轉(zhuǎn)換得到的虛擬泊位5在滿足時間約束的前提下共有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程序中進行匹配運算整理結(jié)果得到虛擬泊位優(yōu)化分配結(jié)果示意圖，如圖8所示。結(jié)果發(fā)現(xiàn)，所有停車需求均得到滿足，各虛擬泊位共享時間窗內(nèi)被匹配到1或2個車輛，泊位利用較為充分，通過匹配優(yōu)化模型處理后的匹配組合避免了車輛未找到車位的現(xiàn)象。將圖8虛擬泊位的分配結(jié)果進行還原，最終得到經(jīng)模型優(yōu)化后的實際泊位匹配結(jié)果，詳見圖9。

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

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

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

圖 10 虛擬泊位開放時間窗

Fig.10 Opening time window of virtual berths

圖 11 需求車輛停放時間窗

Fig.11 Parking time window of vehicle demand

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

表1 優(yōu)先長時停車分配結(jié)果

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

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

4 結(jié)論

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

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

[2] 李濤,關(guān)宏志.考慮用戶時間沖突的停車共享方案優(yōu)化研究[J].交通運輸系統(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ū)典型行政辦公配建泊位共享時間窗口劃分研究[D].南京:東南大學(xué),2016

[5] 劉志廣.城市中心區(qū)典型商場配建停車泊位共享時間窗口研究[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] 段滿珍,楊兆升,張林,等.個性化誘導(dǎo)下的居住區(qū)共享停車泊位分配模型[J].東北大學(xué)學(xué)報:自然科學(xué)版,2017,38(2):174-179

[10] 陳峻,謝凱.中心城區(qū)高校停車泊位共享的動態(tài)分配模型及效果評價[J].中國公路學(xué)報,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].交通運輸系統(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é)人文社科攀登重點項目(SK17PA02);上海市一流學(xué)科建設(shè)項目(S1201YLXK);上海市自然科學(xué)基金項目(18ZR1426200)

路揚(1991-),男,碩士研究生,主要研究方向為交通網(wǎng)絡(luò)建模、智能交通系統(tǒng). E-mail:nryl0627@163.com

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