聚類算法在出租車合乘方案中的應用

譚艷祥 李立軍 彭家睿 徐迅

摘? 要：隨著乘坐出租車出行的人數不斷增加，現階段的“打車難”卻成為人們不得不面對的問題。出租車合乘能有效緩解上下班高峰期打車難的問題，并減少能源浪費和大氣污染。文章建立了考慮繞路與三名乘客合乘的靜態合乘模型。使用基于勢能值和曼哈頓距離的聚類算法對出租車進行聚類，建立了基于非直達系數的合乘費用分攤模型，降低了乘客出行總費用。最后進行仿真實驗，對模型的部分細節進行補充說明，實驗結果表明合乘使得乘客與司機雙方受益。

關鍵詞：出租車合乘;靜態;聚類;費用分攤

中圖分類號：U491? ? ? ? ?文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2020）29-0041-04

Abstract： With the increasing number of people traveling by taxi， "difficulty in taking a taxi" at the present has become a problem that people have to face. Taxi pooling can effectively alleviate the problem of taxi hailing during rush hour and reduce energy waste and air pollution. In this paper， a static multiplicative model with detour and three passengers is established. The potential energy value and Manhattan distance clustering algorithm are used to cluster the taxis， and the co-ride cost sharing model based on non-direct coefficient is established to reduce the total passenger travel cost. Finally， a simulation experiment is carried out to explain some details of the model. The experimental results show that co-riding benefits both passengers and drivers.

Keywords： taxi carpool; static; clustering; cost sharing

引言

隨著中國經濟的發展與城鎮化進程的推進，“都市圈”“城市群”正在不斷發展。城市的快速擴張，帶動了經濟的增長，提高了人民的生活質量。但是包括人口膨脹、交通擁堵、環境惡化、資源緊張在內的城市病卻制約著城市的發展。目前，如何緩解城市病迫在眉睫，其中上下班高峰時期的交通擁堵問題明顯影響了城市生活的體驗[1]。作為城市公共交通方式的重要組成部分，城市出租車的重要性逐漸提高。根據國家統計局2018年的數據，中國出租車保有量為1097237輛，其中北京市出租車保有量為70035輛，上海為41881輛。但是出租車的人均占用道路面積卻是其它公共交通運輸工具的30倍[2]。出租車行業還存在著運營成本偏高、交通擁堵加劇、資源浪費嚴重、環境污染加劇、合乘收費標準不統一等問題[3]。針對出租車存在的一系列問題，國內外相關人員提出利用拼車或合乘的方式緩解出租車所帶來的不利影響。

出租車合乘可以分為靜態合乘與動態合乘。覃運梅等人研究了靜態組合模式下的出租車合乘問題，在考慮司機和乘客雙方利益的基礎上建立相應的數學模型，建立乘客合乘查詢系統， 采用Floyd算法求出最佳行駛路線[4]。程杰等人研究了動態出租車合乘問題，考慮了在乘客組、出租車分類型情況下，引入協調機制，建立了多對多模式的動態出租車合乘模型[5]。丁冉以乘客的出行時間成本和費用成本最小為目標，建立了出租車動態合乘匹配模型，并設計了插入式算法，致力于尋求乘客的出行請求和可乘車輛的最佳匹配[6]。

周和平等人針對多起點到多終點的出租車合乘，構建合乘模型，綜合考慮出行者與駕駛員的利益，確定合理的路徑選擇與費率[7]。劉華杰根據合作博弈相關理論結合出租車合乘的實際情況，引入合作博弈理論以解決出租車合乘費用的分攤問題[8]。考慮行程時間、費用、舒適度對乘客心理決策的影響，通過計算機模擬，分析不同付費比例和交通擁堵率在乘客心理因素影響下對乘客合乘決策的影響[9]。唐方慧該模型以合乘系統中乘客合乘費用最小化，乘客合乘時間最小化以及出租車燃油費用最小化作為目標函數，建立出租車合乘路徑選擇及費率優化模型，并設計出求解該模型的非支配排序遺傳算法[10]。

1 出租車聚類算法

考慮到數據獲取的難易程度，本文做出如下假設：假設每一份訂單中乘客的人數為一人;假設合乘乘客相互之間沒有要求;假設所有乘客起點、終點均在路邊，出租車可直接到達;假設乘客不換乘，從起點到終點只坐一輛出租車;假設載客出租車都愿意參與合乘，且初始時刻車內剩余的座位數為三; 假設車輛無故障行駛，忽略乘客上下車的時間，忽略接送乘客以及到達目的地時加減速的影響，不考慮其它影響因素對到達時間的影響。

本文研究的出租車合乘屬于靜態合乘，建立的是多對多合乘模型。進行合乘匹配時，借鑒了貪心算法的思想，這滿足了先下單的乘客先得到服務的要求，避免出現為追求最優解而導致部分乘客長時間等待的結果。

出租車合乘業務需要將路線相近的多名乘客安排在同一組，由一輛出租車按照一定次序接他們上車，并送他們到達相應目的地，匹配模型的第一步是對出租車聚類。本文描述了一種基于勢能值和曼哈頓距離的聚類算法，該方法對“空間分布有規律而時間分布無規律”的出租車的聚類效果更好。

1.1 勢能值

設數據集為D，其中D={P1，P2，…Pn}，令I={1，2，...，n}，xi表示數據集D中的任意一點，數據點的勢能值可定義為：

