基于分解算法的動(dòng)態(tài)大規(guī)模合乘匹配-路徑規(guī)劃

孫芮，吳文祥

(北方工業(yè)大學(xué)電氣與控制工程學(xué)院，北京 100144)

隨著經(jīng)濟(jì)發(fā)展與城鎮(zhèn)化進(jìn)程的加快，交通擁堵問題日益嚴(yán)重[1]。共享出行作為一種綠色出行方式，為城市走綠色可持續(xù)交通開拓新道路[2]。合乘問題近年來吸引了許多學(xué)者研究，研究目的是解決如何以盡可能小的出行成本實(shí)現(xiàn)最優(yōu)匹配與路徑規(guī)劃，這類研究通常以匹配率、出行時(shí)間等為目標(biāo)函數(shù)，建立合乘匹配與路徑優(yōu)化模型，根據(jù)模型特點(diǎn)設(shè)計(jì)相應(yīng)的算法求解。

在合乘匹配與路徑優(yōu)化模型的研究中，Lee等[3]提出了使用專職司機(jī)為乘客提供服務(wù)的成本最小目標(biāo)函數(shù)，結(jié)果表明合乘最具影響的因素有：合乘過程中參與者數(shù)量、參與者時(shí)間靈活性、參與者出發(fā)地與目的地的相似性。張亦楠[4]以路網(wǎng)的訂單匹配率作為目標(biāo)函數(shù)，利用粒子群算法求解。文獻(xiàn)[5-9]以最小化出行成本、最大訂單匹配率等作為模型的目標(biāo)函數(shù)，對(duì)動(dòng)態(tài)車輛調(diào)度問題進(jìn)行優(yōu)化。但上述研究中，大都考慮訂單匹配率或乘客出行成本，不能在滿足高匹配率的前提下，實(shí)現(xiàn)司機(jī)與乘客的低成本出行。

面對(duì)超大規(guī)模的訂單數(shù)量，需要通過高效的算法來獲得最終匹配方案和路徑規(guī)劃。學(xué)者們提出了各種算法來解決該問題，這些算法可以分為兩類，精確算法和啟發(fā)式算法。在精確算法的研究中：Duan等[10]提出了動(dòng)態(tài)規(guī)劃算法求解司機(jī)與乘客在不同區(qū)域下合乘匹配率。Armant等[11]在混合整數(shù)規(guī)劃算法中引入約束規(guī)劃公式，解決了使用累積約束和時(shí)間依賴性的問題，提高了合乘匹配率。Victoria等[12]分別采用列生成算法和整數(shù)規(guī)劃算法，求解時(shí)變需求下具有時(shí)間窗容量限制的車輛調(diào)度問題。對(duì)中小規(guī)模實(shí)例測試結(jié)果表明，列生成算法比整數(shù)規(guī)劃算法具有更好的效果。在啟發(fā)式算法研究方面：Santos等[13]將一天時(shí)間進(jìn)行劃分，對(duì)每個(gè)時(shí)間段創(chuàng)建一個(gè)靜態(tài)問題的實(shí)例，并用貪心隨機(jī)自適應(yīng)搜索程序(greedy randomized adaptive search procedures, GRASP)求解。Alonso-Mora等[14]提出了一種更通用的實(shí)時(shí)大容量合乘匹配模型，利用貪心算法求解最優(yōu)合乘方案，基于紐約市出租車數(shù)據(jù)測試，該模型和算法可以有效解決大規(guī)模動(dòng)態(tài)合乘問題。宋超超等[15]提出了一種粒子群算法求解動(dòng)態(tài)合乘問題，結(jié)果表明該算法能夠以較高的服務(wù)率與較低的成本完成車輛合乘匹配問題。在上述研究中，精確算法可以得到合乘的最優(yōu)解，但搜索最優(yōu)解會(huì)消耗過多的計(jì)算能力和存儲(chǔ)空間。啟發(fā)式算法效率較高，但無法找到真正意義上的最短路徑，造成車輛繞道距離增大，導(dǎo)致本該匹配成功的司機(jī)與乘客不能成功匹配。

