基于E-CARGO模型的共乘出行匹配建模與優(yōu)化方法

李曉會，董紅斌

（1.哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院，哈爾濱 150001；2.哈爾濱職業(yè)技術(shù)學(xué)院電子與信息工程學(xué)院，哈爾濱 150081）

0 引言

近幾年，隨著私家車數(shù)量的迅速增長，城市的交通壓力越發(fā)緊張。城市汽車保有量的增多，在方便出行之外，也帶來了一系列問題，如交通擁堵、石油資源過度消費、環(huán)境污染等。共乘出行已被證明是充分利用交通資源、緩解停車位緊張、減少環(huán)境污染和優(yōu)化社會效益的有效途徑［1］。車聯(lián)網(wǎng)和全球?qū)崟r定位等技術(shù)為共乘出行應(yīng)用系統(tǒng)提供支持和保障。如何利用計算機技術(shù)，提高共乘出行系統(tǒng)中司機和乘客的匹配效率，已受到更多學(xué)者的關(guān)注和研究。此外，共乘出行系統(tǒng)可以使乘客和車主（司機）分攤共乘出行的相關(guān)費用，例如燃油費、過路費等，這部分費用相當可觀。隨著移動互聯(lián)技術(shù)的不斷進步和互聯(lián)網(wǎng)移動設(shè)備的普及，簡單、安全、靈活、高效和經(jīng)濟的共乘出行系統(tǒng)未來將會更受歡迎。

共乘是指具有出行路徑相同或相似的乘客按照某一匹配方式乘坐被分配的同一輛汽車，在某一行駛區(qū)間共同乘車并分攤出行費用的一種出行方式。共乘出行應(yīng)用系統(tǒng)主要考慮結(jié)合地理位置和時間信息來完成最優(yōu)定價策略和車輛調(diào)度策略［2］。在共乘出行應(yīng)用系統(tǒng)中，可以按乘坐請求在途中與有空座位的車輛匹配。乘客發(fā)出要出行的出發(fā)地點、時間和目的地，應(yīng)用系統(tǒng)根據(jù)某一定價規(guī)則返回用戶大約需要支付的費用，乘客接受費用后可以匹配給一位鄰近的司機：如果是單司機多乘客模式，當司機駕駛的汽車還有空座位，可以接受多名路徑相似的乘客分配一起乘車，完成出行后平臺系統(tǒng)進行結(jié)算；如果是單司機單乘客模式，那么每次司機只能匹配一名乘客發(fā)送的請求，將乘客送達目的地后才會進行下次匹配。

司機可能只接受一個乘客的搭乘，在座位空余的情況下也可能愿意接受多個乘客。同樣，每個乘客可能選擇獨自搭乘司機的車，也可能愿意和其他乘客共乘，存在的司機和乘客之間的共乘關(guān)系如表1 所示。無論哪種出行選擇，乘客與司機的匹配方法都是共乘出行系統(tǒng)的核心。

表1 出行乘客與司機之間的關(guān)系Tab.1 Relationship between passengers and drivers

本文主要對乘客和司機進行在線動態(tài)匹配進行研究，結(jié)合基于角色的協(xié)同（Role-Based Collaboration，RBC）及其E-CARGO（Environment-Class，Agent，Role，Group and Object）模型［3-6］，對共乘匹配問題進行建模，并對共乘中的代理、角色和群組及它們之間的關(guān)系進行了抽象描述，將共乘優(yōu)化問題形式化為一個組角色分配問題，給出形式化定義和目標函數(shù)。通過在一定可接受的靈活時間內(nèi)，在空余座位數(shù)約束下，最大化平臺系統(tǒng)收入來獲得最優(yōu)匹配、增加平臺收入和最大化社會效益。在群組角色指派基礎(chǔ)上，在司機乘客利潤收入距離矩陣上采用Kuhn-Munkres（K-M）算法［7-9］和Java 中的ILOG 軟件包求解獲得最優(yōu)匹配矩陣和時間。

1 相關(guān)工作

