一種出租車合乘業(yè)務(wù)方案設(shè)計

歐先鋒，羅百通，向燦群，黎式南，郭龍源

(湖南理工學(xué)院 a.信息與通信工程學(xué)院；b.復(fù)雜系統(tǒng)優(yōu)化與控制湖南省普通高等學(xué)校重點實驗室，湖南 岳陽 414006)

一種出租車合乘業(yè)務(wù)方案設(shè)計

歐先鋒a,b，羅百通a,b，向燦群a,b，黎式南a,b，郭龍源a,b

(湖南理工學(xué)院 a.信息與通信工程學(xué)院；b.復(fù)雜系統(tǒng)優(yōu)化與控制湖南省普通高等學(xué)校重點實驗室，湖南 岳陽 414006)

以減少出租車的空乘率和乘客等待時間為目標(biāo)，對出租車合乘方案進行了研究，通過采用K-均值聚類算法和矩陣迭代法解決了乘客合乘問題和最短行程的規(guī)劃問題，同時還分別對合乘的不同情況進行了分析，探索了車費計算公式，設(shè)計了一種與合乘方案相應(yīng)的合理的車費計算方法，能夠兼顧到乘客和司機雙方的利益問題，從而提升雙方參與合乘的積極性，為出租車合乘問題的研究提供了一些可能的思路。

合乘業(yè)務(wù)；K-均值聚類；矩陣迭代法；城市交通；車費計算

隨著經(jīng)濟的快速發(fā)展，城市機動車數(shù)量激增，人們的出行越來越方便、快捷，但也帶來了交通擁堵、環(huán)境污染等一系列問題。其中交通擁堵問題是由于道路資源無法滿足人們出行的需要而導(dǎo)致的。合乘方式出行是緩解城市交通擁堵的一種非常簡單有效的方法。

出租車合乘業(yè)務(wù)是指路線相同或相近的2位或多位乘客共同乘坐同一輛出租車出行。系統(tǒng)根據(jù)合乘人數(shù)、乘車時間、實際路線等因素，分別計算出每位乘客的車費。該業(yè)務(wù)在不增加運營車輛總數(shù)的情況下提高運力，有助于緩解打車難問題，并能降低乘客出行成本，提高司機收入。周和平等[1]以公平性為原則，綜合考慮駕駛員與出行者利益，以出行者時間費用成本最小為目標(biāo)函數(shù)，以保障駕駛員合理收益為約束，構(gòu)建出租車合乘路徑選擇與費率優(yōu)化模型，設(shè)計改進的遺傳算法對該模型進行求解；張薇等[2]針對出租車合乘模式下司機的收入問題，建立了合乘模式下司機收入公平心理模型，采用公平理論分析了司機的心理及行為，通過仿真計算，分析了合乘模式下乘客總需求量及司機公平心理對司機收入的影響；針對城市出租車搭載乘客少、資源大量浪費、造成道路擁堵等情況，張亦楠等[3]設(shè)計了一種兩段的智能匹配算法(粒子群算法和遺傳算法)，規(guī)劃最優(yōu)的行車路線，以較少的花費和代價，滿足盡可能多的乘客搭乘用需求，但算法較復(fù)雜。本文對出租車合乘方案進行深入研究，從數(shù)學(xué)的角度，兼顧乘客和司機雙方的利益關(guān)系，建立合理的合乘方案模型，分別從乘客-出租匹配、行駛路徑規(guī)劃、車費計算3個方面進行及求解，算法運算效率更快。

1 問題的提出與分析

設(shè)計一種高效的合乘方案來合理規(guī)劃出租車的行駛路徑和減少出租車的空載率，使乘客等待時間減少和出租車的利用率提高。出租的合乘主要源于合乘乘客的出發(fā)地和目的地與出租車的行駛所經(jīng)過路徑相近或相同，且滿足上車點在規(guī)定的時間和距離內(nèi)實現(xiàn)合乘乘客與出租車的合乘。因此在出租車的合乘中，乘客到達上車點的時間與距離是實現(xiàn)出租車合乘成功的關(guān)鍵。