針對(duì)以上研究局限，所構(gòu)建的合乘匹配模型考慮了訂單匹配數(shù)量、司機(jī)旅行時(shí)間、乘客等待時(shí)間與乘客延誤時(shí)間4個(gè)指標(biāo)，滿足高匹配率的前提下實(shí)現(xiàn)司機(jī)-乘客高質(zhì)量匹配。針對(duì)模型特性，設(shè)計(jì)了基于分解方法的司機(jī)-乘客合乘匹配與路徑規(guī)劃算法。通過引入數(shù)據(jù)預(yù)處理模塊減小合乘匹配問題的規(guī)模，設(shè)計(jì)分解算法將大規(guī)模合乘匹配問題分解為各個(gè)獨(dú)立子問題迭代解決，加快平臺(tái)對(duì)司機(jī)-乘客的匹配速度，實(shí)現(xiàn)司機(jī)-乘客的最優(yōu)匹配。匹配完成后，調(diào)用百度API(application programming interface)線規(guī)劃服務(wù)，獲取司機(jī)-乘客合乘的最短路徑規(guī)劃。研究結(jié)果對(duì)緩解交通擁堵、推動(dòng)合乘服務(wù)現(xiàn)代化發(fā)展以及降低出行者的出行成本具有重要的理論與現(xiàn)實(shí)意義。

1 問題定義與模型設(shè)計(jì)

首先詳細(xì)描述動(dòng)態(tài)合乘匹配問題涉及的基本概念。隨后針對(duì)該問題，建立了帶有約束條件的合乘匹配模型。

1.1 相關(guān)術(shù)語概念

對(duì)于合乘出行中，主要基本要素為：司機(jī)、乘客與平臺(tái)。

定義1(司機(jī))在動(dòng)態(tài)合乘中，私家車司機(jī)用d表示，路網(wǎng)中司機(jī)的集合用D表示。司機(jī)向平臺(tái)提交合乘請求，請求包含的屬性有：起點(diǎn)與終點(diǎn)經(jīng)緯度坐標(biāo)、請求時(shí)間、起點(diǎn)出發(fā)時(shí)間窗、終點(diǎn)到達(dá)時(shí)間窗、車輛最大承載人數(shù)。

定義2(乘客)在動(dòng)態(tài)合乘中，乘客用r表示，路網(wǎng)中乘客的集合用R表示。乘客向平臺(tái)提交合乘請求，請求包含的屬性有：起點(diǎn)與終點(diǎn)經(jīng)緯度坐標(biāo)、請求時(shí)間、起點(diǎn)出發(fā)時(shí)間窗，終點(diǎn)到達(dá)時(shí)間窗。

定義3(平臺(tái))在動(dòng)態(tài)合乘中，平臺(tái)每次更新信息，接收司機(jī)與乘客的合乘請求。平臺(tái)在司機(jī)與乘客的出行時(shí)間窗內(nèi)，將訂單分配給司機(jī)，為司機(jī)規(guī)劃行駛路線，最終完成司機(jī)與乘客的合乘行為。

1.2 模型設(shè)計(jì)

1.2.1 前提假設(shè)

提出的動(dòng)態(tài)合乘匹配模型，做如下假設(shè)：①每輛私家車的最大承載能力是有限并預(yù)先給定的；②假設(shè)車輛的運(yùn)行不受道路交通狀況的影響，車輛以恒定車速行駛；③不考慮乘客的上下車時(shí)間；④在合乘出行過程中，一個(gè)司機(jī)能夠服務(wù)多位乘客，但一位乘客只能被一個(gè)司機(jī)服務(wù)；⑤每位乘客與司機(jī)的出行信息都包含出行時(shí)間窗，出行時(shí)間窗代表從起點(diǎn)出發(fā)的時(shí)間窗與到達(dá)終點(diǎn)的時(shí)間窗。

1.2.2 集合

設(shè)D為司機(jī)的集合，R為乘客的集合，N為路網(wǎng)中節(jié)點(diǎn)的集合，A為路網(wǎng)中路段的集合。

1.2.3 決策變量

(1)

(2)

(3)

1.2.4 參數(shù)

1.2.5 模型建立

(4)

1.2.6 約束條件

(1)合乘模式的約束：

(5)

式(5)確保一位乘客只能被一位司機(jī)服務(wù)。

(2)節(jié)點(diǎn)約束：

(6)

(7)

式(6)、式(7)確保司機(jī)不能同時(shí)從兩個(gè)不同的位置到達(dá)目的地，也不能同時(shí)到達(dá)兩個(gè)不同的目的地[16]。

(3)車容量約束：

(8)

式(8)確保一輛車中所有乘客數(shù)量必須小于等于車輛的最大承載人數(shù)。

(4)司機(jī)出行時(shí)間窗約束：

(9)

(10)

式(9)、式(10)確保司機(jī)實(shí)際出發(fā)與到達(dá)時(shí)間分別滿足出發(fā)時(shí)間窗與到達(dá)時(shí)間窗。

(5)乘客出行時(shí)間窗約束：

(11)

