網(wǎng)約拼車出行的乘客車輛匹配及路徑優(yōu)化

陳玲娟，寇思佳，柳祖鵬

(武漢科技大學(xué)汽車與交通工程學(xué)院，湖北 武漢 430070)

0 引 言

當(dāng)前我國交通需求類型多樣，數(shù)量日漸增多，交通堵塞等問題日益嚴(yán)重。尤其在出行高峰期，為滿足短時(shí)快速舒適到達(dá)的個(gè)性需求，出租車出行是高峰出行的重要方式之一。然而現(xiàn)有出租車數(shù)量、調(diào)配及費(fèi)用等仍導(dǎo)致部分乘客需求難以滿足。隨著共享理念和拼車出行平臺的興起，私家車提供拼車服務(wù)，在自身出行路線上搭乘線路及時(shí)間匹配度高的乘客，一方面從個(gè)體角度能降低車輛出行成本，減少乘客花費(fèi)，同時(shí)從系統(tǒng)角度能有效提高出行效率、減少系統(tǒng)出行費(fèi)用、緩解交通擁堵。網(wǎng)約拼車出行服務(wù)成為網(wǎng)約車調(diào)度的重要發(fā)展方向，逐漸在我國大中城市盛行，其中乘客與車輛的高效匹配和路徑的合理規(guī)劃是優(yōu)化拼車出行和快速響應(yīng)車輛及乘客需求的核心。因此，分析網(wǎng)約拼車出行服務(wù)特征，構(gòu)建乘客匹配與路徑優(yōu)化模型及算法具有重要意義。

國內(nèi)外學(xué)者在網(wǎng)約車調(diào)度、拼車發(fā)展和網(wǎng)約拼車出行相關(guān)領(lǐng)域進(jìn)行了廣泛的研究。在網(wǎng)約車調(diào)度問題中，Adamczyk等人[1]根據(jù)出租車數(shù)量及行駛時(shí)間等標(biāo)準(zhǔn)，比較3種啟發(fā)式算法并選擇最優(yōu)的蟻群系統(tǒng)算法，研究動態(tài)路線規(guī)劃問題最優(yōu)解；Jiang等人[2]提出了基于LS-SVM的方法對網(wǎng)約車的短期需求預(yù)測進(jìn)行研究，為網(wǎng)約車調(diào)度平臺的優(yōu)化提供理論基礎(chǔ)；Liang等人[3]首次將新能源汽車分配與服務(wù)系統(tǒng)結(jié)合，提出了通過結(jié)合預(yù)選和局部修剪策略增強(qiáng)的高效蟻群系統(tǒng)算法，最大化乘客滿意度；Gao等人[4]將機(jī)器學(xué)習(xí)技術(shù)與兩階段隨機(jī)規(guī)劃模型結(jié)合，提出了一種新的基于學(xué)習(xí)的方法，在網(wǎng)約車調(diào)度過程中可減少70%以上的平均等待時(shí)間；在拼車發(fā)展問題中，文獻(xiàn)[5-8]對國外的拼車可行性及發(fā)展情況進(jìn)行了探討；文獻(xiàn)[9-14]對國內(nèi)的拼車可實(shí)施性及發(fā)展性進(jìn)行了探討。在網(wǎng)約車調(diào)度的基礎(chǔ)上，針對網(wǎng)約拼車出行問題從車輛角度，Hosni等人[15]提出了以車輛總收益最高為目標(biāo)，車輛時(shí)間窗為約束的混合整數(shù)規(guī)劃模型；Santos等人[16]建立了乘車共享和出租車合乘2種模式的組合模型計(jì)算合理路線，解決動態(tài)乘車問題；沙強(qiáng)等人[17]針對定時(shí)定點(diǎn)的私家車上下班模式設(shè)計(jì)了合乘系統(tǒng)以提高車輛乘坐率；曹斌等人[18]設(shè)計(jì)了以車輛總繞路距離最小為目標(biāo)的多對多拼車計(jì)費(fèi)模型。從乘客角度，Ma等人[19]提出根據(jù)乘客路程長度定價(jià)的拼車計(jì)費(fèi)模型，適用于一輛出租車搭乘一名或多名乘客；Lyu等人[20]提出了一種以乘客步行距離、道路網(wǎng)絡(luò)因素及最短出行時(shí)間為目標(biāo)，尋找乘車集合點(diǎn)并計(jì)算最短出行路線的方法；Alonsomora等人[21]構(gòu)建了量化乘客等待時(shí)間和出行延誤時(shí)間等參數(shù)的模型；郭羽含等人[22]針對長期合乘問題，提出了以乘客出行總距離等為目標(biāo)的模型；Luo等人[23]以最大化乘客需求為目標(biāo)，研究了固定預(yù)約時(shí)間和可變預(yù)約時(shí)間2種情況下的最佳競爭率；Cheikh-Graiet等人[24]以最大化乘客滿意度為目標(biāo)，提出了動態(tài)拼車優(yōu)化系統(tǒng)實(shí)現(xiàn)短時(shí)間內(nèi)完成乘客間匹配的方法；從車輛和乘客雙方角度，Maciejewsk等人[25]提出了以減少乘客平均等待時(shí)間和提高出租車乘坐率為目標(biāo)的啟發(fā)式分配模型；歐先鋒等人[26]設(shè)計(jì)了合乘車費(fèi)計(jì)算方法，對合乘和最短路徑進(jìn)行規(guī)劃，兼顧乘客和車輛雙方利益，提升雙方參與合乘的積極性；何勝學(xué)等人[27]以出租車運(yùn)行時(shí)間和乘客出行時(shí)間最小為目標(biāo)，構(gòu)建動態(tài)優(yōu)化模型。

