基于時(shí)間窗與優(yōu)先級(jí)的網(wǎng)絡(luò)共享停車匹配模型*

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

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

0 引 言

近些年隨著國內(nèi)機(jī)動(dòng)車保有量的不斷攀升，泊位爭(zhēng)搶日益激烈，現(xiàn)有的停車泊位數(shù)量已無法滿足人們的停車需求，且在城市中心區(qū)域尤為突出[1].面對(duì)巨大的城市停車壓力，可以從兩方面解決停車問題：提高泊位的絕對(duì)數(shù)量，即建設(shè)大量停車設(shè)施，增設(shè)停車泊位；提升泊位利用效率，如共享停車.而共享停車相比停車場(chǎng)建設(shè)更經(jīng)濟(jì)、更科學(xué)，因此，以停車挑戰(zhàn)為動(dòng)力，借鑒現(xiàn)有的共享經(jīng)濟(jì)理念，通過泊位共享手段可以從一個(gè)新的角度來處理停車問題.

現(xiàn)階段共享停車還處于探索階段，不少專家學(xué)者也從各個(gè)方面對(duì)其展開研究，期望通過停車時(shí)間的互補(bǔ)，以解決長期共享停車用戶為核心，充分發(fā)揮停車資源的潛在利用價(jià)值[2].姚恩建等[3]對(duì)共享停車的時(shí)間約束及分配原則做出了透徹的分析，對(duì)圖著色模型進(jìn)行改進(jìn)并建立了共享泊位資源優(yōu)化配置模型，有效地解決待停車輛的最優(yōu)泊位匹配問題，然而在網(wǎng)絡(luò)調(diào)配層面闡述較少.段滿珍等[4-5]發(fā)現(xiàn)居民區(qū)與其他類型場(chǎng)所停車使用上有一定的互補(bǔ)性，對(duì)居民區(qū)泊位時(shí)間特性進(jìn)行詳細(xì)研究，并通過建立雙層規(guī)劃模型解決停車分配不均衡問題，但對(duì)于匹配的時(shí)間約束問題沒有進(jìn)行分析研究.類似的雙層規(guī)劃模型也被許多學(xué)者改進(jìn)，陳峻等[6]利用雙層模型應(yīng)用到對(duì)高校停車場(chǎng)的出租共享分配問題上，分析了多種泊位使用情形，同時(shí)考慮高校停車泊位無法滿足停車需求時(shí)的解決方案，同時(shí)對(duì)共享停車的需求進(jìn)行分類，確定不同停車目的的停車行為影響因素，建立兩種停車行為選擇模型[7].Xiao等[8]在共享停車收費(fèi)問題的研究中，利用投標(biāo)手段確定支付規(guī)則，但沒有明確考慮到停車泊位的空間特性及需求車輛與泊位之間的距離問題.目前對(duì)于網(wǎng)絡(luò)共享停車匹配的研究大都以停車場(chǎng)開放泊位數(shù)為研究對(duì)象[9]，未考慮共享泊位匹配有著嚴(yán)格的時(shí)間約束限制[10-11]，具有一定的局限性，因此,以停車場(chǎng)停車泊位為研究對(duì)象有著巨大的研究潛力[12].

文中設(shè)計(jì)了網(wǎng)絡(luò)共享停車匹配優(yōu)化系統(tǒng)，并建立了整數(shù)非線性規(guī)劃模型(INLP).模型綜合考慮了需求車輛的優(yōu)先級(jí)、泊位周轉(zhuǎn)時(shí)間，以及時(shí)間窗沖突問題，同時(shí)對(duì)整個(gè)停車網(wǎng)絡(luò)的不同供需情形進(jìn)行分析，使匹配效果更科學(xué)、更合理.

1 共享停車問題描述

1.1 共享停車系統(tǒng)

共享停車是指利用停車泊位供需雙方的錯(cuò)峰使用特性，將某些時(shí)段停車場(chǎng)閑置的空余泊位共享對(duì)外出租，通過移動(dòng)終端APP、網(wǎng)絡(luò)平臺(tái)為駕駛員匹配合理的停車泊位，以提高尋車效率及停車場(chǎng)停車泊位利用率.對(duì)于司機(jī)而言，可以通過共享停車系統(tǒng)快速尋找到目的地周圍停車泊位，解決停車問題；對(duì)于整個(gè)系統(tǒng)而言，高效的尋車效率可以減少城市道路中因?qū)ふ臆囄欢a(chǎn)生的無效交通流，保證道路通暢，合理的停車匹配可以提高整個(gè)共享停車場(chǎng)的利用率，將城市中有限的停車資源利用最大化.本文針對(duì)網(wǎng)絡(luò)共享停車場(chǎng)的共享停車匹配進(jìn)行研究，見圖1.