(12)

(13)

(14)

式(11)、式(12)確保乘客實(shí)際上車時(shí)間滿足其出發(fā)時(shí)間窗，式(13)、式(14)確保乘客實(shí)際到達(dá)時(shí)間滿足其到達(dá)時(shí)間窗。

(6)乘客與司機(jī)到達(dá)終點(diǎn)的次序約束：

tdd-[tdr+tdr,dd-M(1-adr)]≥0,

?d∈D；?r∈R

(15)

式(15)確保司機(jī)到達(dá)自己終點(diǎn)之前會(huì)將乘客送至其終點(diǎn)，其中M為一個(gè)非常大的值，保證司機(jī)與乘客成功匹配后才能驗(yàn)證該條件。

(7)司機(jī)總旅行時(shí)間約束：

(16)

式(16)確保該司機(jī)的總旅行時(shí)間小于等于司機(jī)能夠在該行程中花費(fèi)的最大時(shí)間。

2 基于分解方法的合乘匹配與路徑規(guī)劃算法

該節(jié)具體介紹基于分解方法的合乘匹配與路徑規(guī)劃算法。通過預(yù)處理篩選出司機(jī)能夠潛在匹配的乘客集合，利用分解算法，將路網(wǎng)中所有司機(jī)匹配問題分解為各個(gè)獨(dú)立的子問題進(jìn)行最優(yōu)匹配，最后調(diào)取百度地圖API路線規(guī)劃功能，獲得司機(jī)行駛最短路徑。

2.1 預(yù)處理

為了提高計(jì)算的效率，有必要在進(jìn)行分解算法前對(duì)數(shù)據(jù)預(yù)處理，減小合乘匹配問題的規(guī)模，篩選出作為可行解的司機(jī)-乘客匹配方案。具體步驟如下。

Step 1初始化，記錄路網(wǎng)中司機(jī)與乘客的起終點(diǎn)數(shù)據(jù)與出行時(shí)間窗。

Step 2數(shù)據(jù)預(yù)處理，根據(jù)司機(jī)與乘客的起終點(diǎn)，通過時(shí)空約束條件，篩選出司機(jī)d能夠潛在匹配的乘客集合wd。

Step 3更新每位司機(jī)潛在匹配的乘客集合wd。

2.2 基于分解方法的合乘匹配與路徑規(guī)劃算法

2.2.1 基于分解方法的合乘匹配算法

為了提高算法的實(shí)時(shí)性，將路網(wǎng)中所有司機(jī)與乘客的合乘匹配問題，分解為各個(gè)獨(dú)立的子問題迭代解決，具體步驟如下。

Step 1導(dǎo)入每位司機(jī)潛在匹配的乘客集合wd。

Step 5判斷發(fā)生沖突的子問題中合乘質(zhì)量大小，合乘質(zhì)量最大的司機(jī)d獲得服務(wù)該沖突乘客的優(yōu)先權(quán)，其余司機(jī)選擇次優(yōu)的方案作為最優(yōu)接送方案，若某位司機(jī)的所有接送方案中的乘客都存在沖突，則從wd中摘除該名乘客，跳轉(zhuǎn)至Step 3，直至找到最優(yōu)的司機(jī)-乘客匹配方案。

Step 6更新所有司機(jī)的接送方案。

圖1 分解方法示意圖

基于分解方法的合乘匹配算法能夠?qū)⒙肪W(wǎng)中所有司機(jī)與乘客的匹配問題，分解為各位司機(jī)最優(yōu)匹配的獨(dú)立子問題迭代求解，加快動(dòng)態(tài)合乘中的匹配速度。該分解算法能夠得到所有司機(jī)與乘客的最優(yōu)匹配方案，方案包含了司機(jī)接送乘客的順序，乘客所在節(jié)點(diǎn)等信息，是下一步動(dòng)態(tài)路徑規(guī)劃算法的數(shù)據(jù)基礎(chǔ)。

2.2.2 動(dòng)態(tài)路徑規(guī)劃算法

通過分解算法，得到司機(jī)將要接送的乘客順序與乘客所在節(jié)點(diǎn)的經(jīng)緯度信息。司機(jī)從當(dāng)下位置行駛至下一位位置的路徑有多條，如何選擇最短路徑是該動(dòng)態(tài)路徑規(guī)劃算法的研究內(nèi)容。本文通過調(diào)取百度地圖API中路線規(guī)劃服務(wù)，獲取車輛行駛的最短路徑，具體步驟如下。

