郭瑞軍，王晚香

(大連交通大學(xué) 交通運輸工程學(xué)院，遼寧 大連 116028)

0 引言

城市公共交通是由不同運量的軌道交通、公交汽車及出租車組成.出租車因為其方便、快捷、靈活、舒適和可以滿足人們?nèi)找尕S富的出行需要等特點，成為公共交通必不可少的組成部分.

自上世紀(jì)70年代，許多國家采取了對出租車市場經(jīng)濟管制的寬松政策，如澳大利亞、瑞典、瑞士、英國和美國等，解除或者放寬對經(jīng)營者服務(wù)的形式、區(qū)域以及營運線路、車輛等要求［1］.出租車合乘的形式也逐漸出現(xiàn)，“合乘”也稱“拼客”、“拼車”，坐幾個人可以由司機來決定，只要乘客去往同一方向，司機可以向每個客人收取獨自乘車應(yīng)收取的費用.目前在我國出租車“合乘制”還沒有相關(guān)部門的嚴(yán)格定義，本文暫規(guī)定兩個或兩個以上互不相識的乘客在同一地點同時乘坐一輛出租車去往相同或相近的目的地，這種乘坐出租車的方式叫做出租車合乘.

合乘方式改變了傳統(tǒng)的出租車一次運營的單一目的地形式，既充分利用了道路資源又減少了出租車的空駛，為提高我國大城市出租車運輸效率、改變我國大城市出租車運營現(xiàn)狀、解決城市交通擁擠和汽車空駛造成的環(huán)境污染問題提出了一種解決方案.

隨著出租車合乘形式的日益增多，合乘方式運營的規(guī)范化，乘車費用的計算以及對乘客和駕駛員權(quán)益的保障等問題均須解決.盧川等人對合乘的類型劃分、合乘信息的發(fā)布與反饋、合乘車輛數(shù)的確定以及出租車準(zhǔn)點到達(dá)的技術(shù)保障等問題進行了相關(guān)探討［2］;覃運梅等人提出了考慮出租車司機和乘客利益雙贏的數(shù)學(xué)模型，并利用Floyd方法求出最短路以確定行駛路線，計算乘車費用［3］.鄒四發(fā)等人根據(jù)道路交通網(wǎng)絡(luò)模型計算出租車合乘時的最短路徑，并分析了城市道路中的實際問題對最短路徑網(wǎng)絡(luò)的影響等［4-5］.論文針對出租車合乘的線路選擇，運用矩陣迭代法來求解道路交通網(wǎng)絡(luò)中的最短路徑.

1 矩陣迭代法

1.1 最短路徑算法

最短路徑算法是交通流分配中最基本的算法，幾乎所有的交通流分配方法都將它作為一個基本子過程反復(fù)使用.最短路徑算法的設(shè)計問題是圖論、運籌學(xué)和交通規(guī)劃領(lǐng)域的學(xué)者們廣為關(guān)注的問題，因此設(shè)計出了多種方法［6］.所謂的最短路徑問題，就是在一個網(wǎng)絡(luò)中，相鄰節(jié)點間的線路長度是已知的，要從某一起點到某一終點之間，找出一條路線長度最短的通路.

最短路問題的分析分為兩類:①起點到終點的最短路問題;②任意點之間的最短路問題.

由于本文主要解決出租車從起點到兩個終點的最短路徑，同時還要求終點間的最短路徑，所以需分析任意點間的最短路問題.本文利用矩陣迭代法［7］來求解最短路徑.

1.2 矩陣迭代法的算法步驟

構(gòu)造距離矩陣(以距離為權(quán)的權(quán)矩陣)，矩陣給出了節(jié)點間只經(jīng)過一步(一條邊)到達(dá)某一點的距離，如圖1所示.對距離矩陣進行迭代運算，得到經(jīng)過兩步到達(dá)某一點的最短距離.

因此，研究出租車的最短路徑問題時，需要知道各個出行節(jié)點之間的最短路線.可以利用距離矩陣求解最短路的方法.

首先需構(gòu)造一個距離矩陣D=［dij］，如圖1中的距離矩陣D為

這個矩陣給出了只經(jīng)過一步就能到達(dá)某點的最短距離，若想知道兩步到達(dá)某一點的最短距離，可對局陣進行如下計算:

同樣經(jīng)過三步、四步到達(dá)某一節(jié)點的最短距離為:

這時，D(4)=D(3)為最短距離矩陣，通過矩陣可得出最短距離.

