姜艷萍, 宋新潮, 邵欣然

(東北大學 工商管理學院, 遼寧 沈陽 110169)

隨私家車保有量的不斷增加,停車難成為城市中普遍存在的問題,受到社會廣泛關注.我國城市中的停車資源總體呈供不應求的趨勢,在大城市中,停車位與私家車的數(shù)量比為0.8∶1,而在中小城市僅為0.5∶1,均遠低于發(fā)達國家1.3∶1的比例[1].停車資源供需矛盾導致諸如亂停車、長時間尋找停車位、交通擁堵、環(huán)境污染等問題的產(chǎn)生.在停車資源捉襟見肘的情形下,城市中卻還有大量私人擁有的停車位經(jīng)常被閑置.據(jù)統(tǒng)計,我國停車位的平均空置率高達50%,即使在一線城市北京、上海、廣州、深圳,車位平均空置率也達到了44.6%[1].因此,通過共享私人閑置車位來提高車位利用率從而解決停車難問題具有很大潛力.

隨互聯(lián)網(wǎng)技術的快速發(fā)展,為私人閑置車位和需求者提供共享服務的電子共享平臺應運而生[2].電子共享平臺根據(jù)私人閑置車位的位置、價格、供應時間和需求者的停車位置、價格、停車時間、可接受步行距離等信息,統(tǒng)一為需求者匹配私人閑置車位.

現(xiàn)實中有一類人,稱之為具有雙角色特點的主體:他們駕車前往目的地附近停車資源供不應求,而在外出期間他們的私人車位被閑置,這類人既有停車資源的使用需求,又有能力提供車位.如果這類主體之間交換使用私人車位,則可以達到通過鼓勵車位擁有者進行車位共享,從而達到降低車位空置率,滿足更多司機停車需求的目的.因此,本文研究了主體具有雙角色特點的私人閑置車位和需求者的匹配問題.Xu等討論了在大城市工作時間內(nèi)的私人停車位匹配問題.通過既有車位需求又能提供車位的主體之間相互交換車位、只提供車位的主體出租其私人閑置車位和只有車位需求的主體租用車位,提出了頂部交易循環(huán)與交易機制、價格兼容的頂部交易循環(huán)與鏈機制[3].根據(jù)主體偏好得到一個主體之間帕累托最優(yōu)匹配方案,使匹配方案穩(wěn)定,但沒有考慮平臺收益和主體目的地及車位所處區(qū)域的供需差異.

Zhang等針對如何對可共享的私有車位進行再分配問題,在考慮供需時間差異的基礎上,建立了以最大化共享車位利用率和最大化停車需求者滿意度為目標的多目標優(yōu)化模型[4].Shao等提出了使車位擁有者和需求者在工作時間共享小區(qū)停車位的整數(shù)線性規(guī)劃模型,并得到使共享平臺利潤最大的匹配方案[5].Guo等針對在一天的特定時間段內(nèi)臨時回購一些私人停車位的停車場運營公司,提出了一種描述司機到達/離開行為的高斯混合模型,通過指導公司選擇回購金額和停止時間,使運營公司利潤最大化[6].Huang 等針對居住區(qū)空置停車位,考慮停車用戶的超時停車行為,建立了以停車效益最大化為目標的共享停車分配模型.根據(jù)停車效益最大化原則,確定最優(yōu)預留車位比例和需要向居民購買的共享車位數(shù)量[7].Zou等提出了一種公共停車位的分配機制,針對不同司機對車位收益感知不同,以社會福利最大化為目標構建優(yōu)化模型,并通過設計支付規(guī)則激勵司機在參與分配的過程中如實報告自己的私人信息[8].段滿珍等建立了居住區(qū)共享停車泊位分配的雙層規(guī)劃模型,通過對高峰泊位空閑指數(shù)差異均值和司機停車后步行距離目標的雙重約束實現(xiàn)了停車資源的有效利用[9].王艷等綜合考慮了動態(tài)多時段的停車需求,提出了一個最小化所有用戶的總步行距離的公共停車場布局優(yōu)化模型[10].Xiao等采用周期性的雙邊拍賣得到一個社會福利最大化的匹配結果,保證了共享停車位主體匹配結果的公平性,并考慮了如何防止主體退出共享市場[11].林小圍等運用合作博弈理論研究了完全信息靜態(tài)停車博弈問題,給出了一個成本合理、公平的分配機制.基于合作博弈的車位分配結果,系統(tǒng)引導先到的車輛將車停在遠處,后到車輛轉(zhuǎn)移支付給先到車輛,以補償其因讓出近處車位而增加的直接停車成本[12].