目前，國內(nèi)外關(guān)于拼車出行問題的研究基于不同假設(shè)和不同目標(biāo)求解合乘方案、合成定價(jià)制定等，大多從乘客或車輛的個(gè)體角度制定目標(biāo)，缺乏對系統(tǒng)的整體考慮，且模型算法的使用場景限制較多，如定時(shí)定線、出租車合乘等。本文綜合考慮乘客和車輛雙方信息，以拼車方案中系統(tǒng)所有車輛的使用費(fèi)用，途中出行成本及乘客出行時(shí)間窗懲罰成本最少為目標(biāo)，以車輛容量、乘客出發(fā)及到達(dá)時(shí)間窗、路徑無迂回、乘客車輛匹配無重疊等限制為約束條件建立模型，并采用演化策略算法快速求解模型。

1 網(wǎng)約拼車出行匹配與路徑優(yōu)化模型

1.1 問題界定及假設(shè)

本文考慮的系統(tǒng)網(wǎng)約拼車出行匹配與路徑優(yōu)化的靜態(tài)問題，指在某個(gè)區(qū)域內(nèi)，系統(tǒng)有多輛網(wǎng)約車可調(diào)度，其起止位置、出行路線、空余座位等信息可知，該區(qū)域內(nèi)多名拼車乘客有明確的起終點(diǎn)及個(gè)性化出發(fā)到達(dá)時(shí)間窗限制的拼車需求。拼車出行規(guī)劃流程如圖1所示，拼車平臺整合車輛及乘客雙方信息，對多車多乘客進(jìn)行匹配，給出匹配方案和每輛車的走行路徑。

圖1 拼車出行規(guī)劃流程圖

該問題的求解模型和算法建立基于如下假設(shè)：

1)拼車乘客和車輛的起止位置在匹配和規(guī)劃前均已確定，且車輛的行駛順序須先通過乘客需求起點(diǎn)再到終點(diǎn)。

2)一輛車可以接受多名乘客的拼車請求，每名乘客只搭乘一輛車，不考慮換乘問題。

3)乘客數(shù)量在任何時(shí)刻不能超過該車的最大容量，途中禁止隨意搭乘未拼車乘客。

4)位置信息使用兩點(diǎn)間的直線距離，所有車輛以相同勻速在規(guī)劃路徑上行駛，不考慮停啟時(shí)間、乘客上下車時(shí)間及交通擁堵導(dǎo)致的時(shí)間延誤。

1.2 變量及參數(shù)設(shè)置

M：研究區(qū)域內(nèi)所有拼車乘客的總數(shù)量；m=0,1,…,M表示乘客編號。

N：研究區(qū)域內(nèi)乘客上下車需求點(diǎn)的總數(shù)量，N≤2M。

i、j：乘客上下車需求點(diǎn)編號，0≤i,j≤N-1。

K：網(wǎng)約車總數(shù)量，車輛起止點(diǎn)至多為2K。

Q：車輛的最大載客量，Q=4。

Qk：車輛k的剩余載客量。

qi：需求點(diǎn)i的乘客數(shù)量，在車輛起點(diǎn)位置q0=0。

sij：需求點(diǎn)i與需求點(diǎn)j之間的距離。

Cf：車輛的固定使用成本。

c：車輛單位距離的行駛費(fèi)用，不考慮不同車型導(dǎo)致的成本差異。

(1)

(2)