圖1 共享停車網(wǎng)絡(luò)匹配流程圖

對(duì)于每一停車泊位sj，上傳系統(tǒng)的信息包括：泊位開放時(shí)刻oj、關(guān)閉時(shí)刻cj、泊位所屬停車場(chǎng)ph，以及其位置坐標(biāo)(xsj,ysj).泊位預(yù)約用戶di信息向系統(tǒng)平臺(tái)發(fā)送停車請(qǐng)求同時(shí)，會(huì)提供其出發(fā)位置(xdi,ydi) 、出發(fā)時(shí)間bi、預(yù)測(cè)到達(dá)目的地的行駛時(shí)間ti、離開共享停車場(chǎng)的最晚離開時(shí)間li.系統(tǒng)接受共享停車的各類數(shù)據(jù)進(jìn)行整理，建立相應(yīng)的系統(tǒng)時(shí)間窗，并可以實(shí)時(shí)更新時(shí)間窗、需求車輛總數(shù)D、共享泊位總數(shù)S等相關(guān)數(shù)據(jù).將整理后的數(shù)據(jù)利用共享停車匹配系統(tǒng)確定最優(yōu)匹配組合，向用戶提供泊位所屬停車場(chǎng)、停車場(chǎng)位置，待用戶確認(rèn)并到達(dá)后完成匹配，并對(duì)系統(tǒng)時(shí)間窗進(jìn)行更新.系統(tǒng)還對(duì)不同使用頻率的用戶進(jìn)行了分類，將需求車輛分為長期用戶與臨時(shí)用戶，并設(shè)置了優(yōu)先級(jí)系數(shù)αi，對(duì)短期用戶αi設(shè)為1，長期用戶αi取1.5.通過匹配優(yōu)先系數(shù)的設(shè)置，實(shí)現(xiàn)長期用戶的優(yōu)先匹配[13].

1.2 基本假設(shè)

網(wǎng)絡(luò)共享停車匹配優(yōu)化模型在泊位分配過程中遵循以下基本假設(shè)：①所有預(yù)約車輛到達(dá)某處的行駛時(shí)間與空間直線距離成比例且相等；②預(yù)約用戶離開共享泊位的時(shí)間固定且已知；③可對(duì)車輛到達(dá)目的地的行駛時(shí)長進(jìn)行預(yù)測(cè).

2 共享停車網(wǎng)絡(luò)匹配模型

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

為體現(xiàn)分配結(jié)果的合理性及科學(xué)性，建立了以δdisj為核心的網(wǎng)絡(luò)共享供需匹配數(shù)學(xué)優(yōu)化模型，對(duì)預(yù)約停車車輛進(jìn)行分配.同時(shí)對(duì)兩種不同情形的供需數(shù)量關(guān)系進(jìn)行針對(duì)性研究，建立了兩種相應(yīng)的目標(biāo)函數(shù)，并考慮到優(yōu)先匹配問題，力求保證優(yōu)先級(jí)較高的長期預(yù)約用戶優(yōu)先獲得車位，構(gòu)建城市共享停車供需匹配優(yōu)化模型目標(biāo)函數(shù)為

maxZ1=∑D∑Sαi·δdisj·πdi

(1)

maxZ2=∑D∑Sαi·

(2)

當(dāng)網(wǎng)絡(luò)區(qū)域內(nèi)的共享泊位處于供不應(yīng)求狀態(tài)下，為了使停車資源得到充分利用建立了目標(biāo)函數(shù).式(1)表示最大化共享泊位出租時(shí)長同時(shí)兼顧優(yōu)先級(jí)較高的預(yù)約用戶享有優(yōu)先獲得泊位的權(quán)益.其中δdisj為匹配關(guān)系變量，表示需求車輛di與供給泊位sj是否匹配成功，當(dāng)δdisj=1時(shí)，需求di與供給sj匹配成功，若未匹配成功，則δdisj=0.

式(2)表示當(dāng)供給泊位非常充足的情況下，所有車輛均能獲得泊位，因此,優(yōu)先考慮所匹配得泊位與目的地的距離最近，為用戶優(yōu)先選擇距離最短的停車場(chǎng).通過兩種目標(biāo)函數(shù)，為不同情形選擇合理方案，使模型更具針對(duì)性.

2.2 約束條件的建立

(3)

式(3)表示匹配的共享泊位須在需求車輛di的目的地Di的可行范圍內(nèi)，Q為共享單車范圍最大距離，可根據(jù)城市規(guī)?；蚓唧w情況進(jìn)行調(diào)整.

