基于禁忌搜索算法的鐵路客運(yùn)站到發(fā)線運(yùn)用計(jì)劃編制研究

徐晶，李季濤

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

鐵路客運(yùn)站的到發(fā)線運(yùn)用是鐵路行車技術(shù)作業(yè)的重要作業(yè)之一，合理有效的使用到發(fā)線是提高車站通過(guò)能力和車站作業(yè)效率的重要途徑，同時(shí)建立客運(yùn)站到發(fā)線運(yùn)用模型及設(shè)計(jì)相應(yīng)算法是實(shí)現(xiàn)鐵路客運(yùn)站作業(yè)自動(dòng)編制的重要內(nèi)容.基于此，不少專家和學(xué)者對(duì)到發(fā)線的運(yùn)用進(jìn)行了研究.劉杰等以作業(yè)計(jì)劃穩(wěn)定性強(qiáng)和接發(fā)車進(jìn)路條件優(yōu)為目標(biāo)建立多目標(biāo)優(yōu)化模型，運(yùn)用改進(jìn)的帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)對(duì)模型進(jìn)行求解[1].彭其淵等人以列車運(yùn)行晚點(diǎn)和車站作業(yè)秩序影響雙方面最小化為目標(biāo),建立了混合整數(shù)線性規(guī)劃模型.還以列車加權(quán)總晚點(diǎn)時(shí)間與到發(fā)線使用費(fèi)用之和最小為優(yōu)化目標(biāo)建立線性0-1規(guī)劃模型，運(yùn)用分支定界法和模擬退火算法求解[2-3].黃俊生等人構(gòu)建了帶柔性重疊時(shí)間窗編組站的終到列車到發(fā)線應(yīng)用優(yōu)化模型，并用模擬退火算法求解[4].江秀等人建立了滿足到發(fā)線固定使用方案和到發(fā)線均衡使用的多目標(biāo)二次0-1規(guī)劃模型，運(yùn)用LINGO軟件進(jìn)行求解[5].喬瑞軍等人以列車在站內(nèi)走行時(shí)間最短和到發(fā)線均衡運(yùn)用為優(yōu)化目標(biāo)，并運(yùn)用LING軟件求解[6].史峰等人將一端咽喉區(qū)接發(fā)車進(jìn)路排列方案與列車權(quán)重等級(jí)相結(jié)合建立了綜合優(yōu)化模型，運(yùn)用了模擬退火算法求解[7].王保山等人提出了到發(fā)線平均利用率，并以其建立到發(fā)線均衡運(yùn)用模型，運(yùn)用遺傳算法求解模型[8].張?zhí)K波等人將列車占用到發(fā)線的權(quán)值最小、到發(fā)線的均衡運(yùn)用與旅客乘降方便系數(shù)相結(jié)合建立了整數(shù)規(guī)劃模型，并運(yùn)用遺傳算法進(jìn)行求解[9].基于此，本文提出運(yùn)用啟發(fā)式排序規(guī)則和禁忌搜索算法相結(jié)合的優(yōu)化算法來(lái)研究到發(fā)線的運(yùn)用.

1 問(wèn)題描述與分析

在鐵路車站作業(yè)計(jì)劃中，列車對(duì)到發(fā)線的占用不僅和列車性質(zhì)及到發(fā)密集度有關(guān)，還和車站的設(shè)備設(shè)施關(guān)系密切.到發(fā)線運(yùn)用方案的目標(biāo)是保證車站不間斷的接發(fā)旅客列車，避免列車的不必要的等線，保證出發(fā)旅客列車能夠正點(diǎn)發(fā)出，以提高車站的通過(guò)能力.故在實(shí)際作業(yè)中，到發(fā)線的運(yùn)用要滿足以下約束條件，這里假設(shè)客技庫(kù)線容量足夠大.

(1)一列旅客列車在同一時(shí)間片內(nèi)只能占用一條到發(fā)線，一條到發(fā)線在同一時(shí)間片內(nèi)至多被一列旅客列車占用；

(2)同一到發(fā)線的相鄰到發(fā)的兩旅客列車的作業(yè)時(shí)間應(yīng)滿足其最小間隔時(shí)間；

