張水潮，蔡逸飛，黃 銳，周竹萍

(1.寧波工程學院建筑與交通工程學院，浙江寧波315016；2.東南大學交通學院，南京211189；3.南京理工大學自動化學院，南京210094)

0 引 言

停車難是影響城市交通有序運行的一大問題，尤其是城市中心區(qū)亂停車所帶來的交通秩序問題十分嚴重.共享停車為解決停車問題提供了一個新思路，利用停車需求時空分布的差異性，將閑置停車資源共享給需求者，使停車資源最大化被利用.

平臺回購停車位空閑時段，租用給其他用戶的方法是實現(xiàn)共享停車的有效手段.然而實際中存在諸多問題[1]：①從哪些停車場購買，購買多少車位，回購價格，租用價格等如何確定；②收到停車需求后，怎樣判斷是否接受需求，分配至哪個車位，用戶目標停車場沒有車位時是否分配至臨近停車場等問題；③如何處理用戶的違約停放，用戶提出延長停放需求時，如何處理延時和普通需求的關(guān)系.這些問題涉及供給方，平臺及用戶三方利益，決定共享停車能否可持續(xù)發(fā)展.問題①涉及用戶停車行為選擇的研究，問題②和③涉及車位分配問題.

停車行為的研究：Dell[2]等建立混合Logit 模型，發(fā)現(xiàn)收入水平等個體差異是影響停車收費接受程度的重要因素；Simicevic[3]等根據(jù)SP 調(diào)查建立logistic 回歸模型，分析停車收費標準和停車時長限制對出行者停車行為的影響；唐伯明[4]采用BL模型，建立了平日、節(jié)假日城市中心區(qū)路外公共停車場停車選擇行為模型.

現(xiàn)有車位分配問題的研究，通過構(gòu)建多目標優(yōu)化模型確定車位分配.Guo 等[5]采用仿真構(gòu)建停車泊位回購模型，以泊位需求者利益最大為目標，在停車時間約束下獲得停車泊位最優(yōu)使用策略；Shao 等[6]提出二元整數(shù)線性規(guī)劃問題描述共享停車泊位分配問題；張文會[7]建立共享停車泊位利用率最大化和步行距離最小化的雙目標泊位分配模型，采用粒子群算法確定需求分配方案.

上述研究把需求作為一個單獨的數(shù)值，忽視預約需求包含諸多特定屬性，如進入時間，停車時長及延時時長.平臺實際運作時，需要根據(jù)每一時刻停車場的具體占用情況，判斷是否存在車位，哪些需求應(yīng)該被接受，使平臺利益最大化.本文從平臺角度出發(fā)，提出一種基于停車需求的分配方法；以平臺收益及用戶的步行距離作為目標函數(shù)，提出隨機可行解的生成方法，使用蒙特卡洛法求解.

1 泊位分配模型

1.1 基本請求下的分配模型

假設(shè)如下：

(1)適當步行范圍內(nèi)存在多個停車場，用戶需求集中于該范圍內(nèi).

(2)區(qū)域內(nèi)各停車場根據(jù)以往停車占用情況，確定開放時段及可出售車位數(shù).

(3)平臺向區(qū)域內(nèi)停車場購買空閑車位.

(4)平臺收集預約需求，根據(jù)平臺收益判斷需求分配策略.

(5)停車需求分為基本和延時兩種.基本請求時，用戶提供駛?cè)霑r間和停車時長；延時情況，用戶提供延長時間.

集合、變量、參數(shù)的定義如表1所示.

表1 集合、變量、參數(shù)定義Table 1 Definitions of sets,variables and parameters

1.2 模型構(gòu)建

(1)目標函數(shù)1：平臺效益最大化.

式(1)第1 項是租用車位利潤減去回購車位的成本，第2項是停車請求被拒引起的潛在懲罰損失.

約束條件為

式(2)表示任一請求至多分配一個車位，式(3)表示單個泊位同一時刻至多容納一輛車.

(2)目標函數(shù)2：停車步行距離最短.

用戶被分配至非初始目標停車場時，需考慮該停車場與目標停車場的距離.

式(5)表示用戶停車步行距離總和最小.設(shè)最大停車步行距離lmax=350 m.則

采用權(quán)重法處理多目標優(yōu)化問題，最終目標函數(shù)為

約束條件為式(2)～式(4)及式(6).

1.3 延時情況下模型假設(shè)與變量表達

實際應(yīng)用中會出現(xiàn)用戶延長停放時間的情況.假設(shè)：用戶只能進行1 次延時申請；延時請求至少提前1 h，即申請停車時長結(jié)束前1 h.延時情況下集合、參數(shù)與變量如表2所示.

表2 延時情況集合、變量、參數(shù)定義Table 2 Definitions of sets,variables and parameters under delay situation

1.4 模型構(gòu)建

