鐵路技術(shù)站作業(yè)計劃優(yōu)化編制的模型與算法研究.pdf

1、技術(shù)站是鐵路貨物運輸網(wǎng)絡(luò)中的1類關(guān)鍵的節(jié)點，它的作業(yè)效率直接影響著整個鐵路貨物運輸?shù)目煽啃院头?wù)水平。技術(shù)站的日常運輸工作由編制各種類型的作業(yè)計劃來組織和調(diào)度，本文利用現(xiàn)代數(shù)學(xué)規(guī)劃理論與方法探討優(yōu)化編制鐵路技術(shù)站作業(yè)計劃理論體系中的幾個關(guān)鍵的科學(xué)問題，包括配流問題、進路調(diào)度問題和編組調(diào)車問題，主要的研究工作如下:
　　第2章探討了配備有1臺解體調(diào)機和1臺編組調(diào)機的區(qū)段站的配流問題，該問題在于確定各列出發(fā)列車的編組內(nèi)容及其車流來源，

2、并調(diào)度各臺解體和編組調(diào)機的任務(wù)，以使得各列出發(fā)列車滿足滿軸、正點和不違編的編組要求，且衡量配流效率的車輛在站總停留時間最小。本章首先借助于單機器調(diào)度問題的基于時刻索引變量的經(jīng)典模型將該問題構(gòu)建為1個囊括所有決策任務(wù)的混合整數(shù)線性規(guī)劃模型，然后利用構(gòu)建的模型的結(jié)構(gòu)和探討問題的特點提出了3個有效的求解算法，包括1個拉格朗日松弛算法、1個啟發(fā)式算法和1個基于整數(shù)編碼的遺傳算法。以1個來源于實際的數(shù)值算例來測試了所提出方法的效果和效率，測試結(jié)果

3、顯示了所設(shè)計的求解方法都能快速地將實際問題求解到最優(yōu)或近似最優(yōu)，且它們的計算結(jié)果明顯地優(yōu)于由調(diào)度員在現(xiàn)場的實時決策環(huán)境中使用的基于先到先服務(wù)規(guī)則的經(jīng)驗方法找到的結(jié)果。
　　第3章探討了分別為到達列車的解體作業(yè)和出發(fā)列車的編組作業(yè)配備多臺解體調(diào)機和多臺編組調(diào)機的單向編組站的配流問題，該問題研究的是確定各列出發(fā)列車的編組內(nèi)容及其車流來源，指派并調(diào)度各臺解體和編組調(diào)機的任務(wù)，以使得各列出發(fā)列車滿足滿軸、正點和不違編的要求，各臺調(diào)機任務(wù)不

4、沖突。利用并行機調(diào)度問題的基于時刻索引變量的模型來建模調(diào)機的指派和調(diào)度，本章首先構(gòu)建了該問題的1個以車輛在站總停留時間最小為目標(biāo)的混合整數(shù)線性規(guī)劃模型，該模型使用1個連接約束將列車組成問題和解編排序問題納入同一個優(yōu)化體系，然后根據(jù)問題的結(jié)構(gòu)和特點設(shè)計了1個精確算法和2個啟發(fā)式算法，其中，精確算法為CPLEX精確求解所構(gòu)建的優(yōu)化模型的求解方法，啟發(fā)式算法包括1個拉格朗日松弛算法和1個有偏隨機鍵遺傳算法。1個切實且大型的數(shù)值案例被用來測試了

5、所提出的求解方法的效果和效率，測試結(jié)果顯示了所提出的精確算法和有偏隨機鍵遺傳算法都能在限制的時間內(nèi)獲得實際問題的最優(yōu)誤差不高于1％的近似最優(yōu)解，且由所提出的求解方法找到的解都不差于由現(xiàn)場的經(jīng)驗方法找到的解。
　　第4章探討了具有兩個改編系統(tǒng)且系統(tǒng)間存在車輛交換的雙向編組站的配流問題，該問題在于確定各列出發(fā)列車和交換列車的編組內(nèi)容及其車流來源，指派并調(diào)度各臺解體和編組調(diào)機的任務(wù)，以使得各列出發(fā)列車符合開行規(guī)定，各列交換列車滿足編組要

