劉旭東，張學(xué)杰，張驥先，李偉東，張 靜

(1.云南大學(xué) 信息學(xué)院，昆明 650500； 2.云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，昆明 650500)(*通信作者電子郵箱denonji@163.com)

0 引言

汽車租賃公司通過購買車輛，然后將車輛共享給用戶使用，汽車租賃出行是一種經(jīng)濟(jì)環(huán)保的出行方式。目前國內(nèi)汽車租賃市場已成規(guī)模，據(jù)文獻(xiàn)[1]顯示，2015年中國汽車租賃市場依靠網(wǎng)絡(luò)媒介的交易額超過90億元，線下交易額達(dá)356億元，而且汽車租賃市場的需求仍然巨大。另據(jù)文獻(xiàn)[2]顯示，2016年中國汽車銷售量達(dá)到2 802.8萬輛，汽車保有量近2億輛，將為租車市場提供強(qiáng)有力支持。同時，大城市由于交通擁堵等問題，政府出臺限號限行等措施來限制私家車的出行，也為租車市場的發(fā)展創(chuàng)造了良好的環(huán)境。此外，隨著國內(nèi)旅游業(yè)的迅猛發(fā)展，更加刺激著租車行業(yè)加速發(fā)展，可以預(yù)見汽車租賃行業(yè)的發(fā)展?jié)摿薮蟆?/p>

在有限的車輛使用年限內(nèi)提升車輛的使用效率是汽車租賃公司主要的營收方式，但是目前線上汽車租賃平臺主要通過傳統(tǒng)的固定價格對車輛進(jìn)行先來先服務(wù)的出租方式，車輛不能得到最有效的利用。首先，車輛采用傳統(tǒng)的固定價格定價方式，租賃公司為了保證自己在每個時段都有利潤，必須要維持較高的租賃價格，超過了用戶預(yù)期，傷害用戶積極性，將造成平臺中車輛的閑置；其次，固定的價格不能夠及時反映用戶車輛供需關(guān)系，造成需求量大時車輛緊缺不能租出高價格，而空閑時車輛不能降價出租導(dǎo)致車輛閑置；最后，先來先服務(wù)的分配方式雖然可以保證分配的時效性，但是不能獲得整體分配結(jié)果的最優(yōu)，而且車輛的租賃周期最短也為一天，對實時性要求并不高。

所以本文將線上汽車租賃平臺目前的問題總結(jié)為車輛分配的不優(yōu)化與車輛定價的不合理。若將線上汽車租賃公司的車輛分配與定價問題進(jìn)行合理改進(jìn)，將為其提供更多的利潤，更能加快汽車租賃市場的合理發(fā)展。

為了解決線上汽車租賃平臺存在的問題，本文提出了基于競價的租賃車輛資源分配和定價機(jī)制，主要包含三個方面：

1)可信的多需求拍賣機(jī)制設(shè)計。本文為在線汽車租賃平臺設(shè)計了多需求的拍賣機(jī)制，用戶可以對不同理想車輛提出自己的競價，但最終結(jié)果只會滿足每個用戶一種車型。系統(tǒng)通過用戶提交的請求來計算分配車輛，并且在線上汽車租賃平臺中采用拍賣機(jī)制來實現(xiàn)車輛資源的分配和定價具有天然的優(yōu)勢，網(wǎng)絡(luò)線上提交需求的過程，類似于密封拍賣，這也將保證用戶提交的數(shù)據(jù)私密性。最后通過VCG(Vickrey-Clarke-Groves)的價格計算來保證拍賣機(jī)制的可信性。

2)基于網(wǎng)絡(luò)流的車輛資源分配。車輛資源分配是一個RAP(Resource Allocation Problem)，需要先收集用戶需求數(shù)據(jù)，然后使用合理的分配方法獲得最優(yōu)的利益。本文首先抽象出了租賃車輛分配問題數(shù)學(xué)模型，然后選擇將問題等價于網(wǎng)絡(luò)流圖方式來找到該問題的最優(yōu)解，解決車輛的最優(yōu)分配問題。

3)合理的車輛資源定價。在拍賣機(jī)制中，定價問題是一個很重要的問題，既要考慮平臺利益，也要滿足價格的可信，公認(rèn)的可信拍賣機(jī)制就是文獻(xiàn)[3-5]提出的基于VCG機(jī)制的設(shè)計，并已被證明是可以保證在滿足社會福利最大條件的同時又能夠鼓勵可信競價的典型機(jī)制，所以本文將采用VCG的定價機(jī)制來計算用戶的最終支付價格。

1 相關(guān)工作

本文使用競價的方式解決線上汽車租賃平臺的車輛分配和車輛定價問題。對于拍賣機(jī)制的研究應(yīng)用有很多，但在汽車租賃方向還沒有相關(guān)的研究工作；車輛分配與調(diào)度問題在網(wǎng)約車平臺中研究較多，而定價機(jī)制則研究得較少。