要解決出租車之間的路徑規(guī)劃問題，需要考慮出租車和乘客的起始點和目的地的不同，求解最短路徑問題，設(shè)計合乘方案全面兼顧乘客與司機的花費和收益，合理進行行車路線規(guī)劃，提高運送效率，盡可能地減少所有乘客從出發(fā)點到達目的地的乘車時間。同時要使所需的出租車數(shù)量盡量少[1]，即減少出租車的空載率。也即出租車的行駛路徑上盡可能地出現(xiàn)3人合乘的情況，而乘客則要盡可能地選擇只有1個空位的出租車。

合乘方案與乘客、司機雙方的經(jīng)濟利益息息相關(guān)，有效保障兩方的經(jīng)濟花費和收益對能否良好實施合乘方案非常關(guān)鍵，所以選擇合理的車費計算方法至關(guān)重要[2]。在多名乘客共同乘坐的路段，每位乘客僅需花費低于單獨乘車時的車費，在出租車行駛路徑規(guī)劃合理的情況下(不繞路或者合理繞路)，采用合乘的方式應(yīng)該有效地減少乘客的乘車花費，適當(dāng)增加司機的收益。不繞路是指路徑規(guī)劃的最短路徑。合理繞路是指出租車載著乘客A駛向目的地的過程中，繞行一段距離接乘客B。此過程會對乘客A造成一定的損失，需對計費方式進行適當(dāng)調(diào)整，對損失進行補償，保證乘客和司機的經(jīng)濟利益，使乘客付出的車費少于不繞路付出的車費，同時司機的收費多于不繞路的收費。在不繞路計費過程中，合乘方案的車費計算應(yīng)對某乘客超出起步距離的單獨乘車段距離、2人合乘段距離、3人合乘段距離進行統(tǒng)計和距離累計，還有等車時間損失等問題，對司機而言，還需考慮候時費、長途返空費等問題。在合理繞路計費過程中，除考慮上述因素外，還需考慮被繞路乘客的繞行損失、司機中途停車等候等問題，為體現(xiàn)公平性，還需對司機和乘客進行補償。

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

本文針對出租車合乘匹配問題，提出了解決思路，如圖1所示。首先對乘客進行分配，按照起點、終點方位分布情況和乘客各自需求，求出車輛行駛時的最優(yōu)搭乘半徑，將乘客分配到合適的出租車上；然后再對分配到同一輛車上的多名乘客的行駛路徑進行合理規(guī)劃，找出一條合理的行車路線。這樣能夠幫助有需求的乘客搭乘到適宜的出租車。通過使用現(xiàn)實數(shù)據(jù)驗證表明，該算法能夠達到多名乘客共同搭乘出租車的目標(biāo)[3-4]，并應(yīng)用到現(xiàn)實生活中去，有效提高出租車空間資源的利用率，減少乘客等待時間和出租車空載率，實現(xiàn)各方利益的最大化。

圖1 出租車合乘匹配問題解決思路

2.1 乘客分配

2.1.1 乘客分配模型建立思路

如圖2所示，在分配乘客到出租車的過程中，采用K-均值聚類算法，按照起點、終點方位分布情況和乘客需求，規(guī)定以出租車為中心的最佳搭乘半徑r(比如250 m)畫一個圓形區(qū)域，將區(qū)域內(nèi)符合要求的乘客劃分到一輛出租車上(假設(shè)限坐3人)，比較車上乘客各自的目的地方向的夾角，若某一乘客的目的地方向與其他乘客的目的地方向的夾角大于角度α，則該乘客下車；出租車再在r范圍內(nèi)重新尋找乘客，直到滿載3個乘客或r范圍內(nèi)無合適乘客。然后再以剩下沒上車的乘客為中心規(guī)定半徑，將半徑內(nèi)有空位的出租車劃分給沒上車的乘客，再進行乘客目的地方向夾角比較，實現(xiàn)乘客和出租車的匹配劃分，為后續(xù)的路徑規(guī)劃做準(zhǔn)備工作。

