計算機(jī)編制列車運(yùn)行圖的理論與方法

1、主講：彭其淵主講：彭其淵 教授教授/博導(dǎo)博導(dǎo)E-mail:qiyuan- 第一部分 列車運(yùn)行圖的理論與方法第一節(jié)第一節(jié) 列車運(yùn)行圖的作用列車運(yùn)行圖的作用 列車運(yùn)行圖列車運(yùn)行圖是是運(yùn)用坐標(biāo)原理表示列車運(yùn)行的一種圖解方運(yùn)用坐標(biāo)原理表示列車運(yùn)行的一種圖解方式。列車在任一時間的運(yùn)行位置都有唯一的點(diǎn)與之相對應(yīng)。式。列車在任一時間的運(yùn)行位置都有唯一的點(diǎn)與之相對應(yīng)。列車運(yùn)行圖是列車運(yùn)行的工作計劃，它決定著列車占用各區(qū)列車運(yùn)行圖是列車運(yùn)行的工作計劃，它決定著列車占用各區(qū)間的順序、列車在車站到達(dá)和出發(fā)（或通過）的時刻，列車間的順序、列車在車站到達(dá)和出發(fā)（或通過）的時刻，列車在各區(qū)間的運(yùn)行時分，列車在車站的停車時

2、分等。通過列車在各區(qū)間的運(yùn)行時分，列車在車站的停車時分等。通過列車運(yùn)行圖，可以把整個鐵路網(wǎng)的活動聯(lián)系成一個統(tǒng)一的整體，運(yùn)行圖，可以把整個鐵路網(wǎng)的活動聯(lián)系成一個統(tǒng)一的整體，把車、機(jī)、工、電、輛等所有與行車有關(guān)的單位組織起來，把車、機(jī)、工、電、輛等所有與行車有關(guān)的單位組織起來，嚴(yán)格地按照一定程序，有條不紊地進(jìn)行工作。因此，列車運(yùn)嚴(yán)格地按照一定程序，有條不紊地進(jìn)行工作。因此，列車運(yùn)行圖是鐵路運(yùn)輸工作的一個行圖是鐵路運(yùn)輸工作的一個綜合性計劃綜合性計劃。 第二節(jié)第二節(jié) 傳統(tǒng)手工編圖存在的主要問題傳統(tǒng)手工編圖存在的主要問題 編圖問題涉及面廣、制約因素復(fù)雜、技術(shù)難度大，因此編圖問題涉及面廣、制約因素復(fù)雜、技

3、術(shù)難度大，因此在人工編圖的方式下，編圖理論和先進(jìn)技術(shù)手段的應(yīng)用受到在人工編圖的方式下，編圖理論和先進(jìn)技術(shù)手段的應(yīng)用受到了極大的限制，編圖的速度和質(zhì)量得不到科學(xué)的保證?，F(xiàn)有了極大的限制，編圖的速度和質(zhì)量得不到科學(xué)的保證。現(xiàn)有的人工編圖所呈現(xiàn)的主要問題如下：的人工編圖所呈現(xiàn)的主要問題如下：（1 1） 由于手工編制列車運(yùn)行圖周期長、不能作多方案比選由于手工編制列車運(yùn)行圖周期長、不能作多方案比選和評價，運(yùn)行圖質(zhì)量缺乏科學(xué)的保證，編圖機(jī)動性和評價，運(yùn)行圖質(zhì)量缺乏科學(xué)的保證，編圖機(jī)動性差，差，難以適應(yīng)市場競爭的需要難以適應(yīng)市場競爭的需要；（2 2） 手工編圖在從資料收集、準(zhǔn)備，到編調(diào)圖工作的完成手工編圖在

4、從資料收集、準(zhǔn)備，到編調(diào)圖工作的完成以及指標(biāo)的計算、時刻表的打印和運(yùn)行圖繪制的全過以及指標(biāo)的計算、時刻表的打印和運(yùn)行圖繪制的全過程中，重復(fù)勞動量大、牽涉的人員和部門多、程中，重復(fù)勞動量大、牽涉的人員和部門多、組織工組織工作復(fù)雜、效率低、出錯率較高作復(fù)雜、效率低、出錯率較高；（3 3） 手工方式的運(yùn)行圖調(diào)整工作手工方式的運(yùn)行圖調(diào)整工作只能在小范圍內(nèi)進(jìn)行只能在小范圍內(nèi)進(jìn)行，難，難以從全局出發(fā)保證運(yùn)行圖綜合效益，也難以適應(yīng)特殊以從全局出發(fā)保證運(yùn)行圖綜合效益，也難以適應(yīng)特殊的運(yùn)行需要和環(huán)境的要求。的運(yùn)行需要和環(huán)境的要求。第三節(jié)第三節(jié) 計算機(jī)編制列車運(yùn)行圖的特點(diǎn)計算機(jī)編制列車運(yùn)行圖的特點(diǎn) 利用計算機(jī)編制

5、列車運(yùn)行圖具有以下特點(diǎn)：利用計算機(jī)編制列車運(yùn)行圖具有以下特點(diǎn)： （1 1）提供了）提供了高效的數(shù)據(jù)處理手段高效的數(shù)據(jù)處理手段，減輕了列車運(yùn)行圖編制，減輕了列車運(yùn)行圖編制和數(shù)據(jù)資料處理中的勞動強(qiáng)度，提高了處理的速度和精確度，和數(shù)據(jù)資料處理中的勞動強(qiáng)度，提高了處理的速度和精確度，降低了出錯率；降低了出錯率； （2 2）保障了列車運(yùn)行圖編制的科學(xué)性，提供了多方案輔助）保障了列車運(yùn)行圖編制的科學(xué)性，提供了多方案輔助決策的信息，有利于方案的評價和選擇；在此基礎(chǔ)上，吸取決策的信息，有利于方案的評價和選擇；在此基礎(chǔ)上，吸取人工編圖的先進(jìn)經(jīng)驗(yàn)，使列車運(yùn)行圖成為智能化的產(chǎn)物，從人工編圖的先進(jìn)經(jīng)驗(yàn)，使列車運(yùn)行圖成

6、為智能化的產(chǎn)物，從而而保證了列車運(yùn)行圖的質(zhì)量保證了列車運(yùn)行圖的質(zhì)量；（3 3） 實(shí)現(xiàn)了實(shí)現(xiàn)了系統(tǒng)資源共享系統(tǒng)資源共享，保證了編圖信息的存儲、傳輸，保證了編圖信息的存儲、傳輸及處理，改善了數(shù)據(jù)信息的管理和交流，實(shí)現(xiàn)了編圖及處理，改善了數(shù)據(jù)信息的管理和交流，實(shí)現(xiàn)了編圖業(yè)務(wù)的整體化，提高了編圖效率，業(yè)務(wù)的整體化，提高了編圖效率，為實(shí)現(xiàn)鐵路運(yùn)營管為實(shí)現(xiàn)鐵路運(yùn)營管理現(xiàn)代化打下了基礎(chǔ)理現(xiàn)代化打下了基礎(chǔ)；（4 4） 縮短了列車運(yùn)行圖編制全過程的時間縮短了列車運(yùn)行圖編制全過程的時間，提高了鐵路適，提高了鐵路適應(yīng)市場和特殊需要的應(yīng)變能力，改善了鐵路運(yùn)輸服務(wù)應(yīng)市場和特殊需要的應(yīng)變能力，改善了鐵路運(yùn)輸服務(wù)水平，提高

7、了鐵路運(yùn)輸經(jīng)濟(jì)效益；水平，提高了鐵路運(yùn)輸經(jīng)濟(jì)效益；（5 5） 促進(jìn)了全路技術(shù)設(shè)施合理配置和設(shè)備能力的協(xié)調(diào)促進(jìn)了全路技術(shù)設(shè)施合理配置和設(shè)備能力的協(xié)調(diào)，有，有利于設(shè)備應(yīng)用效率的綜合發(fā)揮，有利于促進(jìn)員工素質(zhì)利于設(shè)備應(yīng)用效率的綜合發(fā)揮，有利于促進(jìn)員工素質(zhì)及服務(wù)水平的提高，形成人員設(shè)備及應(yīng)用間的良性循及服務(wù)水平的提高，形成人員設(shè)備及應(yīng)用間的良性循環(huán)，提高了鐵路參與市場競爭制勝的能力。環(huán)，提高了鐵路參與市場競爭制勝的能力。第四節(jié)第四節(jié) 國內(nèi)外研究現(xiàn)狀綜述國內(nèi)外研究現(xiàn)狀綜述一、國外計算機(jī)編制列車運(yùn)行圖研究發(fā)展概況一、國外計算機(jī)編制列車運(yùn)行圖研究發(fā)展概況 國外對計算機(jī)編制列車運(yùn)行圖的研究，一般開始于五十國外對