1)拍賣機(jī)制。使用拍賣機(jī)制對商品進(jìn)行定價已經(jīng)持續(xù)了很長時間，而其中最重要的研究無疑是由Myerson[6]提出的最優(yōu)拍賣機(jī)制。拍賣的機(jī)制在現(xiàn)代已經(jīng)成功應(yīng)用于很多商業(yè)領(lǐng)域，并提供了不菲的商業(yè)利潤。如在美國聯(lián)邦通信委員會(Federal Communications Commission，F(xiàn)CC)的頻譜拍賣資料[7]中顯示，截至2015年9月30日，F(xiàn)CC已經(jīng)完成了87次頻譜拍賣，拍賣所得總金額超過949億美元。在廣告競價拍賣中，Google依靠關(guān)鍵詞競價拍賣的收益占到了其90%以上的收益，并且使用第二競價進(jìn)行關(guān)鍵詞的拍賣競價。同樣，作為全球最大的社交網(wǎng)站Facebook則主要采用基于VCG的拍賣競價方式進(jìn)行廣告的拍賣，并獲得了巨大的收益。而最近在云資源平臺快速發(fā)展的情況下，拍賣機(jī)制也被廣泛應(yīng)用于網(wǎng)絡(luò)云資源的競價拍賣中，其中最好的例子就是亞馬遜彈性計算云(Elastic Compute Cloud，EC2)云資源平臺。張驥先等[8]提出了一種支持云計算虛擬資源分配的可信多需求機(jī)制，可以使資源提供商獲得更大的收益，并且得到了很好的實驗效果。此外，Zaman等[9]提出了基于聯(lián)合競拍的動態(tài)云資源分配，將云資源中如內(nèi)存、CPU、硬盤等作為用戶爭奪的資源，然后使用拍賣機(jī)制來進(jìn)行動態(tài)的云資源分配與定價。在云資源平臺的不斷發(fā)展中，文獻(xiàn)[10]提出了雙向拍賣的云資源拍賣機(jī)制，而文獻(xiàn)[11]提出了多個云平臺協(xié)同共享資源的聯(lián)盟云資源拍賣機(jī)制，即用戶提交的資源請求可以被多個平臺接受并協(xié)同分配，所以在本文的基礎(chǔ)上，未來可對競價租車雙向拍賣或者網(wǎng)點(diǎn)協(xié)同合作拍賣進(jìn)行相關(guān)研究。

盡管拍賣已經(jīng)成功應(yīng)用于很多領(lǐng)域，但目前還沒有被應(yīng)用在線上汽車租賃平臺中，本文則考慮構(gòu)建可以在線上汽車租賃平臺中使用的模型。

2)資源分配。車輛分配問題在網(wǎng)約車中使用得較多，網(wǎng)約車在國內(nèi)互聯(lián)網(wǎng)的高速發(fā)展下獲得了極大的發(fā)展，甚至改變了人們的交通出行方式，如滴滴等交通出行應(yīng)用的興起，越來越多的人使用手機(jī)叫車出行，使得網(wǎng)約車成為當(dāng)代人交通出行中不可缺少的方式。而研究發(fā)現(xiàn)，線上汽車租賃與網(wǎng)約車的形式基本相同，都是通過用戶發(fā)出需求，平臺計算分配車輛給用戶，最后通過平臺來支付完成訂單。但是它們所追求的目的不同，網(wǎng)約車更注重訂單的實效性，線上汽車租賃將更多地考慮平臺車輛是否能夠合理有效分配。目前線上汽車租賃的相關(guān)研究較少，可以通過類比網(wǎng)約車車輛資源分配問題來討論線上汽車租賃車輛的分配問題。

網(wǎng)約車的車輛資源分配相關(guān)內(nèi)容主要集中在用戶訂單分配與車輛的分配。Zhang等[12]在解決網(wǎng)約車的訂單分配中提出了使用就近分配原則，即當(dāng)出現(xiàn)車輛競爭訂單時，對訂單進(jìn)行了就近調(diào)度。就近調(diào)度的好處在于可以在短時間內(nèi)完成訂單的分配，但是存在就近調(diào)度訂單不一定是全局最優(yōu)訂單的問題，如一個用戶分配到距離其最近的車，而附近的車輛可能需要走更遠(yuǎn)的距離去接其他乘客。而Seow等[13]提出的NtuCab則追求訂單等待時間和訂單安排接送距離的最小化，將每個代理機(jī)構(gòu)看作是一個計算單元，每個計算單元擁有N個訂單/車輛對，每個訂單只能滿足一個車輛，而當(dāng)司機(jī)不愿意接單時，會將訂單發(fā)給另外一輛車。對于車輛的調(diào)度，Glaschenko等[14]設(shè)計了出租車實時調(diào)度系統(tǒng)，由于車輛實時調(diào)度系統(tǒng)有很多復(fù)雜性問題，如車輛多、訂單大等，造成了解決調(diào)度問題的困難，該文獻(xiàn)中使用元啟發(fā)算法Meta-heuristics解決調(diào)度問題，并且計算的時間在可接受范圍之內(nèi)。但是在線上汽車租賃平臺中，并不需要實時調(diào)度，更多地是要尋找最優(yōu)的分配方案，所以這些網(wǎng)約車調(diào)度方案并不適用。同時，使用競價的方式進(jìn)行資源分配已經(jīng)成功應(yīng)用在了云資源中，如Liu 等[15]提出了使用競價對不同虛擬機(jī)進(jìn)行分配的方法。