圖2 聚類規(guī)則

2.1.2 乘客分配過程描述

本文的研究對象有多輛出租車和多位有搭載需求(同意合乘)的乘客，出租車應(yīng)該在不超過最大載客容量(本文假設(shè)限定3人)的情況下，滿足乘客各自搭乘需求的同時，規(guī)劃合適的行駛路徑，盡量多地搭載符合要求的乘客，而且還要保證總共行駛的時間最短[4]，其算法如圖3所示。

圖3 乘客與出租車分配算法流程圖

在此過程中，關(guān)鍵問題是要計算得到出租車在每個停車點的搭載區(qū)域，也就是以出租車行駛路徑上的每個節(jié)點(出租車位置、乘客起點、終點)為中心的圓形區(qū)域(規(guī)定半徑)。根據(jù)初始情況時，各節(jié)點附近的出租車搭載情況和乘客各自的搭乘需求，運用K-均值聚類算法，以成功匹配率作為目標(biāo)優(yōu)化函數(shù)，經(jīng)過多次迭代計算獲取最合理的搭乘半徑，達到搭載率最大的目的。乘客分配過程中的目標(biāo)函數(shù)為：

(1)

其中：f(xk)指出租車k在運營時的匹配率；Mk指出租車k在運營過程中成功匹配的乘客數(shù)； nk指出租車k在剛開始的行車路線中應(yīng)途經(jīng)的節(jié)點總數(shù)；sk,n指出租車k的第n個節(jié)點在其搭載區(qū)域內(nèi)所含的乘客上、下車節(jié)點數(shù)量。

2.1.3 約束條件

出租車搭載乘客時，任何時刻都要符合車上共同搭乘的乘客數(shù)目不超過規(guī)定的最大載客容量。即：

(2)

乘車過程中，乘客的上、下車行為一定要發(fā)生在同一輛車上，即在上車點x至下車點m+n+x的路上一直坐在同一輛出租車上，若不然，則視為不能匹配成功。于是有：

(3)

2.2 出租車智能合乘匹配中的行駛路徑規(guī)劃

路徑規(guī)劃問題是對已經(jīng)劃分到同一輛出租車上的乘客，采用矩陣迭代法來對節(jié)點距離矩陣進行迭代運算求解到達乘客目的地的最短行駛路線，在運營出租車的數(shù)量盡量少的情況下，成功搭載盡量多的乘客，同時將行駛時間降到最小。

矩陣迭代法[5-6]主要是通過不斷迭代計算、更正原路徑權(quán)矩陣D而達到逐步向最短路徑權(quán)矩陣D0接近的目的，最后獲得最短路徑權(quán)矩陣D0，其計算公式為：

(4)

其運算規(guī)則為：

(5)

通過式(4)、(5)屢次迭代計算，直到滿足D(n)=D(n-1)，即第n次迭代后的路徑權(quán)矩陣的每一元素與第(n-1)次迭代后的路徑權(quán)矩陣中對應(yīng)元素全部相等，那么矩陣D(n-1)就是最短路權(quán)矩陣D0，即D0=D(n)=D(n-1)，再根據(jù)式(5)計算路權(quán)矩陣的同時可得到路徑矩陣。

首先應(yīng)構(gòu)建路徑路權(quán)矩陣(以距離為權(quán)的權(quán)矩陣)，該矩陣表明了節(jié)點間只經(jīng)過一步(一條邊)抵達某一點的距離，對距離矩陣進行屢次迭代計算，獲得需通過兩步抵達某一點的最短距離。所以，規(guī)劃出租車行駛的最優(yōu)路線時，應(yīng)該計算獲取每個停車節(jié)點之間的最短路線。本文采用距離矩陣求解最短路徑的方法[7]。

2.3 出租車合乘方案的計費方式

