基于整數(shù)線性規(guī)劃的合乘出租車調(diào)度模型

李輝春，李哲民，毛紫陽

（1.國防科技大學(xué) 文理學(xué)院體系科學(xué)系，湖南 長沙 410073；2.國防科技大學(xué) 文理學(xué)院數(shù)學(xué)系，湖南 長沙 410073）

0 引言

在很多大中型城市存在打車困難的現(xiàn)象，尤其是上下班時段乘客出行需求高，打車更加困難?；谶@種現(xiàn)實情況，出租車合乘業(yè)務(wù)便應(yīng)運而生。它是指路線相同或相近的兩位或多位乘客共同乘坐同一輛出租車出行?，F(xiàn)有的出租車合乘調(diào)度方案存在模型復(fù)雜、合乘率低、合乘繞行距離遠、乘客等待時間長等問題，如何設(shè)計一個調(diào)度系統(tǒng)，使得乘客等待的時間和繞行的距離最小，從而提高乘客滿意度，讓更多乘客愿意選擇合乘的出行方式，顯得尤為重要。本文主要討論如何合理規(guī)劃合乘路線以及相應(yīng)的車輛調(diào)度問題，不討論合乘計費規(guī)則。

近年來國內(nèi)外學(xué)者在出租車合乘領(lǐng)域研究成果豐碩。Tao等[1]基于貪心算法和時空網(wǎng)絡(luò)的兩種啟發(fā)式算法建立“一對多”和“多對一”的出租車動態(tài)匹配問題，但最后得到的合乘率較低。Yan等[2]首先提出了一種基于拉格朗日松弛法和子梯度法的啟發(fā)式算法求解車隊路徑/調(diào)度模型，然后構(gòu)建兩個單一的出租車—乘客匹配模型，以減少乘客轉(zhuǎn)移次數(shù)并完成所有乘客和出租車匹配，經(jīng)過測試表明這種方式是可行的，但優(yōu)化程度不是很顯著。程杰等[3]在乘客組、出租車組分類型情況下，引入?yún)f(xié)調(diào)機制，建立了以出行者與駕駛員的利益為優(yōu)化目標(biāo)的多對多模式的動態(tài)出租車合乘模型，并設(shè)計了相應(yīng)的遺傳算法進行求解，最后得到的解為滿意解，但沒有考慮到順路關(guān)系，在迭代次數(shù)不夠大時，所得解具有不穩(wěn)定性。Qi等[4]將一天分為幾個時段，將動態(tài)的出租車調(diào)度問題轉(zhuǎn)換為靜態(tài)調(diào)度問題?；诙鄬Χ嗳∝浐退拓泦栴}（Many-to-Many Pick?up and Delivery Problems，MPDP）建立出租車調(diào)度模型，其中考慮出租車位置和乘客需求等信息，設(shè)計了一種智能啟發(fā)式算法，經(jīng)測試效果良好，尤其適用于大規(guī)模的道路網(wǎng)絡(luò)。Zhang等[5]分析了Jack?son排隊網(wǎng)絡(luò)模型在移動需求匹配系統(tǒng)中的應(yīng)用，在開環(huán)策略下求最優(yōu)問題，進一步發(fā)展了閉環(huán)實時的匹配問題，有效避免了交通擁堵問題。Stiglic等[6]研究了單司機單乘客匹配時，因司機繞行，顧客離開和到達時間對匹配成功率的影響。Nourine?jad等[7]采用貪心算法在滿足限制條件和最節(jié)省總費用函數(shù)的條件下篩選出匹配集合，再從匹配集合中循環(huán)挑選出滿足最多乘客需求的匹配方式。Alonso-Mora等[8]先考慮了所有需求和車輛位置已知時靜態(tài)求解，再考慮有實時性要求時的調(diào)配以及最后空置車輛和久等人員的再匹配，建立出租車合乘業(yè)務(wù)系統(tǒng)模型，并采用L-K、禁忌搜索、模擬退火等啟發(fā)式算法求解，是現(xiàn)有的較好的解決方案。馮田[9]根據(jù)動態(tài)拼車任務(wù)調(diào)度模型計算出任務(wù)的suf?ferage值，并基于任務(wù)調(diào)度中的sufferage算法的原理給出了一種動態(tài)拼車調(diào)度算法。Ou等[10]為減少乘客的等待時間和出租車的空載率，通過K均值聚類算法和矩陣迭代法建立模型使出租車行駛路徑最短，取得了一定成效。Xiao等[11]從合乘用車的角度構(gòu)建了城市交通網(wǎng)節(jié)點，并從乘客等待時間和到達目的地的距離兩方面建立了多目標(biāo)出租車拼車方案選擇模型。并且，他們用兩階段算法計算該模型并引入信息熵來分配權(quán)重向量，獲得滿意的路線，取得了較好的效果。

