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

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

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

文中通過派單模式下平臺的分配策略，均衡乘客之間、司機(jī)之間的利益，同時，又保證分配策略具有較高的訂單任務(wù)分配率，確保平臺收益，保障乘客、司機(jī)、平臺都能獲得較為滿意的利益.為了實(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í)行非共享出行模型及共享出行模型下的算法，和其他主流算法從匹配延遲時間、乘客利益、司機(jī)利益等評估指標(biāo)進(jìn)行了比較與分析，驗(yàn)證了所提模型的有效性和可行性.

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

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

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

定義非共享出行訂單任務(wù)模型為一個三元組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è)車速恒定的情況下，乘客等待時間與司機(jī)接客的路程成正比，乘客更偏好于司機(jī)當(dāng)前位置與訂單出發(fā)位置間距離更短的訂單任務(wù).定義第j個乘客的收益函數(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個司機(jī)當(dāng)前位置p(vi)與第j個乘客當(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)時間的計費(fèi)和起步價，認(rèn)為價格與訂單路程成正比.補(bǔ)貼是提高訂單完成率、促使司機(jī)接按常規(guī)計費(fèi)乘客訂單的重要因素，且可增加網(wǎng)約司機(jī)的收益.定義乘客的訂單rj補(bǔ)貼為Allo(rj).

綜上，訂單路程和補(bǔ)貼是網(wǎng)約車司機(jī)的收益，接客路程是成本.考慮到收益和成本對司機(jī)利益產(chǎn)生的影響不同，故用兩個系數(shù)α、β分別為成本和收益對司機(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個乘客當(dāng)前位置s(rj)與目的地d(rj)之間的距離.若D(p(vi),s(rj′))-αD(s(rj′),d(rj′))-βAllo(rj′)

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

司機(jī)利益不會直接影響乘客利益，但接客距離共同影響了二者的利益函數(shù)，使得司機(jī)利益與乘客利益潛在相關(guān).即，對于一個潛在的訂單任務(wù)匹配(rj,vi)，可能乘客對其偏好程度非常高，但司機(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]存放對于司機(jī)i而言，乘客j在其序列中的序號，便于在子程序Refusal中進(jìn)行序列比較.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：先采用歸納法證明乘客最優(yōu).假設(shè)初始化時，任意一個乘客沒有被拒絕.假設(shè)在某一時刻，已經(jīng)獲得匹配對象的司機(jī)v1拒絕了乘客r1，且司機(jī)v1更偏好乘客r2.假設(shè)存在一個匹配方案，把乘客r1匹配給司機(jī)v1，乘客r2被分配給了相較于司機(jī)v1偏好程度更低的司機(jī).因乘客為r2與司機(jī)v1都更想選擇對方，因此該匹配結(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è)存在另一個穩(wěn)定匹配M，M≠M(fèi)*，rj在M中被匹配，M(rj)為在匹配M中rj的匹配對象.根據(jù)穩(wěn)定匹配的定義，相較于rj拒絕匹配的對象，rj必然更偏好M(rj).所以在M*中，M(rj)必然被rj請求匹配過，然而M(rj)在M*并不是rj的匹配對象，這意味著M(rj)在M*中有更優(yōu)的匹配對象從而拒絕了rj.但是M(rj)在M*中的對象必然比M中的差，這顯然存在矛盾.故rj不在M中被匹配.

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

由性質(zhì)2可知，通過基于延遲接受的穩(wěn)定匹配算法時，一定會獲得匹配結(jié)果.但極少有網(wǎng)約車平臺會長期采用該訂單任務(wù)分配策略，因?yàn)檫@意味著平臺設(shè)定的被動方必然在每一個匹配過程中收益最低.針對上述問題，文中在穩(wěn)定匹配的基礎(chǔ)上提出了一種全部穩(wěn)定匹配算法，目標(biāo)在不確定平臺具體利益傾向和策略的情況下，在多項(xiàng)式時間內(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，此時訂單任務(wù)匹配成功(具體通過子程序BreakDispatch實(shí)現(xiàn))，否則失敗.規(guī)則1用以保證算法2的正確性.

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

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

算法2旨在尋找所有穩(wěn)定匹配.算法2包含兩個部分.第1至4行為主程序All Dispatch，包括調(diào)用算法1獲得乘客最優(yōu)穩(wěn)定匹配(第2行)和對每個訂單迭代地調(diào)用子程序BreakDispatch以打破現(xiàn)有匹配結(jié)果，試圖獲得新的穩(wěn)定匹配結(jié)果(第3至4行).第5至12行為子程序BreakDispatch，通過打破rj在S中的匹配對，并試圖獲得新的匹配.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ù)分配策略

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

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

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

定義共享出行訂單任務(wù)模型為一個四元組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)約車最多可以同時接受3份訂單，約束一輛網(wǎng)約車最多可以同時接受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ù)的因素與非共享出行模型下的影響因素相同，都為等待時間(接客路程).定義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′送至其目的位置，對于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ù)w(rj)share變?yōu)镈(p(vi),s(rj))，此時與非共享出行模型的模型相同.對于共享訂單集合ck而言，整個集合的利益等于集合中各成員利益的代數(shù)和，即w(ck)=∑w(rj)share,rj∈ck.

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

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

(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時，司機(jī)利益函數(shù)w(vi)share變?yōu)閣(vi)share=D(p(vi),s(rj))-αD(s(rj),d(rj))-βAllo(rj)，與非共享出行模型相同.

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

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

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

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

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

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

定義C={ck}表示共享乘車的乘客請求的所有可行子集的集合.根據(jù)實(shí)際情況限定ck集合的大小為2≤|ck|≤3，可通過窮舉搜索計算獲得所有可行的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ù)分配算法在匹配延遲時間、乘客利益、司機(jī)利益等評估指標(biāo)進(jìn)行了比較與分析.

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

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

3.2 比較算法和評價指標(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)的匈牙利算法.乘客請求和出租車之間的距離是匹配成本，該算法目標(biāo)為求得最小成本的匹配.

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

為對比上述算法的性能，采用3個評價指標(biāo)：

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

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

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

3.3 結(jié)果及分析

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

圖2 匹配延遲時間Fig.2 Matching delay time

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

圖3 乘客利益Fig.3 Passengers utilities

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

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

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

4 結(jié)論

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

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

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

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