從已有研究結果可知,大多考慮的是匹配主體只作為需求者或只作為車位供應者的情形.因此,本文針對主體具有雙角色特點的私人閑置車位和需求者的匹配問題,通過參與車位共享的主體之間交換車位,在考慮平臺收益、主體匹配數(shù)量、主體優(yōu)先級等條件下,給出一種能提高車位資源利用率的私人閑置車位與需求者匹配方法.

1 問題描述

基于電子共享平臺,本文研究具有雙角色特點的主體之間的私人閑置車位和需求者匹配問題,主體既有車位需求又能提供私人車位,例如擁有私家車和私人車位的上班族.他們將自己的私人車位在閑置時間內(nèi)通過平臺共享出去,并換得一個位于其目的地附近的可接受車位.

1.1 符號描述

為了描述本文所研究的問題,給出以下量的解釋:

圖1 匹配示意圖

1.2 優(yōu)先級分析和計算

(1)

(2)

(3)

2 私人閑置車位與需求者匹配模型構建與求解

2.1 構建私人閑置車位與需求者匹配優(yōu)化模型

(4)

(5)

(6)

(7)

(8)

(9)

i,j=1,2,…,M,

(10)

(11)

(12)

(13)

xii=0，i=1,2,…,M,

(14)

xij=0或1,i,j=1,2,…,M.

(15)

由于目標函數(shù)式(4)、約束條件式(11)、式(12)和式(15)經(jīng)簡化后構成的模型式(16)～式(19)是經(jīng)典的TSP問題,因此本文建立的多目標優(yōu)化模型式(4)～式(15)也是一個NP-hard問題.

(16)

(17)

(18)

xij=0或1,i,j=1,2,…,M.

(19)

式中,H為非常大的常數(shù).

2.2 算法設計

式(4)～式(15)是一個多目標的0-1整數(shù)規(guī)劃模型,當主體數(shù)量較大時,可采用粒子群算法(PSO)、聲搜索算法(DHS)、NSGA-II算法等啟發(fā)式算法求解.考慮到私人閑置車位與需求者匹配優(yōu)化模型只有3個目標函數(shù),緯度較低,而NSGA-II算法已被證實在求解低維優(yōu)化問題的速度和效率上具有優(yōu)良性能[13-14],因此本文選擇NSGA-II算法求解該模型.

考慮到式(4)～式(15)是離散問題,且約束條件使所建模型的可行解空間具有稀疏性,直接應用NSGA-II算法生成可行解的概率很低,為此對NSGA-II算法進行了改進:①根據(jù)研究問題特點,采用整數(shù)編碼的方式對染色體進行編碼;②為了快速生成初始種群,提出了可行解快速生成方案;③為了保障交叉變異后的染色體依然是可行的,重新設計了染色體變異規(guī)則.本文改進的NSGA-II算法的流程如圖2所示.

圖2 算法流程圖

具體說明如下:

1) 染色體編碼方式:采用整數(shù)編碼方式為染色體進行編碼.一條染色體代表模型的一個解,用變量match_list表示.一條染色體最多有M+1個基因,每個基因可取整數(shù)1,2,…,M,代表一個主體編號,相鄰的兩個基因表示前一個主體占用后一個主體的車位.若match_list對于式(4)～式(15)是可行解,其最后一個元素和第一個元素相同且前M個互不相同,意味著被分配到車位的主體,他自己的車位也必被分配給其他主體;車位被分配出去的主體,也必然會被分配給一個來自其他主體的車位.

2) 快速生成可行解:由于式(4)、式(15)可行解空間比較稀疏,隨機賦值的方式會產(chǎn)生大量不可行解.為了提高生成可行解的速度,本文設計了如下快速生成可行解方案的規(guī)則:

步驟1 找到每個主體作為需求者的可接受車位列表(定義為初始狀態(tài)),初始化空數(shù)組match_list,隨機選擇一個有可接受車位的主體,添加到數(shù)組match_list的末尾,轉(zhuǎn)步驟2;

步驟2 如果match_list為空數(shù)組,轉(zhuǎn)步驟 9；否則轉(zhuǎn)步驟 3;