6、求，且各臺調(diào)機的任務(wù)不沖突。本章將該問題構(gòu)建為1個以車輛在站總停留時間最小為目標(biāo)且包含所有決策的混合整數(shù)線性規(guī)劃模型，其中，有關(guān)調(diào)機運用的子問題采用并行機調(diào)度問題的基于時刻索引的經(jīng)典模型進行建模。利用問題易被分解的特性，本章開發(fā)了2個有效的近似算法，包括1個使用所構(gòu)建的優(yōu)化模型的拉格朗日松弛算法和1個不使用所構(gòu)建的優(yōu)化模型的有偏隨機鍵遺傳算法。為了驗證所提出方法對于實際問題的效果和效率，計算測試采用了1個切實且大型的數(shù)值案例。計算結(jié)果顯

7、示了所提出的有偏隨機鍵遺傳算法能夠在不到100s內(nèi)的時間內(nèi)獲得實際問題的接近最優(yōu)的解，其最優(yōu)誤差接近1％，拉格朗日松弛算法也能在規(guī)定的計算時間末找到最優(yōu)誤差不高于3％的滿意解，更為重要的是，它們的解明顯地優(yōu)于調(diào)度員采用的人工方法確定的解。
　　第5章探討了具有多類型的作業(yè)且作業(yè)間存在復(fù)雜約束的技術(shù)站進路調(diào)度問題，該問題在于為各項行車和調(diào)車作業(yè)同時指派并調(diào)度進路，以使得所有作業(yè)在時間和空間上都無沖突，且定義的作業(yè)間的一致性約束能得到

8、滿足。本章引入車間調(diào)度問題中的工作和活動的概念來描述調(diào)度作業(yè)，并定義可囊括所有的路徑選項和有限的時刻選項的進路模式的概念來表示決策變量，進而將原本包含多項決策任務(wù)的進路調(diào)度問題轉(zhuǎn)換為1個只需指派提前生成的進路模式給活動的約束指派問題。本章將所定義的約束指派問題構(gòu)建為1個最小化總晚點和走行時間，且滿足唯一性約束、一致性約束和相容性約束的0-1線性規(guī)劃模型，在建模時間一致性約束和道岔相容性約束時，基于圖論的極大關(guān)聯(lián)技術(shù)被用來代替?zhèn)鹘y(tǒng)的兩兩關(guān)

9、聯(lián)技術(shù)，以加強生成約束的定界質(zhì)量。本章還討論了如何拓展標(biāo)準(zhǔn)約束指派模型，以使得它能滿足更多的運營要求，且從1個單一的路徑模型轉(zhuǎn)換為1個復(fù)合的路徑和調(diào)度模型，對于標(biāo)準(zhǔn)模型的不可行問題，提出了1個迭代算法通過求解有限個輔助模型來構(gòu)造可獲得可行解的候選進路模式集。最后，1個真實案例的計算結(jié)果顯示了相比于兩兩關(guān)聯(lián)技術(shù)，極大關(guān)聯(lián)技術(shù)可極大地減少生成的約束數(shù)，且所提出的標(biāo)準(zhǔn)模型使用的動態(tài)列車-站線-指派策略在求解質(zhì)量上優(yōu)于車站調(diào)度員的經(jīng)驗方法使用的

10、靜態(tài)列車-站線-指派策略。
　　第6章探討了產(chǎn)生于技術(shù)站實時調(diào)度中的調(diào)車線受限的編組調(diào)車問題。給定待編車列和可使用調(diào)車線集合，該問題在于確定調(diào)車作業(yè)次數(shù)以及待編車列中的各個車輛在各次調(diào)車作業(yè)中的調(diào)動路徑，以使得在不違背調(diào)車線的數(shù)量和能力約束的情況下，各列編成車列都能被實現(xiàn)為站順的順序，并需要最少的連掛鉤數(shù)、調(diào)動車數(shù)、占用調(diào)車線數(shù)和溜放鉤數(shù)。本章首先考慮了將1列待編車列編順為1列編成車列的簡單編組調(diào)車問題，開發(fā)了1類新的使用0-1矩

11、陣編碼編組調(diào)車方案的位串法，通過定義不同的調(diào)車線連掛原則，分別提出了1個連掛全部調(diào)車線的全線位串法和1個單獨預(yù)留1條調(diào)車線給編成車列的留線位串法，1個包含迭代優(yōu)化和局部搜索進程的兩階段迭代搜索算法被開發(fā)來實施這兩個位串法，其中，第一階段通過求解一系列的0-1線性規(guī)劃模型來尋找需要的0-1矩陣，該矩陣再由第二階段定義的搜索規(guī)則進行局部優(yōu)化，最終獲得的編組調(diào)車方案可按字典序優(yōu)化擬定的連掛鉤數(shù)、調(diào)動車數(shù)、占用調(diào)車線數(shù)和溜放鉤數(shù)。本章還將拓展的