考慮臨時和預(yù)約需求的共享泊位動態(tài)分配方法

劉永紅，羅霞，胡劍鵬

(西南交通大學(xué)，交通運輸與物流學(xué)院，成都611756)

0 引言

停車難是我國大城市普遍存在的問題。由于有限的城市用地，停車問題不能單純地通過修建新的停車位來解決[1]。除了由于供需之間的不平衡之外，資源的低利用效率，尤其是在空間及時間上利用的不平衡，也容易造成“停車難”。因此，如何合理利用現(xiàn)有停車資源是停車管理的首要難題。

共享停車是利用不同土地開發(fā)強度下不同時段停車需求的差異，將泊位進(jìn)行錯時共享[2]，能夠有效提高停車泊位的利用率。居住區(qū)大多數(shù)出行均為通勤出行，在白天時段泊位多處于空閑狀態(tài)，如果在白天時段將這些空閑的泊位資源共享出去，不僅有助于盤活現(xiàn)有的空閑停車資源，而且能夠在一定程度上緩解停車緊張的問題。目前，共享停車泊位分配的研究從時間窗約束可分為兩類。不考慮時間窗約束的研究主要有：ZOU等[3]以社會福利最大為目標(biāo)，設(shè)計了一種泊位分配機制，可以激勵駕駛員積極參與停車泊位分配過程并提交自己的真實停車信息；XIAO 等[4]通過引入Vickrey-Clarke-Groves(VCG)拍賣機制，并根據(jù)歷史拍賣記錄，對共享泊位進(jìn)行分配；基于VCG 機制，通過物聯(lián)網(wǎng)，

Price-compatible Top Trading Cycles and Chains(PC-TTCCs)和One-sided Vickrey-Clarke-Groves(OVCG)機制也被引入城市停車管理云平臺中管理泊位[5]；BOUDALI等[6]提出一種多準(zhǔn)則的智能預(yù)訂停車系統(tǒng)，通過優(yōu)化駕駛員的停車偏好，對在線泊位進(jìn)行實時分配；陳峻等[7]建立了由決策層和分配層組成的停車共享泊位動態(tài)分配模型，其上層構(gòu)建了泊位共享的4類判斷準(zhǔn)則，下層預(yù)測停車泊位需求時變狀態(tài)并進(jìn)行動態(tài)分配。

考慮時間窗約束的主要有：SHAO 等[8]以停車系統(tǒng)收益最大為目標(biāo)，建立共享停車泊位分配模型，并通過算例驗證了模型的有效性；姚恩建等[9]基于具有顏色約束的加權(quán)頂點著色問題，建立了共享停車泊位資源優(yōu)化配置模型；張文會等[10]建立共享停車泊位利用率最大化和步行距離最小化的雙目標(biāo)泊位分配模型，并采用粒子群算法求解多目標(biāo)；CAI等[11]建立以拒絕數(shù)量最小，停車場收益、泊位占有率最大等為目標(biāo)的兩階段泊位分配方法；ZHAO等[12]在停車位擁有者和停車需求用戶到達(dá)、離去不確定情況下，建立了以數(shù)據(jù)驅(qū)動策略的停車泊位分配方法；JIANG等[13]在考慮了用戶實際停車時間與提交的停車時間不一致以及業(yè)主不按時離開的停車不準(zhǔn)時情景下，以期望收益最大為目標(biāo)建立了0-1混合整數(shù)規(guī)劃共享停車泊位分配模型；孫會君等[14]在綜合考慮租用車位成本，提供停車服務(wù)收入及拒絕用戶潛在損失的基礎(chǔ)上，建立了以共享停車運營商利潤最大化為目標(biāo)的整數(shù)規(guī)劃泊位分配模型；張水潮等[15]在考慮預(yù)約時刻、時長及延時需求的情景下，建立了以平臺收益最大和步行距離最小的泊位分配雙目標(biāo)規(guī)劃模型；何勝學(xué)等[16]在滿足合理共享停車需求下，建立無人駕駛車位移成本最小的共享停車供需匹配模型，并設(shè)計了相應(yīng)的模擬退火算法。