其中M表示數據對象的質量，||Pj-Pi||表示數據點Pj和Pi之間的距離，dc表示數據點之間的影響程度因子，R表示距離指數，在本文取M=1，R=2，如圖1，可以通過改變參數dc來控制數據聚類的范圍大小。如圖1所示，當dc=1時，與Pi距離不小于3的點給Pi的勢能值帶來的變化接近于零。當dc=2時，與Pi距離不小于5的數據點對Pi的勢能值的影響就非常小了。按照常理，我們一般是對方圓五公里內的出租車聚為一類，因此本文取dc=2。

1.2 數據點之間的曼哈頓距離

定義數據集為D中的數據點Pi（xi，yi）和Pj（xj，yj）之間的曼哈頓距離為dij，其表達式為：

為了得到各個出租車初始位置的勢能函數，我們計算所有出租車兩兩之間的曼哈頓距離。

1.3 聚類中心數量判別值

定義出租車的初始位置為Ti（xi，yi），每輛出租車的勢能值為E（Ti），點間距為U（Ti）。設數據集Taxis中各數據點的數據勢能為E={E（T1），E（T2），…E（Tn）}，根據數據點勢能值的大小進行排序，定義Is={s1，s2，…sn}為數據集Taxis按勢能大小非遞增排序的下標，則有Es1？叟Es2？叟Esn。定義U（Ti）為不同數據點的之間的“距離”，如式（3）：

3 算例研究

實驗數據來自某城市某日某時刻三分鐘之內的真實打車需求數據。數據集中有1001名乘客，667輛空載出租車。乘客起點、要求到達的終點以及當前出租車所在位置分布情況如圖2所示。

圖2中圓圈表示出租車的初始位置，上三角形表示乘客的上車點，下三角形表示乘客的下車點。如圖2所示，出租車初始位置，乘客上車點與下車點三者高度重合。放大之后的圖3可以看到所有出租車初始位置，乘客上車點，乘客下車點均分布在正方形網格上。從出租車初始位置分布圖可以看出，出租車位置總體呈帶狀、密集分布，放大之后可以看到所有出租車位置均分布在正方形網格上。大部分出租車分布在橫坐標從15～30縱坐標從20～35的矩形的由西南至東北的對角線帶狀區域。

圖4中，T479表示編號為479的出租車，P1表示編號為1的乘客。如圖4所示三名乘客合乘出租車的合乘路線十分復雜，基于公平性的合乘費用分攤模型中對于三名乘客合乘距離的界定是不夠清楚的，合乘距離是指三名乘客同時在車上的移動距離還是指某兩名乘客同時在車上的移動距離。基于公平性的合乘費用分攤模型沒有給出清晰的定義，因此給分攤費用的計算帶來了困難，不方便實際操作。設置該城市常規出租車計費方式：起步里程為2公里，起步價為8元，超出起步里程后的單位里程價格為每公里2.0元。假設出租車的平均速度為每小時30公里。基于非直達系數的合乘費用分攤模型對于乘客一，乘客二所在組每名乘客的費用計算結果如表1所示。

由上述表格可知，司機的收入幾乎增加了一倍，三名乘客中有兩名乘客的乘車費用降低了。雖然有兩名乘客P847的費用不變，但是如果是三名乘客單獨合乘的情況，乘客P847需要多等待兩分鐘，也就是說雖然費用不變，乘客? 仍然從合乘中得到了益處——減少了等待時間。

4 結束語

本文借鑒物理中的場的概念，建立了出租車的勢能值，由于聚類中心的勢能值大于該類中的其余點的勢能值，因此可在散點圖中直觀地分辨出聚類中心。本文將普通聚類算法中的歐式距離改為曼哈頓距離，使得聚類算法更符合出租車聚類的特點。本文先進行乘客之間的匹配，再進行一組乘客與出租車的匹配。乘客間的匹配允許閥值范圍內的繞行，提高了合乘匹配成功率。關于費用分攤問題，本文基于非直達系數建立了一個簡單，方便計算的合乘費用分攤模型。文章最后做了仿真實驗，對算法進行了實現，結合具體實例說明了合乘匹配，路徑規劃，費用分攤的結果。

參考文獻：

[1]張昂啟.城市交通運行效率評價[D].首都經濟貿易大學，2014.

[2]楊樹森.公交車·出租車[J].北京成人教育，1996（5）：48-50.

[3]肖強.城市出租車合乘匹配理論模型與關鍵技術研究[D].蘭州交通大學，2017.

[4]覃運梅，石琴.出租車合乘模式的探討[J].合肥工業大學學報（自然科學版），2006（01）：77-79+101.

[5]程杰，唐智慧，劉杰，等.基于遺傳算法的動態出租車合乘模型研究[J].武漢理工大學學報（交通科學與工程版），2013，37（01）：187-191.

[6]丁冉.出租車動態合乘匹配問題研究[D].東南大學，2015.

[7]周和平，鐘璧檣，彭霞花，等.出租車合乘路徑選擇與費率優化模型[J].長沙理工大學學報（自然科學版），2011，8（01）：20-24.

[8]劉華杰.出租車合乘費率優化問題研究[D].蘭州交通大學，2015.

[9]張薇，何瑞春，肖強，等.合乘模式下司機收入公平模型及仿真[J].交通運輸系統工程與信息，2015，15（04）：92-98.

[10]唐方慧.出租車合乘路徑選擇及費率優化問題研究[D].蘭州交通大學，2016.