基于競(jìng)價(jià)的租賃車輛資源分配和定價(jià)機(jī)制

劉旭東，張學(xué)杰，張?bào)K先，李偉東，張 靜

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

0 引言

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

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

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

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

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

3.1 租賃車輛VCG拍賣(mài)算法

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

算法1 VCG-CRA。

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

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

{用戶請(qǐng)求預(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)

{價(jià)格計(jì)算}

8)

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

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

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

根據(jù)式(1)中的數(shù)學(xué)模型與式(2)和(3)的限制條件，要解決的問(wèn)題就是在車輛限制條件下求解得到最大的費(fèi)用流，這與經(jīng)濟(jì)學(xué)中的最小費(fèi)用最大流問(wèn)題相似。最小費(fèi)用最大流的網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件，研究試圖尋找出：流量從起點(diǎn)S到終點(diǎn)E，如何選擇路徑、分配經(jīng)過(guò)路徑的流量，可以在流量最大的前提下，達(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)過(guò)這條邊的容量和費(fèi)用，第一組頂點(diǎn)從1到n表示的是用戶，第二組頂點(diǎn)從1到t表示的是車型。最小費(fèi)用最大流算法的目的就是找出滿足容量限制和費(fèi)用最小(本文的需求其實(shí)是要費(fèi)用最大，而該算法計(jì)算的是最小費(fèi)用，剛好相反，所以這里將用戶費(fèi)用邊取負(fù)值，即可按照最小費(fèi)用最大流求解，之后再將結(jié)果取反即可)的路徑的一個(gè)集合，這個(gè)集合剛好就是滿足本文模型分配的要求，即滿足平臺(tái)利益的同時(shí)又不超過(guò)車輛的數(shù)目。

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

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

證畢。

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

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

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

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

算法2 CRA_Allocation算法。

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

輸出 參與競(jìng)價(jià)被選中用戶及對(duì)應(yīng)車輛X=[x10x11…x1t…xnt],總社會(huì)福利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)用)，存儲(chǔ)到圖G*=(V*,E*)}

23)

G*←SPFS(l)

24)

G-l

25)

end for

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

26)

X,P←G*

{計(jì)算當(dāng)前分配的社會(huì)福利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支付價(jià)格算法

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

VCG競(jìng)價(jià)方案是公認(rèn)的最佳競(jìng)拍定價(jià)方案，它定價(jià)的核心理念就是計(jì)算用戶的社會(huì)福利，用戶需要支付的價(jià)格與自己的出價(jià)沒(méi)有關(guān)系，這樣就可以保證用戶出價(jià)的真實(shí)性，這樣用戶就沒(méi)有必要通過(guò)惡意出價(jià)來(lái)破壞競(jìng)價(jià)環(huán)境，而根據(jù)其他人當(dāng)時(shí)提交價(jià)格的情況來(lái)計(jì)算實(shí)際費(fèi)用，也更能夠說(shuō)明當(dāng)時(shí)競(jìng)價(jià)時(shí)刻的供求關(guān)系，計(jì)算得到的費(fèi)用將更加準(zhǔn)確。因此在算法中需要計(jì)算出該用戶不參與競(jìng)價(jià)和該用戶參與競(jìng)價(jià)但是出價(jià)為零時(shí)的不同情況，所以VCG算法的計(jì)算時(shí)間復(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]，總社會(huì)福利SW;

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

1)

X*←0

2)

SW*←0

{計(jì)算每個(gè)被分配用戶不參與競(jìng)價(jià)和參與競(jìng)價(jià)且競(jìng)價(jià)為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)拍賣(mài)機(jī)制是可信的。

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

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

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

3.4 算法舉例

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

表2 用戶1到用戶5提交的競(jìng)價(jià)需求

根據(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)值為該路徑的容量和價(jià)格，圖中一共有10個(gè)頂點(diǎn)，其中起點(diǎn)是頂點(diǎn)0，終點(diǎn)是頂點(diǎn)9，頂點(diǎn)1～5表示用戶1～5，而頂點(diǎn)6～8表示三種不同的車型。該模型要尋找的問(wèn)題就是在不超過(guò)每條邊容量的情況下，求得從起點(diǎn)到終點(diǎn)的路徑費(fèi)用最少(這里將用戶的競(jìng)價(jià)取為負(fù)，就可以得到的路徑費(fèi)用最大)。

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

實(shí)驗(yàn)將考慮如下問(wèn)題來(lái)評(píng)估VCG-CRA算法：

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 訂單成功率

訂單成功率是網(wǎng)約車最關(guān)心的指標(biāo)之一，因?yàn)橛唵蔚某晒β室欢ǔ潭壬现苯佑绊懹脩趔w驗(yàn)度，而用戶的體驗(yàn)度將直接影響平臺(tái)的用戶量和平臺(tái)收益，所以如何能最大化地使得用戶都分配到自己預(yù)約的車輛，是每個(gè)平臺(tái)都要優(yōu)先考慮的。

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

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

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

4.2.2 平臺(tái)收益

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

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

圖4 不同算法的收益比較

4.2.3 計(jì)算效率

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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