基于模糊減法聚類的出租車合乘業(yè)務(wù)方案設(shè)計

朱瑞林 劉志鵬

摘要：運用模糊減法聚類算法對出租車合乘業(yè)務(wù)方案進行設(shè)計。乘客初末位置以核心區(qū)域為準則進行內(nèi)集和外集的劃分，對內(nèi)集中的乘客選擇離核心區(qū)域最近的空馳出租車選擇3人合乘匹配的方案，外集中的乘客對其初末位置進行合乘適用度匹配之后選擇2人合乘或1人合乘的方案，對不同的合乘方案分別設(shè)計相應(yīng)的計費標準。結(jié)果表明，該方案不但能減少乘客的出行費用，也能增加出租車司機的收入。

關(guān)鍵詞：合乘業(yè)務(wù);模糊聚類;內(nèi)集;外集;計費標準

中圖分類號：TP391 文獻標識碼：A 文章編號：1007-9416（2018）11-0122-02

0 引言

出租車合乘業(yè)務(wù)是指乘客出行時按路線相同或相近原則，多人共同乘坐同一輛車。出租車業(yè)務(wù)系統(tǒng)則根據(jù)合乘乘客數(shù)量、乘車時長及實際乘車路線等情況，分別計算出每位乘客所需要費用。設(shè)計合乘業(yè)務(wù)系統(tǒng)目的在于通過控制運營車輛總數(shù)提高合乘的效率以緩解交通壓力和乘客打車難的困境。肖強等[1]通過對出租車的行駛路線進行模糊聚類分析，對合乘乘客與出租車進行合乘模糊識別的方式來提高合乘幾率。胡繼華[2]等將出租車司機的路徑選擇經(jīng)驗融入到路徑規(guī)劃算法中，可以提高乘客的出行效率。本文根據(jù)乘客分布和車輛位置信息對合乘方式進行了深入研究，綜合考慮了乘客分布密度的區(qū)域劃分、乘客與出租車的匹配過程、車費計算等多方面因素對合乘業(yè)務(wù)的影響。

1 問題描述

針對乘客與出租車司機之間的合乘匹配問題，需要綜合考慮乘客出發(fā)位置、乘客的目的地位置以及空乘出租車的位置之間的距離信息，根據(jù)三者位置信息形成的聚類中心區(qū)域，求解出租車與乘客目的地之間的最優(yōu)路徑。對分布在不同類中心區(qū)域的乘客應(yīng)當設(shè)計合理的行車路線，應(yīng)考慮到乘客從出發(fā)點到目的地所需的時間以及所需的出租車數(shù)量最少，還要同時兼顧乘客出行費用與出租車司機的收益，也就是出租車出乘的時候盡量選擇三人滿座的情況。

2 合乘方案的數(shù)學(xué)模型建立

本文針對出租車與乘客合乘匹配問題，以多個起點至多個目的地的運營方式為出發(fā)點，提出聚類核心區(qū)域模塊劃分的解決思路。根據(jù)乘客的出發(fā)點、目的地以及空馳出租車三者位置信息的分布情況，對其進行基于位置信息密度的模糊聚類分析。

2.1 基于位置信息密度的模糊減法聚類

基于位置信息密度的模糊減法聚類方法對出租車與乘客的匹配進行分析。對乘客的出發(fā)位置、目的地位置以及空馳出租車位置信息進行聚類，得出數(shù)據(jù)集中每一個數(shù)據(jù)點的密度。在其中選擇密度值最大的數(shù)據(jù)點作為第一個中心點位置，通過迭代計算法求出剩下數(shù)據(jù)點的位置密度，根據(jù)需要選擇最佳的密度閾值，由大于閾值的所對應(yīng)位置信息，形成若干聚類中心，不斷地優(yōu)化選取模糊隸屬度，得到模糊影響半徑，通過選取影響半徑可得到若干個區(qū)域。若區(qū)域之間出現(xiàn)了重疊，取區(qū)域的合集并稱之為核心區(qū)域。分析乘客的出發(fā)位置和目的地信息，若兩者都處于核心區(qū)域內(nèi)則將該乘客劃入內(nèi)集中，其他乘客則劃入外集中。

2.2 乘客與出租車的分配過程分析

根據(jù)乘客出發(fā)位置和目的地位置信息是否處于核心區(qū)域進行合乘人員的分配，在選取模糊影響半徑的時候，盡量使內(nèi)集中的乘客密度最大，增加合乘的幾率，直接采取3人合乘的方案，而外集中的乘客采用2人合乘或者1人獨乘的方案。

2.2.1 內(nèi)集乘客的合乘分配方案