共乘出行可以讓車主節(jié)省相關(guān)的費用，提高無車用戶交通出行的便捷性。共乘服務(wù)可能由私家車提供也可能由公共服務(wù)商提供。如果系統(tǒng)是私有的，以盈利為目的，那么提供商可以得到傭金或廣告收入；如果是公共系統(tǒng)，可能會有一個社會目標，比如減少污染和交通擁堵。但無論共乘出行系統(tǒng)的性質(zhì)是什么，都需要完成司機和乘客的匹配，一般來說在匹配中需要考慮的具體目標有：最小化系統(tǒng)中車輛行駛里程，盡量減少系統(tǒng)中的行駛時間和最大化參與者人數(shù)。共乘出行中匹配的成功率是吸引大家參與共乘出行系統(tǒng)中的一個重要性能指標，高成功率會刺激更多的參與者參與進來，本文針對共乘匹配建模與優(yōu)化方法進行了研究。

共乘出行應(yīng)用一般都需要乘客提供出發(fā)時間，因此有很多研究通過時間窗來獲取參與者的時間偏好。文獻［10］中研究限制用戶在一定路程中應(yīng)花費的時間，在應(yīng)用研究中，允許乘客指定他們愿意接受的比直達時間多出的最大超額時間。乘客通過共乘出行系統(tǒng)發(fā)送請求的時間，最早出發(fā)時間和可以接受的抵達目的地時間關(guān)系如圖1 所示。

圖1 共乘中乘客時刻信息Fig.1 Time information of passenger in ride-sharing

文獻［11］中提出了一種新固定時間下的形式化攻擊建模和影響分析方法，驗證了篡改控制設(shè)置對交通和駕駛員的成本影響。通過研究表明，人們更在意的是出行時間得到保證。影響乘客和司機匹配的因素除了時間因素外，也會有其他因素影響匹配是否成功，例如，人們可能更喜歡和比較熟悉的人共乘一輛車，女性乘車時感覺女司機更有安全感等。總之，對潛在的乘客在選擇共乘伙伴時的限制越多，就會越難為該乘客找到成功的匹配［12］。

人們選擇共乘出行除了考慮時間因素，也希望通過選擇共乘出行方式分攤出行成本，降低花銷。因此，也有很多學(xué)者研究關(guān)于在共乘中費用的分攤方式。文獻［13］中研究了各種成本分擔策略，提供了成本分攤策略維持參與或減少車輛使用的必要條件；文獻［14］中考慮到乘車距離的不同，提出按距離遠近成比例分攤費用的方法；文獻［15］中提出了一種基于拍賣機制來確定司機報酬的方式，這種方式考慮到對司機的評估，對司機來說，他們心中愿意支付的費用介于單獨駕駛私家車的費用和乘坐出租車的費用之間，對司機的補償和傭金越高，司機心理對彎路的可接受長度越長；文獻［16］中針對共乘市場準入限制較少、對服務(wù)定價的監(jiān)管也較不嚴格的現(xiàn)狀，從經(jīng)濟學(xué)的供需角度研究勞動力供給的參與彈性和工時彈性對市場勞動供給的影響；文獻［17］中研究激增定價策略，按其動態(tài)價格向提供商支付固定傭金，并得出使用激增定價策略下，所有利益相關(guān)者都可以從具有自調(diào)度能力的平臺上中獲益這一結(jié)論。

在共乘出行時，如果司機時間足夠靈活充裕，他們可能愿意為多個乘客提供服務(wù)，或是一個接一個，或是同時搭乘多名乘客。在為一個司機指派多名乘客時，系統(tǒng)會提供可行的最優(yōu)路線，盡量減少出行成本。文獻［18］中提出并構(gòu)建了實時大容量乘車共享的數(shù)學(xué)模型，該模型可擴展到大量乘客和出行，根據(jù)在線需求和車輛位置動態(tài)生成最優(yōu)路線。文獻［19］中提出一種基于構(gòu)造和局部搜索的啟發(fā)式方法來研究多個乘客共乘的時間模型。

E-CARGO 模型在指派問題和推薦系統(tǒng)［20-23］中得到了一定的應(yīng)用。文獻［20］中針對根據(jù)基站代維人員結(jié)構(gòu)情況優(yōu)化人員分工與指派這一問題，通過E-CARGO 模型對基站代維任務(wù)進行建模和實驗仿真，實驗表明該方法高效、可靠；文獻［21］中使用E-CARGO 模型對資源分配進行建模，并提出多對多推薦問題的優(yōu)化求解方法。共乘出行問題屬于資源分配問題，本文基于角色協(xié)同的工程理論方法和E-CARGO模型對共乘出行系統(tǒng)進行抽象和建模。

2 數(shù)學(xué)模型

2.1 E-CARGO模型介紹