延時需求分配前，使用本文構(gòu)建泊位分配模型進行初始分配，得到平臺初始利潤w1，以及各泊位占用情況znk.在此基礎(chǔ)上，以平臺收益最大化為目標，對延時需求進行分配，即

式(8)第2項是延時停車增加的利潤.

約束條件為

式(9)表示只有當車位da在延時時段全空時，延時請求才可被接受.

2 求解算法

假設(shè)平臺從區(qū)域內(nèi)部停車場h(h∈H)構(gòu)買np個停車位，總計在P個停車場購買N個車位.在初始時刻，車位均為空閑狀態(tài)，區(qū)域內(nèi)共有m個待分配的停車需求，需求解變量為xnm，即確定需求m是否被分配至車位n，為n×m的0-1矩陣.每一列至多有一個1，表示一個需求至多被分配至一個車位中；若該列都為0，表示該需求被拒絕.不同于傳統(tǒng)最優(yōu)問題，該分配問題沒有明顯的下降梯度，且當前階段的分配結(jié)果受制于上一階段殘留的車輛，故采用蒙特卡洛法計算.

隨機生成解集未考慮車位是否被上一時段殘余車輛占據(jù)，故先確定合理的解集生成條件，以縮小解集范圍，使蒙特卡洛法更容易找到最優(yōu)解.

2.1 生成解集

Step 1k=1 時刻，初始化Xnm矩陣為n×m的0 矩陣，xnm∈Xnm，Znk為n×K的0 矩陣，znk∈Znk.vk為k時刻的空閑車位編號，將矩陣Xnm第mk(表示k時段進入停車場的需求)列的任意空閑車位n設(shè)為1，表示時刻1時第mk需求被分配至任意空閑車位n.更新vk，剔除車位n.將k=1 時刻所有需求隨機分配至車位，會出現(xiàn)兩種情況：

情況1k=1 時刻仍有空位，且沒有車輛被分配至同一車位.

情況2k=1 時車位已滿，且有需求被分配至同一車位.

當需求大于供給時任意分配車位，無法判斷哪些需求應(yīng)該被拒絕，先將所有需求隨機分配至一個車位，可能出現(xiàn)情況2.

Step 2若出現(xiàn)情況1，進入Step 3；若出現(xiàn)情況2，尋找k時刻Xnm同一空位出現(xiàn)多個需求的情況，更新Xnm使k時刻的任意空位至多容納一個需求，進入Step 3.

Step 3根據(jù)k時刻的Xnm矩陣，讀取需求mk的停車時長，更新Znk矩陣，計算k+1 時刻的空閑車位編號，更新vk+1，進入Step 4.

Step 4設(shè)k=k+1，將矩陣Xnm第mk列的任意空閑車位n設(shè)為1，更新vk，剔除車位n.同樣出現(xiàn)Step 1中兩種情況，進入Step 2.

Step 5若k=K，結(jié)束算法，生成隨機解Xnm.

此時的Xnm為將k時刻的需求隨機分配至任意空位的結(jié)果，且不存在同一時刻任一空閑車位被分配兩個以上需求的情況.

2.2 確定分配結(jié)果

隨機解生成后，蒙特卡洛法進行L次循環(huán).隨機解集已涵蓋式(2)～式(4)和式(6)，只需帶入式(7)，找出目標函數(shù)最優(yōu)的解集即可.延時情況與非延時情況大致相同，不同在于Step 3 設(shè)置Znk矩陣變量時，要根據(jù)每一時刻的延時需求修正Znk的取值.

3 實 驗

以寧波婦女兒童醫(yī)院停車場為共享停車目標對象，現(xiàn)階段難以收集平臺預約停車信息，故以周邊3 個不同用地性質(zhì)(酒店、住宅、辦公)的停車場作為需求來源，醫(yī)院作為泊位供給方為其余3個地塊的過量停車需求提供泊位.

3.1 停車共享條件判定

(1)泊位占用特性.

整理醫(yī)院1 星期內(nèi)的泊位變化數(shù)據(jù)，如圖1所示.

圖1 日均泊位占用率變化Fig.1 Average daily occupation rate

由圖1 可知：①白天停車高峰集中在07:00 與16:00；夜間停車高峰集中在19:00.②13:00 停車需求減少，出現(xiàn)低谷；21:00 之后停車需求急劇減少，[22:00,06:00]停車需求一直處于較低水平.

(2)車輛駛?cè)?駛離特性.

圖2為日均車輛凈增長量變化.

由圖2可知：①車輛駛?cè)敫叻迤跒?6:00、19:00.②車輛駛離有3個高峰期，即[11:00，13:00]，[17:00,18:00]，[21:00,22:00].③夜間22:00開始，駛出量降低，[00:00,06:00]駛離車輛數(shù)較少，幾乎不存在車輛駛?cè)?夜間車輛駛?cè)?駛離特征與泊位占有率在低水平相符合.