步驟3 如果match_list最后一個主體i沒有可接受車位,將i從match_list倒數(shù)第二個主體的可接受車位列表中刪除,將i的可接受車位列表恢復至初始狀態(tài),將i從match_list中刪除,轉(zhuǎn)步驟2;否則轉(zhuǎn)步驟 4;

步驟4 將match_list最后一個主體i作為需求者的可接受車位中隨機選擇一個主體j;

步驟5 如果j恰好是match_list中的第一個主體,將j添加到數(shù)組match_list的末尾,轉(zhuǎn)步驟 8;否則轉(zhuǎn)步驟 6;

步驟6 如果j存在于match_list中,將j從i的可接受車位列表中刪除,轉(zhuǎn)步驟 2;否則轉(zhuǎn)步驟 7;

步驟7 將j添加到數(shù)組match_list的末尾,將j的可接受車位列表恢復到初始狀態(tài),轉(zhuǎn)步驟 2;

步驟8 成環(huán),匹配結果為主體match_list[i]作為需求者匹配主體match_list[i+1]的車位,i=1,…,longth(match_list)-1,結束;

步驟9 匹配方案為空,結束.

3) 變異算子:由于約束條件式(7)～式(15)使可行解空間比較稀疏,所以按照傳統(tǒng)NSGA-II算法隨機進行0-1變換容易產(chǎn)生不可行解,因此需要對算法的變異操作進行改進,即選定親代個體后,識別其中未匹配成功的主體,將其對應信息作為輸入,重新運行快速生成可行解算法,得到一個新的可行匹配環(huán)R,將R以概率pm直接作為子代新個體,以概率(1-pm)添加到親代個體中,生成子代新個體.

4) 選擇優(yōu)秀可行解:首先根據(jù)約束條件式(7)～式(15)篩選掉新生成的子代個體中的不可行解,然后將剩余的可行子代與親代采用快速非支配排序和擁擠度[13]進行比較,選擇其中表現(xiàn)優(yōu)良的個體作為下一代親體,繼續(xù)迭代運算.

3 算例分析

假設有20個主體U1,U2,…,U20提交共享信息,具體如表1所示.

表1 主體信息

首先根據(jù)表1中步行距離、價格、時間窗等信息篩選出需求者的可接受車位列表和可接受某車位的需求者列表.利用式(1)、式(2)分別計算主體作為供應者和作為需求者的區(qū)域熱度優(yōu)先級,如表2所示.

表2 可接受對象和優(yōu)先級

為了確定私人閑置車位與需求者的匹配方案,以MATLAB 2018b為編程環(huán)境,在Inter Core i5-8250處理器、內(nèi)存為8 GB的Windows10計算機上實現(xiàn)文中所涉及的算法.經(jīng)過10次實驗,確定算法參數(shù)設計如下:N=13,P=6,種群規(guī)模Ω=100,最大迭代次數(shù)50,交叉概率pc=0.9,變異概率pm=0.1.為了避免單次實驗出現(xiàn)的偶然誤差,運行算法10次,剔除重復解后出現(xiàn)次數(shù)最多的Pareto優(yōu)化結果如圖3所示,對應的Pareto解的私人閑置車位與需求者匹配方案和目標函數(shù)值如表3所示.

根據(jù)圖3和表3可以看出,通過本文所提算法求解模型共獲得了8組Pareto最優(yōu)解.在圖3中,X軸、Y軸和Z軸分別對應目標函數(shù)Z1,Z2和Z3.Z1越大表示平臺收益越高,Z2越大表示匹配成功的主體越多,Z3越大表示有更多的優(yōu)先級、較高的主體匹配成功.由圖3可知,如果共享平臺只考慮最大化平臺收益,可能會導致匹配成功的主體數(shù)量較少或優(yōu)先級較高的主體匹配失敗,這類主體要么其目的地附近的車位資源供過于求,要么其私人閑置車位附近的車位資源供不應求,如圖3中的μ6點所示.雖然該方案平臺收益最高,但無論是主體匹配數(shù)量還是總體優(yōu)先級都比較低.如果只考慮最大化總體優(yōu)先級,可能會影響平臺收益, 如圖3中的μ5點所示.雖然該方案主體的總體優(yōu)先級較高,但相較于其他方案,平臺收益卻處于較低水平.因此,共享平臺在制定主體匹配方案時,既要保障平臺收益,還需要兼顧考慮匹配成功的主體數(shù)量和主體的優(yōu)先級水平.