Step 1平臺(tái)更新，判斷司機(jī)d是否沒有出發(fā)且期望發(fā)車時(shí)間小于當(dāng)下時(shí)間，是，則該司機(jī)d信息重新進(jìn)行動(dòng)態(tài)匹配，否則跳轉(zhuǎn)至Step 2。

Step 2判斷車輛是否到達(dá)終點(diǎn)，如果是，記錄并保存司機(jī)d行駛路徑集合，該路徑集合為司機(jī)d最短路徑的集合，如果否，跳轉(zhuǎn)至Step 3。

Step 3根據(jù)最優(yōu)司機(jī)-乘客匹配方案，獲取當(dāng)下階段車輛所在位置與將要行駛的下一個(gè)位置經(jīng)緯度信息。

Step 4向百度地圖API路徑服務(wù)器發(fā)出請求，獲取當(dāng)下位置與下一個(gè)位置的可選路徑集合，選擇最短路徑為車輛當(dāng)下階段要行駛的路徑。

Step 5車輛向前行走一時(shí)步距離，在車輛行駛路線中記錄當(dāng)下行駛路徑信息。

Step 6結(jié)束當(dāng)下時(shí)步的操作。

3 實(shí)例分析

以成都市滴滴網(wǎng)約車訂單數(shù)據(jù)為基礎(chǔ)進(jìn)行試驗(yàn)與分析，通過Python語言進(jìn)行計(jì)算與結(jié)果圖展示。

3.1 數(shù)據(jù)分析

為了比較乘客合乘上下車位置的時(shí)空分布，選擇工作日中的12:00—18:00時(shí)間段的合乘數(shù)據(jù)進(jìn)行分析。圖2為乘客上車位置與下車位置的熱力圖。

圖2 乘客上下車位置熱力圖

由于成都市“三環(huán)十六射”的路網(wǎng)結(jié)構(gòu)，通過合乘的上下車位置熱力圖分析，入城與出城的熱力分布較為顯著。通過圖2(a)可知，乘客的上車點(diǎn)有少部分集中在各入城路段周圍，但多集中在環(huán)線以內(nèi)，說明大部分乘客有出城的出行需求。乘客的下車點(diǎn)雖然很大部分集中在環(huán)線以內(nèi)，但大量乘客的下車點(diǎn)分布在環(huán)線外[圖2(b)]，即出城路段的周圍。圖2表明合乘匹配的時(shí)空效果較好。

通過設(shè)置平臺(tái)的更新時(shí)間為15 s，車輛最大承載能力為4人，路網(wǎng)中司機(jī)與乘客的比例為1∶3，調(diào)節(jié)優(yōu)化模型中的3個(gè)權(quán)重指標(biāo)α、β和γ，分析一周內(nèi)網(wǎng)約車合乘數(shù)據(jù)在不同權(quán)重下的訂單成功匹配率，結(jié)果如圖3所示。

圖3 不同權(quán)重下匹配率

由圖3可知，一周內(nèi)的乘客成功匹配率平均保持在80%以上。如圖3(a)所示，當(dāng)司機(jī)旅行時(shí)間的權(quán)重占比0.7，乘客等待時(shí)間與延誤時(shí)間權(quán)重各占比0.15時(shí)，一周內(nèi)每天8:00—20:00的匹配率穩(wěn)定在85%以上，0:00—8:00與20:00—24:00的匹配率較低。如圖3(b)所示，當(dāng)司機(jī)旅行時(shí)間的權(quán)重占比0.5，乘客等待時(shí)間與延誤時(shí)間權(quán)重各占0.25時(shí)，每天的平均匹配率穩(wěn)定在70%～80%。如圖3(c)所示，當(dāng)司機(jī)旅行時(shí)間的權(quán)重占比0.3，乘客等待時(shí)間與延誤時(shí)間權(quán)重各占0.35時(shí)，每天的匹配率呈現(xiàn)出明顯的高峰與平峰，7:00—10:00匹配率高達(dá)90%以上，17:00—21:00匹配率也均在85%左右，而其余時(shí)間段的司機(jī)-乘客匹配率相比較低。

通過調(diào)節(jié)系統(tǒng)的更新時(shí)間、路網(wǎng)中車輛與乘客的比例，分析當(dāng)下路網(wǎng)中車輛數(shù)與乘客數(shù)的改變對(duì)匹配率的影響，匹配率數(shù)據(jù)如表1所示。

表1 不同更新時(shí)間下的匹配率

由表1數(shù)據(jù)可知，隨著更新時(shí)間的延長，司機(jī)-乘客匹配率有小幅度增長，但增長效果不明顯。當(dāng)路網(wǎng)中車輛數(shù)增多，司機(jī)-乘客匹配率有顯著的增加，說明路網(wǎng)中能夠服務(wù)乘客的車輛數(shù)量，對(duì)匹配率有著重要影響。

