一種穩(wěn)定匹配的任務(wù)分配策略研究

高 欣，周紹峰，柳 絮，孫茂圣

(1.揚(yáng)州大學(xué) 信息工程學(xué)院, 揚(yáng)州 2225127)(2.揚(yáng)州大學(xué) 信息化建設(shè)與管理處，揚(yáng)州 2225127)(3.江蘇旅游職業(yè)學(xué)院 信息工程學(xué)院, 揚(yáng)州 225131)

網(wǎng)約車由于其高效性和便利性已逐漸取代傳統(tǒng)出租車，成為了人們?nèi)粘３鲂械闹饕煌ǚ绞街?乘客可以通過網(wǎng)約車平臺(tái)隨時(shí)發(fā)布出行需求，司機(jī)可及時(shí)獲取出行訂單，乘客的訂單和司機(jī)則由平臺(tái)按照一定規(guī)則快速匹配.網(wǎng)約車平臺(tái)方便快捷的信息交換，大大緩解了傳統(tǒng)出租車模式下由于乘客和司機(jī)之間的時(shí)空偏差造成的信息障礙，成為提高出租車市場(chǎng)效率的有力工具[1-2].近年來，滴滴、Uber、T3出行等國內(nèi)外網(wǎng)約車平臺(tái)迅猛擴(kuò)張.在網(wǎng)約車產(chǎn)業(yè)快速發(fā)展的背景下，提高網(wǎng)約車效率、優(yōu)化城市運(yùn)力、盈利能力已成為研究的不同方向.在城市計(jì)算領(lǐng)域，已有大量關(guān)于網(wǎng)約車出行的研究，可分為路徑規(guī)劃[3]、訂單任務(wù)分配[4]、定價(jià)策略[5]、補(bǔ)貼策略[6]、共享出行[7-8]、需求預(yù)測(cè)[9]等.

目前，網(wǎng)約車的訂單任務(wù)分配策略常見的有兩種，分別是搶單模式和派單模式.搶單模式中，網(wǎng)約車平臺(tái)的主要功能是信息交互，將一名乘客的需求訂單信息發(fā)送給多名合適的空載司機(jī)，司機(jī)根據(jù)其利益偏好和接單速度進(jìn)行搶單，在這種模式下，司機(jī)選擇訂單的自由度更高，但也造成了一定的問題，例如第三方軟件搶單、低收益訂單得不到響應(yīng)、平臺(tái)全局效率低等.在派單模式中，網(wǎng)約車平臺(tái)作為調(diào)度系統(tǒng)，根據(jù)平臺(tái)既定規(guī)則為司機(jī)派發(fā)訂單，司機(jī)僅需執(zhí)行訂單匹配的結(jié)果.在該模式下雖然司機(jī)失去了選擇訂單的自由，但匹配率、完成度和全局效率較高，乘客方、司機(jī)方以及平臺(tái)的利益均得到提高.目前，在平臺(tái)主導(dǎo)權(quán)、利益、條件驅(qū)使下，多數(shù)平臺(tái)已從搶單模式過渡到派單模式.對(duì)于派單模式而言，由網(wǎng)約車平臺(tái)按既定規(guī)則，決定乘客訂單的派發(fā)司機(jī)及派發(fā)順序[10].網(wǎng)約車訂單任務(wù)分配策略不僅關(guān)系著網(wǎng)約車乘客的出行成本、司機(jī)的經(jīng)濟(jì)效益，同時(shí)也影響著網(wǎng)約車平臺(tái)的利益、用戶黏度等.在定位技術(shù)和實(shí)時(shí)交通信息等技術(shù)的支持下，網(wǎng)約車平臺(tái)可以通過高效的訂單匹配算法實(shí)現(xiàn)限定范圍、時(shí)間內(nèi)乘客和司機(jī)的較優(yōu)匹配，提高訂單完成度、增加司機(jī)經(jīng)濟(jì)收益、降低乘客出行成本.正因如此，本文重點(diǎn)在研究網(wǎng)約車派單模式下，訂單任務(wù)分配策略生成問題.