為了驗證算法的優(yōu)良性,將改進的NSGA-Ⅱ算法、粒子群優(yōu)化(PSO)算法與離散和聲鄰域搜索(DHS)算法進行仿真對比.比較本文的快速生成初始解與隨機生成初始解的生成時間.為了減少單次實驗誤差,每組實驗重復10次,實驗結果如表4所示.

表3 私人閑置車位與需求者匹配方案及目標函數(shù)值

圖3 可行解分布散點圖

由表4可知,本文的快速生成初始解在4種算例中均明顯優(yōu)于隨機方案,特別是在20×20和40×40算例規(guī)模下,在隨機方案中每個有效解的生成時間都超過了1 h.表4中的算例規(guī)模越大,本文的快速生成初始解的優(yōu)勢越明顯.因此,利用隨機方案生成初始解集的PSO算法和 DHS算法不能有效求解私人閑置車位與需求者匹配模型.

基于本文的快速生成初始解,引入Elarbi 等[14]提出的兩個性能指標N(Si)和R(Si)對算法性能進行比較.Si為本文提出的改進NSGA-II算法、PSO算法和DHS算法,ΨSi表示由算法Si得到的非支配解集,|ΨSi|表示算法Si得到的解集中的解的個數(shù),N(Si)表示ΨSi中的解不被ΨS1∪ΨS2∪ΨS3中的解占優(yōu)的解的個數(shù),R(Si)表示算法Si得到的ΨSi中解的質(zhì)量,N(Si)和R(Si)分別為

表4 快速生成初始解與隨機生成初始解的時間

(20)

R(Si)=N(Si)/|ΨSi| .

(21)

式中:N(Si)越大,Si得到的非支配解個數(shù)越多;R(Si)越大,Si得到的非支配解的質(zhì)量越高.

改進的NSGA-II相關參數(shù)設置:Ω=100,最大迭代次數(shù)100,變異概率pm=0.9.DHS相關參數(shù):和聲庫的規(guī)模HMS=50,最大迭代次數(shù)Tmax=500,和聲記憶庫保留概率HMCR=0.85,記憶庫擾動概率PAR=0.3,音調(diào)微調(diào)帶寬BW=1.PSO相關參數(shù)設置:種群規(guī)模N=50,學習因子C1=C2=2,慣性權重ω=0.7,最大速度Vmax=0.8.對比結果如表5所示.

表5 算法性能對比

由表5可知,本文算法與PSO算法和DHS算法相比,在求解小規(guī)模私人閑置車位與需求者匹配問題時,本文算法求得的非支配解與PSO算法和DHS算法求得的非支配解基本一致,而在求解大規(guī)模算例時,本文算法求得的非支配解的N(Si)和R(Si)明顯優(yōu)于PSO算法和DHS算法,而大規(guī)模的私人閑置車位與需求者匹配問題更貼近現(xiàn)實.在求解小規(guī)模和大規(guī)模的私人閑置車位與需求者匹配問題時,本文提出的算法運行時間明顯優(yōu)于PSO算法和DHS算法.綜上所述,本文算法與其他方法相比能夠快速有效地求解私人閑置車位與需求者匹配問題.

4 結 語

1) 將私人閑置車位通過平臺共享給車位需求者可以提高車位利用率,是緩解停車困難的重要思路.針對主體具有雙角色特點的私人閑置車位與需求者匹配問題,構建了以平臺收益最高、主體匹配數(shù)量最大和主體優(yōu)先級最高為目標的多目標優(yōu)化模型.

2) 與已有研究成果相比,考慮了具有雙角色特點的主體之間的匹配及主體的區(qū)域熱度優(yōu)先級,在局部區(qū)域供需不平衡的情況下,通過提高區(qū)域熱度優(yōu)先級較高主體的匹配成功率,吸引這類主體留在共享平臺上.

3) 為了求解多目標優(yōu)化模型,優(yōu)化了NSGA-II算法,優(yōu)化后的NSGA-II算法在要求較高的約束條件下,呈現(xiàn)出求解時間更快和全局尋優(yōu)的特點.在未來研究工作中,進一步考慮一個車位允許與多個需求者匹配或者一個需求者可以先后占用不同車位的問題.