(4)

li≤cj

(5)

式(4)～(5)構(gòu)成了停車匹配過程最基本的時(shí)間約束限制，停車需求車輛的停放時(shí)段需要處在共享時(shí)間窗范圍內(nèi)[14-15].式(4)表示車輛di到達(dá)共享停車場(chǎng)ph時(shí)泊位sj已經(jīng)開放共享.需求di匹配過程中，考慮到司機(jī)與待選停車場(chǎng)的距離均不相同，需根據(jù)已知到達(dá)停車場(chǎng)的時(shí)間估算出車輛到達(dá)不同停車場(chǎng)的時(shí)間，與相應(yīng)共享停車場(chǎng)內(nèi)的共享泊位開放時(shí)間窗比較.方便起見，假設(shè)所有單位時(shí)間內(nèi)行駛的空間直線距離相同，實(shí)際預(yù)測(cè)中有更為準(zhǔn)確的預(yù)測(cè)數(shù)值，因此，可根據(jù)距離估算出到達(dá)各共享停車場(chǎng)的行駛時(shí)間.式(5)用于表示對(duì)車輛的離開時(shí)間進(jìn)行限制，要求車輛在泊位關(guān)閉開放之前離開.

∑Sδdisj≤1 ?D

(6)

(lm-an+k)·(ln-am+k)≤0

(7)

任何車輛使用共享泊位上的一個(gè)前提是泊位處于空閑狀態(tài)，式(6)表示每一個(gè)泊位同一時(shí)刻只能服務(wù)至多一個(gè)共享停車用戶.k表示預(yù)留的泊位準(zhǔn)備時(shí)間或周轉(zhuǎn)時(shí)間，通常取值為5 min.式(7)避免匹配到同一泊位的任意兩輛車輛產(chǎn)生時(shí)間上的沖突.對(duì)于任意一個(gè)停車泊位，存在同一共享開放時(shí)段內(nèi)服務(wù)多輛需求車輛，但由于停車匹配有著嚴(yán)格的時(shí)間約束限制，所有已經(jīng)匹配的車輛在時(shí)間上均不會(huì)出現(xiàn)交集.即對(duì)于同一泊位、同一共享時(shí)段的所有車輛來說，無論車輛數(shù)量多少，兩兩之間時(shí)間均不會(huì)產(chǎn)生沖突.

(8)

(9)

(10)

(11)

(12)

(13)

3 案例分析

3.1 算例介紹

文中設(shè)計(jì)了一個(gè)簡單的網(wǎng)絡(luò)共享停車匹配系統(tǒng)來檢驗(yàn)?zāi)Ｐ偷姆峙湫Ч?算例網(wǎng)絡(luò)見圖2，針對(duì)共享泊位供不應(yīng)求的情形下進(jìn)行了模擬仿真，系統(tǒng)共設(shè)置了設(shè)有3個(gè)共享停車場(chǎng)，5個(gè)共享泊位以及10個(gè)泊位預(yù)約車輛，需求車輛各自開往A，B，C，D四個(gè)不同的目的地.示意圖中的位置坐標(biāo)以A為參考原點(diǎn)，需求車輛分布在網(wǎng)絡(luò)的不同方位，對(duì)所有車輛、目的地及共享停車場(chǎng)設(shè)置坐標(biāo)，結(jié)合其他數(shù)據(jù)整理得到表1～2.假設(shè)車輛單位時(shí)間行駛2.9個(gè)距離步長，如由d5坐標(biāo)(-78.6，82.5)及其目的地C的坐標(biāo)(24.0,-50.0)計(jì)算出二者空間直線距離為102.78個(gè)距離步長，進(jìn)而可知行駛時(shí)間為35分鐘.通過表1發(fā)現(xiàn)d2，d4，d6，d8分別為長期預(yù)約用戶，四者優(yōu)先級(jí)系數(shù)為1.5，享有優(yōu)先匹配車位的權(quán)利.在停車需求數(shù)據(jù)表格中發(fā)現(xiàn)，d3與d6，d8，d2與d9的停放時(shí)間窗類似，存在泊位競(jìng)爭(zhēng)關(guān)系.值得注意的，由于各停車場(chǎng)及目的地位置方位均勻較大差距，表中的出發(fā)時(shí)間不等于車輛的到達(dá)時(shí)間，車輛預(yù)測(cè)到達(dá)不同停車場(chǎng)的時(shí)間不同，算例程序會(huì)假想車輛到達(dá)不同停車場(chǎng)的情況，對(duì)各情況分析比較，在滿足一定用戶的優(yōu)先匹配前提下，保證系統(tǒng)最優(yōu).

