基于改進(jìn)H-R雙邊匹配算法的定制公交合乘優(yōu)化

孫 峣，白子建，柯水平，申 嬋

（天津市市政工程設(shè)計研究院，天津 300051）

隨著移動互聯(lián)網(wǎng)的廣泛普及，近年來涌現(xiàn)出許多基于手機(jī)APP的出行新模式，而定制公交作為一種高品質(zhì)、低價格的出行方式，受到了越來越多乘客的青睞[1].深圳已開發(fā)上線的“小豬巴士”，為乘客提供實時出行需求，運營商接受乘客合乘請求成為了可能.目前，國內(nèi)外關(guān)于合乘問題的研究大都基于出租車或小型共享汽車.Santos和Stiglic等學(xué)者[2-3]提出一種采用貪婪算法解決出租車共享的組合優(yōu)化問題，并定量分析不同類型乘客的靈活性對共享車輛運營穩(wěn)定性的影響；張薇等[4]提出用數(shù)學(xué)規(guī)劃的方法求解車輛合乘的穩(wěn)定匹配模型；于匡員[5]建立了合乘車輛的運營成本最小化和乘客服務(wù)數(shù)量最多的多目標(biāo)函數(shù)，采用改進(jìn)的遺傳算法對模型求解，結(jié)果證明該模型可以有效提高社會資源利用率；宮熙楨等[6]通過計算合乘問題中司機(jī)和乘客付出的費用比例，提出了一種合理的計算方法，減少了因費用問題產(chǎn)生的矛盾.

雙邊匹配的研究最早源自解決男性和女性婚姻配對問題[7]，隨后廣泛地應(yīng)用于許多學(xué)科領(lǐng)域.王中興等[8]認(rèn)為，以最大化匹配群體的整體滿意度為目標(biāo)得到的結(jié)果是最優(yōu)的；張亦楠[9]通過分析現(xiàn)實中的合乘行為，認(rèn)為建立以乘客滿意度最大化為目標(biāo)函數(shù)的同時，可以保證運營商的成本和市場份額.綜上所述，目前，針對定制公交合乘的研究相對較少.本文通過對定制公交合乘問題的分析，分別建立了乘客和定制公交車輛效用函數(shù)，提出一種改進(jìn)H-R雙邊匹配算法的定制公交合乘優(yōu)化方法，并對匹配的結(jié)果進(jìn)行比較分析.

1 問題描述

1.1 研究思路

對于本文研究的定制公交合乘優(yōu)化問題，一方面定制公交運營商可以選擇期望的乘客進(jìn)行服務(wù)，另一方面乘客也可以選擇合適的車輛完成出行需求.研究思路如圖1所示.

圖1 定制公交合乘問題研究思路

1.2 定制公交合乘雙邊匹配要素

（3）路況信息.路況信息包括實時路段交通流信息、路網(wǎng)信息等.實時路段交通流信息可以保證定制公交在保證乘客服務(wù)需求的同時，更加靈活地改變運行路徑.路網(wǎng)信息由有向圖G=（V，A）構(gòu)成，其中V是點集合，表示公交站點位置；A是路段集合，每條路段的屬性值aij表示定制公交在節(jié)點（i，j）間的運行時間.

1.3 目標(biāo)函數(shù)與雙邊匹配合乘類型

1.3.1 目標(biāo)函數(shù)

目標(biāo)1：系統(tǒng)最優(yōu)，最大化服務(wù)乘客數(shù)量，即考慮所有乘客的服務(wù)請求，最小化定制公交總的運營里程數(shù)；目標(biāo)2：乘客最優(yōu)，最大化乘客的滿意度，衡量乘客滿意度指標(biāo)包括乘客等待時間最少、乘客出行費用最少；目標(biāo)3：運營商最優(yōu)，最大化運營商收益，用運營商總收益與總成本的差異衡量，即運營商的純利潤；最小化運營商等待時間.

1.3.2 雙邊匹配合乘類型

在定制公交運行過程中，可能會出現(xiàn)以下4種匹配情形，見表1.其中第4種較為常見，多個車輛接送多個乘客，乘客和定制公交車輛可以相互選擇，此時需要采用雙邊匹配策略，使公交車輛分配與乘客的選擇達(dá)到穩(wěn)定狀態(tài).本文主要針對第4種“多輛車-多乘客”的情況進(jìn)行優(yōu)化匹配.

表1 4種匹配合乘類型

2 雙邊匹配的定制公交合乘優(yōu)化模型

2.1 乘客的目標(biāo)函數(shù)

2.2 運營商的目標(biāo)函數(shù)

以最大化運營商的收益為目標(biāo)函數(shù)建立模型，選用運營商接客成本和等客時間兩個指標(biāo)來量化運營商的效用.車輛k選擇服務(wù)乘客p的效用函數(shù)為

2.3 約束條件

2.3.1 運營商乘客時間窗約束

由于定制公交服務(wù)乘客較多，必須保證車輛的準(zhǔn)時性，故其等待乘客的時間應(yīng)保持在可以接受范圍

式中：P表示乘坐定制公交車的乘客集合，K表示參與運行的定制公交車的集合.

2.3.2 車容量約束

定制公交車輛k上的乘車人數(shù)，需要小于座位數(shù)

2.3.3 流量約束

保證每名乘客只被分配到一輛公交車

3 生成偏好列表

3.1 乘客的效用矩陣

