基于個性化需求的拼車路徑匹配算法研究

郭 會，王麗俠

(1.浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004；2.浙江師范大學行知學院，浙江 金華 321004)

基于個性化需求的拼車路徑匹配算法研究

郭 會1，王麗俠2

(1.浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004；2.浙江師范大學行知學院，浙江 金華 321004)

目前，多數(shù)城市都存在著打車難、交通擁擠、汽車造成的空氣污染嚴重等問題，而拼車是解決上述問題的有效方法。拼車既可以緩解交通擁擠解決打車難的問題，又可以節(jié)能減排，利于環(huán)保。面向出租車拼車的個性化需求，提出相應的數(shù)學模型，將拼車問題模型化，同時設計一種基于乘客個性化需求的出租車路徑匹配算法，規(guī)劃最優(yōu)的行車路線，為出租車司機和乘客推薦優(yōu)化的行車路徑和拼車對象。實驗結果表明，提出的基于乘客個性化需求的拼車路徑匹配算法不僅可以提高搭乘成功率，還明顯降低了車輛的運行成本，有利于節(jié)能減排，合理利用資源。

出租車拼車；路徑匹配；個性化需求；環(huán)保

0 引 言

近年來，隨著人們生活水平的不斷提高，城市化進程日益加快，出租車行業(yè)飛速發(fā)展[1]。出租車在給人們生活帶來便利的同時也存在空車率高、實載率低等現(xiàn)象，由此造成了城市交通擁堵、空氣環(huán)境污染、交通資源浪費嚴重等問題[2-4]?！捌窜嚒笔翘岣叱鲎廛嚦溯d率，緩解打車困難，解決交通擁堵的有效手段[5]。目前，國內外學者主要研究的是拼車的基本理論,如合乘的發(fā)展現(xiàn)狀與趨勢、組織模式等。對于合乘的許多方面都是定性的分析,豐富了車輛合乘理論[6-9]。雖然部分研究者對合乘做了定量分析[10],但對于合乘路徑選擇方面的研究,幾乎都是針對一對多組織模式建立的數(shù)學模型,且考慮的因素與約束比較單一。對于模型的計算,主要采用啟發(fā)式算法與貪婪式算法來解決車輛的行駛路徑問題[11]。

文中提出了一種基于乘客個性化需求的出租車拼車算法，該算法有效解決了不同乘客的拼車請求，提高了搭乘成功率，降低了車輛運行成本。

1 出租車匹配問題的描述及數(shù)學模型的建立

1.1 問題描述

文中研究的是兩兩乘客間拼車路徑匹配的問題，它屬于多乘客、帶有固定時間窗口的合乘匹配問題。具體來說，就是在某個固定區(qū)域里，有多輛出租車在行駛，同時有多名乘客有不同的搭乘需求，乘客的出發(fā)點和目的地已經(jīng)確定，并且在上、下車站點對應一個明確的服務時間窗口，乘客必須在規(guī)定的時間窗口之內搭乘[12]。文中假定出租車在某個固定的區(qū)域里均勻分布，出租車能在較短的時間內到達乘客上車地點。此時忽略出租車到達乘客起始點的時間，這樣有利于簡化問題。

1.2 問題形式化建模

為描述問題方便，引入以下符號：

查詢請求集Q={q1,q2,…,qn}為所有有搭乘需要的乘客的查詢請求。其中乘客的請求包括出發(fā)地點si，目的地ei，出發(fā)時間starti，能夠接受的行駛時間runti，即qi={si,ei,starti,runti}。為描述方便，引入以下符號：

S={s1,s2,…,sn}為所有乘客的出發(fā)地點集合。

E={e1,e2,…,en}為所有乘客的目的地地點集合。

Z=S∪E∪Z'

其中，Z'表示除上下車點之外，出租車經(jīng)過的道路節(jié)點的集合；Z為所有位置點的集合。

1.3 約束條件

1.3.1 時間約束

乘客能夠拼車必須使得每個乘客在各自發(fā)出的請求起始時間前能夠上車，故乘客間的起始時間差必須大于乘客間起始位置的最短時間mint，即起點約束：

目前乘客對服務要求越來越高，要求必須在規(guī)定的時間內到達目的地，即終點約束：

1.3.2 個性化約束

