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

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

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

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

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

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

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

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

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

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

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

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