圖2 日均車輛凈增長量變化Fig.2 Average daily net increase of vehicles

(3)停放時長特性.

車輛停放時長概率分布如圖3所示.大部分車輛停放時長在1.5 h以內(nèi)，超過4 h極少.

綜上，將[11:00，13:00]，[17:00, 18:00]作為短時泊位共享時段，[22:00,07:00]作為長時泊位共享時段.

圖3 停放時長概率分布Fig.3 Distribution of parking time

3.2 共享泊位分配計算

假設(shè)酒店、住宅、辦公樓泊位已滿，到3個目的地的車輛均通過共享停車平臺分配至醫(yī)院.各時段的共享泊位，各目的地在共享開放窗口的停車需求如表3所示.

表3 各時段共享泊位供給及停車需求Table 3 Parking berth supply and demand under different time periods

短時共享時間太短，故以長時共享為例.變量取值為：時段為1 h，p=6 元/h，b=2.5 元/h；懲罰因子α=0.5，權(quán)重α1=0.8,α2=0.2 ；酒店距離醫(yī)院348 m，住宅區(qū)距離醫(yī)院300 m；各需求駛?cè)霑r間服從負指數(shù)分布，停車時長服從標準正態(tài)分布，需求總時長為898 h，如圖4 所示；延時模型中，延時需求為停車總需求的10%，平均延時2 h；用戶至少提前1 h提交延時請求，且延時停放結(jié)束時間不能超過共享時間窗口.

Guo[5]的研究中，采用3 000次循環(huán)確保蒙特卡洛法得到最優(yōu)解.為確保準確性，本文分別對非延時及延時進行了10 000、20 000 及30 000 次實驗.對各次實驗得到的目標值從小到大排序，結(jié)果如圖5所示.

不同實驗次數(shù)下平臺效益最大值一致，說明10 000次實驗已能得到最優(yōu)值.效益值呈階梯狀上升，模型目標是在需求已知的情況下，尋找最優(yōu)的車位和需求的配對組合，使停車場容納盡可能多的停車時長.因此，當一種新組合能多容納一個時長時，效益值會上升，將隨機解效益值排序后，形成階梯狀的形式.

圖4 酒店及住宅停車場的初始停車需求分布Fig.4 Distribution of parking demands when first destination are hotel and residence

延時情況的最低效益值為2 954.3，最優(yōu)值為3 313.2，總收益提升12.15%；非延時情況的最低值為2 721.4，最優(yōu)值為3 248.7，提升19.37%.總計有898個車時需求，醫(yī)院100個車位9 h最多提供900車時的停車供給，使部分需求被拒絕.非延時和延時情況如圖6和圖7所示.觀察到00:00以后無論延時還是非延時情況，停車場已基本無空位，需要判斷接受哪些常規(guī)需求和延時需求，并判斷最優(yōu)組合.

非延時情況占用車時778 h，26 個總計120 個車時的停車需求被拒絕；延時情況占用車時761 h，30個總計154個車時的停車需求被拒絕，沒有延時請求被拒絕.沒有延時請求時，占用的車時高于有延時請求，這是由于延時請求收費遠高于基本請求，最優(yōu)解會優(yōu)先滿足延時請求，然后考慮非延時請求，使拒絕的基本停車需求高于非延時情況，造成一定的車位浪費，但這更符合平臺的趨利性.

4 結(jié) 論

本文以共享停車平臺收益及用戶從停車場至目的地步行距離為優(yōu)化目標，構(gòu)建預約請求下，共享停車平臺的泊位分配模型.平臺從自身利益及保證用戶需求兩個角度出發(fā)，確定最優(yōu)需求分配策略.運用縮小解集的蒙特卡洛算法，以醫(yī)院停車場為案例，驗證模型及算法在得到最優(yōu)解時的準確性.針對現(xiàn)狀共享停車分配研究的不足，根據(jù)停車請求特性，綜合考慮停車請求的進入時刻，停放時長，以及延時請求的情況，提出基于蒙特卡洛法的車位分配方法，幫助停車平臺確定最優(yōu)的車位 分配策略，為共享停車的發(fā)展提供一定技術(shù)支持.

圖6 非延時情況的車位占據(jù)情況Fig.6 Berth occupation of no delay situation

圖7 延時情況的車位占據(jù)情況Fig.7 Berth occupation of delay situation

本文收集一定時間段內(nèi)的所有需求并進行分配，需求必須在該時間段之前全部提交，且無法更改，限制了用戶選擇；另外，未考慮價格因素對共享停車需求的刺激作用.在未來研究中，期望構(gòu)建以價格為上層變量，用戶對價格的反應(yīng)為下層變量的動態(tài)請求分配模型.