3.2 算法對(duì)比

在以往研究中，遺傳算法、貪心隨機(jī)自適應(yīng)搜索算法與粒子群算法等廣泛用于求解動(dòng)態(tài)匹配與路徑規(guī)劃模型。通過選用求解效果較好的貪心隨機(jī)自適應(yīng)搜索算法、粒子群算法[13-15]與所提出的基于分解方法的合乘匹配與路徑規(guī)劃算法進(jìn)行對(duì)比，分析本文算法求解動(dòng)態(tài)規(guī)劃模型的實(shí)際應(yīng)用價(jià)值。數(shù)據(jù)選擇工作日中7:00—9:00的合乘請求數(shù)據(jù)驗(yàn)證，算法對(duì)比結(jié)果如圖4、圖5所示。

圖4 不方便成本對(duì)比

圖5 匹配率對(duì)比

如圖4所示，基于分解方法的合乘匹配與路徑規(guī)劃算法結(jié)果優(yōu)于粒子群算法與貪心算法。圖4(a)中，3個(gè)算法的司機(jī)旅行時(shí)間峰值大多集中在30 min，但分解算法下旅行時(shí)間峰值明顯小于30 min，說明該算法下司機(jī)旅行時(shí)間較短。圖4(b)中，貪心與粒子群兩個(gè)算法的乘客等待時(shí)間集中在15～30 min，但分解算法下大部分乘客等待時(shí)間在10 min以內(nèi)。圖4(c)中，貪心與粒子群算法的乘客延誤時(shí)間峰值在20～30 min，但分解算法下乘客延誤時(shí)間峰值在10 min左右。從司機(jī)與乘客的出行成本方面考慮，司機(jī)旅行時(shí)間短，有利于調(diào)動(dòng)司機(jī)服務(wù)的積極性，乘客等待與延誤時(shí)間短，會(huì)增加乘客在合乘中被服務(wù)的滿意度，減少日后訂單流失的概率，所以分解算法在實(shí)際中有較好的反饋效果。

由圖5可知，隨著平臺(tái)更新時(shí)間的增加，3種算法的匹配率都隨之增高，但分解算法的匹配率遠(yuǎn)在貪心與粒子群算法之上，總體匹配率遠(yuǎn)高于85%，表明分解算法能夠保證路網(wǎng)中較高的匹配率。

綜上，通過對(duì)所提出的基于分解方法的合乘匹配與路徑規(guī)劃算法與貪心隨機(jī)自適應(yīng)搜索算法、粒子群算法實(shí)例對(duì)比，結(jié)果表明，本文算法能夠在平臺(tái)更新時(shí)間內(nèi)進(jìn)行快速動(dòng)態(tài)匹配，保證較高匹配率的基礎(chǔ)上，實(shí)現(xiàn)高質(zhì)量的司機(jī)-乘客匹配，提高整個(gè)路網(wǎng)的服務(wù)質(zhì)量。

4 結(jié)論

針對(duì)現(xiàn)有動(dòng)態(tài)合乘中司機(jī)-乘客匹配質(zhì)量不高，算法實(shí)時(shí)性差等研究局限，構(gòu)建了考慮訂單匹配數(shù)量、司機(jī)行駛時(shí)間、乘客等待時(shí)間與乘客延誤時(shí)間的合乘匹配模型，在保證高匹配率的前提下，提高司機(jī)與乘客在合乘過程中的滿意程度。同時(shí)根據(jù)模型特點(diǎn)，設(shè)計(jì)了基于分解方法的合乘匹配與路徑規(guī)劃算法，將整個(gè)路網(wǎng)的司機(jī)-乘客匹配問題分解為各個(gè)獨(dú)立的子問題迭代求解，提高了算法的實(shí)時(shí)性，加快了動(dòng)態(tài)合乘匹配的效率。

現(xiàn)有研究中司機(jī)與乘客出行時(shí)間窗只在數(shù)據(jù)預(yù)處理時(shí)作為硬約束，日后可對(duì)出行時(shí)間窗進(jìn)行分析，研究不同時(shí)間窗下對(duì)路網(wǎng)服務(wù)率的影響。經(jīng)濟(jì)因素也是司機(jī)與乘客選擇合乘的原因之一，如何在合乘過程中對(duì)司機(jī)補(bǔ)貼以及乘客公平的定價(jià)，也是接下來研究的重點(diǎn)。