減少支付車費即能抵達目的地是提高乘客選擇合乘方式出行的積極性的關(guān)鍵，為合乘方案設(shè)計合理的計費方式則能相應(yīng)地減少乘客所需支付的車費。而且由于秉持公平的原則，應(yīng)該保障出租車司機的經(jīng)濟收入。因此，確定一個合理的合乘費率標(biāo)準(zhǔn)是本文提出的合乘方案能夠順利實施的關(guān)鍵因素。確定合乘費率所需要達到的目的，就是在不少于司機按正常費率行駛完全程所得收益的同時，使每個乘客的所需支付車費降到最少[8]。

2.3.1 合乘費用

令出租車的起步價為ps元，超過起步價后，每車公里租價為pr元，乘客i的行程為xi。當(dāng)乘客i單獨搭乘出租車時，其支付車費p(xi)為

(7)

在乘客選擇合乘方式搭乘出租車抵達目的地的過程中，會遇到各種各樣的合乘方式。比如，乘客可能有同一個起點，而終點卻不同；乘車途中又可能有其他人上車(不超過最大限載容量即可)。然而不論哪種合乘方式，對選擇合乘的乘客而言，在其從起點至終點的完整乘車過程中的乘車狀態(tài)可分為2種：合乘狀態(tài)和獨乘狀態(tài)。同一出租車上每位乘客在搭乘時，別的乘客開始搭乘或抵達終點都會導(dǎo)致其乘車狀態(tài)的變化，即乘客合乘出租車的過程也是其乘車狀態(tài)不斷改變的過程[9]。令乘客i搭乘出租車的路程長度為xd，與其他乘客合乘總路段為di，合乘路段所需支付車費的比例(簡稱支付比例)為θ，乘客i的乘車費用可用式(8)表示。

式(8)中的(a)式表示乘客i全程合乘的費用；(b)表示乘客先與人合乘di，再獨乘至終點所需費用；(c)表示先獨乘，且獨乘路程超過起步價里程b的情況下，再與人合乘di所需費用；(d)表示先獨乘，且獨乘路程不超過起步價里程b的情況下，再與人合乘di所需費用；(e)表示乘客先獨乘yi的路程，且獨乘路程超過起步價里程b的情況下，再與人合乘di，最后又獨自乘車直至終點所需的費用；(f)表示乘客先獨乘yi的路程，且獨乘路程不超過起步價里程b的情況下，再與人合乘di，最后又獨自乘車直至終點所需的費用；(g)表示乘客先合乘zi的路程，且合乘路程超過起步價里程b的情況下，再獨乘li，最后又與人合乘直至終點所需的費用；(h)表示乘客先合乘zi的路程，再獨乘li，且此時乘車路程不超過起步價里程b的情況下，最后又與人合乘直至終點所需的費用；(i)表示乘客先合乘zi的路程，且合乘路程不超過起步價里程b，再獨乘li，且此時乘車路程超過起步價里程b的情況下，最后又與人合乘直至終點所需的費用。

(8)

2.3.2 可預(yù)見損失補償

出租車計費方式應(yīng)該具有公平性、雙贏性，避免打擊司機、乘客選擇合乘出行的積極性，不利于合乘方案的實施和推廣[10]。實際合乘中，難免會遇到乘客增加繞行距離、司機中途停車接客等問題。因此，應(yīng)對司機和乘客可預(yù)見的損失進行補償。本文主要是對乘客的繞行補償。

Jr=0.5·c·(F2-F1)

(9)

其中：Jr為乘客因合乘而產(chǎn)生的繞行距離補償/元：c為超過起步里程后的每公里單價/(元/km)：F1為乘客單獨乘車的最短距離/km，由合乘方案模型中矩陣迭代法在乘客輸入乘車起終點后自動算出；F2為乘客合乘的實際距離/km。

2.3.3 出租車合乘方案的計費方式的模型

根據(jù)求出的乘客i的乘車費用ci，考慮到繞行損失補償，則合乘方案的計費模型為：