8、計算機(jī)編制列車運(yùn)行圖的研究，一般開始于五十年代后期年代后期 。 日本日本從從19601960年開始研究利用計算機(jī)編制列車運(yùn)行時刻表。年開始研究利用計算機(jī)編制列車運(yùn)行時刻表。19641964年在列車作業(yè)計劃中利用計算機(jī)編制了具有實(shí)用價值的年在列車作業(yè)計劃中利用計算機(jī)編制了具有實(shí)用價值的運(yùn)行時刻表，并進(jìn)行了以盡可能減少編制時刻表所需勞動和運(yùn)行時刻表，并進(jìn)行了以盡可能減少編制時刻表所需勞動和時間為目標(biāo)的研究。時間為目標(biāo)的研究。 19731973年日本應(yīng)用計算機(jī)編制了東北、高年日本應(yīng)用計算機(jī)編制了東北、高倚、上越、倍越、東海道、山陽等六條線路中部分區(qū)段的列倚、上越、倍越、東海道、山陽等六條線路中部分區(qū)

9、段的列車運(yùn)行圖，效果顯著，節(jié)省了約車運(yùn)行圖，效果顯著，節(jié)省了約2/32/3的編圖時間。的編圖時間。 日本日本應(yīng)用計算機(jī)編制列車運(yùn)行圖主要采取人機(jī)對話的形應(yīng)用計算機(jī)編制列車運(yùn)行圖主要采取人機(jī)對話的形式，編圖人員使用光筆進(jìn)行列車運(yùn)行圖的編制和調(diào)整，大大式，編圖人員使用光筆進(jìn)行列車運(yùn)行圖的編制和調(diào)整，大大的減少了編圖的工作量。近幾年，日本在研究的減少了編圖的工作量。近幾年，日本在研究“人工智能人工智能”的基礎(chǔ)上進(jìn)行列車運(yùn)行圖編制專家系統(tǒng)的開發(fā)，采用搜索樹的基礎(chǔ)上進(jìn)行列車運(yùn)行圖編制專家系統(tǒng)的開發(fā)，采用搜索樹原理和經(jīng)驗(yàn)制約作為知識規(guī)則進(jìn)行驅(qū)動，利用啟發(fā)式手段原理和經(jīng)驗(yàn)制約作為知識規(guī)則進(jìn)行驅(qū)動，利用啟發(fā)式

10、手段（HEURISTICHEURISTIC），進(jìn)行局部自動調(diào)整，從而把人的判斷能力），進(jìn)行局部自動調(diào)整，從而把人的判斷能力和計算機(jī)的高速運(yùn)行能力結(jié)合起來，開發(fā)了列車運(yùn)行圖編制和計算機(jī)的高速運(yùn)行能力結(jié)合起來，開發(fā)了列車運(yùn)行圖編制系統(tǒng)（系統(tǒng)（DIADSDIADS），并在），并在19911991年后的實(shí)際工作中得到了應(yīng)用。年后的實(shí)際工作中得到了應(yīng)用。 原蘇聯(lián)原蘇聯(lián)從五十年代后期開始，對列車運(yùn)行圖的計算機(jī)從五十年代后期開始，對列車運(yùn)行圖的計算機(jī)編制進(jìn)行了大量的研究工作，對模型及模式進(jìn)行了多種試編制進(jìn)行了大量的研究工作，對模型及模式進(jìn)行了多種試驗(yàn)、改進(jìn)和完善。驗(yàn)、改進(jìn)和完善。采用的基礎(chǔ)算法主要為模擬人工

11、方法，采用的基礎(chǔ)算法主要為模擬人工方法，不追求運(yùn)行圖最優(yōu)，而是著眼于實(shí)用，采用人機(jī)對話方式，不追求運(yùn)行圖最優(yōu)，而是著眼于實(shí)用，采用人機(jī)對話方式，應(yīng)用計算機(jī)代替人工煩瑣的運(yùn)算工作，在計算機(jī)給定方案應(yīng)用計算機(jī)代替人工煩瑣的運(yùn)算工作，在計算機(jī)給定方案的基礎(chǔ)上進(jìn)行人機(jī)對話方式的修改調(diào)整，直至滿意為止，的基礎(chǔ)上進(jìn)行人機(jī)對話方式的修改調(diào)整，直至滿意為止，從而減少了運(yùn)行圖編制時間，但優(yōu)化效果甚微。從而減少了運(yùn)行圖編制時間，但優(yōu)化效果甚微。 美國美國從五十年代后期以來一直開展從五十年代后期以來一直開展 “ “應(yīng)用計算機(jī)編制列應(yīng)用計算機(jī)編制列車運(yùn)行圖車運(yùn)行圖”的研究工作，其采用的主要技術(shù)路線是計算機(jī)模的研究工作

12、，其采用的主要技術(shù)路線是計算機(jī)模擬方法和邏輯判別方法。擬方法和邏輯判別方法。19581958年，美國年，美國GRSGRS公司開發(fā)了模擬列公司開發(fā)了模擬列車運(yùn)行程序。該程序由兩部分組成：第一部分為牽引計算程車運(yùn)行程序。該程序由兩部分組成：第一部分為牽引計算程序，確定任意的列車運(yùn)行位置及行車速度；第二部分為邏輯序，確定任意的列車運(yùn)行位置及行車速度；第二部分為邏輯進(jìn)路程序，用于確定某一列車在站停車或通過，列車的會讓進(jìn)路程序，用于確定某一列車在站停車或通過，列車的會讓方案，根據(jù)列車的等級、到達(dá)會車地點(diǎn)的時間以及該方向區(qū)方案，根據(jù)列車的等級、到達(dá)會車地點(diǎn)的時間以及該方向區(qū)間是否空閑等條件確定。間是否空閑

13、等條件確定。 過模擬列車的運(yùn)行過程，確定最佳的信號配置方案及閉過模擬列車的運(yùn)行過程，確定最佳的信號配置方案及閉塞分區(qū)長度，進(jìn)行人員的培訓(xùn)和調(diào)度員、車站值班員的能力塞分區(qū)長度，進(jìn)行人員的培訓(xùn)和調(diào)度員、車站值班員的能力測試，對運(yùn)營中的各種影響因素進(jìn)行研究分析，提出改進(jìn)措測試，對運(yùn)營中的各種影響因素進(jìn)行研究分析，提出改進(jìn)措施等。施等。 英國英國也采用計算機(jī)模擬方法進(jìn)行編圖研究。也采用計算機(jī)模擬方法進(jìn)行編圖研究。19651965年英國借助計算機(jī)，首先在較短的區(qū)段上進(jìn)行列車運(yùn)年英國借助計算機(jī)，首先在較短的區(qū)段上進(jìn)行列車運(yùn)行模擬，后來發(fā)展到在包括行模擬，后來發(fā)展到在包括3030個車站、個車站、300300

14、架信號機(jī)的架信號機(jī)的單線自動閉塞區(qū)段上進(jìn)行列車運(yùn)行模擬。從單線自動閉塞區(qū)段上進(jìn)行列車運(yùn)行模擬。從19711971年開年開始，英國用計算機(jī)直接指揮編組站的作業(yè)過程，廣泛始，英國用計算機(jī)直接指揮編組站的作業(yè)過程，廣泛采用列車運(yùn)行圖自動描繪系統(tǒng)。采用列車運(yùn)行圖自動描繪系統(tǒng)。 此外，德國、比利時、羅馬尼亞、加拿大等國家此外，德國、比利時、羅馬尼亞、加拿大等國家也先后進(jìn)行了計算機(jī)編圖的研究與試驗(yàn)，在不同程度也先后進(jìn)行了計算機(jī)編圖的研究與試驗(yàn)，在不同程度上取得了一些成果。上取得了一些成果。 德國、法國、日本等國相繼建立了高速鐵路列車實(shí)時調(diào)德國、法國、日本等國相繼建立了高速鐵路列車實(shí)時調(diào)度指揮系統(tǒng)，用以控制

