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

2011-06-11 03:34:54郭瑞軍王晚香

大連交通大學學報 2011年4期

郭瑞軍，王晚香

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

0 引言

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

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

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

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

1 矩陣迭代法

1.1 最短路徑算法

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

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

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

1.2 矩陣迭代法的算法步驟

構造距離矩陣(以距離為權的權矩陣)，矩陣給出了節點間只經過一步(一條邊)到達某一點的距離，如圖1所示.對距離矩陣進行迭代運算，得到經過兩步到達某一點的最短距離.

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

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

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

同樣經過三步、四步到達某一節點的最短距離為:

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

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

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

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

圖2 道路網絡實例

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

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

經過第一次迭代運算后，得到兩步到達任意點的最短距離，如

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

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

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

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

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

(4)找出最短路徑

通過反向追蹤法找最短路徑.首先從最短路徑的起點開始，根據起點到各節點的最短路權來搜索最短路徑的每個節點直到路網的終點.

設r為起點，s為終點

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