文獻[7]和文獻[8]是最經(jīng)典的兩篇文獻，本文與其相比有如下新的嘗試：文獻[7]中采用貪心算法求解，即先在滿足限制條件和最節(jié)省總費用函數(shù)的條件下篩選出匹配集合，再從匹配集合中循環(huán)挑選出滿足最多乘客需求的匹配方式。本文的分層序列法與之類似，不同的是將問題轉(zhuǎn)化成了兩個線性規(guī)劃問題，還將車輛最大乘客量通過相鄰節(jié)點度數(shù)之和轉(zhuǎn)化到限制條件中，無需反復(fù)循環(huán)運算，與文獻[7]中的貪心算法相比全局性更強，從而更接近全局最優(yōu)解。文獻[8]先將車和需求匹配建立有向圖，而本文中是以乘客為節(jié)點建立有向圖。對于限制條件，文獻[8]雖將車輛最大乘客量寫入限制條件，但在算法中沒有給出數(shù)學(xué)表達式，而本文將限制條件即相鄰節(jié)點度數(shù)和不超過3量化入算法。

本文的求解思路為：以所需車輛盡量少、乘客等車時間盡量短、乘客乘車繞行里程盡量少為目標(biāo)，將問題分解為合乘乘客分組、行駛路線規(guī)劃、指派車輛3個步驟，分別建立整數(shù)線性規(guī)劃模型，使用分層序列法求解該規(guī)劃問題，具體算法流程如圖1所示。本文的創(chuàng)新點為使用圖論節(jié)點出入度數(shù)概念將車輛最大乘客量量化并轉(zhuǎn)化到限制條件中，從而大大降低了模型復(fù)雜程度，提高了計算效率，而且求解結(jié)果比直接用貪心算法求解的結(jié)果具有更強的全局性。

圖1 算法流程圖

1 合乘條件

對乘客而言，合乘與獨乘相比，不便之處主要有兩點：一是等車時間可能會增加，二是上車后可能會繞路。因此，等車時間和繞行距離應(yīng)盡量小，至少應(yīng)控制在一定范圍之內(nèi)，才不會影響乘客的乘車體驗。而所需車輛數(shù)盡量少的要求，可以在滿足等待時間和繞行距離要求的前提下，通過盡量多地安排合乘來達到。

1.1 數(shù)據(jù)來源與條件假設(shè)

使用2017年湖南省研究生數(shù)學(xué)建模競賽A題[12]的數(shù)據(jù)集測試算法的效率。該數(shù)據(jù)集使用紐約市黃色出租車2016年5月10日上午8：10—8：13共3min內(nèi)的實際打車數(shù)據(jù)（上車數(shù)據(jù)）[13]作為打車需求數(shù)據(jù)，去除異常數(shù)據(jù)及原始行程小于0.483km（0.3英里）的數(shù)據(jù)，并將路網(wǎng)簡化為邊長為500m的正方形網(wǎng)格，雙向可行，人、車的位置點均修正到道路網(wǎng)格之上。

