基于時間窗與優先級的網絡共享停車匹配模型*

路 揚 何勝學 王冬冬 高 蕾

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

0 引 言

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

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

文中設計了網絡共享停車匹配優化系統，并建立了整數非線性規劃模型(INLP).模型綜合考慮了需求車輛的優先級、泊位周轉時間，以及時間窗沖突問題，同時對整個停車網絡的不同供需情形進行分析，使匹配效果更科學、更合理.

1 共享停車問題描述

1.1 共享停車系統

共享停車是指利用停車泊位供需雙方的錯峰使用特性，將某些時段停車場閑置的空余泊位共享對外出租，通過移動終端APP、網絡平臺為駕駛員匹配合理的停車泊位，以提高尋車效率及停車場停車泊位利用率.對于司機而言，可以通過共享停車系統快速尋找到目的地周圍停車泊位，解決停車問題；對于整個系統而言，高效的尋車效率可以減少城市道路中因尋找車位而產生的無效交通流，保證道路通暢，合理的停車匹配可以提高整個共享停車場的利用率，將城市中有限的停車資源利用最大化.本文針對網絡共享停車場的共享停車匹配進行研究，見圖1.

圖1 共享停車網絡匹配流程圖

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

1.2 基本假設

網絡共享停車匹配優化模型在泊位分配過程中遵循以下基本假設：①所有預約車輛到達某處的行駛時間與空間直線距離成比例且相等；②預約用戶離開共享泊位的時間固定且已知；③可對車輛到達目的地的行駛時長進行預測.

2 共享停車網絡匹配模型

2.1 目標函數的建立

為體現分配結果的合理性及科學性，建立了以δdisj為核心的網絡共享供需匹配數學優化模型，對預約停車車輛進行分配.同時對兩種不同情形的供需數量關系進行針對性研究，建立了兩種相應的目標函數，并考慮到優先匹配問題，力求保證優先級較高的長期預約用戶優先獲得車位，構建城市共享停車供需匹配優化模型目標函數為

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

(1)

maxZ2=∑D∑Sαi·

(2)

當網絡區域內的共享泊位處于供不應求狀態下，為了使停車資源得到充分利用建立了目標函數.式(1)表示最大化共享泊位出租時長同時兼顧優先級較高的預約用戶享有優先獲得泊位的權益.其中δdisj為匹配關系變量，表示需求車輛di與供給泊位sj是否匹配成功，當δdisj=1時，需求di與供給sj匹配成功，若未匹配成功，則δdisj=0.

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

2.2 約束條件的建立

(3)

式(3)表示匹配的共享泊位須在需求車輛di的目的地Di的可行范圍內，Q為共享單車范圍最大距離，可根據城市規模或具體情況進行調整.

(4)

li≤cj

(5)

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

∑Sδdisj≤1 ?D

(6)

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

(7)

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

(8)

(9)

(10)

(11)

(12)

(13)

3 案例分析

3.1 算例介紹

文中設計了一個簡單的網絡共享停車匹配系統來檢驗模型的分配效果.算例網絡見圖2，針對共享泊位供不應求的情形下進行了模擬仿真，系統共設置了設有3個共享停車場，5個共享泊位以及10個泊位預約車輛，需求車輛各自開往A，B，C，D四個不同的目的地.示意圖中的位置坐標以A為參考原點，需求車輛分布在網絡的不同方位，對所有車輛、目的地及共享停車場設置坐標，結合其他數據整理得到表1～2.假設車輛單位時間行駛2.9個距離步長，如由d5坐標(-78.6，82.5)及其目的地C的坐標(24.0,-50.0)計算出二者空間直線距離為102.78個距離步長，進而可知行駛時間為35分鐘.通過表1發現d2，d4，d6，d8分別為長期預約用戶，四者優先級系數為1.5，享有優先匹配車位的權利.在停車需求數據表格中發現，d3與d6，d8，d2與d9的停放時間窗類似，存在泊位競爭關系.值得注意的，由于各停車場及目的地位置方位均勻較大差距，表中的出發時間不等于車輛的到達時間，車輛預測到達不同停車場的時間不同，算例程序會假想車輛到達不同停車場的情況，對各情況分析比較，在滿足一定用戶的優先匹配前提下，保證系統最優.

除d7外，其余車輛目的地范圍內均有兩個共享停車場、多個泊位供選擇.如預測d10到達目的地的時間，由此估算d10到達p2、p3的時間.這樣可以更精確地為系統提供匹配參考，對于兩個同一時間開放的泊位來說，可能失去了預約距離較近泊位的機會，但是同樣也可以匹配到距離允許范圍內的泊位，提高了系統的匹配成功率.

圖2 網絡供需分布示意圖

表1 預約用戶預約數據表

表2 共享泊位開放數據表

3.2 算例匹配結果及分析

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

圖3 共享泊位匹配關系示意圖

系統對所有可能的結果進行分析比對，最終得到最優的匹配結果，見圖4.由圖4發現，10個預約用戶有八個成功匹配到合適的泊位，泊位出租總時長為，泊位利用率為.雖有兩輛需求車輛未匹配成功，但是所有長期預約用戶均成功，如d6預測到達停車場p2的時間為8：30，停放時長為3 h 50 min,若將d3分配到p2預測到達時間為08：07，停放時長4 h 13 min可停放至泊位s1，且停放時間長于d6，但由于d6進行了長期預約，因此系統放棄了一定的利用效率，對d6進行了優先匹配.d8預測到達停車場p1的時間為08:27，停放時長為3 h 23 min.

圖4 共享泊位匹配結果示意圖

由結果數據表明，所提出的匹配優化模型是可行的.

1) 模型可以較好地實現優先級較高的用戶泊位匹配.

2) 考慮優先級的匹配匹配結果與以泊位利用率為目標函數的匹配結果有一定差距.

3) 通過算例發現，經模型優化后的分配效果可以較好地利用共享停車資源.

4 結 束 語

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