李輝春，李哲民，毛紫陽

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

0 引言

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

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

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

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

圖1 算法流程圖

1 合乘條件

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

1.1 數據來源與條件假設

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

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

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

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

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

1.2 “順路”關系

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

考慮兩位乘客P1,P2的“順路”關系，不妨設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下車的順序上下車，沒有繞行。

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

三點說明：

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

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

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

圖3 合乘繞行情況示意圖

1.3 “順路”關系圖說明

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

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

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

2 合乘乘客分組

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

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

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

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

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

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

目標函數f2表示邊權值總和盡可能小，即所有乘客總的等待時間要盡可能少，即：

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

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

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

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

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

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

以邊權值和最小為目標，求解出最佳分組方案。

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

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

得到合乘最佳分組方案。

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

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

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

（2）取最大等待里程為D1，如D1=0.2km，建立順路關系圖，求解上述多目標規(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構成最終的合乘分組方案。

3 行駛路線規(guī)劃

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

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

3.1 2人合乘組

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

3.2 3人合乘組

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

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

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

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

4 指派車輛

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

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

求得車輛安排方案后，結合每一合乘組內上下車順序，得到最終的合乘調度方案。

5 實例分析

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

圖4 紐約市出租車數據集

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

圖5 乘客等待時間分布圖

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

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

表1 結果對比

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

6 結語

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

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