歐先鋒，羅百通，向燦群，黎式南，郭龍?jiān)?/p>

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

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

歐先鋒a,b，羅百通a,b，向燦群a,b，黎式南a,b，郭龍?jiān)碼,b

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

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

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

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

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

1 問(wèn)題的提出與分析

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

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

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

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

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

圖1 出租車合乘匹配問(wèn)題解決思路

2.1 乘客分配

2.1.1 乘客分配模型建立思路

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

圖2 聚類規(guī)則

2.1.2 乘客分配過(guò)程描述

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

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

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

(1)

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

2.1.3 約束條件

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

(2)

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

(3)

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

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

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

(4)

其運(yùn)算規(guī)則為：

(5)

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

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

2.3 出租車合乘方案的計(jì)費(fèi)方式

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

2.3.1 合乘費(fèi)用

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

(7)

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

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

(8)

2.3.2 可預(yù)見(jiàn)損失補(bǔ)償

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

Jr=0.5·c·(F2-F1)

(9)

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

2.3.3 出租車合乘方案的計(jì)費(fèi)方式的模型

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

pi=ci-Jr

(10)

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

算法過(guò)程：

while(合乘率>0.9)

{上車過(guò)程：

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

下車過(guò)程：

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

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

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

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

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

表1 出租車車輛信息

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

表2 乘客信息

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

最終出租車行駛過(guò)程中搭乘乘客路線見(jiàn)表3。

表3 出租車行駛路線

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

a.2人合乘同起點(diǎn)起始位置分布圖

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

c.2人合乘不同起點(diǎn)起始位置分布圖

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

e.3人合乘同起點(diǎn)起始位置分布圖

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

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

表4 各乘客在不同乘車方案下的車費(fèi)支付情況 元

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

4 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

[11]肖強(qiáng),何瑞春,俞建寧,等.出租車合乘收益趨勢(shì)影響模型研究[J].蘭州交通大學(xué)學(xué)報(bào),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é)基金項(xiàng)目(2017JJ3099)；湖南省科技計(jì)劃項(xiàng)目(2016TP1021)

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

郭龍?jiān)?1973—)，男，副教授，博士，研究方向：計(jì)算機(jī)視覺(jué)、圖像處理，電子郵箱：goulongyuan@hnist.edu.cn。

TP391

A

2095-5383(2017)02-0043-07