綜上，現(xiàn)有研究對共享停車泊位分配模型目標(biāo)、算法設(shè)計、應(yīng)用場景等方面進(jìn)行了探索，但對于同時存在臨時共享停車需求和提前預(yù)約需求情形下，如何確立泊位匹配優(yōu)先級；以及可通過歷史數(shù)據(jù)預(yù)測未來時段的停車需求時，如何利用預(yù)測數(shù)據(jù)優(yōu)化當(dāng)前時段的泊位分配，從而延伸到所有時段的動態(tài)泊位分配缺乏研究。

在時間窗約束下，現(xiàn)有泊位分配模型研究多關(guān)注當(dāng)前時段的供需，本文則利用滾動時域方法，在當(dāng)前時段泊位分配時，同時考慮其未來幾個時段的供需進(jìn)行統(tǒng)一泊位匹配后，單獨提取只屬于當(dāng)前時段供需結(jié)果，并將當(dāng)前泊位分配結(jié)果反饋到下一時段，實現(xiàn)動態(tài)泊位分配。本文考慮臨時停車需求和提前預(yù)約需求用戶的特點，設(shè)計泊位分配優(yōu)先級權(quán)重。同時，與同質(zhì)處理拒絕用戶的潛在損失不同，本文更加關(guān)注拒絕用戶潛在損失的異質(zhì)性。

1 居住區(qū)共享停車泊位分配模型

1.1 問題描述

居住區(qū)私家車位擁有者根據(jù)自己的使用特性，往往會提前一天通過向共享停車平臺提交車位的空閑時間段及位置等信息的方式，將自己的車位暫時轉(zhuǎn)讓給平臺，即可以認(rèn)為一天內(nèi)的共享停車供給是提前已知。對于停車需求用戶，可以通過手機等設(shè)備在平臺上提前預(yù)約或者臨時發(fā)布自己的停車需求，因此，通常情況下共享停車平臺獲取的是當(dāng)前時間段的共享停車需求，但是，可以根據(jù)共享停車需求歷史數(shù)據(jù)，利用深度學(xué)習(xí)等預(yù)測方法得到未來幾個時段的共享停車需求，即可以認(rèn)為當(dāng)前時段及其未來幾個時段的共享停車需求已知。將一天劃分為T個相等時段，假設(shè)當(dāng)前時段為，本文研究的問題描述為：在已知所有時段的供給，當(dāng)前時段t及直到其未來時段t+f的共享停車需求情況下，如何利用這些信息匹配當(dāng)前時段的供需和如何將時段t的泊位分配結(jié)果反饋到下一時段t+1 掌握t+1,t+2,…,t+f+1 需求情形下的泊位分配中，實現(xiàn)對所有時段的動態(tài)泊位分配。共有臨時停車和提前預(yù)約兩類共享停車需求，基于運營商期望最大化地留住需求，同時，也保證一定的收益。在每個時段考慮泊位分配優(yōu)先級時，對臨時發(fā)布的共享停車需求需優(yōu)先進(jìn)行共享停車位匹配，因為這類停車用戶可以等待平臺匹配泊位結(jié)果的時間比較短，如果不優(yōu)先對其進(jìn)行泊位分配，用戶很可能因為需要一定時間等待服務(wù)，選擇放棄共享停車，從而對共享停車運營商造成一定損失；對于提前預(yù)約的共享停車需求，其發(fā)出需求的時間點(通過手機等設(shè)備在平臺上提交需求的時間點)一般早于實際需要使用的泊位時間點，這些用戶通常能夠接受一定的時間等待服務(wù)，因此，這類用戶的泊位分配優(yōu)先級低于臨時需求用戶。

1.2 共享停車動態(tài)分配模型

1.2.1 共享停車供給

圖1 共享停車供給轉(zhuǎn)化為0-1向量示意Fig.1 Schematic diagram of transformation of shared parking supply into binary variables

1.2.2 共享停車需求

1.2.3 單時段共享泊位分配

圖2 單時段泊位分配Fig.2 Schematic diagram of slots allocation for single time interval

1.2.4 泊位動態(tài)分配流程