式(1)中，[rm,lm] 表示乘客m的需求時(shí)間窗，[erm,dlm]表示可接受時(shí)間窗；α1為提早到達(dá)產(chǎn)生的單位等待時(shí)間費(fèi)用，α2為單位時(shí)間遲到費(fèi)用，α3為超出可接受時(shí)間窗產(chǎn)生的單位時(shí)間懲罰費(fèi)用，α1<α2<α3。式(2)表示基于時(shí)間窗的懲罰費(fèi)用。

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

為提高平均乘客滿意度，合理調(diào)配現(xiàn)有資源，以拼車后車輛總費(fèi)用最低和調(diào)用車輛最少為目標(biāo)函數(shù)建立網(wǎng)約拼車出行匹配與路徑優(yōu)化模型。

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

(3)

約束條件：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式(3)目標(biāo)函數(shù)中第一部分為車輛的行駛費(fèi)用，第二部分表示車輛的使用費(fèi)用，第三部分為車輛基于時(shí)間窗的懲罰費(fèi)用；式(4)表示調(diào)用網(wǎng)約車數(shù)量不超過車輛總數(shù)；式(5)、式(6)表示乘客只能接受1輛車服務(wù)，或者車輛不夠，部分乘客不能被服務(wù)；式(7)、式(8)分別表示車輛在每個(gè)乘客需求點(diǎn)均只經(jīng)過一次；式(9)表示任意乘客m在起點(diǎn)im和終點(diǎn)i′m都被同一輛車服務(wù)，或都不被服務(wù)；式(10)為車輛容量約束；式(11)為時(shí)間窗約束，不允許到達(dá)時(shí)間超過可接受時(shí)間窗，即式(2)中α3=∞；式(12)表示搭載乘客m的車輛必須先到達(dá)im后到達(dá)i′m。

2 問題求解

靜態(tài)網(wǎng)約車的優(yōu)化模型求解關(guān)鍵在于車輛與乘客的匹配關(guān)系，當(dāng)出行高峰期，車輛數(shù)和乘客數(shù)都激增時(shí)，可行解空間也呈現(xiàn)大規(guī)模增長。因此，本文采用演化算法求解匹配關(guān)系。

1)個(gè)體編碼：對M個(gè)乘客依次進(jìn)行編號[1,2，…，M]，采用整數(shù)編碼，在區(qū)間[1,M]內(nèi)隨機(jī)生成M個(gè)取值不同的整數(shù)構(gòu)成個(gè)體編碼Y=[y1,y2，…，yM]。

2)個(gè)體解碼：對個(gè)體編碼[y1,y2，…，yM]從小到大排序，得到[y′1,y′2,…,y′M]，對應(yīng)的乘客編號調(diào)整為[m1,m2,…,mM]，按車輛編號[1,2,…,n]依次完成匹配關(guān)系。

①對車輛a，將Y的首個(gè)基因所代表的乘客匹配給車輛，計(jì)算車輛到達(dá)該點(diǎn)的剩余容量和時(shí)間，如果滿足時(shí)間窗約束，則將其作為車輛所經(jīng)路徑的第一個(gè)到達(dá)點(diǎn)。

②對Y從左至右依次尋找滿足車容量和時(shí)間窗的乘客，匹配進(jìn)該車輛，同時(shí)更新車輛容量和所在位置、到達(dá)時(shí)間等信息。

③若車輛已滿員或已查找完Y中所有乘客，則完成該車輛的乘客匹配，并按匹配順序得到車輛路徑Ra，并將所用車輛數(shù)加1。

④去掉Y中路徑Ra上的所有乘客，其余基因順序不變，更新編碼串Y，返回①，重復(fù)該操作，直到所有乘客均被匹配，得到全部車輛路徑及總使用車輛數(shù)。

3)滿意度值計(jì)算：由上述編碼和解碼過程可以看到，車輛乘客匹配和按乘客次序的路徑求解可以滿足模型約束式(4)～式(12)，保證了車輛與乘客的一一對應(yīng)，滿足時(shí)間窗及容量約束，并遵循先接乘客后到達(dá)的原則。將解碼過程中所有使用車輛的路徑、到達(dá)各點(diǎn)的時(shí)間、總車輛數(shù)等信息代入目標(biāo)函數(shù)式(3)，求得個(gè)體編碼的滿意度值。

4)交叉算子：使用改進(jìn)的部分匹配交叉操作來產(chǎn)生新個(gè)體，具體過程如圖2所示。

圖2 部分匹配交叉示意圖

①隨機(jī)選擇一對個(gè)體編碼Y1、Y2，隨機(jī)選取Y1、Y2中2處相同長度編碼片段，即乘客編號，進(jìn)行標(biāo)記。