文中通過派單模式下平臺(tái)的分配策略，均衡乘客之間、司機(jī)之間的利益，同時(shí)，又保證分配策略具有較高的訂單任務(wù)分配率，確保平臺(tái)收益，保障乘客、司機(jī)、平臺(tái)都能獲得較為滿意的利益.為了實(shí)現(xiàn)上述目標(biāo)，文中建立了二分匹配模型研究訂單任務(wù)分配問題，定義了乘客方、司機(jī)方的利潤函數(shù).并把訂單分配分為非共享出行和共享出行兩種情況.在非共享出行模型下，進(jìn)一步將二分匹配模型具體為集合大小不等的穩(wěn)定匹配問題，提出了基于Gale Shapley (GS)算法的訂單任務(wù)分配算法，以獲得最優(yōu)穩(wěn)定匹配及全部穩(wěn)定匹配.在共享出行模型下，將訂單任務(wù)分配問題分為訂單打包與穩(wěn)定匹配兩部分，訂單打包抽象為最大集合打包問題，穩(wěn)定匹配同非共享出行模型.最后通過在紐約市出租車數(shù)據(jù)集TCL上執(zhí)行非共享出行模型及共享出行模型下的算法，和其他主流算法從匹配延遲時(shí)間、乘客利益、司機(jī)利益等評(píng)估指標(biāo)進(jìn)行了比較與分析，驗(yàn)證了所提模型的有效性和可行性.

1 非共享出行訂單任務(wù)模型及分配策略

非共享出行訂單任務(wù)模型下每個(gè)司機(jī)至多匹配一個(gè)乘客訂單，分析該模型下乘客方和司機(jī)方的利益，使用基于延遲接受思想的算法求解穩(wěn)定匹配，并討論該算法結(jié)果的性質(zhì).最后，考慮到上述算法存在的局限性，提出了一種求解全部穩(wěn)定匹配的算法，以供不同需要.

1.1 非共享出行訂單任務(wù)模型

定義非共享出行訂單任務(wù)模型為一個(gè)三元組NS=，其中：

R為乘客i∈{1,2,...n}發(fā)起的訂單ri集合；

V為司機(jī)j∈{1,2,...m}駕駛的車輛vj集合；

W為乘客發(fā)起訂單獲得的利益w(rj)和司機(jī)執(zhí)行完訂單任務(wù)后的利益w(vi)的集合.

影響乘客利益的主要因素是等待時(shí)間，假設(shè)車速恒定的情況下，乘客等待時(shí)間與司機(jī)接客的路程成正比，乘客更偏好于司機(jī)當(dāng)前位置與訂單出發(fā)位置間距離更短的訂單任務(wù).定義第j個(gè)乘客的收益函數(shù)w(rj)為：

w(rj)=D(p(vi),s(rj))

(1)

w(rj)值越小乘客利益越高(w(rj)≥0).rj為乘客j的訂單任務(wù).D(p(vi),s(rj))為第i個(gè)司機(jī)當(dāng)前位置p(vi)與第j個(gè)乘客當(dāng)前位置s(rj)之間的距離，vi為司機(jī)i的利益.若D(p(vi′),s(rj))

影響司機(jī)利益函數(shù)的因素主要有接客路程、訂單路程、補(bǔ)貼三項(xiàng)因素.其中接客路程是指司機(jī)當(dāng)前位置與訂單出發(fā)位置間的距離，司機(jī)更偏好于較短的接客路程.訂單路程是訂單出發(fā)位置和目的位置間的最短距離，也是是司機(jī)利益的核心部分.為簡化司機(jī)利益模型，不考慮有關(guān)時(shí)間的計(jì)費(fèi)和起步價(jià)，認(rèn)為價(jià)格與訂單路程成正比.補(bǔ)貼是提高訂單完成率、促使司機(jī)接按常規(guī)計(jì)費(fèi)乘客訂單的重要因素，且可增加網(wǎng)約司機(jī)的收益.定義乘客的訂單rj補(bǔ)貼為Allo(rj).

綜上，訂單路程和補(bǔ)貼是網(wǎng)約車司機(jī)的收益，接客路程是成本.考慮到收益和成本對(duì)司機(jī)利益產(chǎn)生的影響不同，故用兩個(gè)系數(shù)α、β分別為成本和收益對(duì)司機(jī)利益函數(shù)產(chǎn)生影響的不同權(quán)重，定義司機(jī)的利益函數(shù)w(vi)為：

w(vi)=D(p(vi),s(rj))-αD(s(rj),d(rj))-

βAllo(rj)

(2)

w(vi)值越小司機(jī)利益越高，司機(jī)更傾向選擇w(vi)值小的訂單任務(wù).D(s(rj),d(rj))表示第j個(gè)乘客當(dāng)前位置s(rj)與目的地d(rj)之間的距離.若D(p(vi),s(rj′))-αD(s(rj′),d(rj′))-βAllo(rj′)

