孫芮，吳文祥

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

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

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

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

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

1 問題定義與模型設計

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

1.1 相關術語概念

對于合乘出行中，主要基本要素為：司機、乘客與平臺。

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

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

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

1.2 模型設計

1.2.1 前提假設

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

1.2.2 集合

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

1.2.3 決策變量

(1)

(2)

(3)

1.2.4 參數(shù)

1.2.5 模型建立

(4)

1.2.6 約束條件

(1)合乘模式的約束：

(5)

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

(2)節(jié)點約束：

(6)

(7)

式(6)、式(7)確保司機不能同時從兩個不同的位置到達目的地，也不能同時到達兩個不同的目的地[16]。

(3)車容量約束：

(8)

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

(4)司機出行時間窗約束：

(9)

(10)

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

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

(11)

(12)

(13)

(14)

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

(6)乘客與司機到達終點的次序約束：

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

?d∈D；?r∈R

(15)

式(15)確保司機到達自己終點之前會將乘客送至其終點，其中M為一個非常大的值，保證司機與乘客成功匹配后才能驗證該條件。

(7)司機總旅行時間約束：

(16)

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

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

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

2.1 預處理

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

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

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

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

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

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

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

Step 1導入每位司機潛在匹配的乘客集合wd。

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

Step 6更新所有司機的接送方案。

圖1 分解方法示意圖

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

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

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

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

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

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

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

Step 5車輛向前行走一時步距離，在車輛行駛路線中記錄當下行駛路徑信息。

Step 6結束當下時步的操作。

3 實例分析

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

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

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

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

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

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

圖3 不同權重下匹配率

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

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

表1 不同更新時間下的匹配率

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

3.2 算法對比

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

圖4 不方便成本對比

圖5 匹配率對比

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

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

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

4 結論

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

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