②互換Y1、Y2中選中的片段，形成子代個(gè)體編碼Y′1、Y′2，Y′1、Y′2中可能存在重復(fù)的乘客編號。

5)變異算子：對個(gè)體編碼Y，隨機(jī)產(chǎn)生2個(gè)取值在[1,M]的整數(shù)，交換該兩點(diǎn)處的基因值，產(chǎn)生新的個(gè)體。如圖3所示。

圖3 變異示意圖

6)對初始個(gè)體編碼進(jìn)行操作3)～5)，得到新種群和新個(gè)體，未達(dá)到迭代終止條件時(shí)，返回操作3)，重復(fù)上述操作。

7)迭代終止條件：設(shè)定以預(yù)設(shè)代數(shù)為算法終止規(guī)則，計(jì)算時(shí)迭代次數(shù)達(dá)到預(yù)設(shè)代數(shù)，則迭代終止，解碼得到全部車輛的路徑、總使用車輛數(shù)及總成本。

3 算例分析

算例初始數(shù)據(jù)采用隨機(jī)函數(shù)生成10輛車的起終點(diǎn)、出發(fā)時(shí)間及最晚到達(dá)時(shí)間和車輛容量信息，并在車輛起終點(diǎn)周圍隨機(jī)生成25個(gè)乘客需求點(diǎn)信息，包括起終點(diǎn)、出發(fā)時(shí)間窗、到達(dá)時(shí)間窗和人數(shù)。取編碼長度L=25，種群規(guī)模N=200，交叉概率Pc=0.4，變異概率Pm=0.9，終止迭代次數(shù)為100，車速v=50 km/h，車輛單位距離的行駛費(fèi)用c=1.5 元/km，車輛固定的使用成本Cf=20 元，早到懲罰系數(shù)α1=5，晚到懲罰系數(shù)α2=15，可接受早到時(shí)長er=8 min，可接受晚到時(shí)長dl=5 min。非拼車路長和車輛非拼車費(fèi)用計(jì)算公式分別如式(13)、式(14)所示：

(13)

(14)

式中，h、h′為車輛起終點(diǎn)，dhh′為車輛非拼車時(shí)起終點(diǎn)間的行駛距離；i、i′為乘客需求起終點(diǎn)，sii′為乘客需求起終點(diǎn)間的出行距離；式(13)中第一部分表示車輛非拼車時(shí)的行駛距離，第二部分表示乘客非拼車時(shí)的出行距離；式(14)中第一部分為車輛非拼車時(shí)的行駛費(fèi)用，第二部分為車輛非拼車時(shí)的固定使用成本。

使用MATLAB對上述演化策略算法進(jìn)行計(jì)算，車輛出行信息、乘客需求信息設(shè)定如表1和表2所示。

表1 車輛出行信息表

表2 乘客需求信息表

使用10輛車和25個(gè)乘客需求計(jì)算車輛短缺情況(總需求數(shù)多于車輛總空余座位數(shù))，再使用10輛車和隨機(jī)選取的編號為1、2、4、8、13、17、18、20、21、24的10個(gè)乘客需求點(diǎn)計(jì)算車輛充足情況(總需求數(shù)少于車輛總空余座位數(shù))。運(yùn)行本文設(shè)計(jì)的演化算法，得到車輛短缺情況下的搜索過程及拼車方案路徑優(yōu)化結(jié)果如圖4、圖5所示。從圖4可看到，經(jīng)過50次搜索后，計(jì)算結(jié)果趨于穩(wěn)定，表明終止迭代次數(shù)取100是有效的。從圖5可看到，每輛車從起始點(diǎn)到終止點(diǎn)的走行路徑及所匹配乘客情況。

圖4 車輛短缺情況下的搜索過程

圖5 車輛短缺情況下的路徑優(yōu)化結(jié)果

車輛短缺情況下網(wǎng)約拼車出行匹配與路徑優(yōu)化的車輛與乘客需求點(diǎn)的匹配情況、車輛單獨(dú)行駛和乘客單獨(dú)乘車時(shí)的非拼車路徑長度及總費(fèi)用與車輛和乘客拼車時(shí)的路徑長度、懲罰費(fèi)用及總費(fèi)用如表3所示。由表3可得，車輛短缺時(shí)，10輛車共搭載26名乘客，仍有部分車輛存有搭載能力，但由于時(shí)間窗的約束導(dǎo)致部分乘客不能匹配。拼車后，路徑總長度相比非拼車路徑總長度減少93.6 km，拼車總費(fèi)用降低129.4元，具有懲罰費(fèi)用的車輛和懲罰費(fèi)用均較少。