此外，司機(jī)對(duì)每一單的利益存在閾值θ，司機(jī)不會(huì)接受低于閾值的訂單任務(wù)，即w(vi)<θ時(shí)，vi拒絕匹配rj.

司機(jī)利益不會(huì)直接影響乘客利益，但接客距離共同影響了二者的利益函數(shù)，使得司機(jī)利益與乘客利益潛在相關(guān).即，對(duì)于一個(gè)潛在的訂單任務(wù)匹配(rj,vi)，可能乘客對(duì)其偏好程度非常高，但司機(jī)的偏好程度很低.

1.2 非共享出行模型中任務(wù)分配策略

在非共享出行模型中，乘客發(fā)起訂單，司機(jī)接受訂單，完成乘行后獲得各自的利益.在該模型下通過穩(wěn)定匹配可實(shí)現(xiàn)乘客與司機(jī)的最優(yōu)匹配，穩(wěn)定匹配結(jié)果可保證司機(jī)與乘客均獲得最優(yōu)利益達(dá)到平衡狀態(tài).

1.2.1 穩(wěn)定匹配策略

在非共享出行模型的訂單任務(wù)匹配中，通過乘客和司機(jī)的偏好矩陣，確定穩(wěn)定匹配(stable matching, SM)結(jié)果，如例1、2.

例1：表1為r1,r2,r33名乘客的訂單任務(wù)和3位駕駛車輛v1,v2,v3司機(jī)的組成的偏好矩陣.

表1 偏好矩陣(例1)

在例1所有可能的訂單任務(wù)匹配結(jié)果中，存在3種穩(wěn)定匹配結(jié)果，分別是：①r1與v1、r2與v2、r3與v3匹配.② 每位司機(jī)得到其最佳選擇：r1與v3、r2與v1、r3與v2匹配.③ 每位司機(jī)都與其第二選擇匹配：r1與v2，r2與v3，r3與v1匹配.

例2：表2是r1,r2,r33名乘客的訂單任務(wù)和3位駕駛車輛v1,v2,v3司機(jī)的利益組成的偏好矩陣.

在例2中，存在一種穩(wěn)定匹配結(jié)果，即r1與v1、r2與v2匹配.

表2 偏好矩陣(例2)

通過例1、2的分析，可以得出，在非共享出行模型的訂單任務(wù)匹配中，總存在一組穩(wěn)定匹配，并可通過算法1的反復(fù)迭代可得到穩(wěn)定匹配結(jié)果，進(jìn)一步說明了訂單任務(wù)的穩(wěn)定匹配必然存在.

算法1給出了一種基于延遲接受的迭代求解訂單任務(wù)穩(wěn)定匹配的方法.算法由主程序Dispatch、子程序Proposal、子程序Refusal 3部分構(gòu)成.程序輸入中，dispatch[i]中存放與司機(jī)i匹配的乘客.fc[i][j]存放對(duì)于司機(jī)i而言，乘客j在其序列中的序號(hào)，便于在子程序Refusal中進(jìn)行序列比較.

第1至第18行為主程序Dispatch.第3行至第11行在使用D_choice初始化fc數(shù)組.第12至15行初始化p_counter和fc的第一列，此二者相互配合，在迭代過程中記錄每個(gè)乘客下一個(gè)請(qǐng)求對(duì)象.第16至18行，依次調(diào)用Proposal子程序，確保每個(gè)乘客都進(jìn)行匹配.

第19至26行為子程序Proposal.核心在于獲取此次Proposal的對(duì)象，若j<0則說明不存在可匹配對(duì)象，此次proposal過程終止.

第27至36行為子程序Refusal.用于詢問被請(qǐng)求方的司機(jī)對(duì)于請(qǐng)求匹配的乘客的回應(yīng)，對(duì)司機(jī)而言，如果乘客存在更好選擇，則進(jìn)行替換，且被替換的乘客需要進(jìn)行下一輪Proposal.如果不存在更好的選擇，則乘客繼續(xù)進(jìn)行Proposal，司機(jī)保持匹配對(duì)象不變.

算法1的時(shí)間復(fù)雜度為O(|R||V|).對(duì)于每一個(gè)司機(jī)而言，其均可能拒絕m-1個(gè)乘客的請(qǐng)求，直至最后一個(gè)司機(jī)獲得其匹配對(duì)象，即請(qǐng)求次數(shù)最多為(m-1)(n-1)+1，故時(shí)間復(fù)雜度為O(|R||V|).因?yàn)樗惴?在多項(xiàng)式時(shí)間內(nèi)可解，故一定存在至少一組穩(wěn)定匹配.