3)車輛的定價。在近代拍賣機(jī)制研究中已經(jīng)對定價方式已經(jīng)作了深入的研究。Maskin等[16]認(rèn)為要考慮規(guī)避用戶的風(fēng)險，并認(rèn)為第一競價就是最有利的標(biāo)準(zhǔn)拍賣機(jī)制。而Milgrom等[17]分析了拍賣競價并不是孤立的，用戶的競價會根據(jù)其他人的競價而改變，并表明了最有利的標(biāo)準(zhǔn)拍賣競價是第二競價，而第二競價也被廣泛地應(yīng)用到了基于競拍的應(yīng)用中。而由Vickrey、Clarke和Groves三人共同提出的VCG拍賣定價機(jī)制無疑是定價機(jī)制的里程碑，已經(jīng)被證明是最有效的拍賣定價機(jī)制，VCG拍賣機(jī)制的出現(xiàn)提供了一種可信機(jī)制的拍賣框架，并且應(yīng)用于諸多領(lǐng)域，如文獻(xiàn)[18]將VCG機(jī)制應(yīng)用在P2P存儲系統(tǒng)中，使得競價者完全根據(jù)自己的意愿來進(jìn)行出價，而沒有提供虛假競價的理由，即用戶提交虛假競價時不會得到好處。

綜上，基于競價的機(jī)制設(shè)計已經(jīng)應(yīng)用于不少領(lǐng)域，但目前還沒有應(yīng)用在汽車租賃平臺中。將競價機(jī)制應(yīng)用到線上汽車租賃平臺中，車輛的合理分配與車輛價格制定問題都是需要解決的重點(diǎn)與難題。本文研究一種可信的競價機(jī)制，旨在解決車輛分配與車輛的價格制定問題。

2 系統(tǒng)模型和前期準(zhǔn)備

本文借鑒云平臺中的資源模型提出了租賃汽車分配的數(shù)學(xué)模型，該模型主要根據(jù)競價模型抽象了汽車租賃平臺的車輛資源與參與競價用戶需求的情況。之后，根據(jù)該數(shù)學(xué)模型構(gòu)造了最大社會福利的數(shù)學(xué)規(guī)劃函數(shù)，根據(jù)汽車租賃的現(xiàn)實情況，本文考慮車輛總數(shù)與用戶最多只能競價成功一輛車的基本限制條件。以后也可以研究增加時間、地點(diǎn)等多維度的限制條件，增加模型的實用性。

其次，用戶i∈U將根據(jù)平臺提供的信息提交自己的車輛車型需求請求，記用戶i提交的請求為Qi=(Ri,Bi)。其中：Ri=(ri1,ri2,…,rit),rij∈{0,1}(j=1,2,…,t)表示用戶對每種車型的請求；Bi=(bi1,bi2,…,bit),bij∈Ri表示用戶對不同車型的競價。

為了清晰描述模型信息，本文根據(jù)系統(tǒng)模型構(gòu)建了如表1所示的汽車租賃平臺車輛資源以及用戶競價請求來舉例說明本文的數(shù)據(jù)模型。

表1 汽車租賃平臺車輛資源與用戶i提交的需求

由表1可知，平臺共提供三種車型，每種車型的數(shù)量分別為m1=2,m2=3,m3=1,每種車型閑置成本為c1=10，c2=15，c3=20。用戶需要根據(jù)不同車型的情況來提出不同的請求，如表1中用戶提交的請求為Ri=(1,0,1),表示選擇車型1和車型3，Bi=(29,0,35),即用戶對車型1的出價為29，車型2的出價為0，車型3的出價為35，所以，該用戶提出的請求為Qi=((1,0,1),(29,0,35))。

汽車租賃平臺想要達(dá)到的目標(biāo)就是如何分配這些有限的車輛資源給用戶，能夠在盡量滿足用戶需求的同時，還能使平臺獲得的利潤最高。構(gòu)建數(shù)學(xué)規(guī)劃模型如式(1)所示：

(1)

(2)

(3)

規(guī)劃函數(shù)(1)表示：循環(huán)每個用戶提交的對每種車型的請求，規(guī)劃出一種能夠使得汽車租賃平臺利益最高的方案。

規(guī)劃函數(shù)(1)的限定條件分別是：式(2)表示每個用戶只能滿足一個車型，式(3)表示每種車型滿足的用戶數(shù)目不能大于平臺提供的該種車型的數(shù)量。

3 基于競價的車輛租賃資源分配及定價機(jī)制

由于式(1)中的數(shù)學(xué)規(guī)劃模型與基于競拍的拍賣機(jī)制的數(shù)學(xué)模型基本一致，因此考慮使用基于競價的拍賣機(jī)制來解決這一問題。本文設(shè)計了一個在線汽車租賃算法來計算租車平臺中車輛的分配與用戶需要支付的價格。車輛的分配算法利用基于網(wǎng)絡(luò)流的分配算法求解數(shù)學(xué)規(guī)劃(1)中的規(guī)劃最優(yōu)解，即拍賣模型中的社會福利最大解。該算法主要是基于最小費(fèi)用最大流的網(wǎng)絡(luò)流算法，獲得最大收益(最小費(fèi)用取反)的同時盡量多地滿足用戶的(最大流)需求，用來分配用戶的線上汽車租賃的提交請求。

3.1 租賃車輛VCG拍賣算法