(3)兩列或多列旅客列車之間進(jìn)路存在交叉干擾時(shí)，應(yīng)安排平行進(jìn)路；

(4)到達(dá)旅客列車與到達(dá)旅客列車使用靠近同一個(gè)站臺(tái)的兩條到發(fā)線時(shí)，應(yīng)滿足其最小間隔時(shí)間；

(5)到達(dá)旅客列車和出發(fā)旅客列車使用靠近同一個(gè)站臺(tái)的兩條到發(fā)線時(shí)，應(yīng)滿足其最小間隔時(shí)間；

(6)具備旅客換乘關(guān)系的旅客列車盡量安排?？吭谕徽九_(tái)的到發(fā)線；

(7)接入到發(fā)線的旅客列車應(yīng)滿足接入的到發(fā)線的有效長(zhǎng)約束；

(8)有上水作業(yè)需求的旅客列車必須接到有上水設(shè)備的到發(fā)線；

(9)為了保證旅客進(jìn)出站的安全，通過(guò)列車應(yīng)盡量安排在正線上.

2 模型分析與建立

2.1 模型的建立

將1d或一個(gè)階段計(jì)劃或自定義的一個(gè)時(shí)間段的時(shí)間劃分為B個(gè)列車密集到達(dá)和出發(fā)程度不相同的時(shí)間，即劃分為B個(gè)時(shí)間片，處于同一時(shí)間片的列車在占用到發(fā)線的時(shí)間上存在著交叉干擾，不能使用同一條到發(fā)線[10].定義列車為m，且m∈T{1,2,…,M}，M為旅客列車數(shù)量.定義到發(fā)線為g，且g∈U{1,2,…,G}，其中G為到發(fā)線條數(shù).Wm為列車等級(jí)權(quán)重，規(guī)定列車等級(jí)越高的列車Wm取值越小.Xmg為0-1變量，當(dāng)Xmg=1時(shí)表示列車m占用到發(fā)線g，反之則不占用.將旅客列車占用到發(fā)線的時(shí)間表示如下：

Tm為旅客列車占用到發(fā)線的全部作業(yè)時(shí)間；t1為旅客列車準(zhǔn)備接車進(jìn)路的時(shí)間、信號(hào)開(kāi)放時(shí)間和列車通過(guò)進(jìn)站點(diǎn)距離的時(shí)間；t2為旅客列車出發(fā)時(shí)刻至其完全排空股道并可接入下一旅客列車的作業(yè)時(shí)間；t3為旅客列車在到發(fā)線停留時(shí)間(可根據(jù)旅客列車的出發(fā)時(shí)間-到達(dá)時(shí)間、入庫(kù)時(shí)間-到達(dá)時(shí)間或出發(fā)時(shí)間-出庫(kù)時(shí)間求出)；

則有

Tm=t1+t2+t3

(1)到發(fā)線固定使用方案

該目標(biāo)是在遵循到發(fā)線的固定使用原則上，使車站不間斷接發(fā)旅客列車，以確保車站的正點(diǎn)率.所以該目標(biāo)是達(dá)到使所有旅客列車對(duì)到發(fā)線占用消耗最小，同時(shí)保證了不同等級(jí)和種類列車接入到發(fā)線的優(yōu)先程度.

(1)

(2)均衡運(yùn)用行車技術(shù)設(shè)備即均衡的運(yùn)用到發(fā)線

為了達(dá)到各到發(fā)線空費(fèi)時(shí)間均衡，本文運(yùn)用各條到發(fā)線的占用時(shí)間與到發(fā)線的平均占用時(shí)間之差的平方和最小來(lái)衡量到發(fā)線的均衡運(yùn)用度.

(2)

(3)方便旅客的旅行

對(duì)于鐵路客運(yùn)站來(lái)說(shuō)，其服務(wù)對(duì)象便是旅客，所以提高旅客的服務(wù)質(zhì)量對(duì)于鐵路客運(yùn)部門是極其重要的，所以該目標(biāo)函數(shù)以平均旅客走行距離最短為優(yōu)化目標(biāo)，從而提高旅客服務(wù)質(zhì)量.Nm是第m列旅客列車乘降旅客數(shù)，Dg是第g條到發(fā)線旅客乘降站臺(tái)離基本站臺(tái)的距離.