1.2.2 算法1的實(shí)例說明

通過下述實(shí)例詳細(xì)說明算法1的流程.

表3 偏好矩陣(實(shí)例)

表3為乘客和司機(jī)的偏好矩陣，在表格中用“-”標(biāo)出r2訂單的乘客拒絕匹配駕駛車輛v1的司機(jī)，v2的司機(jī)拒絕匹配訂單r2的乘客.每個(gè)乘客或司機(jī)對(duì)應(yīng)的偏好序列，從左至右偏好依次下降，即最左端的對(duì)象具有最高偏好程度.

圖1 實(shí)例匹配過程Fig.1 Instance matching procedure

如圖1，在初始狀態(tài)中，司機(jī)沒有和任何乘客匹配.在r1的請(qǐng)求輪次中，r1與v1暫時(shí)匹配.在r2的請(qǐng)求輪次中，r2希望與v2進(jìn)行匹配，但由于v2的駕駛司機(jī)拒絕匹配乘客r2的訂單，所以r2順延至下一位偏好順序發(fā)起請(qǐng)求.但發(fā)起訂單r2的乘客拒絕匹配v1的駕駛司機(jī)，匹配失敗，r2的請(qǐng)求輪次結(jié)束.在r3的請(qǐng)求輪次中，r3對(duì)v1發(fā)起匹配請(qǐng)求，因?yàn)関1更偏好r3，r3與v1暫時(shí)形成匹配.此時(shí)r1需要迭代進(jìn)行匹配請(qǐng)求，向v2發(fā)出匹配請(qǐng)求，因?yàn)関2暫時(shí)沒有匹配對(duì)象且不拒絕r1，所以r1與v2形成另一對(duì)匹配.此時(shí)所有司機(jī)均獲得相應(yīng)的匹配乘客，匹配過程結(jié)束.

1.2.3 非共享出行模型的性質(zhì)

通過基于延遲接受的穩(wěn)定匹配算法獲得的訂單任務(wù)匹配結(jié)果，實(shí)現(xiàn)在非共享出行模型中司機(jī)和乘客的利益函數(shù)達(dá)到平衡狀態(tài)，此時(shí)該匹配結(jié)果是最優(yōu)結(jié)果，定義最優(yōu)訂單任務(wù)匹配結(jié)果如定義1.

定義1：如果在某種匹配策略下，乘客(司機(jī))的收益不小于任何其他匹配策略，則稱這種匹配策略是乘客(司機(jī))最優(yōu)的.

從定義中可知，最優(yōu)性是指在所有任務(wù)的穩(wěn)定匹配結(jié)果中，對(duì)于某一集合中的全部成員例如乘客方而言，均可獲得最高收益.此外，非共享出行模型的任務(wù)匹配結(jié)果具有最有唯一性、匹配結(jié)果存在性以及排他性.

性質(zhì)1(最優(yōu)唯一性)：只存在一種最優(yōu)匹配策略.

證明：如果存在兩種最有匹配策略，假定無平局，此時(shí)乘客(司機(jī))在一種分配策略下的收益總大于另一種分配策略下的收益，因此這兩種分配策略總有一個(gè)不是最優(yōu)的.故只存在一種最優(yōu)訂單任務(wù)匹配策略.

性質(zhì)2(最優(yōu)存在性)：基于延遲接受的匹配結(jié)果，對(duì)于匹配過程的主動(dòng)方來說，利益不小于任何其他的穩(wěn)定匹配結(jié)果，又因?yàn)槿蝿?wù)匹配結(jié)果的最優(yōu)唯一性，主動(dòng)方一定獲得最優(yōu)匹配.

證明：先采用歸納法證明乘客最優(yōu).假設(shè)初始化時(shí)，任意一個(gè)乘客沒有被拒絕.假設(shè)在某一時(shí)刻，已經(jīng)獲得匹配對(duì)象的司機(jī)v1拒絕了乘客r1，且司機(jī)v1更偏好乘客r2.假設(shè)存在一個(gè)匹配方案，把乘客r1匹配給司機(jī)v1，乘客r2被分配給了相較于司機(jī)v1偏好程度更低的司機(jī).因乘客為r2與司機(jī)v1都更想選擇對(duì)方，因此該匹配結(jié)果不穩(wěn)定.通過歸納法可得，任意司機(jī)只拒絕了在任何穩(wěn)定方案中偏好程度更低的乘客，因此可得乘客最優(yōu)的匹配結(jié)果.同理可得司機(jī)最優(yōu)匹配.

