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

徐晶，李季濤

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

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

1 問題描述與分析

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

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

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

(3)兩列或多列旅客列車之間進路存在交叉干擾時，應安排平行進路；

(4)到達旅客列車與到達旅客列車使用靠近同一個站臺的兩條到發(fā)線時，應滿足其最小間隔時間；

(5)到達旅客列車和出發(fā)旅客列車使用靠近同一個站臺的兩條到發(fā)線時，應滿足其最小間隔時間；

(6)具備旅客換乘關系的旅客列車盡量安排停靠在同一站臺的到發(fā)線；

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

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

(9)為了保證旅客進出站的安全，通過列車應盡量安排在正線上.

2 模型分析與建立

2.1 模型的建立

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

Tm為旅客列車占用到發(fā)線的全部作業(yè)時間；t1為旅客列車準備接車進路的時間、信號開放時間和列車通過進站點距離的時間；t2為旅客列車出發(fā)時刻至其完全排空股道并可接入下一旅客列車的作業(yè)時間；t3為旅客列車在到發(fā)線停留時間(可根據旅客列車的出發(fā)時間-到達時間、入庫時間-到達時間或出發(fā)時間-出庫時間求出)；

則有

Tm=t1+t2+t3

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

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

(1)

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

為了達到各到發(fā)線空費時間均衡，本文運用各條到發(fā)線的占用時間與到發(fā)線的平均占用時間之差的平方和最小來衡量到發(fā)線的均衡運用度.

(2)

(3)方便旅客的旅行

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

(3)

2.2 約束條件

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

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

(4)

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

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

(5)

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

(6)

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

Pmgm′g′≥XmgXm′g′Rmm′

(7)

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

(5)到達旅客列車與到達旅客列車使用靠近同一個站臺的兩條到發(fā)線時，應滿足其最小間隔時間

(8)

(6)到達旅客列車和出發(fā)旅客列車使用靠近同一個站臺的兩條到發(fā)線時，應滿足其最小間隔時間

(9)

(7)具備旅客換乘關系的旅客列車盡量安排停靠在同一站臺的到發(fā)線

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

(10)

Hgg′為當到發(fā)線g和g′靠近同一站臺時取1，否則取0.Qmm′為當旅客列車m和m′具有換乘關系時取1，否則取0.

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

(11)

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

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

(12)

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

(10)為了保證旅客進出站的安全，通過列車應盡量安排在正線上

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

(13)

Z(g)為客運站正線集合；Vm為通過列車集合.

2.3 多目標優(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 算法設計

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

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

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

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

由列車運行圖或車站列車時刻表確定.

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

若兩列或多列旅客列車之間進路存在交叉干擾時，則應根據進路的最小占用時間間隔進行安排.

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

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

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

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

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

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

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

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

Step5 對6∶00～7∶00時間段內旅客列車進行到發(fā)線分配，轉Step4；

Step6 對7∶00～8∶00時間段內旅客列車進行到發(fā)線分配，轉Step4；

Step7 對8∶00～9∶00時間段內旅客列車進行到發(fā)線分配，轉Step4；

Step8 對9∶00～10∶00時間段內旅客列車進行到發(fā)線分配，轉Step4；

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

3.2 禁忌搜索算法

禁忌搜索算法是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化算法中的一個成功應用.它的一個重要思想是標記已得到的局部最優(yōu)解，并在進一步的迭代中避開這些局部最優(yōu)解.[11]它的主要參數包括鄰域結構、評價函數、禁忌長度、藐視準則和終止準則，下文將具體設計這些參數.

(1)編碼方式

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

圖1 每小時段編碼序列

(2)鄰域和候選集結構

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

(3)評價函數的構造

評價函數是用于判斷鄰域解的優(yōu)劣性，本文將目標函數作為評價函數，根據文章的目標函數將評價函數設定為：

f=αZ1+βZ2+γZ3

(27)

式中,Z1,Z2,Z3是子決策目標，α,β,γ是子決策目標的權重系數且α+β+γ=1，依車站實際工作經驗將α設為0.4，將β,γ設為0.3.

(4)禁忌表的設置

(5)選擇策略

當新解計算得到的評價函數的值比原解對應的評價函數值小，則將此新解作為本次迭代的鄰域最好的解.用公式表示如下：

(28)

式中,l為當前解，l1為選出的鄰域最優(yōu)解，s(l)為候選解集，f1(s(l))是s(l)的評價函數值.

(6)藐視準則

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

(7)終止準則

本文設置最大迭代數作為算法的終止條件.

在對禁忌搜索算法的各參數分析的基礎上，設計的具體算法步驟如下：

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

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

Step4 判斷禁忌表H中的對象是否滿足藐視準則，若滿足則將此對象加入到候選集中，再從候選集中選出最優(yōu)解作為當前解，若不滿足藐視準則，則在候選集中選出最優(yōu)解作為當前解，更新禁忌表H；

Step5 迭代次數加1，如果迭代次數為設定的最大迭代次數Tmax或解無法改進時，算法終止，輸出此時的最優(yōu)方案，否則轉Step3.

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

4 算例分析

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

圖2 站場平面圖

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

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

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

圖3 到發(fā)線運用計劃圖

表2 到發(fā)線占用

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

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

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

(16)

經計算得到該站在5∶00～10∶00時間段內到發(fā)線利用率如表4所示.分析表4得出以下幾點，首先到發(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下降比較明顯，原因為在圖定方案中運用到發(fā)線8接發(fā)的旅客列車Z82占用時間長達185 min，優(yōu)化方案將其安排在遠離站舍側的到發(fā)線9上，這符合旅客服務質量的要求；其次，與圖定方案相比，優(yōu)化方案的到發(fā)線利用率更加均衡，避免了圖定方案中到發(fā)線8和9的突出性，符合到發(fā)線均衡運用的原則；最后，從圖3到發(fā)線運用計劃中可知，到發(fā)線1上接發(fā)的旅客列車均為等級較高的旅客列車，同時遠離站舍側的編號為8和9的到發(fā)線接發(fā)的旅客列車相對較少，也符合對旅客服務質量的要求.綜上，盡管到發(fā)線1和到發(fā)線8利用率降低了但就總體而言到發(fā)線利用率還是有所提高，同時各到發(fā)線的利用率更加均衡，并且能夠達到旅客服務質量的要求，證明了文章算法的有效性.

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

5 結論

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