(3)

2.2 約束條件

(1)一列旅客列車在同一時(shí)間片內(nèi)只能占用一條到發(fā)線

m∈T(1,2,3,…,M)

(4)

(2)一條到發(fā)線在同一時(shí)間片內(nèi)至多被一列旅客列車占用

g∈U(1,2,3,…,G)

(5)

(3)同一到發(fā)線的相鄰兩旅客列車的作業(yè)時(shí)間應(yīng)滿足其最小間隔時(shí)間

(6)

(4)兩列或多列旅客列車之間進(jìn)路存在交叉干擾時(shí)，可安排如下平行進(jìn)路約束

Pmgm′g′≥XmgXm′g′Rmm′

(7)

Rmm′為當(dāng)旅客列車m和旅客列車m′在咽喉區(qū)進(jìn)路占用上存在交叉時(shí)取1，反之取0.Pmgm′g′為當(dāng)旅客列車m和旅客列車m′在咽喉區(qū)進(jìn)路產(chǎn)生交叉干擾并可以為其安排平行進(jìn)路時(shí)取1，反之取0.

(5)到達(dá)旅客列車與到達(dá)旅客列車使用靠近同一個(gè)站臺(tái)的兩條到發(fā)線時(shí)，應(yīng)滿足其最小間隔時(shí)間

(8)

(6)到達(dá)旅客列車和出發(fā)旅客列車使用靠近同一個(gè)站臺(tái)的兩條到發(fā)線時(shí)，應(yīng)滿足其最小間隔時(shí)間

(9)

(7)具備旅客換乘關(guān)系的旅客列車盡量安排?？吭谕徽九_(tái)的到發(fā)線

(?m,m′∈T,g,g′∈U)

(10)

Hgg′為當(dāng)?shù)桨l(fā)線g和g′靠近同一站臺(tái)時(shí)取1，否則取0.Qmm′為當(dāng)旅客列車m和m′具有換乘關(guān)系時(shí)取1，否則取0.

(8)接入到發(fā)線的旅客列車應(yīng)滿足接入的到發(fā)線的有效長(zhǎng)約束

(11)

Lg為到發(fā)線g的有效長(zhǎng)；lm為旅客列車m的長(zhǎng)度.

(9)有上水作業(yè)需求的旅客列車必須接到有上水設(shè)備的到發(fā)線

(12)

Ts為需要上水作業(yè)的旅客列車集合；Us為有上水設(shè)備的到發(fā)線集合；b為有上水需求的列車總數(shù).

(10)為了保證旅客進(jìn)出站的安全，通過(guò)列車應(yīng)盡量安排在正線上

m′∈Vm(1,2,3,…,m)

(13)

Z(g)為客運(yùn)站正線集合；Vm為通過(guò)列車集合.

2.3 多目標(biāo)優(yōu)化模型

(14)

(15)

(16)

(17)

(18)

(19)

Pmgm′g′≥XmgXm′g′Rmm′

(20)

(21)

(22)

(?m,m′∈T,g,g′∈U)

(23)

(24)

(25)

(26)

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

本文建立的鐵路客運(yùn)站到發(fā)線運(yùn)用模型屬于非線性的0～1整數(shù)規(guī)劃模型，直接求解此模型存在著較大的困難，故在結(jié)合到發(fā)線和旅客列車之間的關(guān)系基礎(chǔ)上采用啟發(fā)式排序規(guī)則與禁忌搜索算法相結(jié)合的優(yōu)化算法求解模型.

3.1 啟發(fā)式排序規(guī)則生成初始方案

運(yùn)用禁忌搜索算法求解對(duì)初始解的質(zhì)量要求較高，初始解的質(zhì)量的好壞決定了最終優(yōu)化方案的優(yōu)劣程度.啟發(fā)式排序規(guī)則是根據(jù)車站行車作業(yè)的長(zhǎng)期實(shí)踐經(jīng)驗(yàn)、技術(shù)作業(yè)標(biāo)準(zhǔn)構(gòu)建的一組行車作業(yè)安排優(yōu)先級(jí)的決策規(guī)則.遵循這些規(guī)則，逐一安排每列旅客列車的行車作業(yè)，便可構(gòu)造出一個(gè)確定性的可行解.其決策規(guī)則如下：

