張小丹

(呼和浩特鐵路局科研所,內(nèi)蒙古呼和浩特 010050)

啟發(fā)式算法在軌道交通換乘路徑求解問題的應用

張小丹

(呼和浩特鐵路局科研所,內(nèi)蒙古呼和浩特 010050)

在城市軌道交通系統(tǒng)中,換乘是一個關鍵環(huán)節(jié)。文章建立了軌道交通簡化模型,初步提出啟發(fā)式算法并引用到軌道交通換乘路徑選擇問題上來,結合某市軌道交通運營線路進行試算,最后證明該算法的有效性。

軌道交通 換乘 啟發(fā)式算法

目前,軌道交通已成為人們出行選擇的常用交通工具,乘客可以方便地從一條線路換乘到另一條線路。因為不同軌道交通線路通常隸屬于不同的運營公司,所以在軌道交通運營過程中存在不同運營商之間分配車資的問題,即“清分問題”。隨著軌道交通建設的迅速擴大和軌道交通網(wǎng)絡的日益復雜,乘客在換乘時往往有多條路徑可以選擇,因此合理求解軌道交通清分問題是十分必要的。

現(xiàn)已有多種清分模型用于求解軌道交通清分問題,如理性情況清分模型、人工分賬清分模型、最短路徑清分模型和K條最佳路徑清分模型。前三種清分模型存在明顯的缺陷,因此一般采用K條最佳路徑模型來求解 。這些清分模型的算法主要是對一些經(jīng)典算法(如Floyd算法,Dijkstra算法等)的改進。目前,啟發(fā)式算法已被成功應用到控制、規(guī)劃、設計等各個領域用來求解實際問題 ,并展現(xiàn)出其廣泛的應用前景。對于城市軌道交通網(wǎng)絡中多條備選路徑的選擇算法,目前國內(nèi)外已有一定研究。本文將啟發(fā)式算法應用到軌道交通換乘路徑的求解過程中,提出一個求解軌道交通K條最佳換乘路徑的啟發(fā)式算法。

1 換乘路徑求解問題

1.1 問題描述

軌道交通換乘路徑求解問題描述為:已知乘客在不同軌道交通線路中乘車的起始站點和目標站點,求乘客從起始站點到目標站點的乘車路徑。其中換乘路徑需滿足以下條件:

(1)起始站點和目標站點不屬于同一條線路;

(2)從起始站點到目標站點的路徑必須是連通的;

(3)從起始站點到目標站點的路徑中不允許有回路。

實際的軌道交通路網(wǎng)規(guī)模比較復雜,我們在求解軌道交通的換乘路徑時需對其進行簡化。

1.2 簡化的軌道交通路網(wǎng)

簡化后的軌道交通路網(wǎng)用有權無向圖G=(V,E,C)來描述,其中:

(1)V是軌道交通路網(wǎng)中線路的關鍵站點的集合。用一組從l開始的連續(xù)自然數(shù)逐條對軌道交通線路中的不同關鍵站點進行編號,每個車站擁有唯一的編號。因此,V是由一組連續(xù)的自然數(shù)組成的集合。

(2)E是圖中邊的集合,邊(i,j)表示關鍵站點i和j之間存在軌道交通線路。

圖1 某市軌道交通運營線路

(3)權值矩陣C=[Cij]。Cij表示邊(i,j)上的權值,即從車站i到車站j之間所經(jīng)過的距離以及車站個數(shù)。

對軌道交通網(wǎng)的簡化是為建立模型和提出算法服務的,如果不進行簡化,對于以后的計算會非常麻煩,為了簡便起見,我們對它進行簡化。

2 模型建立與算法設計

2.1 建立模型

軌道交通網(wǎng)絡可以抽象為有向賦權圖的形式:

其中G為軌道交通網(wǎng)絡的有向賦權圖:V為軌道交通網(wǎng)絡中所有站點的集合:E為連接相鄰兩個軌道交通站點之間路段(邊)的集合;R為經(jīng)過路段e的軌道交通線路集合;W為邊的非負權值(距離)。為了保證軌道交通網(wǎng)絡的連通性,可以根據(jù)一定原則將相鄰軌道交通站點抽象為圖中的同一節(jié)點。

