動(dòng)車組交路計(jì)劃編制及優(yōu)化相關(guān)理論基礎(chǔ)綜述目錄TOC\o"1-3"\h\u13667動(dòng)車組交路計(jì)劃編制及優(yōu)化相關(guān)理論基礎(chǔ)綜述 181731.1動(dòng)車組交路計(jì)劃編制流程 1101431.2動(dòng)車組交路計(jì)劃編制影響因素 25891.2.1列車開行方案 215061.2.2動(dòng)車組類型 3177821.2.3動(dòng)車組管理運(yùn)用模式 3225811.2.4動(dòng)車組檢修 4230931.3動(dòng)車組交路計(jì)劃編制方法優(yōu)化模型及算法理論研究 5228951.1.1模型研究 5287361.1.2算法研究 6動(dòng)車組交路計(jì)劃是動(dòng)車組運(yùn)用問題的核心基礎(chǔ)，主要對象是機(jī)車車輛，所以交路計(jì)劃可以定義為編制出機(jī)車車輛或者說是動(dòng)車組的列車接續(xù)計(jì)劃，并且滿足現(xiàn)有的各種約束條件，例如檢修能力的約束。交路計(jì)劃要求能按照已經(jīng)制定的動(dòng)車組運(yùn)用、檢修管理的模式，在一定的時(shí)間和線路范圍內(nèi)，完成按照列車運(yùn)行圖上制定的列車任務(wù)，而交路計(jì)劃的優(yōu)化，則是在完成任務(wù)的基礎(chǔ)上，進(jìn)一步的達(dá)到車底數(shù)量最少、旅客坐席需求的完全滿足以及檢修次數(shù)最少等目標(biāo)。1.1動(dòng)車組交路計(jì)劃編制流程第一種編制流程是比較常用的，基于列車運(yùn)行圖和相關(guān)的動(dòng)車組運(yùn)用管理模式規(guī)定來編制動(dòng)車組交路計(jì)劃。我國現(xiàn)有的動(dòng)車組運(yùn)用客觀條件有：建成的動(dòng)車組段所數(shù)量較少、間隔距離較長、布局也比較分散，同時(shí)動(dòng)車組保有數(shù)量少、動(dòng)車組的車型多且雜等。而具體的動(dòng)車組運(yùn)用措施手段有：動(dòng)車組檢修采用雙修制、檢修需要回到配屬段所等。這種編制流程需要的是綜合考慮到各個(gè)限制因素，來優(yōu)化編制動(dòng)車組交路計(jì)劃[17]。圖3-1編制流程一第二種編制流程，涉及動(dòng)車組交路和列車運(yùn)行圖的協(xié)調(diào)優(yōu)化，這就需要同時(shí)編制出動(dòng)車組交路計(jì)劃以及列車運(yùn)行計(jì)劃。此編制流程的首要目標(biāo)是達(dá)到最大的動(dòng)車組運(yùn)行效率，同時(shí)滿足旅客出行的需求，因?yàn)樯婕奥每偷男枨笞兓瑥亩容^少采用這種編制流程作為優(yōu)化動(dòng)車組交路計(jì)劃的思路。但是在我國當(dāng)前高鐵陸續(xù)建成的情況下，需要對新開通的線路進(jìn)行編制動(dòng)車組運(yùn)用計(jì)劃時(shí)，就可以滿足列車開行方案的時(shí)刻表上的寬松限制，通過協(xié)調(diào)優(yōu)化來同時(shí)編制列車運(yùn)行圖以及動(dòng)車組交路計(jì)劃，完成優(yōu)化動(dòng)車組交路計(jì)劃的目的。圖3-2編制流程二1.2動(dòng)車組交路計(jì)劃編制影響因素動(dòng)車組交路計(jì)劃作為動(dòng)車組運(yùn)用計(jì)劃的核心和基礎(chǔ)，其編制離不開我國運(yùn)輸組織過程中的分階段、分級(jí)的方法。由于其編制是采用這種層層進(jìn)行的方式，所以，在編制動(dòng)車組交路計(jì)劃時(shí)，就不能只是考慮這單獨(dú)的一個(gè)計(jì)劃編制的影響因素，還要縱向的分析從最初的宏觀的策略規(guī)劃層到最末端的微觀的實(shí)際實(shí)施層，如列車開行方案等環(huán)節(jié)。1.2.1列車開行方案鐵路旅客列車開行方案確定旅客列車運(yùn)行區(qū)段、列車種類、徑路、開行對數(shù)及車底擔(dān)當(dāng)局的計(jì)劃，其中，旅客列車的始發(fā)站、終到站及經(jīng)由線路構(gòu)成旅客列車的運(yùn)行區(qū)段，列車種類區(qū)別出列車不同的等級(jí)或性質(zhì)，開行對數(shù)的多少表示行車量的大小。列車開行方案的確定，則是在客流量的基礎(chǔ)上，即按流開車。列車開行方案能直接影響列車運(yùn)行圖的質(zhì)量，進(jìn)而會(huì)影響到動(dòng)車組交路計(jì)劃的編制。列車開行方案作為運(yùn)輸組織計(jì)劃的一個(gè)重要的輸入條件，它包含的內(nèi)容十分多樣，為達(dá)到減少動(dòng)車組數(shù)量，會(huì)影響開行長距離的列車的列數(shù)，同時(shí)，又要要求列車運(yùn)行圖中的列車時(shí)刻安排合理，那么，動(dòng)車組折返、接續(xù)次數(shù)會(huì)減少，從而達(dá)到另一個(gè)目的，即動(dòng)車組接續(xù)時(shí)間減少。由此可以得出，動(dòng)車組交路計(jì)劃的優(yōu)化離不開列車開行方案，只有確定好一個(gè)合理的列車開行方案，動(dòng)車組的運(yùn)用效率才能盡可能的提高。動(dòng)車組的列車開行方案的確定，離不開對我國實(shí)際情況的分析。我國正處于規(guī)劃和修建高速鐵路的高峰時(shí)期，每年新增的高鐵營業(yè)里程正不斷的擴(kuò)大我國的高鐵客運(yùn)服務(wù)網(wǎng)，對此，列車開行方案的制定離不開對客流屬性的分析。根據(jù)不同的客流規(guī)模和特性，制定的開行方案中的列車類型、開行距離、開行密度等都有差異，這也就更需要充分的考慮列車運(yùn)行線的長短、列車擔(dān)當(dāng)任務(wù)、檢修任務(wù)安排等，力求達(dá)到對動(dòng)車組運(yùn)用時(shí)間的最大化，減少動(dòng)車組的空費(fèi)、無效的檢修等待時(shí)間，從而在降低運(yùn)營成本的方面提高動(dòng)車組的利用率。1.2.2動(dòng)車組類型我國動(dòng)車組的發(fā)展時(shí)間雖然不算長，但是進(jìn)步是巨大的，其中動(dòng)車組的類型也是隨之增加。其中主要是CRH系列動(dòng)車組，這一系列又分為CRH1、CRH2、CRH3、CRH5，四個(gè)主型號(hào)，而根據(jù)動(dòng)車組運(yùn)營的時(shí)速、定員數(shù)量、編組等不同，主型號(hào)下又分為若干個(gè)子型號(hào)。在交路計(jì)劃編制的過程中，要求的是同一交路內(nèi)運(yùn)行線上必須是同一類型的動(dòng)車組，因此，動(dòng)車組交路計(jì)劃就需要根據(jù)不同的動(dòng)車組型號(hào)進(jìn)行單獨(dú)編制。動(dòng)車組型號(hào)的影響也可以根據(jù)我國現(xiàn)在的高鐵路網(wǎng)來分析，不同的線路根據(jù)其客流的不同，規(guī)劃開行的動(dòng)車組必定有差異，這就要求尋找最為適合某一線路的動(dòng)車組型號(hào)，不過一般線路修建前的規(guī)劃中，都會(huì)有建成后開行運(yùn)營的動(dòng)車組數(shù)據(jù)，所以動(dòng)車組類型對于動(dòng)車組交路優(yōu)化的影響，就在于如何做到在同一交路計(jì)劃內(nèi)，采用最合適的動(dòng)車組型號(hào)達(dá)到交路計(jì)劃最優(yōu)。1.2.3動(dòng)車組管理運(yùn)用模式自從我國鐵路改革為國鐵集團(tuán)，即中國鐵路總公司，所屬的18個(gè)鐵路局也變更為中國鐵路某局集團(tuán)有限公司，之后，我國動(dòng)車組的管理變得更加的明確合理，動(dòng)車組由鐵路總公司購買配置，滿足各鐵路局的需求。之后，各大鐵路局擁有動(dòng)車組的分配權(quán)，可將動(dòng)車組配屬到下屬的動(dòng)車組運(yùn)用段所。由此可以看出，這種管理運(yùn)用的模式的優(yōu)點(diǎn)十分明顯，即各鐵路局各自管理、獨(dú)立使用的好處在于責(zé)任明確、檢修質(zhì)量得到了保障，同時(shí)，問題也存在，就是動(dòng)車組的運(yùn)用比較固定僵化，一些可以共用的檢修備用資源，不能充分利用，還有遇到特殊緊急情況時(shí)，不能進(jìn)行靈活的調(diào)整，去最快的解決問題。按照我國鐵路總公司以及各大鐵路局集團(tuán)、客專公司的管理模式，編制動(dòng)車組交路計(jì)劃需要明確動(dòng)車組的歸屬，以及動(dòng)車組在接續(xù)時(shí)的選擇問題，這會(huì)直接影響動(dòng)車組的利用效率，交路計(jì)劃必須考慮到這一問題[18]。1.2.4動(dòng)車組檢修動(dòng)車組檢修是動(dòng)車組交路計(jì)劃編制同樣不可忽略的一大因素。檢修環(huán)節(jié)是保證動(dòng)車組安全、高效執(zhí)行列車任務(wù)的必要手段，我國出臺(tái)的動(dòng)車組檢修規(guī)程，里面明確的規(guī)定了各類動(dòng)車組不同級(jí)別的檢修內(nèi)容、檢修周期和檢修標(biāo)準(zhǔn)時(shí)間，并且在鐵路技術(shù)管理規(guī)程中也明確的要求了必須保證動(dòng)車組只有在技術(shù)狀態(tài)良好的情況下?lián)?dāng)運(yùn)輸任務(wù)，并且保證動(dòng)車組在檢修周期內(nèi)運(yùn)行，在檢修周期允許范圍內(nèi)要安排動(dòng)車組進(jìn)行相應(yīng)級(jí)別的檢修。我國動(dòng)車組的檢修包括一級(jí)檢修到五級(jí)檢修，在動(dòng)車運(yùn)用段所進(jìn)行的主要是一二級(jí)檢修。一級(jí)檢修作為動(dòng)車組日常檢查修理維護(hù)的手段，根據(jù)一級(jí)修規(guī)程規(guī)定，檢修里程按動(dòng)車組型號(hào)分為為4000km和5000km，并且允許有10%的上浮，檢修時(shí)間間隔為48h，即動(dòng)車組每兩天必須進(jìn)行一次一級(jí)修。這些因素都能影響動(dòng)車組交路的優(yōu)化。同時(shí)，檢修的影響還存在于動(dòng)車運(yùn)用段所的布局位置，因?yàn)橐患?jí)修的日常性，所以動(dòng)車組需要經(jīng)常出入動(dòng)車運(yùn)用段所，這里的運(yùn)行距離和時(shí)間在動(dòng)車組運(yùn)用效率的計(jì)算中，都是需要考慮的。最后，還有動(dòng)車運(yùn)用段所的檢修能力，它是影響動(dòng)車組運(yùn)用的關(guān)鍵因素。一級(jí)修在夜晚進(jìn)行，檢修能力與段所的設(shè)備數(shù)量、技術(shù)人員配置等客觀條件掛鉤，所以這些資源在不同動(dòng)車組段所的配置問題，也是一種優(yōu)化的思路。1.3動(dòng)車組交路計(jì)劃編制方法優(yōu)化模型及算法理論研究本節(jié)主要通過對查閱的資料進(jìn)行總結(jié)歸納，在有關(guān)動(dòng)車組交路編制方法的優(yōu)化的文獻(xiàn)中，對已有的常用的建模方法，進(jìn)行詳細(xì)的介紹和說明。通過研究發(fā)現(xiàn)，這些模型的建立都有著一些基本的共同點(diǎn)，但是，針對于不同的優(yōu)化目標(biāo)以及不同的約束條件，后續(xù)采用的設(shè)計(jì)的算法也是非常的多樣化。以下按不同模型的特點(diǎn)進(jìn)行介紹。1.1.1模型研究在針對一些特有的具有多個(gè)優(yōu)化目標(biāo)的編制方法時(shí)，需要建立的就不再是只有一個(gè)目標(biāo)函數(shù)的優(yōu)化模型了，需要建立的稱之為多目標(biāo)優(yōu)化模型。在此模型中，由于需要建立兩個(gè)及以上的目標(biāo)函數(shù)，使得問題的規(guī)模以及復(fù)雜程度都大幅上升。而出現(xiàn)這一問題的原因就在于，我國動(dòng)車組交路計(jì)劃的優(yōu)化方向不止一個(gè)，總結(jié)發(fā)現(xiàn)國內(nèi)研究的較多的優(yōu)化目標(biāo)有動(dòng)車組數(shù)量最小、動(dòng)車組接續(xù)時(shí)間最短、里程最大化等。1）運(yùn)用模式不同的模型我國動(dòng)車組的運(yùn)用方式經(jīng)過了長足的研究，進(jìn)過時(shí)間的磨礪和考驗(yàn)，現(xiàn)在還存在的有不固定區(qū)段、周期式運(yùn)用方式，同時(shí)還有雙修制下的動(dòng)車組運(yùn)用方式。不固定區(qū)段運(yùn)用方式的優(yōu)點(diǎn)在于可以把動(dòng)車組的利用效率提高到最大，而且，因?yàn)槭遣还潭▍^(qū)段，所以動(dòng)車組檢修的情況也可以同時(shí)考慮到，從而通過建立模型，找到動(dòng)車組運(yùn)用數(shù)量的最小數(shù)。但是也存在著問題，不固定區(qū)段運(yùn)用動(dòng)車組，意味著運(yùn)行線路比較復(fù)雜，動(dòng)車組周轉(zhuǎn)以及接續(xù)十分密集，出現(xiàn)不可避免的干擾時(shí)，無法進(jìn)行十分有效的調(diào)整?；蛘哒f調(diào)整起來比較困難。周期式運(yùn)用方式對比不固定方式，其運(yùn)行十分規(guī)律，對于運(yùn)輸計(jì)劃的組織十分有利，在這種情況下，模型的建立涉及的問題則變得比較多，如動(dòng)車組、存車線數(shù)量，動(dòng)車組段所分布情況都要進(jìn)行研究，目標(biāo)則是使用動(dòng)車組數(shù)量最小或動(dòng)車組使用的效率。雙修制，即以動(dòng)車組運(yùn)行時(shí)間和動(dòng)車組運(yùn)行里程兩個(gè)約束條件，作為標(biāo)準(zhǔn)來確定動(dòng)車組安全而高效的運(yùn)行狀況。在這種條件下，增加了交路計(jì)劃編制的難度，建立的優(yōu)化數(shù)學(xué)模型中，動(dòng)車組使用數(shù)量和檢修次數(shù)都會(huì)隨之增加。2）不同優(yōu)化思路的模型基于最優(yōu)接續(xù)網(wǎng)絡(luò)的動(dòng)車組交路計(jì)劃優(yōu)化算法，列車運(yùn)行過程中的接續(xù)時(shí)間是問題的關(guān)鍵，求解方法要求的是搜索的算法速度快，因此，動(dòng)車組使用數(shù)量少，才能達(dá)到總的列車運(yùn)行接續(xù)時(shí)間最短，從而完成找到最優(yōu)接續(xù)網(wǎng)絡(luò)。基于里程最大化，將優(yōu)化目標(biāo)定為動(dòng)車組運(yùn)行里程最大化和列車接續(xù)時(shí)間最小化，在動(dòng)車組一級(jí)檢修的里程周期和時(shí)間周期的約束條件下，運(yùn)用精確算法，對優(yōu)化目標(biāo)進(jìn)行精確化的求解?；诼范谓粨Q的模型，是將多基地動(dòng)車組的運(yùn)用計(jì)劃轉(zhuǎn)為多旅行商的問題，即TSP，模型需要構(gòu)造運(yùn)用計(jì)劃網(wǎng)絡(luò)，從而找到滿足所有約束條件的回路，得到可行的計(jì)劃。為此開發(fā)的算法稱之為概率局域搜索算法，算法可以在建立的網(wǎng)絡(luò)上搜索滿足約束條件且對比得出值最小的回路[19-21]。1.1.2算法研究前文已經(jīng)說明了，旅行商問題已被證明是一種NP-hard問題，用于解決這一問題的方法有許多，主要可根據(jù)問題的規(guī)模大小分為兩類，精確算法和啟發(fā)式算法。 ，當(dāng)遇到規(guī)模大的問題，精確算法的計(jì)算復(fù)雜性因?yàn)橹笖?shù)爆炸而急劇上升，反而無法在有限的時(shí)間內(nèi)做到最優(yōu)。而另一大類的啟發(fā)式算法，經(jīng)過許多學(xué)者的研究，可以通過針對不同的特征的問題，不斷的調(diào)整算法，直至算法可以達(dá)到在規(guī)定的時(shí)間內(nèi)做到最優(yōu)。目前已經(jīng)能比較熟練的運(yùn)用的啟發(fā)式算法也已經(jīng)在前文中列舉出來了，接下來對不同的算法，進(jìn)行詳細(xì)的分析。1）蟻群算法蟻群算法(AntcolonyAlgorithm,ACA)作為一種比較新型的模擬進(jìn)化算法,首次出現(xiàn)在1991年的第一屆歐洲人工生命會(huì)議上，由意大利的學(xué)者M(jìn).Dorigo、V.Maniezzo和A.Colorini等人提出，它的提出源于仿生物學(xué)家的觀察和研究發(fā)現(xiàn)：螞蟻群體能夠在互相協(xié)作的基礎(chǔ)上，找到巢穴和食物之間的最短的路徑，方法是每只螞蟻都能在運(yùn)動(dòng)的過程中在走過的路徑上留下一種可以被同一種群的螞蟻?zhàn)R別的外激素，其包含一些信息，能夠指引后來者找到更好地路徑，而經(jīng)過不斷的重復(fù)這一過程，最后形成正反饋，達(dá)到最優(yōu)。這一算法的優(yōu)點(diǎn)在于它采用的是分布并行的計(jì)算機(jī)制，可以結(jié)合其他方法，魯棒性比較強(qiáng)，但是，會(huì)經(jīng)常陷入局部最優(yōu)解，導(dǎo)致搜索解的時(shí)間變得更長，相比其他算法[22]。2）粒子群算法粒子群算法，全稱粒子群優(yōu)化算法，是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法，由J.Kennedy和R.C.Eberhart等開發(fā)的一種比較新型的進(jìn)化算法。由于其出現(xiàn)的比較晚，所以應(yīng)用在解決旅行商問題方面的研究比較少，但是其優(yōu)點(diǎn)也十分明顯，在于算法的實(shí)現(xiàn)比較容易、精度比較高、參數(shù)調(diào)整較少等方面，但是這種算法的收斂性還需要進(jìn)一步的研究，才可以更好的應(yīng)用到模型中[23]。3）禁忌搜索算法禁忌搜索算法（TabuSearch）是一種亞啟發(fā)式隨機(jī)搜索算法，首次在1986年由Glover提出，該算法通過一個(gè)初始可行解出發(fā)，并選擇多個(gè)特定的搜索方向進(jìn)行移動(dòng)，然后對比后得到目標(biāo)函數(shù)值最合適的那個(gè)移動(dòng)方向。該算法能防止陷入局部最優(yōu)的誤區(qū)，通過引入了禁忌準(zhǔn)則以及對已經(jīng)進(jìn)行的優(yōu)化進(jìn)行記憶和選擇，形成的表被稱為Tabu表。算法優(yōu)點(diǎn)在于局部的搜索能力很強(qiáng)，同時(shí)也有全局的迭代過程，但是缺點(diǎn)也很明顯，太過于依賴初始可行解，并且迭代的尋優(yōu)過程是比較單一的串行搜索[24]。4）模擬退火算法模擬退火算法的提出時(shí)間比較早，于1953年由Metropolis提出，但是真正將其應(yīng)用到組合優(yōu)化的領(lǐng)域是三十年后的1983的Kirkpatrick。這種算法來源于固體退火過程，固體經(jīng)過加熱達(dá)到一個(gè)初始溫度，然后經(jīng)過足夠長的時(shí)間，可以達(dá)到一個(gè)最后的溫度，即算法中的不斷進(jìn)行收斂達(dá)到的最優(yōu)解。這種算法在組合優(yōu)化領(lǐng)域