(1)旅客列車的到達(dá)時(shí)間或出發(fā)時(shí)間的確定規(guī)則

由列車運(yùn)行圖或車站列車時(shí)刻表確定.

(2)列車進(jìn)路選擇規(guī)則

若兩列或多列旅客列車之間進(jìn)路存在交叉干擾時(shí)，則應(yīng)根據(jù)進(jìn)路的最小占用時(shí)間間隔進(jìn)行安排.

(3)旅客列車股道占用安排規(guī)則

股道和列車的唯一性規(guī)則；若兩列旅客列車使用同一到發(fā)線則其到達(dá)時(shí)間或出發(fā)時(shí)間應(yīng)滿足其最小安全間隔時(shí)間；若到達(dá)列車與到達(dá)列車(出發(fā)列車)使用靠近同一站臺(tái)的到發(fā)線時(shí)則應(yīng)滿足其最小安全時(shí)間間隔；到發(fā)線的長(zhǎng)度應(yīng)滿足旅客列車的長(zhǎng)度；若兩列旅客列車存在換乘關(guān)系則應(yīng)安排在靠近同一站臺(tái)的到發(fā)線；若是通過(guò)列車則應(yīng)安排在正線上.

依據(jù)以上決策規(guī)則生成如下旅客列車占用到發(fā)線的初始方案步驟：

Step1 初始化行車作業(yè)所需的各設(shè)備參數(shù)

列車類型(普速旅客列車、高速旅客列車)，旅客列車的到達(dá)與出發(fā)的時(shí)間，股道和道岔以及它們之間的聯(lián)系，進(jìn)路的最小間隔時(shí)間、同一到發(fā)線使用的最小間隔時(shí)間以及靠近同一站臺(tái)的到發(fā)線使用最小間隔時(shí)間，到發(fā)線及旅客列車的長(zhǎng)度；

Step2 生成普速旅客列車集合和高速旅客列車集合；

Step3 本文對(duì)5∶00～10∶00這一時(shí)間段的旅客列車按小時(shí)進(jìn)行編排.即對(duì)5∶00～6∶00，6∶00～7∶00，7∶00～8∶00，8∶00～9∶00，9∶00～10∶00時(shí)間段的旅客列車進(jìn)行到發(fā)線占用的安排.首先對(duì)5∶00～6∶00這一時(shí)間段的到發(fā)旅客列車進(jìn)行到發(fā)線的分配；

Step4 檢索在高速旅客列車集合中是否存在著在該時(shí)段內(nèi)的旅客列車，若存在則在列車選擇進(jìn)路規(guī)則與股道占用規(guī)則基礎(chǔ)上優(yōu)先安排在靠近站舍側(cè)的到發(fā)線，若沒(méi)有則檢索普速旅客列車在這一時(shí)間段內(nèi)的旅客列車并按時(shí)間、列車進(jìn)路選擇規(guī)則及股道占用規(guī)則對(duì)其進(jìn)行分配；

Step5 對(duì)6∶00～7∶00時(shí)間段內(nèi)旅客列車進(jìn)行到發(fā)線分配，轉(zhuǎn)Step4；

Step6 對(duì)7∶00～8∶00時(shí)間段內(nèi)旅客列車進(jìn)行到發(fā)線分配，轉(zhuǎn)Step4；

Step7 對(duì)8∶00～9∶00時(shí)間段內(nèi)旅客列車進(jìn)行到發(fā)線分配，轉(zhuǎn)Step4；

Step8 對(duì)9∶00～10∶00時(shí)間段內(nèi)旅客列車進(jìn)行到發(fā)線分配，轉(zhuǎn)Step4；

Step9 檢索普速旅客列車集合和高速旅客列車集合，若集合不為空，則轉(zhuǎn)Step3；若集合為空則輸出初始方案.

3.2 禁忌搜索算法

