基于矩陣迭代法的出租車合乘最短路徑選擇

郭瑞軍，王晚香

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

0 引言

城市公共交通是由不同運(yùn)量的軌道交通、公交汽車及出租車組成.出租車因?yàn)槠浞奖恪⒖旖荨㈧`活、舒適和可以滿足人們?nèi)找尕S富的出行需要等特點(diǎn)，成為公共交通必不可少的組成部分.

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

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

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

1 矩陣迭代法

1.1 最短路徑算法

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

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

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

1.2 矩陣迭代法的算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)找出最短路徑

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

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

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

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

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

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

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