按照最優(yōu)機(jī)制設(shè)計，本文提出了租賃車輛VCG拍賣(VCG-Car Rental Auction, VCG-CRA)算法。算法主要包括兩個部分：首先是租賃車輛分配算法(CRA_Allocation)，根據(jù)用戶提交的請求進(jìn)行車輛的分配；然后通過租賃車輛定價算法(CRA_Pay)計算用戶需要支付的價格。

算法1 VCG-CRA。

輸入 車型T包括每種車型的數(shù)量mj,車輛的使用成本cj；所有用戶的需求信息Q=[(R1,B1),(R2,B2),…,(Rn,Bn)];

輸出 參與競價被選中用戶及對應(yīng)車輛X=[x10x11…x1t…xnt],總社會福利SW，被選中的用戶需要支付的價格P=[p1p2…pn]。

{用戶請求預(yù)處理}

1)

for allQi,i∈Udo

2)

ifbit

3)

rit=0

4)

bit=0

5)

end if

6)

end for

{車輛分配}

7)

X,SW←CRA_Allocation(Q,T)

{價格計算}

8)

P←CRA_Pay(Q,X,SW,P)

由算法1可知，首先需要等待收集所有用戶提交的用車請求，之后需要對用戶競價進(jìn)行預(yù)處理，即當(dāng)用戶對某一個車型出價低于車輛的閑置成本價時，將此用戶的競價數(shù)據(jù)直接改為0，即刪除這個用戶對此車型的競價(1)～6)行)。這樣既保證了后面計算的有效性，也提高了之后算法的計算效率。然后，使用CRA_Allocation算法進(jìn)行車輛的分配。最后再使用CRA_Pay算法來計算每個用戶真正需要支付的價格。

3.2 基于網(wǎng)絡(luò)流的車輛分配算法

根據(jù)式(1)中的數(shù)學(xué)模型與式(2)和(3)的限制條件，要解決的問題就是在車輛限制條件下求解得到最大的費(fèi)用流，這與經(jīng)濟(jì)學(xué)中的最小費(fèi)用最大流問題相似。最小費(fèi)用最大流的網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個限制的條件，研究試圖尋找出：流量從起點(diǎn)S到終點(diǎn)E，如何選擇路徑、分配經(jīng)過路徑的流量，可以在流量最大的前提下，達(dá)到所用費(fèi)用最小的要求。本文模型的要求是要達(dá)到的所有費(fèi)用最大，所以將每條路徑中的“費(fèi)用”都取負(fù)值，而整體的模型要求就轉(zhuǎn)化為最小費(fèi)用最大流的模型。圖1是根據(jù)本文模型構(gòu)造的最小費(fèi)用最大流的有向圖。

圖1 最小費(fèi)用最大流(容量，費(fèi)用)有向圖

由圖1可以看到，該圖由多條從起點(diǎn)頂點(diǎn)S到終點(diǎn)頂點(diǎn)E的不同路徑組成，每條邊的內(nèi)容分別指經(jīng)過這條邊的容量和費(fèi)用，第一組頂點(diǎn)從1到n表示的是用戶，第二組頂點(diǎn)從1到t表示的是車型。最小費(fèi)用最大流算法的目的就是找出滿足容量限制和費(fèi)用最小(本文的需求其實是要費(fèi)用最大，而該算法計算的是最小費(fèi)用，剛好相反，所以這里將用戶費(fèi)用邊取負(fù)值，即可按照最小費(fèi)用最大流求解，之后再將結(jié)果取反即可)的路徑的一個集合，這個集合剛好就是滿足本文模型分配的要求，即滿足平臺利益的同時又不超過車輛的數(shù)目。

定理1 數(shù)學(xué)規(guī)劃(1)的最優(yōu)解的目標(biāo)函數(shù)值與圖1中的最小費(fèi)用最大流的目標(biāo)函數(shù)值的絕對值相同。

因此，數(shù)學(xué)規(guī)劃(1)的任一可行解對應(yīng)于圖1的一個可行流，且其目標(biāo)函數(shù)值的絕對值相同。

證畢。

求解最小費(fèi)用最大流算法采用了貪心法的思想，即每次找到從起點(diǎn)S到終點(diǎn)E的一條路徑，判斷該路徑是否為增加流量后的費(fèi)用最小的路徑，直到?jīng)]有這樣的路徑。在尋找起點(diǎn)S到終點(diǎn)E的路徑時，由于網(wǎng)絡(luò)中“費(fèi)用”都是負(fù)值，所以本文算法將使用文獻(xiàn)[19]提出的最短路徑快速算法(Shortest Path Faster Algorithm， SPFA)來實現(xiàn)。

定理2 最小費(fèi)用最大流得到最優(yōu)解是數(shù)學(xué)規(guī)劃(1)的最優(yōu)分配算法。

證明 最小費(fèi)用最大流通過在所有增廣路徑(可行流)中尋找單源最短路徑(最小費(fèi)用)，最終將找到符合限制的最優(yōu)解，而最小費(fèi)用最大流與數(shù)學(xué)規(guī)劃(1)等價，所以將計算得到數(shù)學(xué)規(guī)劃模型的最優(yōu)解。