禁忌搜索算法是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化算法中的一個(gè)成功應(yīng)用.它的一個(gè)重要思想是標(biāo)記已得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開(kāi)這些局部最優(yōu)解.[11]它的主要參數(shù)包括鄰域結(jié)構(gòu)、評(píng)價(jià)函數(shù)、禁忌長(zhǎng)度、藐視準(zhǔn)則和終止準(zhǔn)則，下文將具體設(shè)計(jì)這些參數(shù).

(1)編碼方式

本文求解到發(fā)線運(yùn)用最優(yōu)方案的核心問(wèn)題是確定到達(dá)或出發(fā)的每列旅客列車所占用的到發(fā)線，使得最終的優(yōu)化方案能夠滿足列車和到發(fā)線的相關(guān)技術(shù)及理論約束條件.基于禁忌搜索算法的特點(diǎn)，將所研究時(shí)間段以小時(shí)進(jìn)行分段，進(jìn)而將每小時(shí)內(nèi)的旅客列車兩兩進(jìn)行移動(dòng)交換形成解的鄰域，其每小時(shí)段編碼序列如圖1所示.其中每一個(gè)小長(zhǎng)方形代表一條到發(fā)線，以左邊第一個(gè)為靠近站舍側(cè)依次排列，用g表示，m1,m2,…,mn表示旅客列車，這樣的編碼方式為后續(xù)操作奠定基礎(chǔ).

圖1 每小時(shí)段編碼序列

(2)鄰域和候選集結(jié)構(gòu)

通過(guò)移動(dòng)或交換每小時(shí)段的兩旅客列車位置產(chǎn)生鄰域解，在鄰域解中選出部分較優(yōu)的解以構(gòu)成候選集，也可以將所有的鄰域解作為候選集，但由于其搜索范圍大且操作時(shí)間過(guò)長(zhǎng)所以一般不采用.

(3)評(píng)價(jià)函數(shù)的構(gòu)造

評(píng)價(jià)函數(shù)是用于判斷鄰域解的優(yōu)劣性，本文將目標(biāo)函數(shù)作為評(píng)價(jià)函數(shù)，根據(jù)文章的目標(biāo)函數(shù)將評(píng)價(jià)函數(shù)設(shè)定為：

f=αZ1+βZ2+γZ3

(27)

式中,Z1,Z2,Z3是子決策目標(biāo)，α,β,γ是子決策目標(biāo)的權(quán)重系數(shù)且α+β+γ=1，依車站實(shí)際工作經(jīng)驗(yàn)將α設(shè)為0.4，將β,γ設(shè)為0.3.

(4)禁忌表的設(shè)置

(5)選擇策略

當(dāng)新解計(jì)算得到的評(píng)價(jià)函數(shù)的值比原解對(duì)應(yīng)的評(píng)價(jià)函數(shù)值小，則將此新解作為本次迭代的鄰域最好的解.用公式表示如下：

(28)

式中,l為當(dāng)前解，l1為選出的鄰域最優(yōu)解，s(l)為候選解集，f1(s(l))是s(l)的評(píng)價(jià)函數(shù)值.

(6)藐視準(zhǔn)則

為避免最優(yōu)解的丟失，規(guī)定了在找不到鄰域解及迭代一定次數(shù)后特赦禁忌表中的最優(yōu)值作為當(dāng)前解以繼續(xù)迭代搜索.若禁忌表中的某值出現(xiàn)頻率超過(guò)某設(shè)定值時(shí)，則在迭代中若找不到鄰域解時(shí)可將其從禁忌表中解禁作為當(dāng)前解來(lái)繼續(xù)搜索最優(yōu)解.

(7)終止準(zhǔn)則

本文設(shè)置最大迭代數(shù)作為算法的終止條件.

在對(duì)禁忌搜索算法的各參數(shù)分析的基礎(chǔ)上，設(shè)計(jì)的具體算法步驟如下：

Step1 將啟發(fā)式排序規(guī)則生成的初始方案作為本算法的初始解，并賦予禁忌表H=?；

Step2 對(duì)初始解中的旅客列車對(duì)到發(fā)線的占用分解成若干個(gè)小時(shí)段，并以每小時(shí)段中的列車占用到發(fā)線為研究對(duì)象；