使用模糊聚類法對內(nèi)外集確定后，按照乘客的出發(fā)點與終點都在內(nèi)集區(qū)域的準則，對處于內(nèi)集中的乘客按照3人合乘的模式，確保內(nèi)集中的乘客人數(shù)為3的整數(shù)倍。若人數(shù)不是3的整數(shù)倍時，按照距離核心區(qū)域最近的準則，從外集中選擇1-2人歸入到內(nèi)集中構(gòu)成3的整數(shù)倍。在空馳出租車集中依次選取離核心區(qū)域最近的出租車，確定需要合乘的出租車之后，從內(nèi)集中選擇距離該出租車最近的3個乘客進行合乘。

2.2.2 外集乘客的合乘分配方案

在經(jīng)過內(nèi)集乘客人員的合乘匹配之后，剩下乘客的初止位置不都是分布于內(nèi)集中，且出發(fā)點位置和目的地位置的分布都很稀疏，乘客之間的合乘幾率比較低。采用出發(fā)點位置和目的地位置相近的原則進行最多2人的合乘匹配方案。當合乘適應(yīng)度大于某一閾值時選擇合乘。而合乘適應(yīng)度由兩乘客起點與目的地鄰近度決定，其中 ，，其中表示乘客所處的位置坐標。規(guī)定自己與自己的合乘適應(yīng)度為0;以距離最近原則選擇空馳出租車進行乘客的合乘匹配。

2.3 出租車合乘方案的計費標準

出租車合乘方案的的計費標準設(shè)計時應(yīng)包含起步價和里程單價兩個計費項目[3]，起步價p0元/2公里，超過2公里，按p1元/公里計價[4]。設(shè)計3人合乘計費方案如下：通過選取合適的聚類半徑，可知核心區(qū)域乘客之間的起止位置都在內(nèi)集中，直接選用“一口價”的定價計費模式。3人合乘的費用為：，D為核心區(qū)域半徑。對外集中的乘客采用“相同起點”的計費模式，假定第1人的行程L1大于第2人的行程L2，則2人合乘計費方案分別為：， ，當外集中的乘客只能獨乘時，據(jù)行程L采用獨立乘車計費方案為。

3 數(shù)據(jù)處理與實驗結(jié)果分析

為驗證該出租車合乘方案的可行性，收集了某一城市某一時刻部分乘客的打車需求及空馳出租車位置信息如表1所示，采用模糊減法聚類算法進行實驗。

通過Matlab對數(shù)據(jù)進行分析實驗，實驗結(jié)果表明：3人合乘人數(shù)為270人，90臺車;2人合乘人數(shù)為666人，333臺車，1人獨立乘車人數(shù)為65人，65臺車;共計所需出租車為488臺，平均等待時間為503米。使用上述計費模型得出乘客支付費用在3人合乘最少，而此時出租車司機收益最高（見表2）。

4 結(jié)語

本文在多個起點至多個目的地的出租車合乘業(yè)務(wù)模型進行了研究，該方案充分考慮了乘客的等待時間、乘車費用以及所需空馳出租車數(shù)量、司機收益[5]等情況下的合乘。但仍存在一些不足之處，在人與車進行匹配時缺少了靈活性，該方案中的計費模型還有待完善和改進。

參考文獻

[1]肖強，何瑞春，張薇，等.基于模糊聚類和識別的出租車合乘算法研究[J].交通運輸系統(tǒng)工程與信息，2014（5）：119-125.

[2]胡繼華，黃澤，鄧俊，等.融合出租車駕駛經(jīng)驗的層次路徑規(guī)劃方法[J].交通運輸系統(tǒng)工程與信息，2013， 13（1）：185-192.

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

[4]洪麟琳.基于合乘模式的出租車定價研究[D].哈爾濱工業(yè)大學(xué)，2012.

[5]邵增珍，王洪國，劉弘等.車輛合乘匹配問題中服務(wù)需求分派算法研究[J].清華大學(xué)學(xué)報（自然科學(xué)版），2013，（2）：252-258.

Design of Taxi Mixing Business Plan Based on Fuzzy Subtractive Clustering

ZHU Rui-lin1， LIU Zhi-peng2

（1.Chulan Experimental School， Changde City， Hunan Province， Changde Hunan? ?415000;

2.Changde Meteorological Bureau of Hunan Province， Changde Hunan? 415000）

Abstract：The fuzzy subtraction clustering algorithm is used to design the taxi busning business plan. The passengers' initial position is divided into inner and outer sets based on the core area. The inner passengers choose the closest air-conditioned taxi from the core area to select a three-person matching plan. After the location is matched and the fitness is matched， the scheme of selecting two people or one person is selected， and the corresponding charging standards are respectively designed for different multiplication schemes. The results show that the program can not only reduce passenger travel expenses， but also increase the income of taxi drivers.

Key words：multiplication service; fuzzy clustering; inner set; outer set; billing standard