2.2 算法設計

對于上述換乘路徑選擇模型,可以用Dijkstra算法進行求解。由于換乘所帶來的時間損失是產(chǎn)生在軌道交通網(wǎng)絡中兩條線路相交的站點上的,而Dijkstra算法不能直接用于節(jié)點帶權圖的路徑搜索。此外,需要結合Dijkstra算法的路徑搜索過程,將發(fā)生在節(jié)點上的時間損失轉移到相應的路段阻抗上。以下是軌道交通網(wǎng)絡單路徑算法的具體描述:

step0:初始化,定義擬搜索路徑的起點為r,終點為S;d(i)為起點r到節(jié)點i的權值,w(i,j)為連接i、j路段的權值;定義已標記節(jié)點的集合為P,未標記節(jié)點的集合為T,R(i,j)為連接i、j的路段上的軌道交通線路集合,Re為當前使用的軌道交通線路集合。step1:對所有的節(jié)點i,如果i≠r,則d(i)=∞,將i加入未標記節(jié)點集合T;否則d(i)=0,將i加入已標記節(jié)點集合P。step 2:檢驗從所有已標記的點i到與其直接連接的未標記的點j的權重,令,其中,為路段距離,φ為換乘影響因子,δ為換乘開關變量,v為軌道交通車輛平均運營速度,t為平均換乘時間;如果i=r,令;否則如果空集,令;否則令,δ=0。step3:選取下一個點,從集合T中選取d（）j中最小的一個i值,對應點i被選為最短路徑中的一點,將i加人集合P。step4:如果所有節(jié)點均已被標記,則轉入step5;否則,轉入step2。step5:算法結束,通過最優(yōu)路徑上路段的反向查找統(tǒng)計出最優(yōu)路徑距離或時間值、所使用軌道交通線路組合、換乘站點位置、換乘次數(shù)、經(jīng)過站點數(shù)等信息。

3 案例分析

在實際的軌道交通路網(wǎng)模型中,關鍵站點之間可能存在多條路徑,其邊上的權值是經(jīng)過相鄰換乘站點之間的時間和平均站點數(shù)。圖l是簡化后的某市軌道交通運營線路。

邊上的權值是兩相鄰換乘點之間的時間和所經(jīng)過的站點數(shù)。上圖中軌道交通線路與換乘站點之間的關系如下:1號線:11-12-13-14-15;2號線:7-8-9-14-15;4號線:2-7-12-16;5號線:1-5-8-12-17;8號線:4-18;10號線:2-3-4-5-6-10-15;13號線:7-3-1-6-9。

本文主要研究從7到10的換乘路徑選擇,由于從7到10的路徑有很多種,一一列出不太現(xiàn)實,所以只抽取一部分線路進行研究,可供選擇的路徑有以下8條,最后得出最有路徑為7—8—9—10和7—3—4—5—6—10,雖然第二條路徑所經(jīng)歷的站點數(shù)較多,但是總時間并不比第一條多很多,兩條路徑相差不多,所以都可以確定為最優(yōu)路徑。經(jīng)驗證它與實際相符,如果我們要從7到10,通常會選擇2號線換乘直接到達10,或者選擇13號線換乘10號線到達10,這與我們正常的選擇方法近似,所以認為模型是有效的。

4 結語

隨著我國軌道交通的發(fā)展,換乘問題已經(jīng)成為影響軌道交通建設、運營的一個重要因素。由于人們出行的需要,要為各自的出行目的選擇最優(yōu)的出行路徑,現(xiàn)在大部分人都會傾向于選擇乘坐軌道交通,考慮時間、距離、換乘次數(shù)等因素,換乘次數(shù)太多,以本人就會無法接受,會傾向于換乘次數(shù)較少的路徑。鑒于此,本文提出了一個關于選擇軌道交通換乘路徑的算法,也就是通過建立簡單模型而歸納的啟發(fā)式算法,這種算法以前曾經(jīng)也有人提過,但是本文把它應用在軌道交通換乘路徑選擇上來,并驗證了它的可行性。