最小費(fèi)用最大流的CRA_Allocation算法如算法2所示。首先需要初始化圖數(shù)據(jù)(1)～23)行)，將平臺資源情況與收集的用戶請求轉(zhuǎn)化為鄰接矩陣G；之后通過尋找圖中所有滿足流量的路徑(最大流)，再使用SPFA單源最短路徑算法尋找出單元最短路徑(最小費(fèi)用)，并保存路徑到圖G*(24)～26)行)；然后計算將圖G*轉(zhuǎn)化為車輛分配向量X與車輛分配價格向量P(27)行)，再計算當(dāng)前分配的資源社會福利值SW(28)～31)行)；最后返回車輛分配向量X、車輛分配價格向量P與當(dāng)前分配的資源社會福利值SW。

算法2 CRA_Allocation算法。

輸入 車型T包括每種車型的數(shù)量mj,車輛的使用成本cj；所有用戶的需求信息Q=[(R1,B1),(R2,B2),…,(Rn,Bn)]；

輸出 參與競價被選中用戶及對應(yīng)車輛X=[x10x11…x1t…xnt],總社會福利SW。

{初始化圖數(shù)據(jù)，鄰接矩陣G=(V,E)}

1)

G←0

2)

for allU,i∈Udo

{源點(diǎn)到車型，節(jié)點(diǎn)矩陣N，費(fèi)用矩陣C，流量矩陣W}

3)

G←N[0][i+1]=1;

4)

G←C[0][i+1]=0;

5)

G←W[0][i+1]=1;

6)

end for

7)

for allQi,i∈U,j∈Tdo

{用戶到車輛，節(jié)點(diǎn)矩陣N，費(fèi)用矩陣C，流量矩陣W}

8)

ifrij=1 then

9)

G←N[i][n+j]=1;

10)

G←C[i][n+j]=-bij;

11)

G←W[i][n+j]=1;

12)

end if

13)

end for

14)

for allT,j∈Tdo

{車型到終點(diǎn)，節(jié)點(diǎn)矩陣N，費(fèi)用矩陣C，流量矩陣W}

15)

G←N[n+j][n+t]=1;

16)

G←C[n+j][n+t]=0;

17)

G←W[n+j][n+t]=mj;

18)

end for

{尋找圖G中所有滿足流量限制的增廣路徑l(最大流)}

19)

for allG,l∈Gdo

{增廣路徑不存在則跳出循環(huán)}

20)

ifl==0 then

21)

break

22)

end if

{查找該增廣路徑l中的最短路徑(最小費(fèi)用)，存儲到圖G*=(V*,E*)}

23)

G*←SPFS(l)

24)

G-l

25)

end for

{得到最優(yōu)分配X,與分配用戶出價P}

26)

X,P←G*

{計算當(dāng)前分配的社會福利SW}

27)

SW←0

28)

for allxij=1,i∈U,j∈T

29)

SW=pj+SW

30)

end for

31)

ReturnX,SW

3.3 基于VCG的CRA_Pay支付價格算法

最后雖然用戶根據(jù)自己的心理預(yù)期價位提交了自己的租車請求，但實際上的租車費(fèi)用會根據(jù)一些情況而變化，例如上下班高峰時間，用戶的心理價位不能代表當(dāng)時的租車費(fèi)用，因此，這里采用可信的VCG定價方案來計算出用車時實際費(fèi)用的多少。

VCG競價方案是公認(rèn)的最佳競拍定價方案，它定價的核心理念就是計算用戶的社會福利，用戶需要支付的價格與自己的出價沒有關(guān)系，這樣就可以保證用戶出價的真實性，這樣用戶就沒有必要通過惡意出價來破壞競價環(huán)境，而根據(jù)其他人當(dāng)時提交價格的情況來計算實際費(fèi)用，也更能夠說明當(dāng)時競價時刻的供求關(guān)系，計算得到的費(fèi)用將更加準(zhǔn)確。因此在算法中需要計算出該用戶不參與競價和該用戶參與競價但是出價為零時的不同情況，所以VCG算法的計算時間復(fù)雜度較高。VCG算法模型如下：

1)A是車輛最優(yōu)分配算法;

算法3 CRA_Pay算法。

輸入 車型T包括每種車型的數(shù)量mj,車輛的使用成本cj;所有用戶的需求信息Q=[(R1,B1),(R2,B2),…,(Rn,Bn)]，用戶車輛分配結(jié)果X=[x10x11…x1t…xnt]，總社會福利SW;

輸出 最終用戶需要支付的價格，P=[p1p2…pn]。

1)

X*←0

2)

SW*←0

{計算每個被分配用戶不參與競價和參與競價且競價為0}

3)

for eachi←{i|xij∈X,xij≠0},i∈Udo

4)

(SW*,X*)←CRA_Allocation(Q,T)

5)

pi←SW*-(SW-bij)

6)

end for

7)

ReturnP

定理3 最優(yōu)拍賣機(jī)制是可信的。

證明 車輛資源分配算法采用最小費(fèi)用最大流算法求解出最優(yōu)解，文獻(xiàn)[20]證明了在滿足資源分配最優(yōu)解的情況下使用VCG進(jìn)行價格計算一定可以滿足拍賣機(jī)制是可信的，因此最優(yōu)拍賣機(jī)制是可信的。

此外，考慮到使用了最小費(fèi)用最大流模型進(jìn)行車輛分配算法可以得到最優(yōu)解，即解的集合可以保證當(dāng)前分配結(jié)果的社會福利最大，所以在使用VCG算法計算用戶i的出價時，可以保證用戶i最后的出價結(jié)果一定是小于等于自己的競拍價格的(若大于說明還有最優(yōu)解，即用戶i在不參與競價時還有比其更高競價)，該算法對平臺與用戶利益都能保證。