（1）為簡化問題，作如下假設(shè)：調(diào)度中心可以實時獲得乘客打車需求，包括上車地點和目的地。

（2）出租車最多可同時搭載3位乘客，即最多3人合乘。

（3）每個上車點只有1位乘客，即假設(shè)所有的乘客單獨出行。

（4）假設(shè)車輛均以平均速度行駛，則等待時間與等待里程成正比。例如，假設(shè)平均速度為25km/h，則等待時間3min對應(yīng)等待里程1.25km。若平均速度為30km/h，則等待時間3min對應(yīng)等待里程1.5km。

1.2 “順路”關(guān)系

為了提高出租車的合乘效率，合乘乘客應(yīng)盡量滿足“順路”關(guān)系。這可以從以下兩個方面考慮：一是等待里程盡量短，要求合乘乘客的上車地點盡可能接近。二是繞行距離盡量短，要求合乘乘客的行程“順路”。由于目的地有可能完全相反，因此不能只根據(jù)“上車地點接近”這一條件確定合乘關(guān)系，應(yīng)按照順路關(guān)系尋找可能的合乘組合。

考慮兩位乘客P1,P2的“順路”關(guān)系，不妨設(shè)P1先上車，則滿足以下兩個條件之一時，P2與P1“順路”。

（1）P2起點位于P1起點至P1終點的最短路徑上，且P1終點位于P2起點至P2終點的最短路徑上。即按P1上車、P2上車、P1下車、P2下車的順序上下車，沒有繞行。

（2）P2起點位于P1起點至P1終點的最短路徑上，且P2終點位于P2起點至P1終點的最短路徑上。即按P1上車、P2上車、P2下車、P1下車的順序上下車，沒有繞行。

若將路網(wǎng)簡化為矩形網(wǎng)格，且均可雙向行駛，則“P2的終點位于P1起點到終點的最短路徑上”這一條件可以近似簡化為“P2的終點位于以P1起點和P1終點為對角線兩點的矩形中”。那么，簡化后的順路條件如圖2所示。

三點說明：

（1）由于乘客不一定位于十字路口，所以兩乘客位置點之間的實際最短距離不一定等于兩點間的曼哈頓距離（街區(qū)距離）。因此上述簡化是近似的，但在多數(shù)情況下成立。

（2）上述順路關(guān)系不具有傳遞性，即P2與P1順路且P3與P2順路，不一定有P3與P1順路，也不能保證三者合乘時行駛路線不繞行，如圖3所示。本文不再討論三者合乘不繞行的條件。

（3）以上是“嚴格”不繞行條件，如果允許繞行，可增加上述矩形的邊界，擴大矩形。

圖3 合乘繞行情況示意圖

1.3 “順路”關(guān)系圖說明

以乘客為節(jié)點，兩乘客有順路關(guān)系對應(yīng)一條有向邊，由先上車乘客指向后上車乘客，權(quán)值為兩乘客起點間的距離，可建立“順路”關(guān)系有向圖，用鄰接矩陣表示。

考慮到等待里程盡量短的因素，為簡化問題規(guī)模，可以在建立關(guān)系圖時，設(shè)定最長等待里程Dmax，刪除權(quán)值大于該閾值的邊。

“順路”關(guān)系有向圖中，有向邊表示其端點對應(yīng)的兩位乘客有可能合乘，孤立點對應(yīng)的乘客不能與其他乘客合乘。

2 合乘乘客分組

由于最多3人合乘，因此問題轉(zhuǎn)化為在“順路”關(guān)系有向圖中尋找單節(jié)點、兩節(jié)點、三節(jié)點連通子集，使得子集數(shù)量盡量少，同一子集中各乘客起點間的距離盡量小。

由于合乘只可能在邊對應(yīng)的乘客之間進行，因此，可以對有向圖中各個連通分支分別求解。

