關(guān)于合肥市“出租車拼車”問題的優(yōu)化研究*

劉書曼，周宗福，張 晨，黃躍輝，陳詩揚

(安徽大學數(shù)學科學學院，合肥230601)

出租車作為城市交通系統(tǒng)的一員，它需要為城市交通系統(tǒng)運輸效率的提高做出貢獻。但目前出租車“兜客式”的經(jīng)營方式造成了“空車”和低實載率的現(xiàn)象，反而降低了道路運輸效率，同時也增加了城市的環(huán)境污染?！捌闯鲎廛嚒钡呐d起有利于減輕交通負擔，同時還節(jié)約了資源，減少了尾氣污染，而且對于乘客而言，降低了出行的成本。

“拼出租車”即指具有大體相同行駛方向和路徑的乘客，共同乘坐一輛出租車［1］。國內(nèi)對“拼出租車”問題已做過一些研究，文獻［2］［3］對于拼車路線優(yōu)化以及費用分攤問題給出了解決方案，但在考慮路線優(yōu)化時只是將最短路程作為最優(yōu)目標，沒有考慮交通狀況的擁擠以及其他的時間成本。此處則綜合考慮影響最優(yōu)路線的因素:路程、交通狀況、人的滿意度等。對于費用分攤，研究也不同于文獻［2］，不僅將路程作為費用分攤的唯一依據(jù)，還考慮了乘客的優(yōu)先級指數(shù)，充分體現(xiàn)了公平性原則。

1 研究的前期準備

主要通過進行一定范圍的問卷調(diào)查來了解合肥市內(nèi)的“拼出租車”情況，共發(fā)出問卷500張，實際有效問卷380張。通過統(tǒng)計問卷調(diào)查數(shù)據(jù)發(fā)現(xiàn):

在拼車的能愿度上，大多數(shù)人傾向于拼車出行，其中愿意與別人拼車的占63.3%，不愿意與別人拼車的占36.7%，這為此問題的研究提供了動力，也說明此項研究具有研究的實際意義。在拼車目的性上，認為以快速到達目的地為優(yōu)先的占54.55%，認為以節(jié)約金錢為優(yōu)先的占45.45%，這樣，在建立層次分析模型時，可以設(shè)定時間和費用的量化比值為6∶5。在拼車管理上，有87.88%的人認為需要在合肥市制定出相應(yīng)的一套“拼出租車”管理措施(在問卷調(diào)查過程中，也了解到有些出租車司機強行拼車，對每位乘客收取不變的費用，這顯然是不公平的，這也是研究費用分攤問題的原因)。在拼車費用的收取上在問卷中給出了按路程和按人數(shù)兩種方案，贊成按人數(shù)定折扣合適的比例以及贊成按路程的遠近定費用合適的比例見圖1、圖2。

圖1 按人數(shù)定折扣

圖2 按路程遠近定費用

2 拼車最優(yōu)路線問題的研究

2.1 問題的描述

研究的情況是合肥市內(nèi)存在一定潛在數(shù)量的乘客群，由于某種目的而引發(fā)“拼出租車”需求，并且了解到合肥市內(nèi)存在的拼車模式更多的是“一對多”模式，即只將相同的起點但是不同終點的乘客進行配對運送，其拼車模式如圖3。此處研究的就是在類似情形下的拼車路線優(yōu)化問題和拼車費用分攤問題。

圖3 “一對多”拼車模式

圖4 合肥市部分路線圖

2.2 拼車路線最優(yōu)化數(shù)學模型的建立與分析

2.2.1 選擇合適的合乘乘客

在解決“拼出租車”所引發(fā)的相關(guān)問題之前，首要解決的問題是選擇合適的合乘乘客，例如在合肥市某個站口，有數(shù)量較多的乘客有需求“拼出租車”(假設(shè)這些乘客群已自動分好組，即去往同一個方向的在一組)，且同在一組的乘客數(shù)超過了出租車的最大載客量，此時就要考慮選擇合適的乘客人群。在這里，引入乘客優(yōu)先級的量化系數(shù)μ，用來描述拼車對象的選取以及乘客到達各自目的地的先后順序。

如何確定合理的μ值是關(guān)鍵的一步，考慮到出租車出發(fā)點到目的地的距離，乘客的緊急程度，以及對合乘者的性別要求等因素與μ有很大關(guān)系，因此利用這些因素來確定μ值，故引入距離因子κ，乘客的緊急系數(shù) υ(υ∈(0，1))，乘客提出的特殊要求度 ξ(ξ∈(0，1))，這樣，可以建立模型計算 μ 值:

其中，x1，x2，x3∈(0，1)為 κ，υ，ξ之間的權(quán)重比值，通過統(tǒng)計分析可以確定的 x1，x2，x3的值分別為 x1=0.713，x2=0.207，x3=0.080，κ，υ，ξ各值依實際情況而定。綜合考慮乘客的情況進行定量計算，就可以得到的乘客優(yōu)先級的量化系數(shù)μ值，以此作為選擇合適乘客的決策標準，μ值越大，選擇為合乘對象的可能性就越大。