將未來時段的供需考慮到當(dāng)前時段的泊位分配中，目的是在動態(tài)分配中利用多時段優(yōu)化取代單時段優(yōu)化，且通過此操作可能將當(dāng)前時段的某些供給預(yù)留給未來時段的某些需求能夠使整體泊位分配更優(yōu)。在利用滾動時域?qū)ο乱粫r段t+1 進(jìn)行泊位分配時，需要更新供給與需求。共享停車需求的停車時段是連續(xù)且唯一的，其需求矩陣可以直接進(jìn)行更新，即

單個共享停車供給在一天內(nèi)可能存在多個供給時間段，對供給矩陣進(jìn)行更新時，需減去t時段泊位分配后占用的泊位供給，得到剩余的泊位供給為

由此得到下一時段t+1 的泊位供給矩陣為為

綜上，即可完成一定時間內(nèi)共享停車供給和需求的動態(tài)泊位分配，本文構(gòu)建的共享泊位動態(tài)分配流程如圖3所示。

圖3 共享泊位動態(tài)分配流程Fig.3 Flow chart of dynamic shared parking spaces allocation

1.2.5 評價指標(biāo)

2 算法

3 共享泊位分配實例

為驗證共享泊位動態(tài)分配模型的有效性和合理性，選擇來源于成都共享停車APP(私家車位APP)2018年11月1日的數(shù)據(jù)對模型進(jìn)行實證研究。包含3個居住小區(qū)，總的供給和需求量分別為79 和72。部分共享停車供給和共享需求信息如表1所示，其中，“*”為隱私信息。在進(jìn)行模型驗證時直接將實際需求假設(shè)為需求的預(yù)測。

表1 模型驗證所用數(shù)據(jù)樣本Table 1 Sample data for model demonstration

各停車場距離目的地距離分別為915，696，518 m，停車費率分別為1.00，1.35，1.12 元?h-1。f取值設(shè)為3，w2=1(w1>w2是為保證可以對臨時共享停車需求進(jìn)行優(yōu)先泊位分配)。為便于描述，用停車場1、停車場2 及停車場3 表示3 個共享停車場，臨時共享停車需求的目標(biāo)用目標(biāo)1表述，提前預(yù)約共享停車需

求的目標(biāo)用目標(biāo)2表述。

3.1 單個研究時段長度對泊位分配的影響

表2 不同研究時段長度下泊位分配后的目標(biāo)值Table 2 Target value after slots allocation under different time intervals length

從表2和圖4可以得出：

圖4 不同研究時段長度下泊位分配后的評價指標(biāo)Fig.4 Evaluation index after slots allocation under different time intervals length

3.2 臨時和提前預(yù)約停車需求比例對泊位分配的影響

為研究臨時停車需求和提前預(yù)約停車需求比例對共享泊位分配的影響，將T設(shè)為24，f設(shè)為3，臨時共享停車需求所占比例的取值從0～1 變化，其他參數(shù)設(shè)置同上。泊位分配后的目標(biāo)值和評價指標(biāo)的結(jié)果如表3和圖5所示。

表3 不同臨時共享停車需求比例下泊位分配后的結(jié)果Table 3 Results after slots allocation under different temporary shared parking demand ratios

圖5 不同臨時共享停車需求比例下泊位分配后的評價指標(biāo)Fig.5 Evaluation index after slots allocation under different temporary shared parking demand ratios

從表3和圖5可以看出：

3.3 未來時段的數(shù)量f 對泊位分配的影響

為研究將當(dāng)前時段的未來幾個時段的供給和可預(yù)測的需求同時考慮的情況下對泊位分配效果的影響，將T設(shè)為24，設(shè)為0.5，變化f的取值，其他參數(shù)設(shè)置同上。不同f取值下目標(biāo)值和評價指標(biāo)的變化情況如表4所示。

表4 不同f 下泊位分配后的結(jié)果Table 4 Results after slots allocation under different f