Step4 判斷禁忌表H中的對(duì)象是否滿足藐視準(zhǔn)則，若滿足則將此對(duì)象加入到候選集中，再?gòu)暮蜻x集中選出最優(yōu)解作為當(dāng)前解，若不滿足藐視準(zhǔn)則，則在候選集中選出最優(yōu)解作為當(dāng)前解，更新禁忌表H；

Step5 迭代次數(shù)加1，如果迭代次數(shù)為設(shè)定的最大迭代次數(shù)Tmax或解無(wú)法改進(jìn)時(shí)，算法終止，輸出此時(shí)的最優(yōu)方案，否則轉(zhuǎn)Step3.

按此算法分別求出對(duì)研究時(shí)段內(nèi)的若干個(gè)小時(shí)段內(nèi)的旅客列車對(duì)到發(fā)線的占用最優(yōu)方案或較優(yōu)方案，若保證每一小時(shí)段內(nèi)的旅客列車占用為相對(duì)最優(yōu)方案，那么即可得到研究時(shí)段內(nèi)的最優(yōu)方案或較優(yōu)方案.最終的優(yōu)化方案由于是分段求解所得，所以在合并后的解中可能存在相鄰時(shí)間段內(nèi)的旅客列車時(shí)間上的沖突，故再根據(jù)同一到發(fā)線的兩相鄰列車到達(dá)或出發(fā)的最小間隔時(shí)間進(jìn)行調(diào)整，最終得到問(wèn)題的最優(yōu)解.

4 算例分析

某客運(yùn)站站場(chǎng)平面圖如圖2，其中實(shí)線9、8、Ⅶ、5 是接發(fā)上行旅客列車的到發(fā)線，實(shí)線4、3、Ⅱ、1是接發(fā)下行旅客列車的到發(fā)線，黑色實(shí)心圓點(diǎn)表示此處設(shè)有客車上水栓，即9條到發(fā)線均可滿足旅客列車的上水作業(yè).該站共有8個(gè)站臺(tái)，9條到發(fā)線，其中編號(hào)為Ⅱ和Ⅶ的到發(fā)線為正線，編號(hào)為6的到發(fā)線為機(jī)車走行線故不接發(fā)旅客列車作業(yè).規(guī)定使用靠近同一站臺(tái)的兩到達(dá)旅客列車的到達(dá)時(shí)間應(yīng)滿足的最小間隔時(shí)間為10 min、到達(dá)旅客列車與出發(fā)旅客列車使用靠近同一站臺(tái)的到發(fā)線時(shí)應(yīng)滿足的最小間隔時(shí)間為10 min、同一到發(fā)線相鄰兩旅客列車的最小間隔作業(yè)時(shí)間為5 min.

圖2 站場(chǎng)平面圖

本文以該站5∶00～10∶00到發(fā)的29對(duì)旅客列車為研究對(duì)象編制此時(shí)段車站到發(fā)線運(yùn)用計(jì)劃，其到發(fā)時(shí)刻表如表1.將運(yùn)用啟發(fā)式排序規(guī)則得出的5∶00～10∶00時(shí)間段的初始解進(jìn)行分割，分割為5∶00～6∶00，6∶00～7∶00，7∶00～8∶00，8∶00～9∶00，9∶00～10∶00共五個(gè)時(shí)間段的旅客列車對(duì)到發(fā)線的使用情況，再運(yùn)用禁忌搜索算法分別對(duì)每一時(shí)間段進(jìn)行求解，在求解過(guò)程中針對(duì)每一時(shí)段的初始解的實(shí)際情況具體考慮是否將靠近站舍側(cè)的編號(hào)為1的到發(fā)線上的旅客列車固定不動(dòng)，其它旅客列車按算法要求進(jìn)行計(jì)算.其中，禁忌搜索算法參數(shù)的設(shè)置如下：最大迭代次數(shù)Tmax取50，在計(jì)算時(shí)段內(nèi)的旅客列車n分別取7，7，4，7，4，則其禁忌長(zhǎng)度分別取5，5，2，5，2，由于n較小故候選集取整個(gè)鄰域解.

表1 5∶00～10∶00時(shí)間段旅客列車到發(fā)時(shí)刻表