2.2.2 模型的建立與分析

(1)路線簡化圖的建立?？紤]的最優(yōu)線路是指:路程最短，交通狀況最優(yōu)，紅綠燈個數(shù)最少，路程最短即指所花的費用最省，時間最少，交通狀況與紅綠燈個數(shù)也與時間相關(guān)?？紤]到擁擠的交通狀況會使乘客焦慮，降低人的幸福感，故另外引入滿意度系數(shù)λ∈(0，1)，λ可根據(jù)交通狀況擁擠程度(車流量來衡量)確定。為了簡化研究的復雜性，選取部分路線進行研究。假定有5位乘客需要拼車，如圖4(其中選取了5個目的地和一個出租車出發(fā)點，用表示)。

其中，主要的道路為黃山路、金寨路、屯溪路、徽州大道、馬鞍山路、巢湖路、蕪湖路、明光路。

利用圖論相關(guān)知識，將選取的地點抽象為頂點(節(jié)點)，將地點之間的路線抽象為邊(鏈接)，給出了合肥市部分路線簡化圖，如圖5。

圖5 合肥市部分路線簡化圖

其中，V= { v1，v2，…，v13}為該路線簡化圖的頂點集，E= {e1，e2，…，e17}為該路線簡化圖的邊集。v1代表出租車出發(fā)點，頂點 v4，v7，v8，v12，v11分別代表目的地 1，2，3，4，5，乘客 i到達目的地 i。根據(jù)實際情況及假定的乘客需求分析，通過式(1)給出表1。

表1 乘客優(yōu)先級量化系數(shù)表

圖6 關(guān)于路線優(yōu)化的層次分析圖

因此，根據(jù)乘客優(yōu)先級的量化系數(shù)μ值得大小，選擇本次合乘乘客是乘客1、乘客2、乘客3和乘客4。

(2)路線簡化圖邊權(quán)重的確定。接下來需要確定每條邊的權(quán)重，構(gòu)造賦權(quán)路線圖模型。先通過建立模糊層次分析［4］模型來確定各個因素對最優(yōu)路線的貢獻比例，再進一步確定各邊的權(quán)重。

模糊層次分析法引入模糊一致矩陣［5］，無需再進行一致性檢驗，同時使用冪法來計算權(quán)向量，可以得到計算精度較高的且與實際情況較吻合的權(quán)向量。以下是具體步驟:

1)確定目標層為最優(yōu)路線，指標層為費用和時間，因素集為路程、交通狀況、紅綠燈的個數(shù)。圖6表示之間的層次關(guān)系。

2)利用0.1 ～0.9 數(shù)量標度［5］，構(gòu)造優(yōu)先關(guān)系矩陣 F=(fij)n×n。

4)利用冪法［6，7］計算權(quán)向量 W。

其中，ω0代表初邊權(quán)重，式(2)中的路程代表的并非實際具體數(shù)據(jù)，而是各邊之間的比例關(guān)系(以最短路程作為基準，分別與其他各邊進行比值)，交通狀況指數(shù)則是根據(jù)車流量的大小，賦予1～9這些數(shù)值得到的。紅綠燈指數(shù)則是各地點之間的紅綠燈個數(shù)比值。

由前面所述，此處還引入了滿意度系數(shù)λ，表示乘客對交通狀況的心里感受，因此在計算最終邊權(quán)值時將λ設(shè)為最終的影響邊權(quán)重的因子，建立如下模型計算ω:

得到圖3中每條邊的權(quán)重如表2:

表2 路線簡化圖的各邊權(quán)重

(3)基于分步Floyd算法的最優(yōu)路線方案。研究的兩點之間的最優(yōu)路線是指在圖5中找兩點之間權(quán)值和最小的那些邊，采用的是Floyd算法［8］求解兩點之間的最小權(quán)值路線。雖然Floyd算法是用來求解兩點之間最短路徑的算法，此處將最短路徑擴展為最小權(quán)和路線，考慮了多種因素對最優(yōu)路線的影響，這也是合理的。

在之前，已經(jīng)確定了乘客的優(yōu)先級，即確定了出租車送往目的地的順序，因此，想利用分步的Floyd算法找到最優(yōu)路線，即首先利用Floyd算法找到頂點v1到v4的最優(yōu)路線，然后再利用同樣的方法找頂點v4到v7的最優(yōu)路線，依次類推，直到找到頂點v8到v12的最優(yōu)路線，其中分步計算的想法是類似于圖論學科中找最短路徑的常用的最鄰近算法［9］。尋找最優(yōu)路線具體過程:

1)頂點v1到v4的最優(yōu)路線:考慮的頂點是v1，…，v5。

① 構(gòu)造權(quán)重矩陣 D1(wij)5×5，其中當(vi，vj)∈E 時，wij就為頂點 vi到 vj的邊權(quán)值，若(vi，vj)?E，wij=∞，即:

③最后，通過反向追蹤法確定頂點v1到v4的最優(yōu)路線，即是:

2)通過同樣的方法，依次得到頂點v4到v7，頂點v7到v8，頂點v8到v12的最優(yōu)路線為:

3 基于最優(yōu)路線的拼車費用分攤問題的解決方法

3.1 拼車費用分攤問題的分析

對于拼車費用的分攤，主要從公平性原則出發(fā)。通過調(diào)查了解到有的地區(qū)拼車費用采用固定的費率分攤，如按人數(shù)定折扣或按路程定折扣，這雖然具有一定的合理性，但還有一些關(guān)鍵因素沒有考慮在內(nèi)，例如在最優(yōu)路線選取的問題上考慮了乘客的優(yōu)先級，對于那些優(yōu)先級高的乘客有必要多收取一些費用(假定每位乘客都是理性人，地位是對等的，若有某位乘客因為自己特殊要求以及時間緊急對其他乘客產(chǎn)生消極的外部性，他需要對自己產(chǎn)生的消極外部性多支付一些費用)。結(jié)合前期的調(diào)查準備，綜合考慮按人數(shù)定折扣和路程遠近兩種方式解決費用分攤問題，由于按人數(shù)定折扣方案在費用分攤計算中是隱形體現(xiàn)的，因為拼車人數(shù)越多(最大不超過出租車最大載客量)，分攤的費用越少，形象上說是折扣越多，因此在計算費用分攤時只考慮路程遠近以及乘客的優(yōu)先級指數(shù)δ，用來表示各乘客的緊急系數(shù)υ與特殊要求度ξ之和的比值。

3.2 費率ri的確定

先引入一些參數(shù)，C為總費用，C0為出租車起步價，L0為起步價路程，r0為正常費率(即超過起步價路程后每公里價格)，Ci為第i位乘客所需支付的費用，li(i=1，2，…，n)為分段的路程，即l1表示出租車出發(fā)點到目的地1的路程，l2表示目的地1到目的地2的路程，以此類推。

拼車費用的分攤即如何將C分割，使每位乘客所支付的費用Ci盡可能是公平的。此問題的關(guān)鍵是找到恰當?shù)谋壤齬i(表示第i位乘客的費率)，使得Ci=ri×C，C=C1+…+Cn(可能存在乘客到達目的地的路程小于L0，則該乘客需支付的費用為C0/n，n為拼車總?cè)藬?shù))。此處所考慮的ri與路程遠近和乘客的優(yōu)先級指數(shù)δ有關(guān)。

前文，在確定乘客優(yōu)先級的量化系數(shù)μ時，考慮了距離因子κ，乘客的緊急系數(shù)υ，乘客提出的特殊要求度ξ，并給出了3者的權(quán)重比值，則以此為依據(jù)考慮路程遠近和乘客優(yōu)先級之間的權(quán)重比，設(shè)定I1，I2，其中I1表示路程遠近對ri的貢獻度，I2表示乘客優(yōu)先級指數(shù)δ對ri的貢獻度，則建立如下模型計算ri:

其中，δi表示第i為乘客的優(yōu)先級指數(shù)，可以利用給出的υ與ω的值，通過數(shù)學上常用的取比例值的方法得到(針對不同的拼車情況，δi的取值是不同的)，公式(1)中l(wèi)j可以不是具體的路程數(shù)據(jù)，只要確定比例關(guān)系即可。

結(jié)合實際研究的問題，n取4，則 C=C0+r0×(l1+… +l4)。并設(shè)定 I1=0.713，I2=0.287，通過計算，最終得到:r1=0.13，r2=0.20，r3=0.30，r4=0.37，于是每位乘客所需支付的費用為

按照這樣的比例分攤費用無疑充分地體現(xiàn)了公平。

4 結(jié)語

“拼車問題”是當今人們比較關(guān)心的一個問題，由于沒有相關(guān)運營方法規(guī)定，在路線與費用收取上處于比較混亂的狀態(tài)。通過建立數(shù)學模型，提出了路線最優(yōu)化與費用分攤的解決方案，具有一定的實際意義，希望在對相關(guān)策略的制定中會有所幫助，對于該問題的進一步研究提供參考。

［1］王羅.出租車共乘問題研究［D］.長沙:長沙理工大學，2008

［2］覃運梅，石琴.出租車合成模式的探討［J］.合肥工業(yè)大學大學學報:自然科學版，2006，29(1):77-79

［3］郭瑞軍，王晚香.基于矩陣迭代法的出租車合乘最短路徑選擇［J］.大連交通大學學報，2011，26(1):29-32

［4］張吉軍.模糊層次分析法(FAHP)［J］.模糊系統(tǒng)與數(shù)學，2000，14(2):86

［5］張燕姑.基于模糊一致矩陣的研究［J］.計算機工程與設(shè)計，2005，26(6):1492-1493

［6］徐萃薇，孫繩武.計算方法引論［M］.北京:高等教育出版社，2007

［7］周鐵，徐樹方，張平文，等.計算方法［M］.北京:清華大學出版社，2006

［8］胡運權(quán)，郭耀煌.運籌學教程［M］.北京:清華大學出版社，1998

［9］SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constrains［J］.Operations Research，1987，35(2):254-265