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

張小丹

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

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

張小丹

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

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

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

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

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

1 換乘路徑求解問題

1.1 問題描述

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

(1)起始站點(diǎn)和目標(biāo)站點(diǎn)不屬于同一條線路;

(2)從起始站點(diǎn)到目標(biāo)站點(diǎn)的路徑必須是連通的;

(3)從起始站點(diǎn)到目標(biāo)站點(diǎn)的路徑中不允許有回路。

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

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

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

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

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

圖1 某市軌道交通運(yùn)營線路

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

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

2 模型建立與算法設(shè)計(jì)

2.1 建立模型

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

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

2.2 算法設(shè)計(jì)

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

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

3 案例分析

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

邊上的權(quán)值是兩相鄰換乘點(diǎn)之間的時(shí)間和所經(jīng)過的站點(diǎn)數(shù)。上圖中軌道交通線路與換乘站點(diǎn)之間的關(guān)系如下: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)實(shí),所以只抽取一部分線路進(jìn)行研究,可供選擇的路徑有以下8條,最后得出最有路徑為7—8—9—10和7—3—4—5—6—10,雖然第二條路徑所經(jīng)歷的站點(diǎn)數(shù)較多,但是總時(shí)間并不比第一條多很多,兩條路徑相差不多,所以都可以確定為最優(yōu)路徑。經(jīng)驗(yàn)證它與實(shí)際相符,如果我們要從7到10,通常會選擇2號線換乘直接到達(dá)10,或者選擇13號線換乘10號線到達(dá)10,這與我們正常的選擇方法近似,所以認(rèn)為模型是有效的。

4 結(jié)語

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