張利鳳, 慕銀平, 靖富營

(1.成都大學(xué) 旅游與文化產(chǎn)業(yè)學(xué)院,四川 成都 610106; 2.電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院,四川 成都 611731; 3.重慶工商大學(xué) 智能制造服務(wù)國際科技合作基地,重慶 400067)

0 引言

隨著汽車保有量的增加，停車難問題日益凸顯。為緩解停車難問題，各地政府開始倡導(dǎo)共享閑置車位。如2017年太原市發(fā)布的《關(guān)于進(jìn)一步推動(dòng)太原市“互聯(lián)網(wǎng)+停車服務(wù)”的指導(dǎo)意見》指出，辦公區(qū)停車位白天緊張，夜間閑置，而居住區(qū)則相反，因此可采取錯(cuò)時(shí)停車，實(shí)現(xiàn)車位共享。雖然車位共享既為平臺(tái)和車位擁有者帶來了收益，也提高了車位利用率，但是居民在使用共享車位時(shí)，卻出現(xiàn)了未按約定時(shí)間駛離的現(xiàn)象。這一現(xiàn)象導(dǎo)致共享車位的推行遭遇阻力。

實(shí)際中，車位共享平臺(tái)與私家車位擁有者合作，將車位的空閑時(shí)段進(jìn)行回購后，提供給需要車位的顧客[1]。共享平臺(tái)首先發(fā)布車位空閑信息并接受顧客的預(yù)訂。當(dāng)預(yù)訂周期結(jié)束，進(jìn)入服務(wù)周期時(shí)，預(yù)訂用戶可能由于某些特殊原因?qū)е虏荒馨磿r(shí)離開。此時(shí)，平臺(tái)將面臨后一位到達(dá)的預(yù)訂顧客無車位可停的風(fēng)險(xiǎn)，從而面臨較大的損失。因此，本文需解決的問題為：面對預(yù)訂顧客有延時(shí)行為時(shí)，平臺(tái)如何制訂預(yù)訂策略，既能保障平臺(tái)的收益也能減少停車時(shí)間的沖突。

私家車的普及導(dǎo)致了停車位的稀缺，因此車位的預(yù)約分配面臨著挑戰(zhàn)。針對傳統(tǒng)車位預(yù)約分配的文獻(xiàn)，主要是以最大化收益為目標(biāo)構(gòu)建整數(shù)規(guī)劃模型以決策是否應(yīng)該接受顧客的預(yù)訂。許多學(xué)者基于此，分別構(gòu)建靜態(tài)[2～4]和動(dòng)態(tài)[5,6]的優(yōu)化模型對車位的預(yù)訂分配進(jìn)行了研究；Schlote等基于顧客的停車意愿與車位的空置率相關(guān)的情形下，將研究從單個(gè)停車場拓展到了多個(gè)停車場的車位動(dòng)態(tài)分配問題[7]；除此之外，部分研究基于停車資源使用者間的競爭關(guān)系，構(gòu)建了博弈模型對車位的分配進(jìn)行了研究[8,9]。

為緩解停車難問題，車位共享逐漸出現(xiàn)。關(guān)于共享車位分配的研究文獻(xiàn)較少，Shao等首次基于供需信息確定的前提下，構(gòu)建整數(shù)規(guī)劃模型對共享車位預(yù)訂的靜態(tài)分配問題進(jìn)行研究[10]；林小圍等基于動(dòng)態(tài)的車位預(yù)訂供需信息，以停車場利用率最大化為目標(biāo)構(gòu)建整數(shù)規(guī)劃對共享車位的分配問題進(jìn)行研究[11]；Chou等基于需求隨機(jī)的情形下，以最大化停車場收益為目標(biāo)，研究了共享車位動(dòng)態(tài)預(yù)訂控制問題[12]； Wu等通過構(gòu)建非線性規(guī)劃模型研究了位置和服務(wù)質(zhì)量決策問題，并設(shè)計(jì)啟發(fā)式算法求解模型[13]；Yan等構(gòu)建了一種實(shí)時(shí)預(yù)約方式，并提出了多對一的匹配機(jī)制，以更好地利用稀缺的停車資源[14]。上述車位的預(yù)約分配問題均假定顧客會(huì)按時(shí)離開。在實(shí)際中，預(yù)約顧客可能因?yàn)橥话l(fā)情況導(dǎo)致未按照預(yù)訂時(shí)間離開，此時(shí)將可能導(dǎo)致停車時(shí)間沖突。