最后通過反向追蹤來確定相應(yīng)的最短路線.在研究兩位乘客同時乘一輛出租車去不同地點時，應(yīng)先考慮將其中一位乘客送達(dá)目的地后再送另一位乘客.可以先利用矩陣迭代法找出到達(dá)第一個目的地的最短路徑，然后再用同樣方法找出從第一個目的地到終點的最短路徑，從而使得總的路線最短.

2 利用矩陣迭代法求出租車合乘的最短路徑

出租車合乘路線選擇模型中，合乘的乘客必須是在合乘站點上車去往同一方向的兩個不同目的地，且目的地之間距離相近.在獲得兩名乘客的目的地后，出租車司機可以按照道路交通網(wǎng)絡(luò)模型選擇最短路徑的走法并且在行駛過程中不再搭載其它乘客.

圖2 道路網(wǎng)絡(luò)實例

道路網(wǎng)絡(luò)如圖2所示，如果出租車司機要將兩位乘客A和B分別送到各自的地第6點和第8點，則首先要找出從出發(fā)點1到目的地6的最短距離a、出發(fā)點1到目的地8的最短距離b和目的地6和8之間的最短距離c.然后用最短距離a和最短距離b中的最小值與最短距離c相加就得到出租車將兩位乘客送達(dá)兩個目的地所需最短距離.最后，通過反推法找出出發(fā)點到兩個目的地的最短路徑.

(1)根據(jù)圖2所示得出距離矩陣為:

經(jīng)過第一次迭代運算后，得到兩步到達(dá)任意點的最短距離，如

同理，可以根據(jù)計算求出其他元素，得到D(2)距離矩陣.

(2)根據(jù)距離矩陣D(2)計算D(3)

然后得出距離矩陣D(3)，同理，可計算D(4)，D(5)，… ，D(n).

(3)經(jīng)過不斷迭代計算直到得出 D(8)=D(9)，最終的最短距離矩陣為:

因此，可以由上述距離矩陣查出網(wǎng)絡(luò)圖中任意兩點之間的最短距離.例如:出發(fā)點1到目的地6的最短距離a=4、出發(fā)點1到目的地8的最短距離b=5和目的地6和8之間的最短距離c=3.由于最短距離a和最短距離b中的最小值與最短距離c相加就得到出租車將兩位乘客送達(dá)兩個目的地所需最短距離，所以從起點分別到兩個終點的最短距離為4+3=7.

(4)找出最短路徑

通過反向追蹤法找最短路徑.首先從最短路徑的起點開始，根據(jù)起點到各節(jié)點的最短路權(quán)來搜索最短路徑的每個節(jié)點直到路網(wǎng)的終點.

設(shè)r為起點，s為終點

①從起點r開始，尋找與r相鄰的節(jié)點i滿足

其中，dri為 r到 i的距離;Lmin(i，s)為 i到 s的最短路權(quán);Lmin(r，s)為r到s的最短路權(quán).

②再找到 i到相鄰點 j，滿足 dij+Lmin(j，s)=Lmin(i，s)

如上例所示，從起點1開始到6的最短路徑為1－4－5－6;從目的地6開始到8的最短路徑為6－5－8.

由此可知，從起點1開始將兩位不同的乘客送到兩個目的地6和8時，可以走的最短路徑是1－4－5－6－5－8.

3 結(jié)論

出租車運營行業(yè)通過發(fā)展合乘制，可以降低出租車負(fù)面外部效應(yīng)，減少了城市環(huán)境污染和噪聲污染，降低了城市交通阻塞和交通事故發(fā)生率，使得人、車、路得到有效的利用，使出租車營運符合可持續(xù)發(fā)展的交通要求.

本文利用了運籌學(xué)中最短路徑的矩陣迭代法建立交通網(wǎng)絡(luò)模型，從理論上解決出租車在合乘時的路線選擇問題.今后研究的內(nèi)容應(yīng)集中在相關(guān)制度的制定上，以保證出租車合乘的安全、規(guī)范運營.

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

［2］盧川，吳群.城市居民出行合乘出租車問題的研究［J］.道路交通與安全，2007，7(5):52-55.

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

［4］鄒旭東，鄭四發(fā).具有交通限制約束的道路網(wǎng)絡(luò)最優(yōu)路徑算法［J］.公路交通科技，2002，19(4):82-84.

［5］周培德.交通道路網(wǎng)中任意兩點之間最短路徑的快速算法［J］.計算機科學(xué)與工程，2002，24(4):35-37.

［6］王煒.道路交通工程系統(tǒng)分析方法［M］.北京:人民交通出版社，2001.

［7］運籌學(xué)教材組.運籌學(xué)(修訂版)［M］.北京:清華大學(xué)出版社，1990.