E-CARGO 模型是由加拿大學(xué)者朱海濱教授基于角色協(xié)同理論的研究與探討提出的一種基于角色協(xié)同的模型［24-26］，是角色分配基本理論的研究和擴展，適用于社會系統(tǒng)和經(jīng)濟系統(tǒng)的形式化分析建模。在E-CARGO 模型中，系統(tǒng)Σ可以描述為一個九元組，即。其中：C是類集，O是目標集，A是Agent 集合，M是消息集合，R是角色集合，E是環(huán)境集合，G是群組集合，S0是系統(tǒng)的初始狀態(tài)，H是用戶集合。系統(tǒng)中，A和H、E和G是緊耦合集，一個用戶和他的Agent 可以一起扮演一個角色，每個群組都在一個環(huán)境下工作運行，環(huán)境對群組有規(guī)范作用。在ECARGO 模型中，所有的Agent 都僅有一個中心處理事務(wù)，每個Agent 在一個時間內(nèi)只扮演一個角色。

現(xiàn)實中的很多系統(tǒng)均可抽象表示映射到E-CARGO 模型中，將問題本身或?qū)栴}分解成子問題：首先確定角色和Agent，然后通過約束來描述角色或Agent 之間的關(guān)系和限制約束，再按角色和群組進行指派，最后通過評估準則對指派結(jié)果進行循環(huán)指派和評估，確定最終指派方案。

2.2 E-CARGO模型對共乘問題建模

在共乘出行系統(tǒng)中進行乘客和司機匹配時，要考慮可接受的時間范圍、利潤收入和空座情況進行車輛調(diào)度匹配和換乘方式。乘客為了節(jié)約出行費用和時間，有時從出發(fā)點到目的地過程中可能需要換乘匹配多個司機。

定義1共乘出行系統(tǒng)平臺中司機角色R（Role）。R∷=。其 中：n表示司機角色的ID編號；表示共乘系統(tǒng)司機角色處理的消息集合；Ac表示當前扮演該角色的Agent 集合，即與該司機匹配的乘客集合；Ap表示可以扮演該角色的Agent 集合，即可以匹配的乘客集合；No表示扮演該角色的Agent 可以獲取到的對象集合，主要包括共同順路搭乘的乘客；Q1 表示Agent 扮演該角色所需的最小評估值，即出行費用。在共乘出行系統(tǒng)平臺下，角色R表示等待接受調(diào)遣指派的汽車司機。

定義2共乘出行系統(tǒng)乘客代理A（Agent）。A∷=。其中：n表示此乘客代理的ID 編號；Rc表示此代理正在扮演的角色，即正在乘坐的汽車司機；Rp表示此代理將來可以扮演的角色集合，即將來換乘匹配的汽車司機；Ng表示此代理所屬的群組號；Qr表示此代理對角色集合中每個角色的評估值。在共乘出行系統(tǒng)平臺下，Agent 表示發(fā)出出發(fā)時間、地點和目的地請求的乘客。

在三維遙感影像可視化建模之前，必須先對各幅DEM文件進行鑲嵌，利用三維遙感解譯軟件ArcScene來實現(xiàn)三維地形的可視化建模，將DEM和DOM切片的地形數(shù)據(jù)和遙感數(shù)據(jù)為信息源，形成三維遙感影像(圖4)。

定義3為司機匹配的乘客向量L是在一定時間范圍內(nèi)，每一個司機可匹配乘客數(shù)的向量。