分組后子集數(shù)量盡量少等價于各子集邊數(shù)總和盡量大，而后者在規(guī)劃模型中更容易表示。

2.1 求解合乘分組的多目標(biāo)規(guī)劃模型

設(shè)順路關(guān)系圖中某個連通分支含有n個節(jié)點，對于任一條有向邊，權(quán)值cij表示對應(yīng)2位乘客起點間的距離，當(dāng)i與j不相鄰時，cij=∞，則C=(cij)n×n構(gòu)成權(quán)值矩陣。取決策變量xij,1≤i,j≤n,i≠j，表示：

目標(biāo)函數(shù)f1表示邊數(shù)盡可能大，即達成合乘的乘客數(shù)要盡可能多，這樣才能最大限度地發(fā)揮合乘優(yōu)勢，即：

目標(biāo)函數(shù)f2表示邊權(quán)值總和盡可能小，即所有乘客總的等待時間要盡可能少，即：

約束條件C1表示節(jié)點出度不超過1，即對任意乘客i，至多有1位乘客與之順路，即：

約束條件C2表示節(jié)點入度不超過1，即對任意乘客j，至多與1位乘客順路，即：

約束條件C3表示相鄰節(jié)點度數(shù)和不超過3，以保證連通子集至多包含3個節(jié)點，即每個合乘分組的人數(shù)不會超過3個人：

其中j與i順路，即在關(guān)系圖中存在有向邊ij→。根據(jù)C1與C2,i,j兩點的出、入度總和不超過4，而等于4時表示i,j均為中間節(jié)點，則至少是4點相連，與最多3點相連的要求矛盾，因此必須添加約束C3，才能保證合乘分組中不超過3人。

2.2 分層序列法求解多目標(biāo)規(guī)劃

在求解上文的多目標(biāo)規(guī)劃問題時，由于兩個目標(biāo)不可能同時取得，所以本文使用分層序列法[14]求解該多目標(biāo)規(guī)劃問題。先以f1即邊數(shù)總和最大為目標(biāo)，求出邊數(shù)總和的最大值Emax，再將邊數(shù)總和不小于該最大值作為新的約束條件C4，則有：

以邊權(quán)值和最小為目標(biāo)，求解出最佳分組方案。

綜上，先求解0-1線性規(guī)劃問題，如下式所示：

得到f1最大值Emax，再增加約束條件C4，求解新的0-1線性規(guī)劃問題：

得到合乘最佳分組方案。

2.3 減小規(guī)模，分步求解

由于問題規(guī)模較大，直接求解計算量大、效率低。例如本文所用數(shù)據(jù)集，若假設(shè)車輛平均速度為30km/h，合乘等待時間不超過1.5min，即限制合乘等待里程不超過Dmax=0.75km時，最大的連通分支仍包含200多個節(jié)點。因此為了減小問題規(guī)模，可采用如下分步求解策略。

（1）令待分組乘客集合T為全體乘客集合。

（2）取最大等待里程為D1，如D1=0.2km，建立順路關(guān)系圖，求解上述多目標(biāo)規(guī)劃模型。在得到的最佳分組方案中，只保留3人合乘組，記為G1，其他節(jié)點放回待分組乘客集合T。

（3）取最大等待里程為D2，要求D2＞D1，如D2=0.6km，按照同樣方法求得新的最佳分組方案，仍然只保留3人合乘組，記為G2，其他節(jié)點放回集合T。

（4）取最大等待里程為D3，要求D3＞D2，如D3=1.5km，求最佳分組方案，記為G3。

（5）G=G1?G2?G3構(gòu)成最終的合乘分組方案。

3 行駛路線規(guī)劃

若以總路程最短為目標(biāo)，則可以添加一個虛節(jié)點，將問題轉(zhuǎn)化為旅行商問題（Traveling Salesman Problem，TSP）[15]，使用整數(shù)線性規(guī)劃模型求解。但是，顯然乘客起點應(yīng)在終點之前，即同一乘客只能先上車后再下車，因此該問題是有順序要求的TSP問題，需要添加一組關(guān)于節(jié)點順序的約束條件。

