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

張小丹

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

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

張小丹

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

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

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

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

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

1 換乘路徑求解問(wèn)題

1.1 問(wèn)題描述

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

(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ù)雜,我們?cè)谇蠼廛壍澜煌ǖ膿Q乘路徑時(shí)需對(duì)其進(jìn)行簡(jiǎn)化。

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

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

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

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

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

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

對(duì)軌道交通網(wǎng)的簡(jiǎn)化是為建立模型和提出算法服務(wù)的,如果不進(jìn)行簡(jiǎn)化,對(duì)于以后的計(jì)算會(huì)非常麻煩,為了簡(jiǎn)便起見(jiàn),我們對(duì)它進(jìn)行簡(jiǎ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)過(guò)路段e的軌道交通線路集合;W為邊的非負(fù)權(quán)值(距離)。為了保證軌道交通網(wǎng)絡(luò)的連通性,可以根據(jù)一定原則將相鄰軌道交通站點(diǎn)抽象為圖中的同一節(jié)點(diǎn)。

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

對(duì)于上述換乘路徑選擇模型,可以用Dijkstra算法進(jìn)行求解。由于換乘所帶來(lái)的時(shí)間損失是產(chǎn)生在軌道交通網(wǎng)絡(luò)中兩條線路相交的站點(diǎn)上的,而Dijkstra算法不能直接用于節(jié)點(diǎn)帶權(quán)圖的路徑搜索。此外,需要結(jié)合Dijkstra算法的路徑搜索過(guò)程,將發(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(mén),R(i,j)為連接i、j的路段上的軌道交通線路集合,Re為當(dāng)前使用的軌道交通線路集合。step1:對(duì)所有的節(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)重,令,其中,為路段距離,φ為換乘影響因子,δ為換乘開(kāi)關(guān)變量,v為軌道交通車(chē)輛平均運(yùn)營(yíng)速度,t為平均換乘時(shí)間;如果i=r,令;否則如果空集,令;否則令,δ=0。step3:選取下一個(gè)點(diǎn),從集合T中選取d（）j中最小的一個(gè)i值,對(duì)應(yīng)點(diǎn)i被選為最短路徑中的一點(diǎn),將i加人集合P。step4:如果所有節(jié)點(diǎn)均已被標(biāo)記,則轉(zhuǎn)入step5;否則,轉(zhuǎn)入step2。step5:算法結(jié)束,通過(guò)最優(yōu)路徑上路段的反向查找統(tǒng)計(jì)出最優(yōu)路徑距離或時(shí)間值、所使用軌道交通線路組合、換乘站點(diǎn)位置、換乘次數(shù)、經(jīng)過(guò)站點(diǎn)數(shù)等信息。

3 案例分析

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

邊上的權(quán)值是兩相鄰換乘點(diǎn)之間的時(shí)間和所經(jīng)過(guò)的站點(diǎn)數(shù)。上圖中軌道交通線路與換乘站點(diǎn)之間的關(guān)系如下:1號(hào)線:11-12-13-14-15;2號(hào)線:7-8-9-14-15;4號(hào)線:2-7-12-16;5號(hào)線:1-5-8-12-17;8號(hào)線:4-18;10號(hào)線:2-3-4-5-6-10-15;13號(hào)線: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,通常會(huì)選擇2號(hào)線換乘直接到達(dá)10,或者選擇13號(hào)線換乘10號(hào)線到達(dá)10,這與我們正常的選擇方法近似,所以認(rèn)為模型是有效的。

4 結(jié)語(yǔ)

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