綜上，本文使用競拍的方式解決線上車輛租賃的車輛分配與定價問題，最優(yōu)車輛分配算法采用最小費(fèi)用最大流模型進(jìn)行計算，最優(yōu)支付算法可以按照VCG機(jī)制計算規(guī)則來設(shè)計。接下來將舉簡單實例具體說明機(jī)制的執(zhí)行過程。

3.4 算法舉例

設(shè)一個線上汽車租賃平臺某天能提供的車輛車型和數(shù)目如表2所示，提供的車型有(真實情況為真實的車型號，這里為了方便理解，采用了不同檔次名稱表示)：經(jīng)濟(jì)型、舒適型和精英型各1輛。表2中還列出了經(jīng)過用戶預(yù)約競價后，服務(wù)器收到的用戶請求。

表2 用戶1到用戶5提交的競價需求

根據(jù)表2的數(shù)據(jù)繪制了關(guān)于表2的最小費(fèi)用最大流(容量、費(fèi)用)圖如圖2所示。

圖2 表2數(shù)據(jù)最小費(fèi)用最大流(容量，費(fèi)用)圖

首先，為了轉(zhuǎn)化為本文的模型，需要將費(fèi)用全部取反，然后如圖2所示，每條邊代上的權(quán)值為該路徑的容量和價格，圖中一共有10個頂點(diǎn)，其中起點(diǎn)是頂點(diǎn)0，終點(diǎn)是頂點(diǎn)9，頂點(diǎn)1～5表示用戶1～5，而頂點(diǎn)6～8表示三種不同的車型。該模型要尋找的問題就是在不超過每條邊容量的情況下，求得從起點(diǎn)到終點(diǎn)的路徑費(fèi)用最少(這里將用戶的競價取為負(fù)，就可以得到的路徑費(fèi)用最大)。

根據(jù)數(shù)據(jù)可以計算得到滿足條件的三條路徑分別是：0→1→6→9，該路徑的費(fèi)用為20元；0→3→8→9，該路徑的費(fèi)用為45元；0→4→7→9，該路徑的費(fèi)用為26元。所以競價成功的分別是用戶1、3、4，三條路徑合計平臺的最大收益為91元，為最大收益，而且在滿足用戶需求的同時也沒有超過平臺額定的車型數(shù)目。

之后，根據(jù)分配模型，給每個用戶都分配到了車輛，接著需要計算每個用戶真正需要支付的價格。

首先，計算用戶1需要支付經(jīng)濟(jì)型車型的價格，根據(jù)VCG算法，先要計算用戶1不參與競價時的分配情況，根據(jù)分配算法得到三條路徑分別是：0→2→6→9，競價為20； 0→3→8→9，競價為45；0→4→7→9，競價為26。即用戶2競拍到經(jīng)濟(jì)型車型的競價為20元，用戶3將競拍到精英型車型的競價為45元，而用戶4拍到舒適型的競價為26元，此時的總社會福利為91元。之后，計算用戶1參與競價，但是出價為0的情況，可知總社會福利為71(=91-20)元，所以用戶1只需要支付20(=91-71)元，大于經(jīng)濟(jì)型車型的閑置成本，所以用戶1最后要支付的價格為20元。

然后，計算用戶3需要支付精英車型的價格，首先，也要計算用戶3不參與競價時的分配情況，根據(jù)分配算法得到三條路徑分別是：0→1→6→9，競價為20；0→5→8→9，競價為44；0→4→7→9，競價為26。即用戶1競拍到經(jīng)濟(jì)型車型的競價為20元，用戶5競拍到精英型車型的競價為44元，用戶4拍到舒適型的競價為26元，此時的總社會福利為90元。之后，計算用戶1參與競價，但是出價為0的情況，可知總社會福利為46(=91-45)元，所以用戶1只需要支付44(=90-46) 元，大于精英車型的閑置成本，所以用戶1最后要支付的價格為44元，比自己的競價要少1元。

最后，計算用戶4需要支付舒適車型的價格，用戶4在不參與競價時重新規(guī)劃路徑為：0→2→6→9，競價為20；0→3→8→9，競價為45；0→1→7→9，競價為25。即用戶2競拍到經(jīng)濟(jì)型車型競價為20元，用戶3競拍到精英型車型的競價為45元，而用戶1拍到舒適型的競價為25元，此時的總社會福利為90元。之后，計算用戶5參與競價，但是出價為0的情況，得知總社會福利為65(=91-26)元，所以用戶5只需要支付25(=90-65)元，大于舒適型車型的閑置成本，所以用戶5最后要支付的價格為25元，同樣比自己的競價要少1元就可以拍到此車型。

4 實驗與分析

4.1 實驗設(shè)計

本章通過實驗來評估本文機(jī)制是否合理有效。對于線上車輛租賃平臺的車輛分配與定價問題，目前沒有相關(guān)文獻(xiàn)能夠提供有效的實驗方法來進(jìn)行評估，所以，為了體現(xiàn)利用拍賣機(jī)制的分配與定價合理有效，本文將模擬不同租車網(wǎng)點(diǎn)的車型車輛情況，采用隨機(jī)樣本數(shù)據(jù)訂單對機(jī)制進(jìn)行實驗測試，實驗數(shù)據(jù)模擬用戶訂單完全隨機(jī)產(chǎn)生。實驗搭建在Intel i7-4710MQ 2.5 GHz,8 GB內(nèi)存平臺。實驗設(shè)置如下：