15、指揮高速列車運(yùn)行。度指揮系統(tǒng)，用以控制指揮高速列車運(yùn)行。 總之總之，國外利用計算機(jī)采用模擬方法編制列車運(yùn)行圖已，國外利用計算機(jī)采用模擬方法編制列車運(yùn)行圖已趨于成熟，得到了普遍的應(yīng)用和推廣。由于計算機(jī)及其輔助趨于成熟，得到了普遍的應(yīng)用和推廣。由于計算機(jī)及其輔助裝置的不斷更新，編圖周期也日漸縮短，從而可編制較多的裝置的不斷更新，編圖周期也日漸縮短，從而可編制較多的方案運(yùn)行圖以供選擇，或通過便利的人機(jī)交互手段提高編圖方案運(yùn)行圖以供選擇，或通過便利的人機(jī)交互手段提高編圖質(zhì)量。質(zhì)量。 與此同時，國外也持續(xù)開展了建立數(shù)學(xué)模型、開發(fā)相應(yīng)與此同時，國外也持續(xù)開展了建立數(shù)學(xué)模型、開發(fā)相應(yīng)算法、實(shí)現(xiàn)計算機(jī)局部編圖

16、乃至整體優(yōu)化的研究，曾先后提算法、實(shí)現(xiàn)計算機(jī)局部編圖乃至整體優(yōu)化的研究，曾先后提出了以數(shù)學(xué)規(guī)劃類模型為主的各種不同形式的數(shù)學(xué)模型。但出了以數(shù)學(xué)規(guī)劃類模型為主的各種不同形式的數(shù)學(xué)模型。但由于列車運(yùn)行圖的龐大規(guī)模及復(fù)雜內(nèi)涵，往往不是由于模型由于列車運(yùn)行圖的龐大規(guī)模及復(fù)雜內(nèi)涵，往往不是由于模型本身存在病態(tài)無法計算，就是算法的復(fù)雜性無法收斂，迄今本身存在病態(tài)無法計算，就是算法的復(fù)雜性無法收斂，迄今仍未見有實(shí)用性進(jìn)展的公開報道。仍未見有實(shí)用性進(jìn)展的公開報道。 二、國內(nèi)研究概況二、國內(nèi)研究概況 我國鐵路對利用電子計算機(jī)編制列車運(yùn)行圖的研我國鐵路對利用電子計算機(jī)編制列車運(yùn)行圖的研究始于六十年代初期。三十多年

17、來，許多鐵路高校和究始于六十年代初期。三十多年來，許多鐵路高校和科研單位采用不同的方法對不同的問題作了深入細(xì)致科研單位采用不同的方法對不同的問題作了深入細(xì)致的研究，無論在理論上還是實(shí)用開發(fā)方面均取得了許的研究，無論在理論上還是實(shí)用開發(fā)方面均取得了許多成果。多成果。 6060年代年代鐵科院運(yùn)輸所鐵科院運(yùn)輸所率先在我國研究利用計算機(jī)鋪畫率先在我國研究利用計算機(jī)鋪畫單線非平行運(yùn)行圖。經(jīng)過多年的研究，鐵科院于單線非平行運(yùn)行圖。經(jīng)過多年的研究，鐵科院于19851985年開年開發(fā)了發(fā)了“人機(jī)對話方式鋪畫全路直通客車方案人機(jī)對話方式鋪畫全路直通客車方案”軟件，先后軟件，先后在在PDP-11PDP-11和和V

18、AXVAX系列計算機(jī)上運(yùn)算，軟件實(shí)現(xiàn)了許多功能，系列計算機(jī)上運(yùn)算，軟件實(shí)現(xiàn)了許多功能，但由于當(dāng)時計算機(jī)運(yùn)算速度和技術(shù)水平的限制，系統(tǒng)仍不但由于當(dāng)時計算機(jī)運(yùn)算速度和技術(shù)水平的限制，系統(tǒng)仍不能直接應(yīng)用。能直接應(yīng)用。 近十年來，經(jīng)過近十年來，經(jīng)過鐵科院運(yùn)輸所鐵科院運(yùn)輸所堅(jiān)持不懈的努力，對該堅(jiān)持不懈的努力，對該軟件進(jìn)行了大量的修改和完善，目前已應(yīng)用于實(shí)際編制全軟件進(jìn)行了大量的修改和完善，目前已應(yīng)用于實(shí)際編制全路客車直通方案。該軟件系統(tǒng)采用人機(jī)對話方式，實(shí)現(xiàn)了路客車直通方案。該軟件系統(tǒng)采用人機(jī)對話方式，實(shí)現(xiàn)了運(yùn)行時分累計，運(yùn)行輪廓方案，兌現(xiàn)方案和檢調(diào)方案的鋪運(yùn)行時分累計，運(yùn)行輪廓方案，兌現(xiàn)方案和檢調(diào)方案

19、的鋪畫，對主要樞紐客運(yùn)站進(jìn)行行車間隔檢查、車站到發(fā)線檢畫，對主要樞紐客運(yùn)站進(jìn)行行車間隔檢查、車站到發(fā)線檢查和庫線檢查以及打印方案指標(biāo)等功能。查和庫線檢查以及打印方案指標(biāo)等功能。 哈爾濱鐵路局哈爾濱鐵路局從七十年代開始研究計算機(jī)編制列車運(yùn)行從七十年代開始研究計算機(jī)編制列車運(yùn)行圖工作，利用圖工作，利用DJS-C4DJS-C4機(jī)研究模擬人工編圖。機(jī)研究模擬人工編圖。19871987年與鐵科院年與鐵科院一起承擔(dān)了鐵道部下達(dá)的一起承擔(dān)了鐵道部下達(dá)的“電子計算機(jī)編制列車運(yùn)行圖電子計算機(jī)編制列車運(yùn)行圖”的的科研項(xiàng)目，在哈爾濱至安達(dá)間單線貨物列車運(yùn)行圖。其方法科研項(xiàng)目，在哈爾濱至安達(dá)間單線貨物列車運(yùn)行圖。其方

20、法是建立數(shù)學(xué)模型和車站越行判別條件及區(qū)間占用判別條件的是建立數(shù)學(xué)模型和車站越行判別條件及區(qū)間占用判別條件的數(shù)學(xué)公式，利用模擬人工算法對模型進(jìn)行求解。但由于數(shù)學(xué)數(shù)學(xué)公式，利用模擬人工算法對模型進(jìn)行求解。但由于數(shù)學(xué)模型復(fù)雜且不夠全面，軟件功能不夠完善，計算結(jié)果離實(shí)際模型復(fù)雜且不夠全面，軟件功能不夠完善，計算結(jié)果離實(shí)際應(yīng)用仍有一定距離。但作為用數(shù)學(xué)模型描述并采用一定算法應(yīng)用仍有一定距離。但作為用數(shù)學(xué)模型描述并采用一定算法求解的計算機(jī)編圖模式，取得了許多可借鑒的經(jīng)驗(yàn)。求解的計算機(jī)編圖模式，取得了許多可借鑒的經(jīng)驗(yàn)。 北方交通大學(xué)北方交通大學(xué)從七十年代初開始就應(yīng)用計算機(jī)對有關(guān)從七十年代初開始就應(yīng)用計算機(jī)對

21、有關(guān)列車運(yùn)行圖問題進(jìn)行了多方面的研究。首先，他們通過大列車運(yùn)行圖問題進(jìn)行了多方面的研究。首先，他們通過大量模擬試驗(yàn)鋪劃滿表列車運(yùn)行圖，取得了雙線自動閉塞區(qū)量模擬試驗(yàn)鋪劃滿表列車運(yùn)行圖，取得了雙線自動閉塞區(qū)段旅客列車扣除系數(shù)方面的一些重要數(shù)據(jù)和結(jié)論，并開展段旅客列車扣除系數(shù)方面的一些重要數(shù)據(jù)和結(jié)論，并開展了編制具有較合理彈性及均衡性雙線列車運(yùn)行圖的研究。了編制具有較合理彈性及均衡性雙線列車運(yùn)行圖的研究。此外，還配合鐵路重載運(yùn)輸和組合列車的試驗(yàn)開行，用計此外，還配合鐵路重載運(yùn)輸和組合列車的試驗(yàn)開行，用計算機(jī)進(jìn)行了相應(yīng)的模擬計算和研究。近年來，又開展了列算機(jī)進(jìn)行了相應(yīng)的模擬計算和研究。近年來，又開展