除d7外，其余車輛目的地范圍內(nèi)均有兩個(gè)共享停車場(chǎng)、多個(gè)泊位供選擇.如預(yù)測(cè)d10到達(dá)目的地的時(shí)間，由此估算d10到達(dá)p2、p3的時(shí)間.這樣可以更精確地為系統(tǒng)提供匹配參考，對(duì)于兩個(gè)同一時(shí)間開放的泊位來說，可能失去了預(yù)約距離較近泊位的機(jī)會(huì)，但是同樣也可以匹配到距離允許范圍內(nèi)的泊位，提高了系統(tǒng)的匹配成功率.

圖2 網(wǎng)絡(luò)供需分布示意圖

表1 預(yù)約用戶預(yù)約數(shù)據(jù)表

表2 共享泊位開放數(shù)據(jù)表

3.2 算例匹配結(jié)果及分析

網(wǎng)絡(luò)共享泊位分配成功的必要條件要求泊位共享時(shí)間窗與所匹配到的車輛停放時(shí)間沒有沖突，且該泊位處于車輛目的地一定的距離范圍內(nèi).鑒于這兩點(diǎn)對(duì)所有泊位進(jìn)行逐個(gè)分析，確定所有滿足匹配成功兩個(gè)基本條件的匹配組合，見圖3.以s2為例，其泊位共享時(shí)間窗為(09：30，18：00)，共享時(shí)長為8 h 30 min，d1，d5，d4，d7，d10均在其時(shí)間窗范圍內(nèi)，但s2所屬停車場(chǎng)p1均不在d4，d5，d10的目的地允許距離范圍內(nèi)，因此僅d1及d7可與s2建立匹配關(guān)系.

圖3 共享泊位匹配關(guān)系示意圖

系統(tǒng)對(duì)所有可能的結(jié)果進(jìn)行分析比對(duì)，最終得到最優(yōu)的匹配結(jié)果，見圖4.由圖4發(fā)現(xiàn)，10個(gè)預(yù)約用戶有八個(gè)成功匹配到合適的泊位，泊位出租總時(shí)長為，泊位利用率為.雖有兩輛需求車輛未匹配成功，但是所有長期預(yù)約用戶均成功，如d6預(yù)測(cè)到達(dá)停車場(chǎng)p2的時(shí)間為8：30，停放時(shí)長為3 h 50 min,若將d3分配到p2預(yù)測(cè)到達(dá)時(shí)間為08：07，停放時(shí)長4 h 13 min可停放至泊位s1，且停放時(shí)間長于d6，但由于d6進(jìn)行了長期預(yù)約，因此系統(tǒng)放棄了一定的利用效率，對(duì)d6進(jìn)行了優(yōu)先匹配.d8預(yù)測(cè)到達(dá)停車場(chǎng)p1的時(shí)間為08:27，停放時(shí)長為3 h 23 min.

圖4 共享泊位匹配結(jié)果示意圖

由結(jié)果數(shù)據(jù)表明，所提出的匹配優(yōu)化模型是可行的.

1) 模型可以較好地實(shí)現(xiàn)優(yōu)先級(jí)較高的用戶泊位匹配.

2) 考慮優(yōu)先級(jí)的匹配匹配結(jié)果與以泊位利用率為目標(biāo)函數(shù)的匹配結(jié)果有一定差距.

3) 通過算例發(fā)現(xiàn)，經(jīng)模型優(yōu)化后的分配效果可以較好地利用共享停車資源.

4 結(jié) 束 語

研究網(wǎng)絡(luò)區(qū)域內(nèi)的共享停車匹配系統(tǒng)，建立了考慮優(yōu)先級(jí)的網(wǎng)絡(luò)共享停車匹配優(yōu)化模型.模型對(duì)匹配的時(shí)間窗約束問題、距離問題及優(yōu)先級(jí)問題做出了描述，對(duì)不同情形的供需情況進(jìn)行分析.通過整數(shù)規(guī)劃邏輯判斷理論對(duì)模型的改進(jìn)，使得運(yùn)行效率更加高效、準(zhǔn)確.算例結(jié)果表明：模型既能保證泊位總體利用效率的最大化又能兼顧匹配的優(yōu)先級(jí)，模型匹配效果較為理想.同時(shí)在未來研究中，會(huì)綜合考慮以下要素：①考慮到需求車輛的反饋問題；②優(yōu)化行駛路徑及行駛時(shí)間預(yù)測(cè)；③對(duì)共享停車分配的網(wǎng)絡(luò)均衡性做出進(jìn)一步研究.