表3 車輛短缺情況下的匹配情況、路徑長度和費(fèi)用結(jié)果

車輛充足情況下的搜索過程及拼車方案路徑優(yōu)化結(jié)果如圖6、圖7所示。同樣從圖6可看到，迭代100次后，計(jì)算結(jié)果滿足收斂要求。圖7中給出了5輛車的路徑結(jié)果，16名乘客全部匹配成功，車輛并未全部調(diào)用。

圖6 車輛充足情況下的搜索過程

圖7 車輛充足情況下的路徑優(yōu)化結(jié)果

車輛充足情況下網(wǎng)約拼車出行匹配與路徑優(yōu)化的車輛與乘客需求點(diǎn)的匹配情況、車輛單獨(dú)行駛和乘客單獨(dú)乘車時(shí)的非拼車路徑長度及總費(fèi)用與車輛和乘客拼車時(shí)的路徑長度、懲罰費(fèi)用及總費(fèi)用如表4所示。從表4中可看到，車輛充足時(shí)，共調(diào)用5輛車，10個(gè)乘客需求點(diǎn)共16名乘客均被搭載，拼車路徑總長度相對非拼車路徑總長度減少36.7 km，拼車總費(fèi)用降低50.8元，只有一輛車具有少量懲罰費(fèi)用。

表4 車輛充足情況下的匹配情況、路徑長度和費(fèi)用結(jié)果

算例數(shù)據(jù)中包含部分乘客與車輛具有相同起終點(diǎn)的特殊情況，對算例結(jié)果進(jìn)行分析，乘客需求點(diǎn)19與車輛7具有相同終點(diǎn)、乘客需求點(diǎn)16與車輛2具有相同起終點(diǎn)，乘客需求點(diǎn)5與14具有相同起點(diǎn)、乘客需求點(diǎn)10與21具有相同終點(diǎn)、乘客需求點(diǎn)4與18、11與22具有相同起終點(diǎn)，但由于出發(fā)到達(dá)時(shí)間窗和懲罰費(fèi)用等限制，與車輛起終點(diǎn)相同的乘客不一定匹配到該車輛，相同起終點(diǎn)的乘客也不一定匹配到同輛車，與實(shí)際相符。若能實(shí)現(xiàn)車輛信息和乘客出行信息的提前發(fā)布和時(shí)間窗動態(tài)調(diào)整，能大幅降低總成本?？傮w來看，該算法能實(shí)現(xiàn)乘客與車輛、乘客與乘客的合理匹配，車輛空位的有效利用、行駛路徑和出行費(fèi)用的合理優(yōu)化，達(dá)到了平均乘客滿意度較高。

4 結(jié)束語

本文以含有時(shí)間窗的多車輛靜態(tài)拼車為研究對象，從車輛出行成本和乘客時(shí)間窗內(nèi)出行的雙方利益角度分析了網(wǎng)約拼車出行的費(fèi)用結(jié)構(gòu)，在滿足車輛容量，路徑規(guī)劃，車輛分配等約束條件下以拼車總費(fèi)用最少建立了網(wǎng)約出行匹配和路徑優(yōu)化模型。并采用智能演化算法，給出了求解可行解的編碼解碼方法和最優(yōu)解搜索的運(yùn)算步驟。運(yùn)用MATLAB進(jìn)行算例分析，分別計(jì)算了車輛短缺和車輛充足2種情況下的匹配方案和路徑優(yōu)化，驗(yàn)證了算法的有效性，表明合理匹配可實(shí)現(xiàn)調(diào)用車輛資源、平均乘客滿意度、拼車路徑和費(fèi)用優(yōu)化。同時(shí)發(fā)現(xiàn)由于出行時(shí)間懲罰函數(shù)的影響，使得相同起終點(diǎn)，時(shí)間間隔小的車輛和乘客也無法匹配，說明了乘客和車輛信息對稱的重要性。

本文對網(wǎng)約拼車出行問題求解算法進(jìn)行了研究，提出的模型和算法能快速響應(yīng)拼車乘客和車輛的匹配及路徑規(guī)劃需求，但模型僅考慮靜態(tài)優(yōu)化問題，未考慮乘客需求和網(wǎng)約車供給的動態(tài)變化，同時(shí)模型中路徑的優(yōu)化以起終點(diǎn)距離為依據(jù)，未考慮城市路網(wǎng)道路擁堵導(dǎo)致的額外時(shí)間成本，在后續(xù)研究中，將作為進(jìn)一步探討的方向。