求經(jīng)過pi(i=1,2,…,2n)每一點的最短路徑（非回路），且pi和pi+n為對應(yīng)節(jié)點，要求在所得路徑中pi在pi+n之前。pi與pj間的距離記為dij。增加虛節(jié)點p0，令d0i=di0=0。 取決策變量

3.1 2人合乘組

對于2人合乘組，由順路關(guān)系，上車順序可以認為已經(jīng)確定，主要是確定兩人下車的先后順序。因為下車順序只有兩種可能，所以簡單比較后便容易確定。

3.2 3人合乘組

對于3人合乘組，前文已經(jīng)討論過，不能保證3人的合乘路線沒有繞行，3人上車的順序也不能保證與有向邊端點的順序一致。

行駛路線規(guī)劃等價于確定3人上下車的順序，即確定3人的起點、終點共6個點的順序。共有則：

則該問題的整數(shù)線性規(guī)劃模型如下：

其中C1表示每一節(jié)點的出度必須為1；C2表示每一節(jié)點的入度必須為1；ui表示節(jié)點在路徑中的順序；C3表示路徑只能構(gòu)成一個圈；C4為指定對應(yīng)節(jié)點在路徑中出現(xiàn)的順序。顯然，兩人合乘組也可以用以上模型求解上下車順序。

4 指派車輛

每一合乘組內(nèi)的上下車順序確定后，根據(jù)第一位上車乘客的起點位置，就近安排車輛，使得總的等待里程最短。0-1線性規(guī)劃模型如下。

假設(shè)有M個合乘組，N輛車，應(yīng)有M≤N；車j與組i第一位乘客起點的距離記為dij；取決策變量xij∈{0,1}，則：

求得車輛安排方案后，結(jié)合每一合乘組內(nèi)上下車順序，得到最終的合乘調(diào)度方案。

5 實例分析

本文使用紐約市黃色出租車2016年5月10日上午8：10—8：13共3min內(nèi)的實際打車數(shù)據(jù)作為打車需求數(shù)據(jù)，即把該時間段內(nèi)乘客的實際到達地點假設(shè)為乘車的目的地。將經(jīng)緯度坐標(biāo)簡化為直角坐標(biāo)，以km為單位。并假設(shè)車輛的平均行駛速度為30km/h。經(jīng)過初步數(shù)據(jù)處理，去除了異常數(shù)據(jù)及原始行程小于0.483km（0.3英里）的數(shù)據(jù)，將該雙向可行的路網(wǎng)簡化為邊長為500m的正方形網(wǎng)格，并把人、車的位置點均修正到道路網(wǎng)格之上。最后得到了一個測試數(shù)據(jù)集，包含1 001位乘客的上車坐標(biāo)、目的地坐標(biāo)和當(dāng)前667輛空車的坐標(biāo)，如圖4所示。

圖4 紐約市出租車數(shù)據(jù)集

通過本文算法的計算，調(diào)度中心需要安排424輛出租車對乘客進行服務(wù)。其中合乘車輛總數(shù)為316輛，占所有調(diào)度車輛的74.53%；兩人合乘56輛，占13.21%；3人合乘260輛，占61.32%；單人乘車共108輛，占25.47%。整體平均車載人數(shù)為2.36人。這說明該算法能有效地安排合乘車輛，使更多的乘客通過合乘的方式出行，盡可能提高出租車的運載效率。其次，本算法中乘客的平均等待時間為0.513min，且87%的乘客等待時間在1min以內(nèi)，如圖5所示。這說明本算法能夠節(jié)約乘客的等車時間，提高乘客打車效率。除此之外，由于本算法優(yōu)化了行車路線，所有乘客的繞行中位數(shù)為0（超過50%的乘客不繞行），這大大節(jié)約了車輛的行駛時間，使得合乘更加高效。綜上所述，本算法能有效安排出租車合乘方案，在較小的等待時間和繞行距離下盡可能匹配更多的“合乘”車輛，大大增加了出租車的交通運輸效率，并為乘客減少了出行費用，為出租車司機增加了收入。