基于以上數(shù)據(jù)，采用MATLAB軟件對(duì)設(shè)計(jì)的禁忌搜索算法進(jìn)行程序的開(kāi)發(fā)，通過(guò)對(duì)各時(shí)段的算例求解并用人機(jī)結(jié)合的方法對(duì)算法求得的方案進(jìn)行調(diào)整，得到最終優(yōu)化方案如圖3所示和圖定方案與原方案的旅客列車對(duì)到發(fā)線的占用的比對(duì)圖，如表2.

圖3 到發(fā)線運(yùn)用計(jì)劃圖

表2 到發(fā)線占用

通過(guò)對(duì)車站作業(yè)的大量觀測(cè)，取準(zhǔn)備接車時(shí)間和旅客列車進(jìn)路走行時(shí)間即t1及準(zhǔn)備發(fā)車時(shí)間和旅客列車尾部越過(guò)到發(fā)線上出站信號(hào)機(jī)的時(shí)間之和即t2均為30 s，得到旅客列車占用到發(fā)線時(shí)間如表3所示.

表3 到發(fā)線占用時(shí)間

基于圖3到發(fā)線運(yùn)用計(jì)劃圖、表2到發(fā)線占用和表3到發(fā)線占用時(shí)間，本文定義到發(fā)線利用率為αq，下述表達(dá)式(16)中Time(t,q)表示Tq中的列車t占用到發(fā)線q的時(shí)間，d表示計(jì)算時(shí)段時(shí)間，取5∶00～10∶00即取300 min.

(16)

經(jīng)計(jì)算得到該站在5∶00～10∶00時(shí)間段內(nèi)到發(fā)線利用率如表4所示.分析表4得出以下幾點(diǎn)，首先到發(fā)線2、3、4、5、7、9的利用率分別提高了15.17%、1.17%、16.17%、5.00%、3.00%、17.16%，尤其是到發(fā)線2、4、9的利用率有了顯著提升.但到發(fā)線1和8分別降低了11.66%和35%，其中到發(fā)線8下降比較明顯，原因?yàn)樵趫D定方案中運(yùn)用到發(fā)線8接發(fā)的旅客列車Z82占用時(shí)間長(zhǎng)達(dá)185 min，優(yōu)化方案將其安排在遠(yuǎn)離站舍側(cè)的到發(fā)線9上，這符合旅客服務(wù)質(zhì)量的要求；其次，與圖定方案相比，優(yōu)化方案的到發(fā)線利用率更加均衡，避免了圖定方案中到發(fā)線8和9的突出性，符合到發(fā)線均衡運(yùn)用的原則；最后，從圖3到發(fā)線運(yùn)用計(jì)劃中可知，到發(fā)線1上接發(fā)的旅客列車均為等級(jí)較高的旅客列車，同時(shí)遠(yuǎn)離站舍側(cè)的編號(hào)為8和9的到發(fā)線接發(fā)的旅客列車相對(duì)較少，也符合對(duì)旅客服務(wù)質(zhì)量的要求.綜上，盡管到發(fā)線1和到發(fā)線8利用率降低了但就總體而言到發(fā)線利用率還是有所提高，同時(shí)各到發(fā)線的利用率更加均衡，并且能夠達(dá)到旅客服務(wù)質(zhì)量的要求，證明了文章算法的有效性.

表4 到發(fā)線利用率

5 結(jié)論

本文建立了滿足約束條件的鐵路客運(yùn)站到發(fā)線運(yùn)用的0～1整數(shù)規(guī)劃模型，提出了將啟發(fā)式排序規(guī)則和禁忌搜索算法相結(jié)合的優(yōu)化算法求解模型，并以某鐵路客運(yùn)站5∶00～10∶00時(shí)間段到發(fā)的旅客列車為例對(duì)模型和算法進(jìn)行驗(yàn)證.驗(yàn)證結(jié)果優(yōu)于車站人員憑工作經(jīng)驗(yàn)編制的到發(fā)線運(yùn)用計(jì)劃，并且編制時(shí)間較短，靈活性較高.但由于算法的分段求解再整合為最終解，故存在相鄰時(shí)間段列車沖突現(xiàn)象，此時(shí)要人為的對(duì)其調(diào)整，所以下一步將對(duì)這一情況進(jìn)行具體分析，以進(jìn)一步提高算法的適用性.