22、了列車運(yùn)行實(shí)時調(diào)整的研究。車運(yùn)行實(shí)時調(diào)整的研究。 蘭州鐵道學(xué)院蘭州鐵道學(xué)院在在8080年代研究了單線非追蹤列車運(yùn)行圖年代研究了單線非追蹤列車運(yùn)行圖的數(shù)學(xué)模型，并用啟發(fā)式算法編制程序在的數(shù)學(xué)模型，并用啟發(fā)式算法編制程序在IBM-370IBM-370機(jī)上編制機(jī)上編制了了6 6個區(qū)間、個區(qū)間、1212對貨物列車的實(shí)驗(yàn)運(yùn)行圖。近年來，長沙鐵對貨物列車的實(shí)驗(yàn)運(yùn)行圖。近年來，長沙鐵道學(xué)院也開展了列車運(yùn)行圖的優(yōu)化及計算機(jī)編制問題的研道學(xué)院也開展了列車運(yùn)行圖的優(yōu)化及計算機(jī)編制問題的研究。他們根據(jù)列車運(yùn)行圖的組合特點(diǎn)，用優(yōu)化理論方法建究。他們根據(jù)列車運(yùn)行圖的組合特點(diǎn)，用優(yōu)化理論方法建立了單、復(fù)線區(qū)段列車運(yùn)行圖優(yōu)

23、化的初步數(shù)學(xué)模型，建立立了單、復(fù)線區(qū)段列車運(yùn)行圖優(yōu)化的初步數(shù)學(xué)模型，建立了單線區(qū)段列車運(yùn)行圖優(yōu)化的理論和方法，采用優(yōu)化計算了單線區(qū)段列車運(yùn)行圖優(yōu)化的理論和方法，采用優(yōu)化計算與人機(jī)對話相結(jié)合的方法，編制了衡陽冷水灘單線區(qū)段與人機(jī)對話相結(jié)合的方法，編制了衡陽冷水灘單線區(qū)段試驗(yàn)貨物列車運(yùn)行圖。試驗(yàn)貨物列車運(yùn)行圖。 從八十年代初開始了計算機(jī)編制列車運(yùn)從八十年代初開始了計算機(jī)編制列車運(yùn)行圖的研究，采取理論研究與實(shí)際應(yīng)用開發(fā)并舉，著重于行圖的研究，采取理論研究與實(shí)際應(yīng)用開發(fā)并舉，著重于實(shí)際應(yīng)用的研究路線，實(shí)際應(yīng)用的研究路線，19871987年底在年底在VAX-750VAX-750機(jī)上試編出了三機(jī)上試編出了

24、三個區(qū)段的單線貨物列車運(yùn)行圖。個區(qū)段的單線貨物列車運(yùn)行圖。19901990年年19931993年，與成都年，與成都鐵路局合作研制開發(fā)了單線區(qū)段實(shí)用列車運(yùn)行圖編制系統(tǒng)，鐵路局合作研制開發(fā)了單線區(qū)段實(shí)用列車運(yùn)行圖編制系統(tǒng)，鋪劃了廣元馬角壩區(qū)段單線列車運(yùn)行圖。該系統(tǒng)采用鋪劃了廣元馬角壩區(qū)段單線列車運(yùn)行圖。該系統(tǒng)采用“窗口窗口”滾動技術(shù)，即首先在運(yùn)行圖中的某一時間段的某滾動技術(shù)，即首先在運(yùn)行圖中的某一時間段的某些區(qū)間內(nèi)開一個些區(qū)間內(nèi)開一個“窗口窗口”，然后再在該，然后再在該“窗口窗口”內(nèi)進(jìn)行列內(nèi)進(jìn)行列車會讓和越行的局部優(yōu)化，并通過車會讓和越行的局部優(yōu)化，并通過“窗口窗口”的滾動尋求滿的滾動尋求滿意解。

25、意解。 在復(fù)線列車運(yùn)行圖研究方面，在復(fù)線列車運(yùn)行圖研究方面，19891989年實(shí)現(xiàn)了計算機(jī)編年實(shí)現(xiàn)了計算機(jī)編制符離集徐州北區(qū)段列車運(yùn)行圖。并在此基礎(chǔ)上采用模制符離集徐州北區(qū)段列車運(yùn)行圖。并在此基礎(chǔ)上采用模型控制為主，人機(jī)交互為輔，開發(fā)了型控制為主，人機(jī)交互為輔，開發(fā)了“復(fù)線列車運(yùn)行圖計復(fù)線列車運(yùn)行圖計算機(jī)系統(tǒng)算機(jī)系統(tǒng)”，并于，并于19931993年年1111月月1 1日投入實(shí)際運(yùn)用，編制了濟(jì)日投入實(shí)際運(yùn)用，編制了濟(jì)南徐州兩個相連區(qū)段的實(shí)用列車運(yùn)行圖。經(jīng)過三年的深南徐州兩個相連區(qū)段的實(shí)用列車運(yùn)行圖。經(jīng)過三年的深入研究和不斷完善，該系統(tǒng)在入研究和不斷完善，該系統(tǒng)在19971997年初全路列車運(yùn)行圖

26、大年初全路列車運(yùn)行圖大調(diào)整的過程中，編制了京滬線天津上海、京廣線安陽調(diào)整的過程中，編制了京滬線天津上海、京廣線安陽浦圻和京九線臨清梁堤頭等區(qū)段的實(shí)用列車運(yùn)行圖，在浦圻和京九線臨清梁堤頭等區(qū)段的實(shí)用列車運(yùn)行圖，在我國第一次實(shí)現(xiàn)了計算機(jī)編制樞紐列車運(yùn)行圖和復(fù)線干線我國第一次實(shí)現(xiàn)了計算機(jī)編制樞紐列車運(yùn)行圖和復(fù)線干線上的方向列車運(yùn)行圖。上的方向列車運(yùn)行圖。 開發(fā)的此系統(tǒng)在開發(fā)的此系統(tǒng)在19971997年年4 4月通過了鐵道部鑒定，主要月通過了鐵道部鑒定，主要解決了樞紐銜接各方向列車到發(fā)的協(xié)調(diào)配合、樞紐大小運(yùn)解決了樞紐銜接各方向列車到發(fā)的協(xié)調(diào)配合、樞紐大小運(yùn)轉(zhuǎn)列車工作組織、技術(shù)站直通列車接續(xù)以及敵對進(jìn)路

27、的交轉(zhuǎn)列車工作組織、技術(shù)站直通列車接續(xù)以及敵對進(jìn)路的交叉干擾等問題。叉干擾等問題。 此外，濟(jì)南局、北京局、成都局、上海局、蘭州局、此外，濟(jì)南局、北京局、成都局、上海局、蘭州局、柳州局、鄭州局、上海鐵道大學(xué)、廣州鐵路職工大學(xué)等單柳州局、鄭州局、上海鐵道大學(xué)、廣州鐵路職工大學(xué)等單位也都先后在這方面進(jìn)行了研究，取得了一些成績。位也都先后在這方面進(jìn)行了研究，取得了一些成績。三、國內(nèi)外計算機(jī)編圖的方法綜述三、國內(nèi)外計算機(jī)編圖的方法綜述 綜觀國內(nèi)外對計算機(jī)編圖研究的歷史和現(xiàn)階段的情況，綜觀國內(nèi)外對計算機(jī)編圖研究的歷史和現(xiàn)階段的情況，所采用的方法主要有以下幾種：所采用的方法主要有以下幾種： （1 1）模擬方

28、法）模擬方法 有模擬列車運(yùn)行、模擬人工鋪劃等方法。該方法主要有模擬列車運(yùn)行、模擬人工鋪劃等方法。該方法主要以人工編圖的原則和經(jīng)驗(yàn)為條件，生成計算機(jī)編圖的判別以人工編圖的原則和經(jīng)驗(yàn)為條件，生成計算機(jī)編圖的判別準(zhǔn)則和執(zhí)行程序，實(shí)現(xiàn)人工編圖的全過程。采用該方法編準(zhǔn)則和執(zhí)行程序，實(shí)現(xiàn)人工編圖的全過程。采用該方法編圖，其質(zhì)量和效果在很大程度上取決于判別準(zhǔn)則和執(zhí)行過圖，其質(zhì)量和效果在很大程度上取決于判別準(zhǔn)則和執(zhí)行過程程序設(shè)計的合理與全面性。程程序設(shè)計的合理與全面性。 （2 2）移動列車始發(fā)點(diǎn)）移動列車始發(fā)點(diǎn) 該方法一般在雙線區(qū)段采用。編圖時按某一時間間隔該方法一般在雙線區(qū)段采用。編圖時按某一時間間隔給定列