1)數(shù)據(jù)上，本文根據(jù)一嗨租車中的租車點(diǎn)提供的車量、車型數(shù)據(jù)進(jìn)行模擬實驗，主要通過對北京、上海租車點(diǎn)的車輛規(guī)模進(jìn)行了統(tǒng)計，得出每個網(wǎng)點(diǎn)平均有15種車型供用戶選擇，按照每種車型4～5輛計算，車輛總數(shù)大概在100輛左右，表3為實現(xiàn)使用的平臺資源數(shù)量。

2)根據(jù)統(tǒng)計車輛的數(shù)據(jù)結(jié)果，模擬了不同用戶量、不同規(guī)模的請求，每個用戶都提出自己的車輛需求，且用戶平均提交的車輛需求訂單為總體車輛的40%。

3)實驗數(shù)據(jù)采用隨機(jī)數(shù)，用戶出價按照車輛成本為基準(zhǔn)隨機(jī)加減。每組數(shù)據(jù)進(jìn)行多次實驗，結(jié)果取均值。

4)使用Java語言實現(xiàn)先來先服務(wù)(FCFS)、最大利潤優(yōu)先(MAXBENIFIT)算法與本文的VCG-CRA算法。

實驗將考慮如下問題來評估VCG-CRA算法：

1)評估指標(biāo)。由于目前沒有基于競價機(jī)制的汽車租賃相關(guān)文獻(xiàn)與評估指標(biāo)、方法，本文根據(jù)汽車租賃行業(yè)與計算機(jī)算法的重點(diǎn)關(guān)注指標(biāo)，設(shè)計使用以下三個指標(biāo)來衡量本文算法的實驗結(jié)果：訂單成功率、平臺收益和計算效率，這些指標(biāo)雖然不能全面考量算法的性能，但也能夠說明算法應(yīng)用于汽車租賃平臺中提升的效果。

2)算法對比。本文將考慮通過先來先服務(wù)與最大利潤優(yōu)先的算法進(jìn)行對比實驗，說明不同算法情況下的效果。

3)不同規(guī)模、不失一般性實驗。實驗主要以用戶數(shù)量分為不同規(guī)模：小規(guī)模(300個用戶)、中規(guī)模(500 個用戶)和大規(guī)模(1 000 個用戶)進(jìn)行測試，測試研究不同用戶數(shù)對算法的影響。此外，還以平臺車輛數(shù)分為不同規(guī)模，具體研究用戶數(shù)與平臺車輛規(guī)模對VCG-CRA算法效率的影響程度。

表3 不同用戶規(guī)模的線上汽車租賃平臺資源

4.2 實驗結(jié)果

4.2.1 訂單成功率

訂單成功率是網(wǎng)約車最關(guān)心的指標(biāo)之一，因為訂單的成功率一定程度上直接影響用戶體驗度，而用戶的體驗度將直接影響平臺的用戶量和平臺收益，所以如何能最大化地使得用戶都分配到自己預(yù)約的車輛，是每個平臺都要優(yōu)先考慮的。

先來先服務(wù)(FCFS)調(diào)度算法在計算機(jī)中很常見，而目前線上租賃行業(yè)也基本都采取這樣的方式來出租車輛，先來先服務(wù)算法的好處是簡單、容易實現(xiàn)，但這樣的分配方式并不利于平臺的車輛分配。最大利潤優(yōu)先(MAXBENIFIT)算法是順應(yīng)平臺要求利潤最大化誕生的，在收集了所有用戶數(shù)據(jù)后，很自然地想到可以考慮優(yōu)先滿足最大競價者，但這樣的局部最優(yōu)并不一定是全局最優(yōu)解。不同算法的訂單成功率比較如圖3所示。

圖3 不同算法的訂單成功率比較

從圖3可以看到，在模擬線上車輛租賃平臺的數(shù)據(jù)中，VCG-CRA算法與最大利潤優(yōu)先(MAXBENIFIT)算法在三種不同規(guī)模的用戶量下都可以滿足所有車輛的分配，達(dá)到100%的車輛分配；而先來先服務(wù)(FCFS)算法的訂單成功率只有70%～80%，會造成車輛分配的不均，導(dǎo)致車輛的閑置。由于目前線上車輛租賃平臺大多采用類似先來先服務(wù)(FCFS)的算法模式，所以VCG-CRA算法與最大利潤優(yōu)先(MAXBENIFIT)算法在車輛的分配效果上都比目前模式好，比先來先服務(wù)算法提高了20～30個百分點(diǎn)。

4.2.2 平臺收益

經(jīng)過最小費(fèi)用最大流算法的計算，可以得到最優(yōu)的車輛分配及平臺可以獲得的最大收益，但是最大收益情形下的用戶請求不是可信的。通過可信的VCG價格的重新計算，會犧牲部分平臺的收益，換取可信合理的用戶價格，將會根據(jù)用戶需求量而變動。