由于每個乘客對于拼車有不同的要求，有的乘客希望節(jié)省費用，因此希望能夠找到跟他的路線幾乎完全匹配的拼車對象，而有的乘客希望節(jié)省時間的同時有人能夠跟他分擔部分費用?；谠摽紤]，提出一種滿足乘客個性化需求的拼車算法，通過控制參數(shù)C來滿足不同的用戶請求。其中，C為起點間距離與終點間距離的總和與該出租車所經(jīng)過的所有距離的比值：

當C=0表示乘客希望找到路徑完全匹配的拼車對象，C=0.5表示乘客希望找到至少66.66%路徑匹配的拼車對象，C=1表示乘客希望至少50%路徑匹配。

1.4 拼車目標

基于乘客個性化匹配問題可將目標分為兩個：

(1)滿足乘客的個性化需求，且拼車距離最遠。

(2)總花費最低。

文中提出一個既有利于司機又有利于乘客的計費方法。

司機的收入為：

CostTax=distmax(n,m)*per*1.2

其中，per為每公里的價格。

出租車拼車過程中，如果司機沒有提高收入，將打擊出租車司機的積極性，因此設置司機的收入為拼車對象起點終點總費用的1.2倍，由此來激勵司機的積極性。

乘客的費用為：

costPassern=CostTax*dist(sn,en)real/ (dist(sn,en)real+dist(sn,en)real)