29、車始發(fā)點(diǎn)，實(shí)現(xiàn)一條運(yùn)行線的行車間隔檢查及處理給定列車始發(fā)點(diǎn)，實(shí)現(xiàn)一條運(yùn)行線的行車間隔檢查及處理的遞推鋪劃，當(dāng)發(fā)現(xiàn)不滿足間隔時間時，移動列車始發(fā)點(diǎn)，的遞推鋪劃，當(dāng)發(fā)現(xiàn)不滿足間隔時間時，移動列車始發(fā)點(diǎn)，重新進(jìn)行該條運(yùn)行線的鋪劃，如此重復(fù)進(jìn)行，直到處理完重新進(jìn)行該條運(yùn)行線的鋪劃，如此重復(fù)進(jìn)行，直到處理完畢。畢。（3 3）逐區(qū)間遞推鋪劃）逐區(qū)間遞推鋪劃 該方法主要用于單線區(qū)段。從該區(qū)段的某一端開始，該方法主要用于單線區(qū)段。從該區(qū)段的某一端開始，依區(qū)間出現(xiàn)的先后順序進(jìn)行檢查鋪劃。對相對的兩個方向依區(qū)間出現(xiàn)的先后順序進(jìn)行檢查鋪劃。對相對的兩個方向而言，其中一列順列車運(yùn)行方向鋪劃，另一列則反方向鋪而言，其中

30、一列順列車運(yùn)行方向鋪劃，另一列則反方向鋪劃；依要求也可以從限制區(qū)間開始向區(qū)段兩端延伸鋪劃。劃；依要求也可以從限制區(qū)間開始向區(qū)段兩端延伸鋪劃。（4 4）數(shù)學(xué)模型方法）數(shù)學(xué)模型方法 利用邏輯代數(shù)、線性規(guī)劃、圖論及動態(tài)規(guī)劃方法建立利用邏輯代數(shù)、線性規(guī)劃、圖論及動態(tài)規(guī)劃方法建立描述列車運(yùn)行圖的數(shù)學(xué)模型，通過編程實(shí)現(xiàn)計算機(jī)求解。描述列車運(yùn)行圖的數(shù)學(xué)模型，通過編程實(shí)現(xiàn)計算機(jī)求解。從目前的研究結(jié)果看，由于列車運(yùn)行圖涉及面廣、影響因從目前的研究結(jié)果看，由于列車運(yùn)行圖涉及面廣、影響因素繁雜，難以用一個模型進(jìn)行描述，有些因素還難以用數(shù)素繁雜，難以用一個模型進(jìn)行描述，有些因素還難以用數(shù)學(xué)表達(dá)式表達(dá)，甚至本身之間就是

31、相互矛盾和制約的。對學(xué)表達(dá)式表達(dá)，甚至本身之間就是相互矛盾和制約的。對于這樣一個于這樣一個NPNP完全問題，鑒于現(xiàn)階段計算機(jī)速度、容量以完全問題，鑒于現(xiàn)階段計算機(jī)速度、容量以及算法上的局限，還難以通過數(shù)學(xué)模型和相應(yīng)的求解算法及算法上的局限，還難以通過數(shù)學(xué)模型和相應(yīng)的求解算法得出滿意且符合實(shí)用的列車運(yùn)行圖。得出滿意且符合實(shí)用的列車運(yùn)行圖。（5 5）人工智能專家系統(tǒng)方法）人工智能專家系統(tǒng)方法 利用智能化語言編程，把列車運(yùn)行圖的物理?xiàng)l件和人利用智能化語言編程，把列車運(yùn)行圖的物理?xiàng)l件和人工經(jīng)驗(yàn)作為知識規(guī)則，生成編圖專家系統(tǒng)，并按照列車的工經(jīng)驗(yàn)作為知識規(guī)則，生成編圖專家系統(tǒng)，并按照列車的走行順序進(jìn)行組合

32、的運(yùn)行實(shí)驗(yàn)。這種方法首先起源于日本，走行順序進(jìn)行組合的運(yùn)行實(shí)驗(yàn)。這種方法首先起源于日本，是在對是在對“人工智能人工智能”的研究及運(yùn)用日趨活躍的背景下發(fā)展的研究及運(yùn)用日趨活躍的背景下發(fā)展起來的。起來的。（6 6）范圍約束搜索樹法）范圍約束搜索樹法 該方法把運(yùn)行圖看作各區(qū)間列車運(yùn)行順序的一個組該方法把運(yùn)行圖看作各區(qū)間列車運(yùn)行順序的一個組合，以運(yùn)行時間帶代替運(yùn)行線鋪畫列車，把運(yùn)行圖編制合，以運(yùn)行時間帶代替運(yùn)行線鋪畫列車，把運(yùn)行圖編制作為一個搜索問題來解決。采用作為一個搜索問題來解決。采用以時間帶代替運(yùn)行線以時間帶代替運(yùn)行線鋪鋪畫列車運(yùn)行圖，各列車的運(yùn)行時間帶在各區(qū)間單獨(dú)考慮畫列車運(yùn)行圖，各列車的運(yùn)行

33、時間帶在各區(qū)間單獨(dú)考慮時，幅度比較寬，但如果把相鄰區(qū)間合并起來考慮，由時，幅度比較寬，但如果把相鄰區(qū)間合并起來考慮，由于列車運(yùn)行的連續(xù)性，各列車就會因自身或與其他列車于列車運(yùn)行的連續(xù)性，各列車就會因自身或與其他列車之間相互制約可能的到發(fā)時刻，在時刻上的傳播約束條之間相互制約可能的到發(fā)時刻，在時刻上的傳播約束條件，使時間帶的寬度變窄。隨著被考慮區(qū)間的增多，各件，使時間帶的寬度變窄。隨著被考慮區(qū)間的增多，各列車運(yùn)行時間帶的寬度也越來越窄，甚至接近于列車運(yùn)列車運(yùn)行時間帶的寬度也越來越窄，甚至接近于列車運(yùn)行線。行線。 虛擬節(jié)點(diǎn)虛擬節(jié)點(diǎn) 第一區(qū)間第一區(qū)間 運(yùn)行順序運(yùn)行順序 第二區(qū)間第二區(qū)間運(yùn)行順序運(yùn)行順

34、序 最后區(qū)間最后區(qū)間運(yùn)行順序運(yùn)行順序 圖圖 1.1 確定列車運(yùn)行順序的搜索樹確定列車運(yùn)行順序的搜索樹 第第三三區(qū)間區(qū)間運(yùn)行順序運(yùn)行順序 （7 7）人機(jī)對話方式）人機(jī)對話方式 列車運(yùn)行圖的編制，具有影響因素多，組織規(guī)模大，列車運(yùn)行圖的編制，具有影響因素多，組織規(guī)模大，信息量大，變化快的特點(diǎn)。從決策問題的特征分析，運(yùn)行信息量大，變化快的特點(diǎn)。從決策問題的特征分析，運(yùn)行圖編制可分為方案圖（草圖）編制、基本圖（詳圖）編制圖編制可分為方案圖（草圖）編制、基本圖（詳圖）編制和實(shí)績列車運(yùn)行圖編制。在上述三類運(yùn)行圖編圖層處理的和實(shí)績列車運(yùn)行圖編制。在上述三類運(yùn)行圖編圖層處理的決策問題中，結(jié)構(gòu)化決策問題和非結(jié)構(gòu)

35、化決策問題的比例決策問題中，結(jié)構(gòu)化決策問題和非結(jié)構(gòu)化決策問題的比例可用圖可用圖1.21.2表示。表示。 非結(jié)構(gòu)化 結(jié)構(gòu)化 編制列車運(yùn)行圖方案圖 編制列車運(yùn)行圖基本圖 編制實(shí)績列車運(yùn)行圖 圖 1.2 問題結(jié)構(gòu)化程度示意圖 利用計算機(jī)編制列車運(yùn)行圖是一個要求理論與實(shí)際相利用計算機(jī)編制列車運(yùn)行圖是一個要求理論與實(shí)際相結(jié)合、技術(shù)難度非常大的工作，國內(nèi)外學(xué)者為此做了大量結(jié)合、技術(shù)難度非常大的工作，國內(nèi)外學(xué)者為此做了大量的研究工作，嘗試過許多解決方法，但是他們在取得一定的研究工作，嘗試過許多解決方法，但是他們在取得一定的成果的同時，又存在著各種問題，而產(chǎn)生這些問題的根的成果的同時，又存在著各種問題，而產(chǎn)生

