譚艷祥 李立軍 彭家睿 徐迅

摘? 要：隨著乘坐出租車出行的人數(shù)不斷增加，現(xiàn)階段的“打車難”卻成為人們不得不面對(duì)的問(wèn)題。出租車合乘能有效緩解上下班高峰期打車難的問(wèn)題，并減少能源浪費(fèi)和大氣污染。文章建立了考慮繞路與三名乘客合乘的靜態(tài)合乘模型。使用基于勢(shì)能值和曼哈頓距離的聚類算法對(duì)出租車進(jìn)行聚類，建立了基于非直達(dá)系數(shù)的合乘費(fèi)用分?jǐn)偰Ｐ停档土顺丝统鲂锌傎M(fèi)用。最后進(jìn)行仿真實(shí)驗(yàn)，對(duì)模型的部分細(xì)節(jié)進(jìn)行補(bǔ)充說(shuō)明，實(shí)驗(yàn)結(jié)果表明合乘使得乘客與司機(jī)雙方受益。

關(guān)鍵詞：出租車合乘;靜態(tài);聚類;費(fèi)用分?jǐn)?/p>

中圖分類號(hào)：U491? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：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

引言

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

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

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

1 出租車聚類算法

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

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

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

1.1 勢(shì)能值

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

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

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

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

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

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

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

3 算例研究

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]張昂?jiǎn)?城市交通運(yùn)行效率評(píng)價(jià)[D].首都經(jīng)濟(jì)貿(mào)易大學(xué)，2014.

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

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

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

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

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

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

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

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

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