圖4是不同算法得到的不同的收益情況，可以看到，通過最小費(fèi)用最大流算法得到的平臺收益是最高的，是最優(yōu)的分配方式，而先來先服務(wù)(FCFS)算法得到的平臺收益最低，只有最小費(fèi)用最大流算法收益的60%左右；通過最大費(fèi)用優(yōu)先(MAXBENIFIT)和VCG算法計算得到的平臺整體收益都比較高，其中最大費(fèi)用優(yōu)先(MAXBENIFIT)算法可以得到最小費(fèi)用最大流算法95%左右的收益，VCG-CRA算法也可以達(dá)到其90%以上的收益，比先來先服務(wù)算法的平臺收益提高了30個百分點(diǎn)。而且最小費(fèi)用最大流算法、最大費(fèi)用優(yōu)先(MAXBENIFIT)算法和VCG-CRA三種算法的收益情況都比較穩(wěn)定，而FCFS算法的收益有波動情況。

圖4 不同算法的收益比較

4.2.3 計算效率

由于租車平臺的要求,用戶最短的使用周期都在1天，所以線上汽車租賃平臺對于計算效率的要求并不是很高，但是本文算法仍然需要考慮計算車輛分配以及定價所花費(fèi)的時間，以便全面評價算法效果。

如圖5中所示，車輛分配算法的執(zhí)行時間其實很短，其中先來先服務(wù)(FCFS)算法的執(zhí)行花費(fèi)時間最短，三種用戶規(guī)模下基本30 ms內(nèi)就可以完成分配，而最小費(fèi)用最大流算法因為需要尋找最優(yōu)的分配，所以耗時比較長，需要60 ms左右的時間；而花費(fèi)時間最多的是VCG-CRA算法，由于每個用戶都需要重新分配計算所有用戶的競價，所以需要執(zhí)行多次分配算法，可以看到在模擬數(shù)據(jù)中，為用戶計算最后應(yīng)付價格花費(fèi)的時間大概是1 s左右，還在可以接受的范圍內(nèi)。此外，隨著用戶規(guī)模數(shù)的增加，無論是分配算法還是價格計算，都需要花費(fèi)更多的時間，最小費(fèi)用最大流、先來先服務(wù)(FCFS)與最大費(fèi)用優(yōu)先(MAXBENIFIT)的分配算法都增加了少量執(zhí)行時間，而VCG-CRA算法價格計算執(zhí)行的時間增長呈倍數(shù)的增長，從300用戶到1 000用戶的用戶規(guī)模，最小費(fèi)用最大流算法的執(zhí)行時間從50 ms增加到了90 ms，耗時增加了156%，而VCG-CRA算法卻從原來消耗566 ms增加到了1 846 ms，增加了300%，可見VCG-CRA算法價格計算的執(zhí)行效率對用戶數(shù)量很敏感，隨用戶量的增加，執(zhí)行時間增長很快。

圖5 不同算法的執(zhí)行時間比較

為研究VCG-CRA算法的執(zhí)行速度是否也受到網(wǎng)點(diǎn)資源數(shù)目的影響，接下來還進(jìn)行了不同規(guī)模組的不同網(wǎng)點(diǎn)的實驗。

如圖6所示，算法時間的消耗隨用戶數(shù)與車輛數(shù)的增加而增長。當(dāng)車輛數(shù)一定時，隨著用戶的成倍增加，算法的時間消耗增長速度基本一致，如150的車輛數(shù)中，隨著300、500、1 000用戶規(guī)模的增長，算法的執(zhí)行時間基本成倍地增長；而當(dāng)用戶數(shù)一定時，隨著車輛數(shù)目的增加，算法的執(zhí)行時間增長很快，可以看到車輛數(shù)翻倍的情況下，時間的消耗有近400%的增長。所以綜上，平臺車輛數(shù)目的增加對于算法計算的影響更大。

圖6 不同規(guī)模(用戶×車輛數(shù))計算耗時比較

在線汽車租賃平臺中車輛的出租周期最短都為1天，所以實驗中的時間消耗可以接受，車輛的租賃也會根據(jù)不同區(qū)域的網(wǎng)點(diǎn)來分配車輛，所以一般不會有太大規(guī)模的車輛數(shù)來參與計算。

因此基于競價拍賣機(jī)制的在線汽車租賃機(jī)制可以有效應(yīng)用于在線汽車租賃平臺，該機(jī)制能夠完成最優(yōu)的車輛分配與合理的價格制定，并且計算時間效率在可以接受的范圍內(nèi)。

5 結(jié)語

本文針對線上車輛租賃平臺的問題進(jìn)行建模，使用基于競價的機(jī)制設(shè)計，來解決平臺車輛分配與車輛的定價問題。從理論分析和仿真實驗結(jié)果以及對比其他算法也可以看出，本文算法允許用戶對不同車型提交競價，能夠使得平臺的車輛最優(yōu)地分配給不同用戶，并且在車輛的定價上，可以在保證用戶可信出價的同時，合理地根據(jù)用戶需求為車輛進(jìn)行定價，具有車輛最優(yōu)分配、合理定價的優(yōu)勢。最終實驗表明，本文算法取得了很好的結(jié)果，能有效提高線上車輛租賃平臺的車輛使用率。在未來的研究工作中，擬加入附近的租車網(wǎng)點(diǎn)，形成網(wǎng)點(diǎn)聯(lián)盟，提高競價機(jī)制的實用性與網(wǎng)點(diǎn)車輛的使用效率。