pi=ci-Jr

(10)

3 實驗分析

3.1 實驗參數(shù)設(shè)置

實驗參數(shù)的設(shè)置為：合乘率r=0.9；車配人半徑R1=0.25 km；人配車上座優(yōu)先參數(shù)[2,1,0]；人配車半徑R2=0.5 km。

算法過程：

while(合乘率>0.9)

{上車過程：

1)車配人。在半徑為R1=0.25 km內(nèi)的人隨機上車，每輛車盡量坐滿3人。

下車過程：

2)人車配對。根據(jù)給出的約束條件對每輛存在合乘的車輛進行人人配對，配對成功則合乘，否則不合格的人下車。

3)人配車。未上車的乘客搜索半徑為R2=0.5 km內(nèi)車輛，根據(jù)搜索范圍內(nèi)車輛上座率作排序，優(yōu)先上存在乘客的租出車，增加合乘率。

4)計算合乘率及相關(guān)參數(shù)}

結(jié)論：R1、R2越大，合成率越高；上座優(yōu)先參數(shù)為[2，1，0]時合乘率最大，[1，2，0]次之。

3.2 實驗數(shù)據(jù)

為了對模型和算法進行驗證，收集某城市的部分打車需求數(shù)據(jù)、空馳出租車的位置信息，假設(shè)路網(wǎng)為正方形網(wǎng)格，道路可雙向行駛(以一車3乘為例)，其中空馳出租車的位置信息如表1所示。

表1 出租車車輛信息

合乘乘客信息如表2所示。

表2 乘客信息

3.3 實驗結(jié)果分析

根據(jù)起始位置和目的地能否起到路徑優(yōu)化的作用，由本文的算法得到如圖4所示為6，34，55，150，239，345號車對3人共乘時的車配人仿真結(jié)果。

a.6,34,55號車輛上3人共乘車配人結(jié)果

b.150,239,345號車輛上3人共乘車配人結(jié)果

最終出租車行駛過程中搭乘乘客路線見表3。

表3 出租車行駛路線

圖5顯示了數(shù)據(jù)中不同合乘情況時，合乘起點初始位置和隨后的城市路網(wǎng)最優(yōu)路徑。圖中左邊一列坐標(biāo)是以左下角為基點，右邊一列坐標(biāo)是以左上角為基點。

a.2人合乘同起點起始位置分布圖

b.2人合乘同起點網(wǎng)絡(luò)最優(yōu)路徑

c.2人合乘不同起點起始位置分布圖

d.2人合乘不同起點網(wǎng)絡(luò)最優(yōu)路徑

e.3人合乘同起點起始位置分布圖

f.3人合乘同起點網(wǎng)絡(luò)最優(yōu)路徑圖5 合乘起點初始位置和城市路網(wǎng)最優(yōu)路徑圖

根據(jù)本文中提出的車費計算模型得出某出租車在3人合乘情況下的車費支付情況如表4和出租車司機收益情況如表5。

表4 各乘客在不同乘車方案下的車費支付情況 元

表5 出租車司機在不同乘車方案下的收益 元

4 結(jié)語

本文在充分考慮乘客和司機各自需求的前提下，優(yōu)化設(shè)計了一種高效的出租車合乘方案模型。該模型充分考慮了乘客的需求(等待時間盡量短，乘車價格盡量少)和司機的需求(空車等待時間少，收益明顯增加)，通過對出租車合乘方案的設(shè)計問題進行分析研究，將相關(guān)問題及約束條件采用了數(shù)學(xué)語言描述，針對方案設(shè)計過程中遇到的關(guān)鍵問題，采用兩段式解決的辦法，采用基于K均值聚類、矩陣迭代法的優(yōu)化模型，實現(xiàn)了合乘路線最優(yōu)的目標(biāo)。