針對共享時(shí)間沖突的研究，李濤和關(guān)宏志為避免小區(qū)內(nèi)部使用者和外部使用者的時(shí)間相沖突，構(gòu)建優(yōu)化模型研究了如何實(shí)施共享停車[1]；Guo等通過構(gòu)建高斯混合模型求解了平臺(tái)的最大回購量，并通過數(shù)值仿真得到了避免時(shí)間沖突下的共享終止時(shí)刻[15]；路揚(yáng)等以共享時(shí)間不沖突為約束條件討論了共享車位的供需匹配問題[16]。上述研究是以共享車位的時(shí)間不沖突作為約束條件探討車位的匹配問題，而Aydina等針對酒店預(yù)訂顧客存在延長停留時(shí)間的問題進(jìn)行研究[17]。由于酒店可以拒絕延時(shí)申請，因此酒店不會(huì)面臨時(shí)間沖突，而本文將研究因顧客延時(shí)離開導(dǎo)致時(shí)間沖突情形下的共享車位預(yù)訂控制策略。

1 隨機(jī)動(dòng)態(tài)規(guī)劃模型的構(gòu)建

實(shí)施車位共享時(shí)，平臺(tái)將面臨兩個(gè)階段：預(yù)訂階段和服務(wù)階段。在預(yù)訂階段，平臺(tái)決策是否接受顧客的預(yù)訂；在服務(wù)階段，平臺(tái)將車位提供給預(yù)訂顧客。若共享平臺(tái)期初回購的車位數(shù)量為Q[1,15]，首先將預(yù)訂階段離散化為τ個(gè)周期，每個(gè)周期最多允許一個(gè)預(yù)訂到達(dá)[17,18]，再將服務(wù)階段也離散化為T個(gè)周期。

首先在預(yù)訂周期，由于預(yù)訂顧客的停車時(shí)長可能不同，將顧客開始停車的周期i和結(jié)束停車的周期j視為一個(gè)產(chǎn)品(i,j)。用X=(x11,x12,…,x1T,xTT)表示預(yù)訂狀態(tài)，其中xij表示已接受的產(chǎn)品(i,j)的預(yù)訂數(shù)量。每接受一個(gè)產(chǎn)品(i,j)的預(yù)訂，平臺(tái)將獲取凈收益fij。用pijt表示需求為(i,j)的顧客在預(yù)訂周期t出現(xiàn)的概率，Vt(X)表示從預(yù)訂周期到服務(wù)周期結(jié)束的期望總收益，則有以下隨機(jī)動(dòng)態(tài)規(guī)劃(Random Dynamic Programming,簡稱RDP)模型成立:

(1)

(2)

(3)

(6)

顯然，式(1)的邊界條件是Vτ+1(X)=π(X)。其中，式(3)表示服務(wù)周期的收益由延時(shí)收入與懲罰成本構(gòu)成；式(4)表示實(shí)際接受的預(yù)訂數(shù)量與延時(shí)量不超過車位總量；式(5)表示延時(shí)需求服從二項(xiàng)分布。

由于式(1)中預(yù)訂狀態(tài)的維度較高，很難直接進(jìn)行求解。實(shí)際上，若將每一個(gè)服務(wù)周期作為一種資源，產(chǎn)品(i,j)需要耗費(fèi)多種資源，因此該問題屬于網(wǎng)絡(luò)收益管理問題。接下來，我們將分不同情況合理簡化網(wǎng)絡(luò)結(jié)構(gòu)。

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

2.1 延時(shí)需求可以被拒絕的產(chǎn)品分解算法

(7)

(8)

zij≤wij,i=1,2,…,T-1;j=i,i+1,…,T-1

(9)

wij～b(xij,qij),i=1,2,…,T-1;j=i,i+1,…,T-1

(10)

2.1.1 單產(chǎn)品分解模型(Product-Based Decomposition model,簡稱:PBD)構(gòu)建

(11)

(12)

(13)

ηij≤bij,i=1,2,…,T;j=i,i+1,…,T

(14)

bij,ηij∈Z+,i=1,2,…,T;j=i,i+1,…,T

(15)

(16)

其中xij≤bij。若延時(shí)可以被拒絕，則式(16)的邊界條件為:

(17)

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

PBD算法:Step1:初始化參數(shù):預(yù)訂周期和服務(wù)周期τ,T,預(yù)訂到達(dá)率pijt,延時(shí)概率qij,車位容量Q;Step2:當(dāng)預(yù)訂周期的預(yù)訂狀態(tài)為x時(shí),若產(chǎn)品(i,j)到達(dá),將式(16),(17)帶入表達(dá)式(11),求解式(11)～(14),將最優(yōu)解取整得到b?ij,η?ij; Step3:根據(jù)式(16),(17),計(jì)算vtij(xij;b?ij,η?ij)-vtij(xij+1;b?ij,η?ij)。當(dāng)產(chǎn)品(i,j)的預(yù)訂需求到達(dá)時(shí),若fij?vtij(xij;b?ij,η?ij)-vtij(xij+1;b?ij,η?ij),則接受該需求;反之,則拒絕該需求。