性質(zhì)3(最優(yōu)排他性)：在最優(yōu)穩(wěn)定匹配中沒有獲得匹配的乘客，在其他穩(wěn)定匹配中也不可能被匹配.

證明：M*為乘客最優(yōu)穩(wěn)定匹配，rj為M*中沒有被匹配的乘客.假設(shè)存在另一個(gè)穩(wěn)定匹配M，M≠M(fèi)*，rj在M中被匹配，M(rj)為在匹配M中rj的匹配對(duì)象.根據(jù)穩(wěn)定匹配的定義，相較于rj拒絕匹配的對(duì)象，rj必然更偏好M(rj).所以在M*中，M(rj)必然被rj請(qǐng)求匹配過，然而M(rj)在M*并不是rj的匹配對(duì)象，這意味著M(rj)在M*中有更優(yōu)的匹配對(duì)象從而拒絕了rj.但是M(rj)在M*中的對(duì)象必然比M中的差，這顯然存在矛盾.故rj不在M中被匹配.

1.3 全部穩(wěn)定匹配策略

由性質(zhì)2可知，通過基于延遲接受的穩(wěn)定匹配算法時(shí)，一定會(huì)獲得匹配結(jié)果.但極少有網(wǎng)約車平臺(tái)會(huì)長期采用該訂單任務(wù)分配策略，因?yàn)檫@意味著平臺(tái)設(shè)定的被動(dòng)方必然在每一個(gè)匹配過程中收益最低.針對(duì)上述問題，文中在穩(wěn)定匹配的基礎(chǔ)上提出了一種全部穩(wěn)定匹配算法，目標(biāo)在不確定平臺(tái)具體利益傾向和策略的情況下，在多項(xiàng)式時(shí)間內(nèi)獲得全部訂單任務(wù)的穩(wěn)定匹配.為了在算法1穩(wěn)定匹配的基礎(chǔ)上，獲得新的匹配，需要通過以下3項(xiàng)規(guī)則進(jìn)行約束.

規(guī)則1：給定S和rj，當(dāng)S(rj)與另一名乘客rj′試圖進(jìn)行匹配，并且S(rj)相較于rj′更偏好rj，此時(shí)訂單任務(wù)匹配成功(具體通過子程序BreakDispatch實(shí)現(xiàn))，否則失敗.規(guī)則1用以保證算法2的正確性.

規(guī)則2：給定S和rj，在調(diào)用子程序BreakDispatch的訂單任務(wù)匹配過程中需要保證乘客請(qǐng)求rj′中j′≥j，此時(shí)匹配成功.如果j′

規(guī)則3：給定S和rj，如果rj在S中未匹配，那么該輪涉及rj的匹配過程直接結(jié)束.規(guī)則3用以保證算法2的執(zhí)行效率.

算法2旨在尋找所有穩(wěn)定匹配.算法2包含兩個(gè)部分.第1至4行為主程序All Dispatch，包括調(diào)用算法1獲得乘客最優(yōu)穩(wěn)定匹配(第2行)和對(duì)每個(gè)訂單迭代地調(diào)用子程序BreakDispatch以打破現(xiàn)有匹配結(jié)果，試圖獲得新的穩(wěn)定匹配結(jié)果(第3至4行).第5至12行為子程序BreakDispatch，通過打破rj在S中的匹配對(duì)，并試圖獲得新的匹配.BreakDispatch中需要調(diào)用算法1中的子程序Proposal和Rufusal.第7至8行，在約定規(guī)則下打破現(xiàn)有匹配(rj,S(rj))，因?yàn)橐?guī)則的約束，BreakDispatch可能成功可能不成功.如果成功，則將獲得新的匹配S’，將其加入集合S(第10行)，并遞歸調(diào)用BreakDispatch以獲得新的穩(wěn)定匹配.

2 共享出行模型及訂單任務(wù)分配策略

非共享出行模型只考慮了一個(gè)乘客訂單和司機(jī)匹配的情況，然而在現(xiàn)實(shí)情況中，在出行高峰時(shí)期難打到車時(shí)，人們常常會(huì)選擇共享出行.基于此，文中建立了共享出行模型，重新定義了共享出行模型下的司機(jī)利益函數(shù)，乘客利益函數(shù)，仍然通過穩(wěn)定匹配算法獲得了訂單任務(wù)穩(wěn)定匹配策略結(jié)果.

2.1 共享出行訂單任務(wù)模型