36、這些問題的根本原因就在于他們所采用的方法都是把列車運(yùn)行圖的編制本原因就在于他們所采用的方法都是把列車運(yùn)行圖的編制問題作為結(jié)構(gòu)化決策問題全部交由計算機(jī)來處理。問題作為結(jié)構(gòu)化決策問題全部交由計算機(jī)來處理。 編制列車運(yùn)行圖的過程是在有限的鐵路運(yùn)輸設(shè)備和人編制列車運(yùn)行圖的過程是在有限的鐵路運(yùn)輸設(shè)備和人力的條件下，把由戰(zhàn)略計劃層制定的列車運(yùn)行方案變?yōu)榫吡Φ臈l件下，把由戰(zhàn)略計劃層制定的列車運(yùn)行方案變?yōu)榫唧w的能夠?qū)嵤┑牧熊囘\(yùn)行計劃的過程。在這個過程中，既體的能夠?qū)嵤┑牧熊囘\(yùn)行計劃的過程。在這個過程中，既有結(jié)構(gòu)化決策問題，又有非結(jié)構(gòu)化決策問題，處理時不能有結(jié)構(gòu)化決策問題，又有非結(jié)構(gòu)化決策問題，處理時不能一概而

37、論。一概而論。 因此結(jié)合我國實(shí)際情況，提出了采用人機(jī)對話方式編因此結(jié)合我國實(shí)際情況，提出了采用人機(jī)對話方式編制客貨列車運(yùn)行圖的方法。制客貨列車運(yùn)行圖的方法。 在編制列車運(yùn)行圖過程中，編圖者的在編制列車運(yùn)行圖過程中，編圖者的業(yè)務(wù)知識業(yè)務(wù)知識可分為可分為三個部分：三個部分： 1 1編制列車運(yùn)行圖的技能；編制列車運(yùn)行圖的技能； 2 2編圖區(qū)段內(nèi)與行車有關(guān)的鐵路設(shè)施、設(shè)備編圖區(qū)段內(nèi)與行車有關(guān)的鐵路設(shè)施、設(shè)備 情況以及與編圖有關(guān)的數(shù)據(jù)；情況以及與編圖有關(guān)的數(shù)據(jù)； 3 3編圖區(qū)段列車運(yùn)行方案、運(yùn)輸需求和客流編圖區(qū)段列車運(yùn)行方案、運(yùn)輸需求和客流 情況等信息。情況等信息。 列車運(yùn)行圖 輸出 閱讀列車運(yùn)行圖知識

38、 2.線路設(shè)備 有關(guān)知識 (數(shù)據(jù)庫) 1.編制列車 運(yùn)行圖技能 (模型） 與本職工作 有關(guān)的知識 圖 1.3 人機(jī)對話編制列車運(yùn)行圖示意圖 3.列車運(yùn)行圖 方案等 命令 計計算算機(jī)機(jī) 人人 其其它它鐵鐵路路計計劃劃制制定定者者 進(jìn)行計算機(jī)編制列車運(yùn)行圖時，將第進(jìn)行計算機(jī)編制列車運(yùn)行圖時，將第1 1、2 2部分知識賦予計算機(jī)，部分知識賦予計算機(jī)，使編圖者只需根據(jù)自己所掌握的第使編圖者只需根據(jù)自己所掌握的第3 3部分，采用人機(jī)對話方式，由計部分，采用人機(jī)對話方式，由計算機(jī)編制列車運(yùn)行圖。算機(jī)編制列車運(yùn)行圖。 采用以模型優(yōu)化計算機(jī)控制為主，人機(jī)對話調(diào)整為輔，采用以模型優(yōu)化計算機(jī)控制為主，人機(jī)對話調(diào)整

39、為輔，人機(jī)結(jié)合互補(bǔ)的方式編制列車運(yùn)行圖，其人機(jī)結(jié)合互補(bǔ)的方式編制列車運(yùn)行圖，其特點(diǎn)特點(diǎn)是：是：（1 1）能充分發(fā)揮計算機(jī)的高速計算能力和人的主觀能動性，）能充分發(fā)揮計算機(jī)的高速計算能力和人的主觀能動性，避免了采用單一方式所帶來的不足。避免了采用單一方式所帶來的不足。（2 2）結(jié)合了我國編圖的實(shí)際情況，能有效的解決客貨列車）結(jié)合了我國編圖的實(shí)際情況，能有效的解決客貨列車運(yùn)行圖綜合編制、復(fù)線方向直通列車在技術(shù)站接續(xù)、樞紐運(yùn)行圖綜合編制、復(fù)線方向直通列車在技術(shù)站接續(xù)、樞紐各銜接方向列車的均衡到達(dá)、各局間分界口列車合理銜接、各銜接方向列車的均衡到達(dá)、各局間分界口列車合理銜接、樞紐內(nèi)大小運(yùn)轉(zhuǎn)列車的協(xié)調(diào)配

40、合以及機(jī)車交路勾畫等問題。樞紐內(nèi)大小運(yùn)轉(zhuǎn)列車的協(xié)調(diào)配合以及機(jī)車交路勾畫等問題。第一節(jié)第一節(jié) 鐵路網(wǎng)描述鐵路網(wǎng)描述 鐵路是一個復(fù)雜的網(wǎng)絡(luò)，旅客列車和貨物列車在列車鐵路是一個復(fù)雜的網(wǎng)絡(luò)，旅客列車和貨物列車在列車運(yùn)行圖的指導(dǎo)下有序地在鐵路網(wǎng)上運(yùn)行。構(gòu)成鐵路網(wǎng)絡(luò)的運(yùn)行圖的指導(dǎo)下有序地在鐵路網(wǎng)上運(yùn)行。構(gòu)成鐵路網(wǎng)絡(luò)的主要因素是分界點(diǎn)（指車站和線路所）和線路。為了討論主要因素是分界點(diǎn)（指車站和線路所）和線路。為了討論的方便，在構(gòu)造簡化的鐵路網(wǎng)絡(luò)圖時，只保留與列車運(yùn)行的方便，在構(gòu)造簡化的鐵路網(wǎng)絡(luò)圖時，只保留與列車運(yùn)行直接相關(guān)的網(wǎng)絡(luò)干支線和樞紐聯(lián)絡(luò)線等。同時，把車站看直接相關(guān)的網(wǎng)絡(luò)干支線和樞紐聯(lián)絡(luò)線等。同時，把

41、車站看成一個點(diǎn)，車站到發(fā)線因素以及與車站相關(guān)的進(jìn)路因素在成一個點(diǎn)，車站到發(fā)線因素以及與車站相關(guān)的進(jìn)路因素在構(gòu)建模型時作為約束條件構(gòu)建模型時作為約束條件 。 簡化的鐵路網(wǎng)絡(luò)圖由節(jié)點(diǎn)和?。ㄟB接節(jié)點(diǎn)的線路）組簡化的鐵路網(wǎng)絡(luò)圖由節(jié)點(diǎn)和弧（連接節(jié)點(diǎn)的線路）組成。對應(yīng)于單線鐵路和雙線鐵路的弧，給出如下定義：成。對應(yīng)于單線鐵路和雙線鐵路的弧，給出如下定義： 定義定義1 1 在構(gòu)造的網(wǎng)絡(luò)圖中，如果在構(gòu)造的網(wǎng)絡(luò)圖中，如果a a、b b為弧為弧j j的兩端節(jié)的兩端節(jié)點(diǎn)，則節(jié)點(diǎn)點(diǎn)，則節(jié)點(diǎn)a a和節(jié)點(diǎn)和節(jié)點(diǎn)b b是相鄰的；當(dāng)是相鄰的；當(dāng)a a為弧為弧j j的起點(diǎn)，的起點(diǎn)，b b為弧為弧j j的終點(diǎn)，則弧的終點(diǎn)，則弧j

42、 j是從節(jié)點(diǎn)是從節(jié)點(diǎn)a a出發(fā)并到達(dá)節(jié)點(diǎn)出發(fā)并到達(dá)節(jié)點(diǎn)b b。同樣，當(dāng)兩條。同樣，當(dāng)兩條弧弧i i和和j j有相同節(jié)點(diǎn)有相同節(jié)點(diǎn)a a時，則弧時，則弧i i與弧與弧j j是相鄰的。是相鄰的。 定義定義2 2 單向弧單向?。涸谝粋€網(wǎng)絡(luò)圖：在一個網(wǎng)絡(luò)圖G G中，有兩個相鄰節(jié)中，有兩個相鄰節(jié)點(diǎn)和，由至存在線路，如圖點(diǎn)和，由至存在線路，如圖2.1.12.1.1所示，經(jīng)過此線路只所示，經(jīng)過此線路只能由節(jié)點(diǎn)到達(dá)，反之則不能。對應(yīng)于這樣線路的弧稱為能由節(jié)點(diǎn)到達(dá)，反之則不能。對應(yīng)于這樣線路的弧稱為單向弧。單向弧。jajb j圖圖2.1.1 2.1.1 單向弧示意圖單向弧示意圖 組成復(fù)線鐵路的上、下行線路在網(wǎng)絡(luò)

43、圖中用單向弧組成復(fù)線鐵路的上、下行線路在網(wǎng)絡(luò)圖中用單向弧表示，其集合為表示，其集合為SCSC。 定義定義3 3 雙向弧雙向?。涸谝粋€網(wǎng)絡(luò)圖：在一個網(wǎng)絡(luò)圖G G中，有兩個相鄰節(jié)點(diǎn)中，有兩個相鄰節(jié)點(diǎn)和，連接和的線路存在如下特性：既可經(jīng)由此線路從節(jié)點(diǎn)和，連接和的線路存在如下特性：既可經(jīng)由此線路從節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)，也可沿此線路從節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)，對應(yīng)于這樣線到達(dá)節(jié)點(diǎn)，也可沿此線路從節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)，對應(yīng)于這樣線路的弧稱為雙向弧。如圖路的弧稱為雙向弧。如圖2.1.22.1.2所示，雙向弧的集合為所示，雙向弧的集合為DCDC。在網(wǎng)絡(luò)構(gòu)造時，單線鐵路對應(yīng)的弧為雙向弧。在網(wǎng)絡(luò)構(gòu)造時，單線鐵路對應(yīng)的弧為雙向弧。圖圖2.1.