從表4 可以得出，歸一化后的目標(biāo)2 對f的變化較為敏感，隨著f的增大，總目標(biāo)逐漸減小，整體結(jié)果逐漸變優(yōu)，當(dāng)f取14 時，對比f為0 時，總目標(biāo)優(yōu)化了17.2%。因此，可以得出在泊位進(jìn)行分配時，考慮未來幾個時段的供給和需求會使泊位分配效果更好。為進(jìn)一步驗證本模型所考慮的f的有效性，將需求在原有基礎(chǔ)上增加80%，當(dāng)f取14時，總目標(biāo)對比f取0 時優(yōu)化了13.7%。需求擴大后和需求不擴大時對應(yīng)的歸一化目標(biāo)和評價指標(biāo)的變化情況如圖6所示。

圖6 擴大和不擴大需求后改變f 的結(jié)果對比Fig.6 Comparison of results of changing f after expanding and not expanding demand

從圖6 可以看出，在這兩種情況下，隨著f的增大，總目標(biāo)越優(yōu)。此外，隨著f的增大，共享停車供給的利用率逐漸增加，共享停車需求的拒絕率都有不同程度的減小。進(jìn)一步驗證了本文所提出的將未來幾個時段供需考慮到當(dāng)前時段進(jìn)行泊位分配的合理性。

3.4 懲罰系數(shù)對泊位分配的影響

為比較目標(biāo)1和目標(biāo)2的懲罰系數(shù)對泊位分配的影響，分別將η1和η2的取值固定，變化η2及η1，其他參數(shù)取值同上，其結(jié)果如圖7所示。

從圖7可以得出，當(dāng)固定一個拒絕停車需求的懲罰系數(shù)，改變另一個懲罰系數(shù)時，固定的懲罰系數(shù)對應(yīng)的目標(biāo)變化幅度較小。此外，對比圖7中固定η1和η2的結(jié)果，當(dāng)η2固定時，系統(tǒng)整體擾動(包括目標(biāo)1、目標(biāo)2及總目標(biāo)的變化)相比固定η1時更小，得出η2的變化相比η1的變化對整個泊位分配系統(tǒng)影響更為明顯，因此，在泊位分配中整體優(yōu)化目標(biāo)對η2更為敏感。

圖7 η1 和η2 單獨變化時的目標(biāo)值Fig.7 Target value when η1 and η2 change separately

3.5 目標(biāo)歸一化的權(quán)重系數(shù)對泊位分配的影響

在前面的所有實驗場景中，為保證臨時共享停車需求可以優(yōu)先分配到泊位，w1都是設(shè)為1.5，w2設(shè)為1，為進(jìn)一步驗證w1和w2的相對關(guān)系對泊位分配的影響，將w2和w1分別設(shè)為1，變化w1、w2，其他參數(shù)同上，得到不同取值下泊位分配效果如圖8所示。

圖8 w1 和w2 相對變化時的目標(biāo)值Fig.8 Target value when ratio of w1 and w2 changes

從圖8中可以得出：

4 結(jié)論

用率在某個區(qū)間范圍有較小幅度的波動，而拒絕率基本保持不變。因此，在這種情況下，利用率對于w1和w2的相對大小關(guān)系具有弱相關(guān)性，而拒絕率與兩者的相對大小關(guān)系基本不存在相關(guān)性。

本文建立了同時存在臨時和提前預(yù)約共享停車需求的多居住區(qū)共享停車場泊位分配雙目標(biāo)規(guī)劃模型，在此基礎(chǔ)上提出了共享停車泊位的動態(tài)分配方法。選取泊位利用率、需求拒絕率、需求滿足率、需求時空容量滿足率指標(biāo)對模型的有效性進(jìn)行驗證。研究結(jié)果表明：

(1)臨時和提前預(yù)約共享停車需求比例大致相當(dāng)時，會使泊位分配后總目標(biāo)最優(yōu)；

(2)將未來時段的供需考慮到當(dāng)前時段的泊位分配中，會使泊位分配總目標(biāo)更優(yōu)，考慮的未來時段數(shù)量越多，泊位分配效果越好；

(3)提前預(yù)約停車需求的拒絕懲罰系數(shù)對整個泊位分配影響較臨時停車需求的拒絕懲罰系數(shù)大；

(4)增加提前預(yù)約停車需求部分的權(quán)重，總目標(biāo)更優(yōu)。