在共享出行訂單任務(wù)模型下，乘客希望通過與他人拼車，用非共享模型下更多的等待時(shí)間和可能延長的訂單距離換取更少的花費(fèi)，而司機(jī)通過共享模型可以在同一段路程上搭載多個(gè)訂單上的乘客，收入較非共享模型下更高.

定義共享出行訂單任務(wù)模型為一個(gè)四元組SM=，其中：

ck={rj1,rj2,…,rjn}為共享一輛網(wǎng)約車的訂單集合；

S為出發(fā)位置的集合；

W為乘客發(fā)起訂單獲得的利益w(rj)share和司機(jī)執(zhí)行完訂單任務(wù)后的利益w(vi)share的集合；

Squ為接送順序的集合.

在共享模型中，目標(biāo)是找到完成所有訂單的最短路徑，且最短路徑?jīng)Q定了各訂單的接送順序.根據(jù)實(shí)際打車情況，一輛網(wǎng)約車最多可以同時(shí)接受3份訂單，約束一輛網(wǎng)約車最多可以同時(shí)接受3份訂單，即|ck|≤3.

2.2 利益函數(shù)

基于非共享出行模型下乘客的利益函數(shù)w(rj)和司機(jī)的利益函數(shù)w(vi)，根據(jù)共享出行模型的需求特點(diǎn)，重新定義乘客的利益函數(shù)w(rj)share和司機(jī)的利益函數(shù)w(vi)share.

首先定義司機(jī)的利益函數(shù)w(rj)share.影響乘客的利益函數(shù)的因素與非共享出行模型下的影響因素相同，都為等待時(shí)間(接客路程).定義Dck(p(vi),s(rj))為乘客訂單rj屬于駕駛vi的司機(jī)的共享訂單集合ck，表示從駕駛vi的司機(jī)當(dāng)前位置到乘客訂單rj的出發(fā)位置之間的距離.顯然，Dck(p(vi),s(rj))是最短路徑的一部分.需要注意的是，Dck(p(vi),s(rj))并不是vi的司機(jī)當(dāng)前位置到乘客訂單rj的出發(fā)位置之間的最短距離，因?yàn)樵诮觬j前可能需要接其他乘客.除此以外，與非共享出行模型不同的是，乘客關(guān)心其實(shí)際行駛距離較訂單路徑最短路徑多出的距離.因?yàn)榭赡芟葘⑵渌丝蛂j′送至其目的位置，對(duì)于rj而言，其相較于非共享模型下的最短距離要多(除非rj′就在rj的最短路徑上).用Dck(s(rj),d(rj))表示乘客rj從出發(fā)位置到目的位置在最短路徑的距離.乘客rj多行的距離可以用Dck(s(rj),d(rj))-D(s(rj),d(rj))來表示.故乘客rj在共享出行模型下的利益函數(shù)w(rj)share為：

w(rj)share=Dck(p(vi),s(rj))+

θ[Dck(s(rj),d(rj))-D(s(rj),d(rj))]

(3)

其中，θ為系數(shù)，表示接客距離和多行距離的比例.w(rj)share值越小意味著rj的偏好程度越高.當(dāng)|ck|=1時(shí)，乘客利益函數(shù)w(rj)share變?yōu)镈(p(vi),s(rj))，此時(shí)與非共享出行模型的模型相同.對(duì)于共享訂單集合ck而言，整個(gè)集合的利益等于集合中各成員利益的代數(shù)和，即w(ck)=∑w(rj)share,rj∈ck.

與非共享出行模型相似，影響司機(jī)利益的因素同樣可以歸納為接客距離、訂單距離之和、補(bǔ)貼3點(diǎn)，具體為：

(1) 接客距離，Dck(vi)為司機(jī)vi與第一個(gè)上車乘客的接客距離.

(2) 訂單距離之和.司機(jī)獲得利益與距離之和直接相關(guān).

(3) 補(bǔ)貼.共享訂單集合ck的補(bǔ)貼用Allo(ck)表示.

定義司機(jī)的利益函數(shù)w(vi)share為：

w(vi)share=Dck(vi)-α∑D(s(rj),d(rj))-βAllo(ck)

(4)

當(dāng)|ck|=1時(shí)，司機(jī)利益函數(shù)w(vi)share變?yōu)閣(vi)share=D(p(vi),s(rj))-αD(s(rj),d(rj))-βAllo(rj)，與非共享出行模型相同.

同樣地，假設(shè)存在訂單利益閾值θ，定義司機(jī)不會(huì)接受低于閾值θ的訂單，即w(vi)<θ時(shí)，vi的司機(jī)拒絕匹配發(fā)起訂單ck的乘客.