根據(jù)式（1）得出乘客偏好列表.表2為乘客對車輛的效用矩陣，將表2結(jié)果進(jìn)行排序，得到乘客對車輛的偏好列表（見表3），效用值越大，排序越靠前.

表2 乘客對車輛的效用矩陣

表3 乘客對車輛的偏好列表

3.2 車輛的效用矩陣

根據(jù)式（3）計算出車輛的偏好列表.表4為車輛對乘客的效用矩陣，將表4結(jié)果進(jìn)行排序，得到車輛對乘客的偏好列表（見表5），效用值越大，排序越靠前.

表4 車輛對乘客的效用矩陣

表5 車輛對乘客的偏好列表

4 改進(jìn)的H-R雙邊穩(wěn)定匹配算法

采用改進(jìn)的H-R雙邊匹配算法對問題進(jìn)行求解，首先設(shè)定：①輸入變量：每位乘客對每輛公交車的排序列表，每輛公交車對每位乘客的排序列表.需要強(qiáng)調(diào)的是，如果乘客出行時間不能與公交車進(jìn)行匹配，則將效用賦予很小的值，即使最終結(jié)果匹配，也不能將兩者進(jìn)行匹配.因此，為了使乘客盡可能多的被服務(wù)，需要首先對乘客進(jìn)行優(yōu)先級排序.優(yōu)先級排序的原則是對出行時間窗只能滿足少量公交車的乘客給予優(yōu)先匹配.②輸出變量：滿足穩(wěn)定匹配的M對定制公交車和乘客.算法步驟如下.

步驟一：初始化.初始化所有乘客和車輛元素為未匹配狀態(tài)，初始化配對集合S為空集；將乘客按照可以匹配車輛數(shù)進(jìn)行優(yōu)先級排序，可以匹配車輛數(shù)越少，優(yōu)先級越高.

步驟二：第一輪匹配.第一輪每位乘客p都選擇效用值最大的車輛k進(jìn)行匹配，若車輛k沒有與其他乘客進(jìn)行匹配，則車輛接受乘客的請求；若車輛k已接受其他乘客p′請求服務(wù)，且車容量已達(dá)到最大限制，則車輛k會比較乘客p和p′，選擇優(yōu)先級高的乘客進(jìn)行匹配，優(yōu)先級相同的乘客將按照效用值大小進(jìn)行匹配.未匹配成功的乘客將重新回到初始化列表中.

步驟三：循環(huán)N輪匹配.循環(huán)進(jìn)行步驟二的匹配過程，直至所有乘客都有定制公交車匹配.

5 實例分析

為了驗證定制公交匹配模型的穩(wěn)定性，現(xiàn)以某市道路交通路網(wǎng)為研究對象.某市定制公交線路圖和乘客實時需求信息請求點分別如圖2-3所示.實例中根據(jù)公交公司提供的班車服務(wù)數(shù)據(jù)，將14條班車線路假定為定制公交線路，從400位乘客需求中隨機(jī)抽取1/5數(shù)據(jù)作為乘客實時需求信息.定制公交需要偏移路線或者引導(dǎo)乘客到站乘車.實例中將參數(shù)標(biāo)定結(jié)果為：定制公交車速為50 km/h，車輛運營成本6元/km，α1=0.6，α2=0.4，α3=0.7，α4=0.3.

圖2 某市定制公交線路[10]

圖3 乘客實時需求信息請求點[10]

通過考慮雙邊匹配的定制公交合乘優(yōu)化方法計算，得到80位乘客與14輛定制公交車的匹配結(jié)果：乘客編號 7、23、28、34、39、45、55、58、79 共 9 名乘客效用函數(shù)值過?。ㄜ囕v經(jīng)過路線無法滿足乘車的時間窗要求），將其作為無法服務(wù)的乘客剔除，車輛-乘客匹配結(jié)果如表6所示.

表6 車輛-乘客匹配結(jié)果

進(jìn)一步分析模型的優(yōu)越性，將本模型提出的考慮雙邊匹配的定制公交合乘優(yōu)化方法（S1優(yōu)化策略）與只考慮乘客提出需求時間順序進(jìn)行車輛匹配的方法（S2優(yōu)化策略）進(jìn)行對比，結(jié)果見表7.由表7可知：考慮雙邊匹配的定制公交合乘優(yōu)化方法在保證運送乘客的前提下，可以有效縮短定制公交的運行距離，節(jié)省運營成本；同時也減少了乘客的等待時間，提高了服務(wù)水平和乘客滿意度，并且也減少了未被服務(wù)乘客數(shù)量.其原因是某幾條需求較高的線路由于車容量的限制，導(dǎo)致后續(xù)乘客需求無法被滿足，所以在優(yōu)化過程中，應(yīng)優(yōu)先考慮“瓶頸”乘客的需求首先被滿足.

表7 兩種策略下優(yōu)化結(jié)果比較

6 結(jié)語

單純考慮乘客選擇定制公交的方案，會造成定制公交車輛運營成本增加和運行效率下降，因此在保證乘客和定制公交運營商雙方的利益都得到滿足的前提下，筆者提出一種基于改進(jìn)H-R雙邊匹配的定制公交合乘優(yōu)化方法.結(jié)果顯示所提出的改進(jìn)H-R雙邊匹配算法符合實時調(diào)度需求，最大化服務(wù)乘客的同時，避免了車輛的繞行或車容量達(dá)到飽和的情況發(fā)生，最終達(dá)到降低定制公交車輛運營成本的目的，為實時定制公交線路的開通和運營調(diào)度提供了理論支撐.