圖5 乘客等待時間分布圖

為了比較本算法與其他算法的優(yōu)劣，本文選取了同年（2017年）參加該數(shù)學(xué)建模競賽的10組優(yōu)秀論文的算法作為參照，選取以下指標(biāo)進行比較：①車輛數(shù)目：指調(diào)度中心需要安排的出租車數(shù)目。②等待中位數(shù)：指乘客所需等待里程的中位數(shù)，以km為單位。即出租車從出發(fā)至接到該乘客所行駛的里程，該指標(biāo)越低說明乘客所需要等待的時間越短。③久等乘客數(shù)：指等待時間超過3min的乘客數(shù)量。④繞行距離：指乘客乘車過程中繞行的距離，以km為單位。本文選取繞行中位數(shù)和75百分位數(shù)兩個指標(biāo)對其描述。其中，繞行中位數(shù)表示乘客繞行距離的中等水平，反映出算法的有效性；繞行75百分位數(shù)表示乘客繞行距離75%處的數(shù)值，間接反映出算法的穩(wěn)健性。

計算結(jié)果如表1所示，其中算法1至算法10的結(jié)果是10篇優(yōu)秀論文的結(jié)果。

表1 結(jié)果對比

由表1知，本文方法所得結(jié)果在繞行中位數(shù)和繞行距離75%兩個指標(biāo)均為0，和其余結(jié)果相比最優(yōu)，說明本文方法繞行距離相對較小，路徑規(guī)劃較優(yōu)。其余3個指標(biāo)雖不是最優(yōu)，但是仍處于中等水平，處于乘客能夠接受的范圍。通過簡單估算，本文合乘后的汽車行駛總里程為1 799.1km，未合乘的總里程下界為3 739.4km，這說明與非合乘的情況進行對比時，本文提出的合乘方案具有絕對的里程優(yōu)勢，對于提高交通運輸力有顯著的作用。此外，本文提出的模型只用簡單的凸優(yōu)化理論便可求解，體現(xiàn)出了本模型簡單高效的特點。

6 結(jié)語

本文在考慮乘客和司機雙方需求的前提下，針對出租車合乘問題提出了一種分步的整數(shù)線性規(guī)劃方法，相比傳統(tǒng)算法，使用圖論節(jié)點出入度數(shù)概念將車輛最大乘客量量化轉(zhuǎn)化到限制條件中，求解結(jié)果比起已有的直接貪心算法具有更強的全局性。從測試結(jié)果看，本算法所得到的合乘路線繞行距離較小，這對于乘客和司機來說都是較好的方案。但本算法得到的合乘方案有可能出現(xiàn)少數(shù)顧客久等的現(xiàn)象，這方面還有待進一步完善和改進。

此外，本文方法除了能解決出租車合乘問題外，還可以解決公交車線路規(guī)劃和郵遞員收件、派件等問題。例如，規(guī)劃公交車線路可以視作多人合乘問題，只需要在本方法中將合乘人數(shù)上限設(shè)置為公交車載客量，便可以根據(jù)市民出行需求設(shè)計出合乘人數(shù)盡可能多、行駛路程盡可能短的高效的公交線路。郵遞員收件、派件同樣可以視作多人合乘問題，只需要將快件視作乘客，將收件過程視作接乘客上車，將派件過程視作送乘客下車，根據(jù)快件所在的地點便可以構(gòu)成一個多人合乘模型。例如，派件的過程可視作出發(fā)點為快遞公司，目的地為派件地址的多人合乘問題；收件的過程可視作出發(fā)點為各個攬件點，目的地為快遞公司的多人合乘問題。