2.3 穩(wěn)定匹配算法

為了在共享出行模型中獲得訂單任務(wù)穩(wěn)定匹配結(jié)果，基于非共享出行模型的穩(wěn)定匹配算法，將穩(wěn)定匹配算法劃分為打包和匹配兩個(gè)步驟：

步驟1：根據(jù)乘客訂單的偏好程度進(jìn)行打包至可行子集；

步驟2：乘客請(qǐng)求的每個(gè)子集都被視為非共享出行模型下的單獨(dú)調(diào)度的乘客訂單.即先最大化打包共享出行模型下的穩(wěn)定匹配問題中的訂單，后求解穩(wěn)定匹配策略.

因?yàn)榇虬挠唵伪徽w看做一個(gè)非共享出行模型下的新訂單，所以步驟2中求解穩(wěn)定匹配的過程與算法1的過程相同，在此不做贅述.

定義C={ck}表示共享乘車的乘客請(qǐng)求的所有可行子集的集合.根據(jù)實(shí)際情況限定ck集合的大小為2≤|ck|≤3，可通過窮舉搜索計(jì)算獲得所有可行的ck.步驟1的目標(biāo)是最大限度地打包乘客訂單到可行的子集，用布爾變量xk表示ck是否成功打包，目標(biāo)函數(shù)是最大化乘客訂單：

(5)

xk∈{0,1}

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

文中實(shí)現(xiàn)了非共享出行模型及共享模型中的穩(wěn)定匹配算法，把穩(wěn)定匹配算法在紐約市出租車數(shù)據(jù)集TCL數(shù)據(jù)集進(jìn)行了模擬實(shí)驗(yàn)，并與其他主流訂單任務(wù)分配算法在匹配延遲時(shí)間、乘客利益、司機(jī)利益等評(píng)估指標(biāo)進(jìn)行了比較與分析.

3.1 數(shù)據(jù)集及相關(guān)設(shè)定

文中選用的是紐約市出租車數(shù)據(jù)集TCL，對(duì)2019年03月14日收集的綠色出租車行車記錄，共20 929條記錄進(jìn)行了整理.由于數(shù)據(jù)集提供的數(shù)據(jù)內(nèi)容有限，假設(shè)共有500輛出租車提供服務(wù)，出租車的初始位置遵循從市中心向外圍的二維正態(tài)分布，網(wǎng)約車系統(tǒng)的時(shí)間窗口為10 s.

3.2 比較算法和評(píng)價(jià)指標(biāo)

把非共享出行模式下穩(wěn)定匹配算法的訂單任務(wù)結(jié)果記為SM-P，把共享出行模式下穩(wěn)定匹配算法的訂單任務(wù)結(jié)果記為SM-T.其中參數(shù)α=1,β=0.為驗(yàn)證文中所提模型的有效性和可行性，把3種算法與文中的穩(wěn)定匹配算法進(jìn)行比較：

(1) 貪婪算法.將最近的空閑出租車發(fā)送給乘客訂單進(jìn)行匹配.

(2) 改進(jìn)的匈牙利算法.乘客請(qǐng)求和出租車之間的距離是匹配成本，該算法目標(biāo)為求得最小成本的匹配.

(3) KM算法.其中乘客利益和司機(jī)利益的比例系數(shù)為1，即α=1.該算法的目的在于最大化系統(tǒng)整體利益.

為對(duì)比上述算法的性能，采用3個(gè)評(píng)價(jià)指標(biāo)：

(1) 匹配延遲時(shí)間.從乘客請(qǐng)求發(fā)送到系統(tǒng)，系統(tǒng)進(jìn)行匹配后將結(jié)果發(fā)送給該乘客之間的延遲時(shí)間.

(2) 在非共享出行模型下和共享出行模型下的乘客利益.

(3) 在非共享出行模型下和共享出行模型下的司機(jī)利益.對(duì)于3個(gè)指標(biāo)，值越小說明算法的性能更優(yōu).

3.3 結(jié)果及分析

如圖2，對(duì)于所有的算法，超過75%的乘客請(qǐng)求會(huì)在一個(gè)時(shí)間窗口內(nèi)獲得訂單匹配結(jié)果.相較而言，匈牙利算法的調(diào)度延遲較小，文中所提穩(wěn)定匹配算法在兩種出行模型下延遲時(shí)間均稍長一些.貪婪算法在第一個(gè)時(shí)間窗口中獲得匹配的比例最低，而隨著延遲時(shí)間增長，其增長速度明顯有快速提高.但在時(shí)效內(nèi)不能得到匹配結(jié)果的匹配策略會(huì)導(dǎo)致乘客取消訂單，故調(diào)度延遲應(yīng)在時(shí)效范圍內(nèi).