2.2 延時(shí)需求不能被拒絕的線性規(guī)劃算法

2.2.1 確定性線性規(guī)劃(Deterministic linear programming,簡稱DLP)模型構(gòu)建

(18)

(21)

實(shí)際中，滿足延時(shí)需求可能會(huì)導(dǎo)致后續(xù)到達(dá)的預(yù)訂需求無車位可停，因此假設(shè)存在一個(gè)容量無限大的虛擬停車場，以存放超過容量的延時(shí)需求[20]。第k個(gè)服務(wù)周期在虛擬停車場停放的車輛數(shù)為

用虛擬停車場的車輛數(shù)作為衡量拒絕已接受預(yù)訂產(chǎn)品數(shù)量的指標(biāo)，構(gòu)建非線性規(guī)劃(Non-linear programming,簡稱NLP)模型如下:

式(22)表示平臺(tái)的收益由平臺(tái)的預(yù)訂收入，延時(shí)收入以及懲罰成本所構(gòu)成。

(23)

求解DLP2模型得到產(chǎn)品預(yù)訂量后，根據(jù)式(26)～(29)計(jì)算可得產(chǎn)品(i,j)的拒絕數(shù)量rij，此時(shí)若平臺(tái)已經(jīng)接受的預(yù)訂量為X時(shí)，平臺(tái)獲得的期望收益可由以下表達(dá)式估計(jì)得到:

(30)

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

為對RDP模型進(jìn)行求解，通過構(gòu)建DLP2模型計(jì)算當(dāng)前預(yù)訂狀態(tài)下的最優(yōu)預(yù)訂量，并采用離散差分的方法計(jì)算機(jī)會(huì)成本，得到預(yù)訂控制策略。設(shè)計(jì)算法如下:

DLP2算法Step1:初始化參數(shù):預(yù)訂周期和服務(wù)周期τ,T,預(yù)訂到達(dá)率pijt,延時(shí)概率qij,車位容量Q;Step2:當(dāng)預(yù)訂周期t的預(yù)訂狀態(tài)為X時(shí),若產(chǎn)品(i,j)到達(dá),求解式(21),(24),(31)～(34)得到xij;再根據(jù)式(26)～(29)計(jì)算得到rij,將X,xij,rij帶入(30)式,計(jì)算R^DLP22,t+1(X)-R^DLP22,t+1(X+ehij)。Step3:若fij?R^DLP22,t+1(X)-R^DLP22,t+1(X+ehij),則接受該需求,更新預(yù)訂狀態(tài)X=X+ehij;否則,拒絕該需求,預(yù)訂狀態(tài)不變。

3 數(shù)值仿真

3.1 算法有效性檢驗(yàn)

根據(jù)圖1可得，當(dāng)車位容量較小時(shí)，DLP2算法有效性低于PBD算法，而車位容量較大時(shí)，兩種算法有效性較好。隨著車位數(shù)量的增加，當(dāng)延時(shí)概率較小時(shí)，DLP2算法獲得的收益大于PBD算法獲得的收益；反之，PBD算法獲得的收益大于DLP2算法獲得的收益。實(shí)際中，延時(shí)收費(fèi)高于預(yù)訂收費(fèi)，顧客會(huì)盡可能避免出現(xiàn)延時(shí)行為，即延時(shí)概率較小。此時(shí)，DLP2算法具有有效性。

圖1 不同延時(shí)概率下各算法的有效性

3.2 參數(shù)靈敏度分析

3.2.1 機(jī)會(huì)成本的靈敏度分析

當(dāng)平臺(tái)面對預(yù)訂顧客到達(dá)時(shí)，決策的關(guān)鍵是對機(jī)會(huì)成本進(jìn)行估計(jì)?？紤]到延時(shí)概率將會(huì)影響服務(wù)周期的產(chǎn)品收益，因此接下來將通過數(shù)值仿真驗(yàn)證延時(shí)概率對不同算法下的機(jī)會(huì)成本的影響，具體仿真結(jié)果見圖2。

圖2 不同延時(shí)概率下的機(jī)會(huì)成本

