聚類算法在出租車合乘方案中的應(yīng)用

譚艷祥 李立軍 彭家睿 徐迅

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

關(guān)鍵詞：出租車合乘;靜態(tài);聚類;費用分攤

中圖分類號：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

引言

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

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

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

1 出租車聚類算法

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

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

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

1.1 勢能值

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

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

1.2 數(shù)據(jù)點之間的曼哈頓距離

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

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

1.3 聚類中心數(shù)量判別值

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

3 算例研究

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

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

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

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

4 結(jié)束語

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

參考文獻：

[1]張昂啟.城市交通運行效率評價[D].首都經(jīng)濟貿(mào)易大學(xué)，2014.

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

[3]肖強.城市出租車合乘匹配理論模型與關(guān)鍵技術(shù)研究[D].蘭州交通大學(xué)，2017.

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

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

[6]丁冉.出租車動態(tài)合乘匹配問題研究[D].東南大學(xué)，2015.

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

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

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

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