costPasserm=CostTax*dist(sm,em)real/ (dist(sn,en)real+dist(sm,em)real

其中，dist(sn,en)real表示乘客n從起點到目的地的最短距離。

2 算法設計

由于出租車拼車問題是一個混合整數(shù)規(guī)劃問題,涉及到的約束較多。一般的方法雖然能夠求解,但往往結果不夠理想[13]。通常對于這樣的NP問題,采用貪心算法可以達到較優(yōu)的效果。對于拼車過程，查詢服務質量很重要，因此文中采用貪心算法尋找最優(yōu)的拼車對象。算法具體描述如下：

輸入：查詢集合Q={q1,q2,…,qn}，qn={sn,en,startn,runtn}；用戶個性化參數(shù)C。

輸出：每個能夠滿足個性化要求的乘客推薦滿足條件的拼車對象。

1.對于區(qū)域內的所有位置采用SPFA求出所有位置間的最短距離

2.Fori=1ton//對于任何一個查詢首先找到滿足時間約束的拼車對象

3.For(j=i+1;j

4.If(stC>0){

5.計算etC1,etC2

6.If(etC1<0&&etC2<0 ){

7.計算c//c為實際計算出來的參數(shù)

8.If(c≤C)

9.putqi，qiintoresultRi}

10.Elsecontinue}

11.ReturnRi//對于每個用戶按費用高低給出相應的拼車對象}

12.ReturnR

通過分析上述算法，SPFA的算法復雜度為O(ke)(k<2)。尋找匹配路徑時，循環(huán)的復雜度為O(n2)，所以該拼車算法的復雜度為O(ke+n2)。

3 實驗及結果分析

為驗證算法的有效性及性能，以中國南京市實際路網(wǎng)的某個區(qū)域作為研究對象進行實驗，該區(qū)總共位置為10 000，每條不同的道路有不同的速度即行駛時間的限制。設查詢時間為下午5點到晚上9點為驗證參數(shù)，對參數(shù)C的設置進行了對比分析。

實驗內容包括：不同參數(shù)設置對拼車成功率的影響；不同參數(shù)設置對查詢時間的影響；不同參數(shù)設置對乘客拼車平均時間的影響。

實驗環(huán)境：Intel@Celeron@CPUE3300，2．50GHz，4GB內存，操作系統(tǒng)為Window7Professional。

首先考慮查詢數(shù)量對各個指標的影響。此時C=0,查詢?yōu)殡S機生成的，時間段設置為交通擁堵的下班高峰期下午5點到晚上9點，因為該時間段對出租車的需求較高。很顯然某個時間段查詢越多，拼車成功率越高，司機增加的收入越高，用戶的付費越低，這是因為拼車的人越多，越能找到匹配度高的拼車對象。實驗結果如圖1～3所示：相同時間段內拼車查詢越多拼車成功率越高，查詢運行時間越長，但總體的時間效率是很高的。

然后考慮C值對各個指標的影響。此時查詢數(shù)量為5 000，C值越大，說明乘客對路徑匹配要求越高。當C值為100%時說明乘客希望找到100%路徑匹配的拼車對象，很顯然C值越小，拼車成功率越低，司機收入越低，用戶的付費越少。這是因為C值越大，越難找到匹配度高的拼車對象。一旦找到，乘客間的路徑匹配度較高，故司機運行的總路程會減少，故收入會降低。實驗結果如圖4～6所示。

圖1 拼車成功率(1)

圖2 拼車查詢運行時間(1)

圖3 拼車合乘平均時間(1)

圖4 拼車成功率(2)

圖5 拼車查詢運行時間(2)

圖6 拼車合乘平均時間(2)

4 結束語

文中構建了個性化出租車拼車路徑匹配問題的數(shù)學模型，并提出解決此問題的算法。通過對中國南京市的某個時間段，10 000個乘客服務需求的數(shù)據(jù)結果分析，表明該算法能夠在較快時間給出優(yōu)秀的拼車方案，整體搭乘成本及搭乘成功率較高。還進行了個性化服務需求的實驗，結果表明該算法能夠滿足用戶的個性化需求。文中研究的是兩兩乘客拼車路徑匹配問題，尚未涉及更多乘客，也沒有出租車的實際分布狀況對拼車路徑匹配的影響，這也是后期將要開展的研究方向。

[1] 王麗珍.大城市出租車靜態(tài)和動態(tài)合乘模式的探討[D].長沙：長沙理工大學,2012.

[2] 侯惠勤.公共服務藍皮書：中國城市基本公共服務力評價[M].北京:社會科學文獻出版社,2012.

[3] 常超凡，陳團生，劉明君,等.城市出租車擁有量對分擔率影響分析[J].交通科技與經(jīng)濟,2007,9(3):75-76.

[4] 晉江月.拼車的經(jīng)濟學分析[J].科技信息,2006(11):97.

[5] 戴云琪.“拼車”行為的問題研究[J].市場周刊:理論研究,2007(11):94-96.

[6] 王 羅.出租車共乘問題研究[D].長沙：長沙理工大學,2008.

[7]MorencyC.Theambivalenceofridesharing[J].Transportation,2007,34(2):239-253.

[8]ShaheenSA,CohenAP,RobertsJD.CarsharinginNorthAmerica:marketgrowth,currentdevelopments,andfuturepotential[J].TransportationofResearchRecordJournalofTransportationResearchBoard,1986(1):116-124.

[9]PrettenthalerFE,SteiningerKW.Fromownershiptoserviceuselifestyle:thepotentialofcarsharing[J].EcologicalEconomics,1999,28(3):443-453.

[10] 彭霞花.出租車合乘的關鍵技術研究[D].長沙:長沙理工大學,2009.

[11]BarthM,ToddM.Simulationmodelperformanceanalysisofamultiplestationsharedvehiclesystem[J].TransportationResearchPartCEmergingTechnologies,1999,7(4):237-259.

[12] 王永明.交通標志自動分割與識別算法及數(shù)學模型研究[D].昆明:云南師范大學,2005.

[13] 張 瑾，何瑞春.解決動態(tài)出租車“拼車”問題的模擬退火算法[J].蘭州交通大學學報,2008,27(3):85-88.

Research on Carpool Path Matching Algorithm Based on Personalized Needs

GUO Hui1,WANG Li-xia2

(1.College of Mathematics Physics and Information Engineering,Zhejiang Normal University, Jinhua 321004,China; 2.Xingzhi College of Zhejiang Normal University,Jinhua 321004,China)

At present,there are some common problems such as taxi difficult to call,traffic congestion,heavy air pollution in many cities and so on.Car-sharing is an effective method to solve these problems.Car-sharing can not only ease traffic congestion and solve the problem of taking a taxi is difficult,but also reduce energy consumption and emissions to be helpful for environmental protection.A corresponding mathematical model is proposed and a taxi path matching algorithm is designed based on the individual needs of passengers.In addition,the best route with minimal cost and price is designed to meet the requirement of passengers as much as possible.Experimental results show that the proposed car-sharing path matching algorithm can improve success rate of car-sharing and reduce the travel cost and it is beneficial to energy conservation and emission reduction,reasonable use of resources.

car-sharing;path matching;individual needs;environmental protection

2015-05-15

2015-08-19

時間：2017-01-04

國家自然科學基金資助項目(61170108，61402418)；教育部人文社科研究項目(12YJCZH142)；浙江省自然科學基金(LQ13F020007，LY15F020013)

郭 會(1990-)，女，碩士研究生，研究方向為信息安全和隱私保護；王麗俠，副教授，研究方向為智能計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1017.006.html

TP301.6

A

1673-629X(2017)01-0057-04

10.3969/j.issn.1673-629X.2017.01.013