雙角色主體間的私人閑置車位和需求者匹配模型

姜艷萍, 宋新潮, 邵欣然

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

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

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

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

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

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

1 問題描述

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

1.1 符號(hào)描述

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

圖1 匹配示意圖

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

(1)

(2)

(3)

2 私人閑置車位與需求者匹配模型構(gòu)建與求解

2.1 構(gòu)建私人閑置車位與需求者匹配優(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)

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

(16)

(17)

(18)

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

(19)

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

2.2 算法設(shè)計(jì)

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

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

圖2 算法流程圖

具體說明如下:

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

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

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

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

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

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

步驟5 如果j恰好是match_list中的第一個(gè)主體,將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的可接受車位列表恢復(fù)到初始狀態(tài),轉(zhuǎn)步驟 2;

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

步驟9 匹配方案為空,結(jié)束.

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

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

3 算例分析

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

表1 主體信息

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

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

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

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

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

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

圖3 可行解分布散點(diǎn)圖

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

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

表4 快速生成初始解與隨機(jī)生成初始解的時(shí)間

(20)

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

(21)

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

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

表5 算法性能對(duì)比

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

4 結(jié) 語

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

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

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