定義4司機接送乘客的利潤收入矩陣Q是一個m×n矩陣，其中Q［i，j］代表司機rolej(0≤j

定義5匹配矩陣T是一個m×n的矩陣，其中T［i，j］代表Agenti是否匹配搭乘司機rolej的車：T［i，j］=1 代表搭乘；T［i，j］=0 代表不搭乘；T［2，2］=1 表示指派第3 個代理（乘客）到角色（司機）3 的車輛上乘坐。

定義6當司機角色R同一時間段搭載乘客數(shù)量≤最大載客量時，稱司機角色是可運行的，即。

定義7乘客從出發(fā)地到目的地可能多次換乘，La[i](0≤i

定義8司機角色范圍向量記為L[j]∈N(0≤j

定義9總行收入r為匹配矩陣T之后，所有司機收入之和，即：?？偸杖氲那蠼膺^程：將利潤收入矩陣與分配矩陣進行矩陣點乘。

目標函數(shù)為：

約束為：

案例分析 假設(shè)在一定可接受的接送乘客距離范圍內(nèi)，有10 名乘客同時呼叫乘車，有4 名司機可調(diào)用派遣，車型均為5 座小汽車，乘客不換乘，根據(jù)司機距離每名乘客遠近及接送距離產(chǎn)生的利潤收入矩陣如下：

分配矩陣可能如下：

當按（a）分配矩陣進行調(diào)度總收入為73，按（b）分配矩陣進行司機派遣送收入為81，且L（a）=［4，2，4，0］，L（b）=［4，0，3，3］，即在分配方案（a）中第4 位司機沒有匹配到乘客，在分配方案（b）中第2 位司機沒有匹配到乘客。

2.3 算法分析

K-M 算法［7-8］的時間復(fù)雜度為O（m3），優(yōu)于窮舉搜索法?？梢詫⑸鲜鰡栴}轉(zhuǎn)化為整數(shù)規(guī)劃來進行求解最大匹配矩陣T，算法的偽代碼描述如下：

算法1 Kuhn-Munkres 求解最優(yōu)匹配算法。

輸入 司機角色數(shù)量n，乘客代理數(shù)量m，n維角色搭載乘客數(shù)量向量L，同時乘客換乘向量La，m×n司機接送乘客的利潤收入矩陣Q；

輸出 最優(yōu)匹配矩陣T和時間。

3 實驗分析

實驗在Microsoft Windows 10 Home 操作系統(tǒng)下實現(xiàn)，其中CPU 配置為AMD Ryzen 5 PRO 3500U w/ Radeon Vega Mobile Gfx 2.10 GHz，內(nèi)存為8 GB，軟件環(huán)境為Version：Eclipse Java Oxygen（4.7.3），JDK 的版本是1.8.0_181。乘客和司機的距離矩陣Q中的值隨機生成，取值范圍1～10；司機數(shù)值分別取10～100 進行實驗，最優(yōu)匹配時間如表2 所示。

表2 不同Agent數(shù)量下匹配算法時間 單位：msTab.2 Matching algorithm time with different number of Agents unit：ms

本文將采用的K-M 算法與ILOG 軟件包算法進行了比對，通過實驗發(fā)現(xiàn)：使用ILOG 軟件包求解時，相似規(guī)模的問題都會消耗相似的時間，且時間長。使用K-M 算法時，在Agent 數(shù)量m（m<400）一定規(guī)模下，所需時間增長緩慢；當Agent 規(guī)模大于某一數(shù)量（400600）時算法時間開銷急劇增大，但總體時間性能優(yōu)于ILOG 算法。與ILOG 軟件包算法相比，K-M 算法所用平均時間至少減少了21%。

將K-M 算法與遺傳算法［27］、貪心算法［28］進行對比，設(shè)Agent 數(shù)量為0～1 000，小汽車L［j］最大同時搭載乘客數(shù)為4，群體大小為50，終止進化代數(shù)為150，交叉概率為0.5時，所花平均時間如圖3 所示?？梢园l(fā)現(xiàn)當僅考慮到局部最優(yōu)時貪婪算法時間開銷與K-M算法相差不多，但在約束限制下，滿足全局最優(yōu)目標函數(shù)時，貪婪算法時間開銷較大。對比遺傳算法，在Agent 數(shù)量相同時，貪婪算法和K-M 算法在共乘匹配中時間平均減少了60%。

圖2 不同Agent規(guī)模下ILOG軟件包算法和K-M算法時間性能Fig.2 Time performance of ILOG software package algorithm and K-M algorithm with different number of Agents

圖3 不同Agent規(guī)模下三種算法時間性能比較Fig.3 Time performance comparison of three algorithms with different number of Agents

4 結(jié)語

本文主要研究在共乘出行系統(tǒng)中，空余座位數(shù)有限和允許乘客多次換乘的約束條件下，基于E-CARGO 模型對共乘出行問題進行形式化建模，并應(yīng)用K-M 算法求解最優(yōu)匹配矩陣。通過實驗應(yīng)用K-M 算法和ILOG 軟件包求解最優(yōu)匹配矩陣，并進行時間性能對比分析。在未來的工作中，將深入研究匹配組合優(yōu)化求解方法，提高匹配率和時間性能以滿足動態(tài)共乘匹配的實時需求。如何基于E-CARGO 模型進行定價和匹配來吸引越來越多乘客和司機參與共乘出行系統(tǒng)也是未來我們要研究的方向和內(nèi)容。