44、2 2.1.2 雙向弧示意圖雙向弧示意圖jajb j 實(shí)際上，網(wǎng)絡(luò)圖構(gòu)造中，單線鐵路對應(yīng)的實(shí)際上，網(wǎng)絡(luò)圖構(gòu)造中，單線鐵路對應(yīng)的雙向弧，也可看成由兩條單向弧組成，只不過雙向弧，也可看成由兩條單向弧組成，只不過由由j ja a至至j jb b這一事件與由這一事件與由j jb b至至j ja a的事件互為敵對，的事件互為敵對，不能同時發(fā)生。不能同時發(fā)生。 定義定義4 4 如圖如圖2.1.42.1.4所示，弧所示，弧d d與弧與弧a a、b b、c c具有包含關(guān)具有包含關(guān)系，記為系，記為( (a a、b b、c c) )d d，稱弧，稱弧d d為為包含弧包含弧，弧，弧a a、b b、c c為為被包被包

45、含弧含弧，且弧，且弧a a稱為稱為被包含起始弧被包含起始弧，弧，弧c c稱為稱為被包含終止弧被包含終止弧。 包含弧與被包含弧在物理上是同一徑路，因此在模型包含弧與被包含弧在物理上是同一徑路，因此在模型構(gòu)造時應(yīng)視為相同弧進(jìn)行約束。構(gòu)造時應(yīng)視為相同弧進(jìn)行約束。 包含弧與被包含弧經(jīng)常在鐵路樞紐內(nèi)出現(xiàn)。包含弧與被包含弧經(jīng)常在鐵路樞紐內(nèi)出現(xiàn)。 定義定義5 5 如圖如圖2.1.52.1.5所示，在列車實(shí)際運(yùn)行徑路中，若所示，在列車實(shí)際運(yùn)行徑路中，若弧弧i i被一列車占用，則另一弧被一列車占用，則另一弧j j必不能被另一列車同時占用。必不能被另一列車同時占用。反之亦然反之亦然。稱弧稱弧i i與弧與弧j j存

46、在敵對進(jìn)路關(guān)系，記為存在敵對進(jìn)路關(guān)系，記為ijij。bcadij圖圖2.1.3 敵對進(jìn)路示意圖敵對進(jìn)路示意圖 這樣，對于構(gòu)造的簡化鐵路網(wǎng)絡(luò)圖，可以用改進(jìn)的鄰這樣，對于構(gòu)造的簡化鐵路網(wǎng)絡(luò)圖，可以用改進(jìn)的鄰接目錄表示，即用弧的編號與其對應(yīng)節(jié)點(diǎn)順序排列表示。接目錄表示，即用弧的編號與其對應(yīng)節(jié)點(diǎn)順序排列表示。如圖如圖2.1.42.1.4所示的網(wǎng)絡(luò)圖，可以寫出其所有節(jié)點(diǎn)的到達(dá)鄰接所示的網(wǎng)絡(luò)圖，可以寫出其所有節(jié)點(diǎn)的到達(dá)鄰接目錄和出發(fā)鄰接目錄。目錄和出發(fā)鄰接目錄。 kijhlabdc圖圖2.1.4 2.1.4 簡化鐵路網(wǎng)絡(luò)示意圖簡化鐵路網(wǎng)絡(luò)示意圖 出發(fā)鄰接目錄出發(fā)鄰接目錄 到達(dá)鄰接目錄到達(dá)鄰接目錄 A(a)

47、=i,c,j,b A(a)= A(a)=i,c,j,b A(a)= A(b)=k,c,l,d A(b)=j,a A(b)=k,c,l,d A(b)=j,a A(c)=h,d A(c)=i,a,k,b A(c)=h,d A(c)=i,a,k,b A(d)= A(d)= A(d)=l,b,h,c A(d)=l,b,h,c第二節(jié)第二節(jié) 模型構(gòu)造模型構(gòu)造一、約束條件一、約束條件 這里，引入這里，引入dtimedtime表示一天的時間，表示一天的時間，dtimedtime為一常數(shù)，為一常數(shù)，當(dāng)用小時、半小時、分、半分、當(dāng)用小時、半小時、分、半分、1/41/4分為單位表示時間時，分為單位表示時間時，分別為

48、：分別為：2424、4848、14401440、28802880、57605760。同時，引入符號于。同時，引入符號于模型中，其意義為：模型中，其意義為：x yxyxyxdtimeyxy 當(dāng)時當(dāng)時 令令L L表示區(qū)間線路對應(yīng)聯(lián)弧集，表示區(qū)間線路對應(yīng)聯(lián)弧集，L LB B表示半自動閉塞區(qū)間表示半自動閉塞區(qū)間線路對應(yīng)弧集，線路對應(yīng)弧集，L LZ Z表示自動閉塞區(qū)間線路對應(yīng)弧集，表示自動閉塞區(qū)間線路對應(yīng)弧集，DCDC為為網(wǎng)絡(luò)雙向弧集，網(wǎng)絡(luò)雙向弧集，SCSC為網(wǎng)絡(luò)對應(yīng)單向弧集，為網(wǎng)絡(luò)對應(yīng)單向弧集，N N表示網(wǎng)絡(luò)節(jié)點(diǎn)集，表示網(wǎng)絡(luò)節(jié)點(diǎn)集，T T表示在構(gòu)造網(wǎng)絡(luò)上運(yùn)行的列車集合，表示在構(gòu)造網(wǎng)絡(luò)上運(yùn)行的列車集合，

49、T Tj j表示在雙向弧表示在雙向弧j j上上由一端至另一端的列車集合，由一端至另一端的列車集合，T Tj j表示在雙向弧表示在雙向弧j j上與上與T Tj j+ +集集合中列車運(yùn)行方向相反的列車集合，合中列車運(yùn)行方向相反的列車集合， 并有：并有： LLLBZDCjSCDCL 1 1 區(qū)間列車運(yùn)行時間約束區(qū)間列車運(yùn)行時間約束k1k2jXFik1XDik2QXtqQXtttyikijikijij12圖圖2.2.1 2.2.1 列車區(qū)間運(yùn)行時分約束示意圖列車區(qū)間運(yùn)行時分約束示意圖XDXFQXtqQXtttyiT jL kkNkjkjikikikijikijijBLEL21121212(,)、且 (

50、2.2.1)(2.2.1)2 2 列車停站時分約束列車停站時分約束 若令表示列車若令表示列車i i在節(jié)點(diǎn)在節(jié)點(diǎn)k k對應(yīng)車站的停站時分，則列車對應(yīng)車站的停站時分，則列車i i在節(jié)點(diǎn)在節(jié)點(diǎn)k k的停站時間應(yīng)滿足如下條件。的停站時間應(yīng)滿足如下條件。XDikXFikktsik圖圖2.2.2 2.2.2 列車停站時分約束示意圖列車停站時分約束示意圖XFXDtsiT kNikikik(,)(2.2.2)(2.2.2)3 3 列車間隔時間約束列車間隔時間約束 （1 1） 列車追蹤間隔時間約束列車追蹤間隔時間約束 當(dāng)列車在弧當(dāng)列車在弧j j( )( )上運(yùn)行時，同向列車間應(yīng)按追蹤間隔上運(yùn)行時，同向列車間應(yīng)按

