李曉會(huì)，董紅斌

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

共乘出行應(yīng)用一般都需要乘客提供出發(fā)時(shí)間，因此有很多研究通過(guò)時(shí)間窗來(lái)獲取參與者的時(shí)間偏好。文獻(xiàn)［10］中研究限制用戶在一定路程中應(yīng)花費(fèi)的時(shí)間，在應(yīng)用研究中，允許乘客指定他們?cè)敢饨邮艿谋戎边_(dá)時(shí)間多出的最大超額時(shí)間。乘客通過(guò)共乘出行系統(tǒng)發(fā)送請(qǐng)求的時(shí)間，最早出發(fā)時(shí)間和可以接受的抵達(dá)目的地時(shí)間關(guān)系如圖1 所示。

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

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

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

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

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

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

2.1 E-CARGO模型介紹

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

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

2.2 E-CARGO模型對(duì)共乘問(wèn)題建模

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

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

定義2共乘出行系統(tǒng)乘客代理A（Agent）。A∷=。其中：n表示此乘客代理的ID 編號(hào)；Rc表示此代理正在扮演的角色，即正在乘坐的汽車(chē)司機(jī)；Rp表示此代理將來(lái)可以扮演的角色集合，即將來(lái)?yè)Q乘匹配的汽車(chē)司機(jī)；Ng表示此代理所屬的群組號(hào)；Qr表示此代理對(duì)角色集合中每個(gè)角色的評(píng)估值。在共乘出行系統(tǒng)平臺(tái)下，Agent 表示發(fā)出出發(fā)時(shí)間、地點(diǎn)和目的地請(qǐng)求的乘客。

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

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

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

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

定義6當(dāng)司機(jī)角色R同一時(shí)間段搭載乘客數(shù)量≤最大載客量時(shí)，稱(chēng)司機(jī)角色是可運(yùn)行的，即。

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

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

定義9總行收入r為匹配矩陣T之后，所有司機(jī)收入之和，即：?？偸杖氲那蠼膺^(guò)程：將利潤(rùn)收入矩陣與分配矩陣進(jìn)行矩陣點(diǎn)乘。

目標(biāo)函數(shù)為：

約束為：

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

分配矩陣可能如下：

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

2.3 算法分析

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

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

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

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

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

實(shí)驗(yàn)在Microsoft Windows 10 Home 操作系統(tǒng)下實(shí)現(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。乘客和司機(jī)的距離矩陣Q中的值隨機(jī)生成，取值范圍1～10；司機(jī)數(shù)值分別取10～100 進(jìn)行實(shí)驗(yàn)，最優(yōu)匹配時(shí)間如表2 所示。

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

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

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

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

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

4 結(jié)語(yǔ)

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