根據(jù)圖2可得，機(jī)會(huì)成本隨著預(yù)訂周期的推移將減少。隨著延時(shí)概率的增加，DLP2算法拒絕預(yù)訂的可能性增加，因此機(jī)會(huì)成本逐漸增加，而在PBD算法中，隨著延時(shí)概率的增加，需求量增加，機(jī)會(huì)成本將減少。

3.2.2 預(yù)訂周期的靈敏度分析

由于預(yù)訂周期的長短會(huì)影響平臺(tái)的收益，因此，平臺(tái)需要設(shè)置合理的預(yù)訂周期來接受預(yù)訂顧客。接下來將分析不同預(yù)訂周期數(shù)對平臺(tái)收益的影響，具體仿真結(jié)果見圖3～圖4。

圖3 DLP2算法下不同預(yù)訂周期數(shù)的總收益

圖4 PBD算法下不同預(yù)訂周期數(shù)的總收益

根據(jù)圖3～圖4得到，隨著預(yù)訂決策周期數(shù)的增加，平臺(tái)的邊際收益將先增加后減少。因此，預(yù)訂周期存在最優(yōu)值。根據(jù)圖3，圖4還可以得到，車位容量越小，總收益越快達(dá)到穩(wěn)定值，即車位容量與最優(yōu)預(yù)訂周期數(shù)成正比。

3.2.3 預(yù)訂價(jià)格的靈敏度分析

接下來，我們將研究不同的預(yù)訂價(jià)格下平臺(tái)的預(yù)訂控制效果。定義平臺(tái)的服務(wù)率=平臺(tái)接受的預(yù)訂總數(shù)/預(yù)訂需求總數(shù)，車位的利用率=服務(wù)周期接受的車位總數(shù)/車位容量。通過對不同的預(yù)訂價(jià)格進(jìn)行數(shù)值仿真，結(jié)果如圖5所示。

根據(jù)圖5可得，延時(shí)概率增加，平臺(tái)的車位利用率也會(huì)增加。當(dāng)延時(shí)概率較小且預(yù)訂價(jià)格較低時(shí)，DLP2算法下的平臺(tái)服務(wù)率和車位利用率均高于PBD算法下的平臺(tái)服務(wù)率和車位利用率，反之，也成立。隨著延時(shí)概率的增加，DLP2算法下的平臺(tái)服務(wù)率逐漸減小，而PBD算法下的平臺(tái)服務(wù)率卻有所上升。

圖5 不同預(yù)訂價(jià)格下的平臺(tái)服務(wù)率和車位利用率的變化

4 結(jié)論

本文針對車位共享用戶可能存在延時(shí)行為的問題，構(gòu)建了預(yù)訂顧客延時(shí)離開的隨機(jī)動(dòng)態(tài)規(guī)劃模型。由于隨機(jī)動(dòng)態(tài)規(guī)劃模型很難進(jìn)行求解，因此分別構(gòu)建了模型的上下界，并基于延時(shí)能否被拒絕兩種情況設(shè)計(jì)算法求解平臺(tái)的預(yù)訂策略。最后，本文通過大量的數(shù)值仿真研究發(fā)現(xiàn)：隨著預(yù)訂周期數(shù)的增加，總收益將增加，但是當(dāng)預(yù)訂周期數(shù)增加到一定程度時(shí)，總收益將趨于穩(wěn)定，即預(yù)訂周期數(shù)存在最優(yōu)值。同時(shí)，車位數(shù)量越多，則平臺(tái)設(shè)置的預(yù)訂周期越長，反之，則平臺(tái)設(shè)置的預(yù)訂周期越短。隨著延時(shí)概率的增加，若延時(shí)可以被拒絕，平臺(tái)接受預(yù)訂的可能性將增加；而若延時(shí)不可以被拒絕，則平臺(tái)接受預(yù)訂的可能性將減小。雖然隨著延時(shí)概率的增加，DLP2算法下的平臺(tái)服務(wù)率下降，但是在服務(wù)周期，延時(shí)概率增加，則延時(shí)需求增加，因此不論延時(shí)需求是否可以被拒絕，延時(shí)概率增加均會(huì)提高車位的利用率，從而提高平臺(tái)的收益。當(dāng)延時(shí)概率較大或者車位容量較小時(shí)，PBD算法下獲得的收益高于DLP2算法所獲得的收益，此時(shí)，平臺(tái)需激勵(lì)顧客提前提供延時(shí)信息以進(jìn)行決策；反之，平臺(tái)可以采用DLP2算法進(jìn)行預(yù)訂控制決策。本文為共享車位的預(yù)訂分配提供了理論支持和實(shí)踐指導(dǎo)，具有一定的現(xiàn)實(shí)意義。