本文設(shè)計的出租車合乘方案模型，在用盡量少的出租車搭載數(shù)目盡量多的乘客，同時使合乘總花費達到最少。采用2個算法(K均值聚類、矩陣迭代法)分階段解決了合乘匹配和路徑規(guī)劃的難題。最后運用所提出的出租車合乘方案模型對附件中的實際數(shù)據(jù)進行了分析驗證，結(jié)果表明：該能模型能有效解決附件中出租車合乘調(diào)度問題。但仍存在一些不足，如在車與人的匹配問題，會出現(xiàn)有一個車或者幾個車在每一個?？空军c都有一個人下車，而另外一些車在這一路一直是空載等問題有待完善和改進，使合乘方案更加合理、高效。如本文在研究合乘匹配問題中加入的約束條件不夠全面，因為在現(xiàn)實生活中還需考慮道路擁堵情況，天氣環(huán)境因素等影響，使合乘方案更貼近現(xiàn)實。

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

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

[3]張亦楠,魏志強,劉昊.出租車多人合乘匹配問題的研究[J].信息通信,2014(3):70-71.

[4]張亦楠.出租車合乘模式下的智能匹配問題的研究與實現(xiàn)[D].青島:中國海洋大學(xué),2014.

[5]劉洪麗,顧銘.矩陣迭代法在物流中心選址中的應(yīng)用分析[J].現(xiàn)代商貿(mào)工業(yè),2013(20):64-66.

[6]劉洪麗,馮伯林.基于最優(yōu)化思想的城市交通流分配[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2005,29(6):913-916.

[7]郭瑞軍,王晚香.基于矩陣迭代法的出租車合乘最短路徑選擇[J].大連交通大學(xué)學(xué)報,2011,32(4):28-31.

[8]覃運梅,石琴.出租車合乘模式的探討[J].合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2006,29(1):77-79.

[9]劉佳.租車合乘方式及定價模型優(yōu)化研究[D].重慶:重慶交通大學(xué),2016.

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

[11]肖強,何瑞春,俞建寧,等.出租車合乘收益趨勢影響模型研究[J].蘭州交通大學(xué)學(xué)報,2016,35(4):141-147.

[12]CHORFIi H,ALATEE A,ALOQEELY A,et al.A smart real-time ride-share for riyadh city[J].Procedia-Social and Behavioral Sciences,2015,195:1932-1937.

[13]FAHNENSCHREIBER S,GüNDLING F,KEYHANI M H,et al.A multi-modal routing approach combining dynamic ride-sharing and public transport[J].Transportation Research Procedia,2015,13:176-183.

Design and Research of Taxi-pooling Service

OUXianfenga,b,LUOBaitonga,b,XIANGCanquna,b,LIShinana,b,GUOLongyuana,b

(a.College of Information & Communication Engineering;b.Key Laboratory of Optimization & Control for Complex Systems,Hunan Institute of Science and Technology,Yueyang 414006,China)

To reduce the passengers’ waiting time and the taxis’ unloaded ratio,the authors studied the problem of taxi-pooling,solved matching problem between vehicles and passengers,and minimized the taxi route through K-means clustering algorithm and matrix iteration method.At the same time,they explored the formula for calculating fare based on the analysis of different conditions of taxi-pooling,then put forward a reasonable pricing optimization model considering the benefits of both the taxi driver and passengers,which would increase the participation of the two parties.This proposed algorithm presented some feasible ideas on the research of taxi-pooling and the allocation of taxi resources,which was beneficial for improving urban traffic conditions.

taxi-pooling;k-means clustering;matrix iteration method;urban traffic;fare calculation

10.13542/j.cnki.51-1747/tn.2017.02.010

2017-05-18

湖南省自然科學(xué)基金項目(2017JJ3099)；湖南省科技計劃項目(2016TP1021)

歐先鋒(1983—),男，講師，博士，研究方向：圖像處理、視頻壓縮編碼及傳輸。

郭龍源(1973—)，男，副教授，博士，研究方向：計算機視覺、圖像處理，電子郵箱：goulongyuan@hnist.edu.cn。

TP391

A

2095-5383(2017)02-0043-07