51、追蹤間隔運(yùn)行。運(yùn)行。 k2jk1k2jk1k2jk1i1i1i1i2i2i2XDik12XDik22tdjtfjXFik11XFik21XFik11XFik21tzj圖圖2.2.3 2.2.3 自動閉塞區(qū)間列車間隔約束示意圖自動閉塞區(qū)間列車間隔約束示意圖jLZXDXDQXtdQXtziiT jL kNkjikikikjikjZELZ22121212101222()(,;)、且);,(0)1 (112112121112ZLBZjkijkikikijkNkLjTiitzQXtfQXXFXF且、(2.2.3)(2.2.3)(2.2.4)(2.2.4)（2 2） 列車連發(fā)間隔時間約束列車連發(fā)間隔時間約

52、束當(dāng)列車在弧當(dāng)列車在弧j j( )( )上運(yùn)行時，同向列車應(yīng)按連發(fā)條件運(yùn)行。上運(yùn)行時，同向列車應(yīng)按連發(fā)條件運(yùn)行。如圖所示，如圖所示，列車連發(fā)間隔時間應(yīng)列車連發(fā)間隔時間應(yīng)滿足如下約束條件：滿足如下約束條件： k2jk1k2jk1i1i1i2i2XDik12XFik11XFik21XFik11tltjXFik21tlcjXDik12圖圖2.2.4 2.2.4 半自動閉塞區(qū)間列車間隔約束示意圖半自動閉塞區(qū)間列車間隔約束示意圖(2.2.5),(0)1 ()(212121121211211111112BBLELBBjkijkijijikijikikikijkjkNkkLjTiitlcQXtltQXtyt

53、tQXtqQXXFXF且、jLB 4 4 同向列車越行條件約束同向列車越行條件約束 由于列車等級不同，牽引列車的機(jī)車也可能不一樣，由于列車等級不同，牽引列車的機(jī)車也可能不一樣，不同等級的列車在同一弧不同等級的列車在同一弧j j對應(yīng)的區(qū)間線路上運(yùn)行時分也不對應(yīng)的區(qū)間線路上運(yùn)行時分也不一樣。一樣。 k2j2k1j1k0i2i1XDik11XFik21XFik11圖圖2.2.5 2.2.5 列車越行示意圖列車越行示意圖XDXDtdiiTkNkjkjjjL lctz ilevellctz ilevelikikjELBLZZZ2111122612111121221( . . )(,( ).( ).)、，

54、且、XDiyQXtqXDQXtltQXtlci iTkNkjkjkjjLlctz ilevellctz ilevelikijikjikikjikjELBLBLBBB2121201112012011227121110112121()( . . )( ,( ).( ).)，且，越行后的列車出發(fā)間隔需滿足：越行后的列車出發(fā)間隔需滿足： XFXFtfyi iT kNkjjL lctz ilevellctz ilevelikikjBL1121222812112221( . . )( ,( ).( ).)且tfytfjLtLtQXtttyjLjjZjikijijB22222222222當(dāng)當(dāng)其中其中5 5

55、車站間隔時間約束車站間隔時間約束 為了保證行車安全和最佳地利用區(qū)間通過能力，列車為了保證行車安全和最佳地利用區(qū)間通過能力，列車到達(dá)、出發(fā)或通過車站均需滿足一定的時間間隔約束。到達(dá)、出發(fā)或通過車站均需滿足一定的時間間隔約束。（1 1） 不同時到達(dá)間隔時間約束不同時到達(dá)間隔時間約束i1i2k0k1k2j1j2tBk1tHk1XDik11XDik21XFik11圖圖2.2.6 2.2.6 不同時到達(dá)和會車間隔約束示意圖不同時到達(dá)和會車間隔約束示意圖XDXDtBikikk21111（2.2.92.2.9）iiTiTiTkNkBT jDC jDCjj1212111211、且且,;,（2 2） 會車間隔時

56、間約束會車間隔時間約束XFXDtHikikk11211DCjDCjNkTiTijj21121,22（2.2.102.2.10）（3 3） 同方向列車不同時到發(fā)間隔時間約束同方向列車不同時到發(fā)間隔時間約束k2j2k1j1k0i2i1XDik11XFik21tdfk1圖圖2.2.7 2.2.7 同方向列車不同時到發(fā)間隔約束示意圖同方向列車不同時到發(fā)間隔約束示意圖XFXDtdfikikk21111(,)|iiiT iT kNKBD jjL kjkjE LB L121211121112、，（2.2.112.2.11）（4 4） 同方向列車不同時發(fā)到間隔時間約束同方向列車不同時發(fā)到間隔時間約束 k2j2

57、k1j1k0i2i1XFik11XDik21圖圖2.2.8 2.2.8 同方向列車不同時發(fā)到間隔約束示意圖同方向列車不同時發(fā)到間隔約束示意圖XDXFtfdikiKK21111),(|21|1121112121LBLEjkjkLjjBDKNkTiTiii，、，、(2.2.12)（5 5） 不同時通過間隔時間約束不同時通過間隔時間約束 k1k0j2j1XDik21XDik11i1i2tbtk1k2XDXDtbtikikk2111121jTi22jTiKN1KDST1jSC jDC KjKjAB SCB DC121112,| 、 ， 且且(2.2.13) (2.2.13) 圖圖2.2.9 2.2.9

58、 不同時通過間隔時間約束示意圖不同時通過間隔時間約束示意圖（6 6）列車單獨(dú)占用聯(lián)弧約束）列車單獨(dú)占用聯(lián)弧約束 對于某些聯(lián)弧，如單線區(qū)間線路聯(lián)弧，在一定的時間對于某些聯(lián)弧，如單線區(qū)間線路聯(lián)弧，在一定的時間范圍內(nèi)只允許一列車占用。范圍內(nèi)只允許一列車占用。 k2k1k0j2j1XDik11XFik21i2i1圖圖 2.2.10 2.2.10 列車單獨(dú)占用聯(lián)弧約束示意圖列車單獨(dú)占用聯(lián)弧約束示意圖XFXFXtBXtHtyXttXtqikikikkikkijikjikj21101111111111110110XFXFXtHQXtBtyXttQXtqikikikkikkijikjikj1021100100

59、2120121110()kN kN10,iTj11iTj21j1j2DC（ ）(2.2.14) (2.2.15) 8 8 敵對徑路約束列車敵對徑路約束列車 在實(shí)際運(yùn)行過程中，由于設(shè)備條件和線路配置關(guān)系，在實(shí)際運(yùn)行過程中，由于設(shè)備條件和線路配置關(guān)系，存在如圖所示的敵對徑路。存在如圖所示的敵對徑路。i2i1j1j2k1圖圖2.2.11 2.2.11 敵對徑路約束示意圖敵對徑路約束示意圖XDXFtdsikikMk112111XFXDtdsikikMk211121（i1、i2T，k1N,j1、j2L,L(i1,G1,i2,G2)=M1(M2),M1、M2DJKk1）(2.2.16) 9 9 機(jī)車乘務(wù)組

60、工作時間約束機(jī)車乘務(wù)組工作時間約束XDXFtjiKiK21iLJkkNkkTi2121,、(2.2.17) 10 10 天窗時間約束天窗時間約束jk2k1t2t12.2.12 “2.2.12 “天窗天窗”約束示意圖約束示意圖XFtXDtXFtXDtikjikjikjikj12121122iT,jL,k1N,k2N,且k1=jB|Lk2=jE|L(2.2.18) 11 11 列車到發(fā)時刻特殊要求約束列車到發(fā)時刻特殊要求約束tXDtiT kNtXFtiT kNikik12112111 (,)(,)(2.2.19) 12 12 車站到發(fā)線約束車站到發(fā)線約束 (, )(, )XDtXFtDFXiki