圖2 匹配延遲時(shí)間Fig.2 Matching delay time

圖3為乘客利益及其比例.從整體上看，匈牙利算法和非共享出行模型下穩(wěn)定匹配算法SM-P的乘客利益更高，原因是匈牙利算法的權(quán)重是客請(qǐng)求和出租車之間的距離，優(yōu)先考慮了乘客的利益；而非共享出行模型只考慮了一個(gè)乘客的訂單需求，且通過穩(wěn)定匹配算法獲得最優(yōu)利益，因此乘客的利益更高.而KM算法和在共享出行模型中的算法結(jié)果SM-T的表現(xiàn)整體較差，因?yàn)镵M算法中乘客利益和司機(jī)利益的比例系數(shù)設(shè)為1，導(dǎo)致利益不偏向任何一方.而共享出行模型中的算法結(jié)果SM-T表現(xiàn)較差的原因是在共享出行模型中，會(huì)折衷部分乘客的利益實(shí)現(xiàn)共享出行.

圖3 乘客利益Fig.3 Passengers utilities

貪婪算法中獲得高利益的比例非常低，而在利益中間值附近有一個(gè)很大程度的提高，說明大部分乘客的利益都落在這個(gè)利益中間值附近.貪婪算法具有一定隨機(jī)性，該結(jié)果符合在各個(gè)指標(biāo)上的表現(xiàn)的預(yù)期.

圖4展示了司機(jī)利益及其比例，匈牙利算法、非共享出行模型下穩(wěn)定匹配算法結(jié)果SM-P、KM算法和共享出行模型中的算法結(jié)果SM-T的表現(xiàn)與它們?cè)诔丝屠嫔系谋憩F(xiàn)正好相反，符合預(yù)期.若重視司機(jī)利益必然導(dǎo)致乘客利益受損.貪婪算法的結(jié)果顯然明顯低于其他所有算法，因?yàn)樨澙匪惴ㄊ且粋€(gè)近似隨機(jī)的算法，其他算法在不同程度上保證了司機(jī)的利益.

圖4 司機(jī)利益Fig.4 Drivers utilities

4 結(jié)論

(1) 在非共享出行模型中，建立了乘客和司機(jī)的利益函數(shù)，提出了基于延遲接受思想的迭代算法，獲得訂單任務(wù)的最優(yōu)穩(wěn)定匹配結(jié)果.同時(shí)，證明了該算法的最優(yōu)唯一性和最優(yōu)存在性等3個(gè)重要性質(zhì).

(2) 為考慮平臺(tái)具體利益傾向和策略的情況基于穩(wěn)定匹配算法，提出了一種通過打破現(xiàn)有穩(wěn)定匹配對(duì)的方法以獲取全部穩(wěn)定匹配，進(jìn)一步提高穩(wěn)定匹配效果.在共享出行模型中，同樣建立了乘客和司機(jī)的利益函數(shù)，在該模型下的穩(wěn)定匹配問題可通過最大集合打包問題和任務(wù)匹配兩個(gè)步驟進(jìn)行.

(3) 通過模擬實(shí)驗(yàn)實(shí)現(xiàn)了文中在非共享出行和共享出行下的穩(wěn)定匹配算法，并在數(shù)據(jù)集TCL進(jìn)行模擬實(shí)驗(yàn)，從匹配延遲時(shí)間、司機(jī)利益、乘客利益等3個(gè)評(píng)估指標(biāo)與其他主流算法進(jìn)行比較與分析，說明所提模型的有效性和可行性.

(4) 研究了基于穩(wěn)定匹配的訂單任務(wù)分配策略，為解決利益平衡問題奠定了理論基礎(chǔ).但所提模型尚未考慮在策略決策方有動(dòng)機(jī)最大化利益時(shí)的可行性，因此在未來的研究工作中，需要進(jìn)一步研究：① 將基于穩(wěn)定匹配的訂單任務(wù)分配策略作為一種分配策略框架，在該框架下提高各方利益.② 根據(jù)具體利益傾向設(shè)計(jì)對(duì)應(yīng)算法，例如最小化遺憾成本、最小化平等成本等，當(dāng)利益與之匹配時(shí)，設(shè)計(jì)相應(yīng)的求解算法.