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

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

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

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

1 問(wèn)題描述

1.1 研究思路

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

圖1 定制公交合乘問(wèn)題研究思路

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

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

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

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

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

1.3.2 雙邊匹配合乘類(lèi)型

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

表1 4種匹配合乘類(lèi)型

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

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

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

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

2.3 約束條件

2.3.1 運(yùn)營(yíng)商乘客時(shí)間窗約束

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

式中：P表示乘坐定制公交車(chē)的乘客集合，K表示參與運(yùn)行的定制公交車(chē)的集合.

2.3.2 車(chē)容量約束

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

2.3.3 流量約束

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

3 生成偏好列表

3.1 乘客的效用矩陣

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

表2 乘客對(duì)車(chē)輛的效用矩陣

表3 乘客對(duì)車(chē)輛的偏好列表

3.2 車(chē)輛的效用矩陣

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

表4 車(chē)輛對(duì)乘客的效用矩陣

表5 車(chē)輛對(duì)乘客的偏好列表

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

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

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

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

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

5 實(shí)例分析

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

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

圖3 乘客實(shí)時(shí)需求信息請(qǐng)求點(diǎn)[10]

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

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

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

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

6 結(jié)語(yǔ)

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