目錄PAGEi高鐵動車組交路優(yōu)化模型機求解研究中文摘要摘要：21世紀是中國飛速發(fā)展的時代，在“交通強國，鐵路先行”的強國理念下，我國高速鐵路的發(fā)展也是一日千里。而隨著高鐵的不斷發(fā)展，動車組的運行范圍不斷擴大，基礎建設和運營的成本在鐵路的投資上占了很大的比例，因此，如何提高動車組的運用效率直接關系到高鐵的經(jīng)濟效益。對此，作為運輸組織的核心計劃之一的動車組交路計劃，其優(yōu)化方法的研究具有重大的意義。本文通過綜合研究國內(nèi)和國外的動車組交路的相關文獻，分析了動車組交路的研究現(xiàn)狀。首先介紹了不同檢修條件下的動車組交路優(yōu)化研究，之后詳細介紹了我國對于動車組運用方面的研究和發(fā)展。然后開始對動車組交路計劃的編制優(yōu)化理論進行研究總結(jié)，從編制流程到動車組交路計劃的影響因素，再到優(yōu)化理論中的模型構建的方法以及求解模型的算法，為本文動車組交路優(yōu)化方法的研究打下堅實的基礎。模型構建采用借鑒經(jīng)典旅行商問題的思路，建立了一個包含多約束、多目標函數(shù)的優(yōu)化模型，通過分析求解的思路，最后采用精確算法中的CPLEX，并設計了合適的算例，對動車組交路優(yōu)化模型的有效性進行了檢驗。關鍵詞：高速鐵路；動車組；交路計劃；CPLEX目錄中文摘要 i目錄 iii1緒論 11.1研究背景及意義 11.2研究內(nèi)容安排 22高速鐵路動車組交路優(yōu)化研究現(xiàn)狀 32.1國外高速鐵路動車組交路優(yōu)化研究現(xiàn)狀 32.1.1考慮檢修的動車組交路優(yōu)化研究 32.1.2不考慮檢修的動車組交路優(yōu)化研究 32.2國內(nèi)高速鐵路動車組交路優(yōu)化研究現(xiàn)狀 42.2.1我國動車組運用方式 42.2.2我國動車組運用問題算法研究 52.2.3我國動車組運用其他方面的研究 62.3本章小結(jié) 63動車組交路計劃編制及優(yōu)化相關理論 73.1動車組交路計劃編制流程 73.2動車組交路計劃編制影響因素 83.2.1列車開行方案 83.2.2動車組類型 93.2.3動車組管理運用模式 93.2.4動車組檢修 93.3動車組交路計劃編制方法優(yōu)化模型及算法概述 103.3.1模型概述 103.3.2算法概述 113.4本章小結(jié) 134動車組交路計劃優(yōu)化模型建立 134.1模型建立的基礎 134.1.1模型構建分析 134.1.2旅行商問題的說明 144.1.3總結(jié) 154.2數(shù)學模型建立 154.2.1模型符號的定義 154.2.2約束條件描述 174.2.3目標函數(shù)確定 184.3優(yōu)化模型分析及求解探討 184.3.1整數(shù)規(guī)劃問題求解思路194.3.2多目標函數(shù)問題求解思路194.4本章小結(jié) 205動車組交路優(yōu)化模型求解研究 205.1算例數(shù)據(jù)確定 215.2算例計算結(jié)果 225.3本章小結(jié) 246總結(jié)與展望 246.1論文總結(jié) 246.2展望 25參考文獻 26正文緒論1.1研究背景及意義中國高速鐵路的發(fā)展的開端，對于不同的標準和定義，國內(nèi)外的說法也不一，但是，于2008年8月1日開通運營的京津城際，是真正意義上的第一條無任何爭議的，國內(nèi)外所公認的高速鐵路。截至2020年12月31日，中國的高速鐵路營業(yè)里程已達3.8萬公里，牢牢的占據(jù)著世界第一的位置。這離不開國家的大力支持，從2004年國務院審議通過的《中長期鐵路網(wǎng)規(guī)劃》（下文寫為《規(guī)劃》）中的“四縱四橫”到2016年進一步調(diào)整的《規(guī)劃》中的“八縱八橫”通道[1]，以及各類城際鐵路和區(qū)域連接線，終于形成了網(wǎng)絡化的高速鐵路線路，那么問題也隨著高鐵線路建設發(fā)展而來。高鐵動車組的管理也被鐵路部門越來越重視，其中動車組交路便是其中一環(huán)。動車組交路計劃與動車組運用計劃、檢修計劃并行，但是要編制動車組運用計劃與檢修計劃，動車組交路計劃的編制便是重要的基礎。下表1.1是一些數(shù)據(jù)（截止至2020年底），數(shù)據(jù)來源于《中國國家鐵路集團有限公司2020年統(tǒng)計公報》：表1-1我國高鐵動車組部分數(shù)據(jù)表名稱數(shù)據(jù)單位高鐵營業(yè)里程3.8萬公里高鐵新建里程2521公里全國動車組標準組3918組全國動車組輛數(shù)31340輛國有動車組標準組3828組國有動車組輛數(shù)30620輛從上表可看出，我國對于高鐵動車組的建設發(fā)展十分支持，投入也十分巨大。因此，針對我國動車組資源十分龐大的現(xiàn)狀，動車組交路的優(yōu)化所涉及的問題也十分復雜，例如動車組運用優(yōu)化就要考慮列車開行需求、動車組保有量、動車運用所駐留檢修能力、動車組檢修規(guī)程和動車組管理模式等條件的限制。本文就將對動車組交路編制的優(yōu)化方法問題進行研究。1.2研究內(nèi)容安排本文研究重點在于高鐵動車組交路的優(yōu)化方法及相關內(nèi)容，主要的研究內(nèi)容安排如下：第一章為緒論，用于描述本文的研究背景和意義，在我國高速鐵路飛速發(fā)展的背景下，通過對國內(nèi)外相關動車組運用的文獻的查閱，認識到動車組交路計劃編制優(yōu)化的重要性，以及涉及的各類影響因素，最后提出本文所要研究的主要內(nèi)容和結(jié)構安排。第二章為高速鐵路動車組交路相關問題的研究現(xiàn)狀，總結(jié)國內(nèi)外關于動車組交路優(yōu)化的研究思路和已有的研究成果，也包含所涉及的動車組運用方面的內(nèi)容。第三章為動車組交路編制的基本理論，這一章主要說明了動車組交路計劃的具體編制方法，以及優(yōu)化方法的一些基礎理論依據(jù)。包括動車組交路的編制流程的分析，影響因素的總結(jié)，以及對數(shù)學規(guī)劃的優(yōu)化模型和求解算法的說明。第四章為動車組交路優(yōu)化的數(shù)學規(guī)劃模型的建立，針對我國目前實際的動車組交路的計劃編制的優(yōu)化需要，建立合適的優(yōu)化模型。并對建立的模型進行分析以及求解思路的探討。第五章為動車組交路優(yōu)化模型的求解，即算例設計及求解分析，本章用于承接上一章中建立的數(shù)學規(guī)劃模型，通過設計出算例對建立的數(shù)學規(guī)劃模型進行應用，通過對得出的優(yōu)化結(jié)果分析，對建立的模型進行有效性的驗證。第六章為總結(jié)與展望，論文的工作總結(jié)部分簡單的描述了本文主要進行的工作，展望部分對本文研究過程中發(fā)現(xiàn)的問題、受到的啟發(fā)進行了總結(jié)。以下圖1.1是本文的研究路線圖：圖1-1研究路線圖正文2高速鐵路動車組交路優(yōu)化研究現(xiàn)狀2.1國外高速鐵路動車組交路優(yōu)化研究現(xiàn)狀根據(jù)查閱的資料進行的總結(jié)，可以得出國外的高速鐵路動車組交路優(yōu)化的研究，主要根據(jù)是否考慮檢修而分成以下兩大類。2.1.1考慮檢修的動車組交路優(yōu)化研究根據(jù)動車組交路的編制流程，檢修因素是其中重要的一環(huán)，在列車運行的過程中，這種約束作用回不斷的累加起來，又因為一般運用的數(shù)學規(guī)劃模型是線性的，所以無法去表述出來。根據(jù)國外的研究表明，一般對于這個約束，采用智能優(yōu)化算法或者是啟發(fā)式算法去處理，并且能獲得比較好的處理效果。其中啟發(fā)式算法是相對于最優(yōu)化算法提出的，它主要以仿自然體算法為主，主要包括蟻群算法、神經(jīng)網(wǎng)絡、模擬退火法等。Tomoshi于2011年也是最早提出啟發(fā)式搜索方法，他建立的模型是集合劃分的多商品流模型，針對附加檢修約束的動車組交路計劃編制問題，能在比較短的時間內(nèi)獲得近優(yōu)解[2]。Yasutaka在2012年提出的結(jié)合局部搜索的蟻群算法，主要針對違反軟約束數(shù)量最小這一條件的動車組交路計劃編制問題，當然，這也是包括了定期檢修的約束的[3]。Zhou等人在2017年采用了多種群的遺傳算法，對建立的優(yōu)化模型進行的求解，模型的優(yōu)化目標是和動車組效率密不可分的列車接續(xù)時間以及檢修的成本，最后達到的效果也比較理想[4]。Lusby等人在2017年也提出了一個數(shù)學模型關于基礎路徑的描述，此模型能比較容易地處理檢修相關的約束條件[5]。2.1.2不考慮檢修的動車組交路優(yōu)化研究關于不考慮檢修的動車組交路計劃編制問題，一般是基于多商品流理論去建立數(shù)學規(guī)劃模型，然后使用經(jīng)典精確算法或者是商用優(yōu)化引擎來求解。多商品流理論是網(wǎng)絡流理論的發(fā)展過程中出現(xiàn)的，在鐵路的車流分配以及車流徑路的優(yōu)化等方面有較多的應用。國外的研究學者在做優(yōu)化動車組交路計劃的課題時，絕大部分是采用多商品流理論進行建模，十分貼合實際的著重考慮客流需求，包含重聯(lián)分解的過程，也把動車組的運用效率、服務質(zhì)量、運營成本等比較實際的作為優(yōu)化目標。采用的求解工具為CLPEX，CPLEX是一種數(shù)學優(yōu)化技術，主要用于提高效率、快速實現(xiàn)策略并提高收益率，它可將一些復雜的業(yè)務問題換一種表現(xiàn)形式，變?yōu)閿?shù)學規(guī)劃模型，并找到這個模型的解決方案[6]。2.2國內(nèi)高速鐵路動車組交路優(yōu)化研究現(xiàn)狀因為國內(nèi)高速鐵路的起步比較晚，所以早期有關于動車組交路的編制方法是在借鑒國外研究成果之上的，但是隨著我國高鐵的發(fā)展，路網(wǎng)規(guī)模越來越大，后面的研究也越來越切合我國動車組運用管理的實際需求。2.2.1我國動車組運用方式在我國發(fā)展動車組之前，普速列車的既有線全部是采用固定運用方式來進行機車周轉(zhuǎn)，但是動車組運用的方式對比于普速列車，有著它的特殊性，國內(nèi)學者對此也進行了深入的研究。動車組運用方式研究最早可追溯到1998年，趙鵬等人針對動車組運用方式對比研究了固定式、不固定式和半固定式，三種方式，得出的結(jié)論是半固定式最佳。并且還根據(jù)研究，添加了實際的約束條件，例如站間固定、區(qū)段套跑[7]。直到2002年，蘭淑梅等研究發(fā)現(xiàn)，動車組駛出檢修段所后，可以在多個不同的方向上擔當若干次往返作業(yè)，直至到達定下的運行公里數(shù)去最近的段所檢修，這種新型動車組運行方式也被稱為環(huán)形運轉(zhuǎn)方式[8]。為了進一步加強動車組運用的規(guī)律性，同時滿足能解決維修段所等基地的零部件和人員的配置問題，耿敬春等于2006年提出一種周期式動車組運用方式。在此基礎上，簇式運用方式由花偉等在2010年提出，這種方式可以滿足日常檢修和定期檢修的安排，還可以進一步提高運用效率，對比周期方式也有更大的活動范圍，這對于整個動車組周轉(zhuǎn)系統(tǒng)有著更為協(xié)調(diào)的作業(yè)[9]。動車組運用方式的研究，是我國高鐵動車組發(fā)展的縮影，從最初的對比研究到后面一代又一代的更替，動車組運用越來越科學合理。2.2.2我國動車組運用問題算法研究我國動車組運用面對的問題比較多，也比較雜，所以針對有著不同約束條件的不同的問題，我國學者的研究方向也不盡相同。但是對于算法的研究里，大多是啟發(fā)式算法，例如模擬退火算法和蟻群算法等。同時，還針對了具體不同的約束條件，進行了具體的分析建模，例如動車組周轉(zhuǎn)的整數(shù)規(guī)劃模型，并采用兩階段的啟發(fā)式算法求解。張杰等在2006年，對于動車組的運用問題，有意的將動車組運用計劃轉(zhuǎn)化為交路段生成以及交路生成兩個問題，然后提出了新的解決思路，即運用緊湊接續(xù)算法研究，動車組運用問題經(jīng)過了分解轉(zhuǎn)化的過程，算法的選用也比較合理，最后求解的復雜性在所有有意去鋪墊的條件下顯著的下降[10]。王瑩等于2009年針對客運專線中動車組運用計劃以及檢修計劃所涉及的相關影響因素，采用列生成算法，描述出了此問題的動態(tài)變化的特點。主要涉及的是“以車定線”和“以車調(diào)線”兩種優(yōu)化理論方法。接著在2010年，王瑩等通過建立數(shù)學規(guī)劃模型嘗試優(yōu)化動車組運用時，研究在優(yōu)化模型的約束條件遠小于決策變量的特定條件下，通過設計分支定價算法，對案例進行分析發(fā)現(xiàn)，動車組的運用效率只有在檢修能力和備用車數(shù)量相匹配時才能達到最大化[11]。關于模擬退火算法的研究，郭海燕等早在2007年，首先考慮了將動車組運用問題轉(zhuǎn)化為旅行商問題（TSP），并且通過實際嘗試各類優(yōu)化算法，綜合考慮各類算法的特點，研究認為模擬退火算法是解決問題的最佳算法。后續(xù)張洪雨在2020年再次運用模擬退火算法，針對動車組交路計劃優(yōu)化的研究，建立起數(shù)學規(guī)劃模型，選取武深高鐵網(wǎng)絡以及列車時刻表的數(shù)據(jù)進行了仿真模擬，將得出的結(jié)果與人工方法進行對比，發(fā)現(xiàn)在交路數(shù)量相同的情況下，人工方法的檢修次數(shù)比模擬退火算法多了一次，這就大大降低了動車組的利用率，檢修成本也大大增加[12]。關于蟻群算法的研究，2009年佟璐等同樣采用將動車組運用問題轉(zhuǎn)化為旅行商問題（TSP）的方法，進而運用蟻群算法去求解。在研究過程中，根據(jù)目標，一是要滿足動車組維修需求的同時盡量減少動車組的使用數(shù)量，第二個目標是還要有利于動車組調(diào)度與調(diào)整,考慮到動車組運用的均衡性，建立起數(shù)學模型，然后選取武廣客運專線的數(shù)據(jù)，包括基礎的線路數(shù)據(jù)以及列車運行的數(shù)據(jù)，通過蟻群算法，到達了在動車組維修的需求滿足下，動車組維修次數(shù)最小的結(jié)果，從而提高動車組的利用率。2013年李華等通過歸納總結(jié)蟻群算法的思路，針對動車組交路優(yōu)化求解問題的一些特點，把算法的主要內(nèi)容進行了改進，包括蟻群算法的解的構造、路徑選擇與回路生成、信息素更新和總體的步驟優(yōu)化[13]。2.2.3我國動車組運用其他方面的研究基于最優(yōu)接續(xù)網(wǎng)絡的動車組交路計劃優(yōu)化模型與算法研究中，苗建瑞等（2012）在列車運行圖已知的條件下，通過建立多目標的整數(shù)規(guī)劃模型，設計了基于動車組運用數(shù)量最少的接續(xù)網(wǎng)絡分層優(yōu)化啟發(fā)式算法，算法的驗證采用的是廣深線的數(shù)據(jù)，結(jié)論是方法可用于求解動車組交路計劃的最優(yōu)解[14]。基于里程最大化的動車組交路計劃優(yōu)化方法中，李建等（2017）考慮的是在動車組一級檢修的里程周期和時間周期的約束條件下，將優(yōu)化目標定為動車組運行里程最大化和列車接續(xù)時間最小化，建立0-1整數(shù)規(guī)劃模型，采用設計小型動車組交路計劃編制算例的方法，通過Lingo11.0數(shù)學規(guī)劃軟件進行了精確求解，最后結(jié)論也說明了此種方法適用于小型規(guī)模的動車組交路計劃的優(yōu)化，針對大型交路計劃的優(yōu)化，還需要探索啟發(fā)式算法的設計來解決問題[15]。基于到發(fā)線運用的動車組交路計劃優(yōu)化方法研究中，孫靜霞等描述了在現(xiàn)存的車站到發(fā)線數(shù)量不足、到發(fā)線運用計劃不完善的實際情況下，動車組交路計劃的編制也存在著問題。該文章通過確定優(yōu)化目標為以最少的動車組數(shù)量來完成相應的鐵路運輸任務，在運行圖已知的情況下，構建起動車組接續(xù)網(wǎng)絡，建立模型。后續(xù)將京津城際的實際線路數(shù)據(jù)代入模型，采用IBMILOGCPLEXOptimizationStudioV12.3軟件進行求解，最終結(jié)論驗證了模型的可行性[16]。2.3本章小結(jié)本章按國外和國內(nèi)的相關動車組交路計劃的研究進行總結(jié)，國外的研究主要分為兩大類，即是否考慮檢修的動車組運用問題，由此對應的算法也不盡相同。而國內(nèi)的研究則比較多樣化，但是可以從我國動車組的發(fā)展歷程來總結(jié)。從初期的研究動車組的基礎的運用方式，到對動車組交路計劃編制的基本理論的完善，最后開始對動車組交路計劃優(yōu)化方法和算法研究的不斷深入，可以看出我國對動車組交路計劃優(yōu)化的研究已經(jīng)到了一個比較成熟的階段，無論是模型的建立還是算例的模擬，以及運用智能軟件來求解，都還有很大的領域去探索，去發(fā)掘。正文3動車組交路計劃編制及優(yōu)化相關理論動車組交路計劃是動車組運用問題的核心基礎，主要對象是機車車輛，所以交路計劃可以定義為編制出機車車輛或者說是動車組的列車接續(xù)計劃，并且滿足現(xiàn)有的各種約束條件，例如檢修能力的約束。交路計劃要求能按照已經(jīng)制定的動車組運用、檢修管理的模式，在一定的時間和線路范圍內(nèi)，完成按照列車運行圖上制定的列車任務，而交路計劃的優(yōu)化，則是在完成任務的基礎上，進一步的達到車底數(shù)量最少、旅客坐席需求的完全滿足以及檢修次數(shù)最少等目標。3.1動車組交路計劃編制流程第一種編制流程是比較常用的，基于列車運行圖和相關的動車組運用管理模式規(guī)定來編制動車組交路計劃。我國現(xiàn)有的動車組運用客觀條件有：建成的動車組段所數(shù)量較少、間隔距離較長、布局也比較分散，同時動車組保有數(shù)量少、動車組的車型多且雜等。而具體的動車組運用措施手段有：動車組檢修采用雙修制、檢修需要回到配屬段所等。這種編制流程需要的是綜合考慮到各個限制因素，來優(yōu)化編制動車組交路計劃[17]。圖3-1編制流程一第二種編制流程，涉及動車組交路和列車運行圖的協(xié)調(diào)優(yōu)化，這就需要同時編制出動車組交路計劃以及列車運行計劃。此編制流程的首要目標是達到最大的動車組運行效率，同時滿足旅客出行的需求，因為涉及旅客的需求變化，從而比較少采用這種編制流程作為優(yōu)化動車組交路計劃的思路。但是在我國當前高鐵陸續(xù)建成的情況下，需要對新開通的線路進行編制動車組運用計劃時，就可以滿足列車開行方案的時刻表上的寬松限制，通過協(xié)調(diào)優(yōu)化來同時編制列車運行圖以及動車組交路計劃，完成優(yōu)化動車組交路計劃的目的。圖3-2編制流程二3.2動車組交路計劃編制影響因素動車組交路計劃作為動車組運用計劃的核心和基礎，其編制離不開我國運輸組織過程中的分階段、分級的方法。由于其編制是采用這種層層進行的方式，所以，在編制動車組交路計劃時，就不能只是考慮這單獨的一個計劃編制的影響因素，還要縱向的分析從最初的宏觀的策略規(guī)劃層到最末端的微觀的實際實施層，如列車開行方案等環(huán)節(jié)。3.2.1列車開行方案鐵路旅客列車開行方案確定旅客列車運行區(qū)段、列車種類、徑路、開行對數(shù)及車底擔當局的計劃，其中，旅客列車的始發(fā)站、終到站及經(jīng)由線路構成旅客列車的運行區(qū)段，列車種類區(qū)別出列車不同的等級或性質(zhì)，開行對數(shù)的多少表示行車量的大小。列車開行方案的確定，則是在客流量的基礎上，即按流開車。列車開行方案能直接影響列車運行圖的質(zhì)量，進而會影響到動車組交路計劃的編制。列車開行方案作為運輸組織計劃的一個重要的輸入條件，它包含的內(nèi)容十分多樣，為達到減少動車組數(shù)量，會影響開行長距離的列車的列數(shù)，同時，又要要求列車運行圖中的列車時刻安排合理，那么，動車組折返、接續(xù)次數(shù)會減少，從而達到另一個目的，即動車組接續(xù)時間減少。由此可以得出，動車組交路計劃的優(yōu)化離不開列車開行方案，只有確定好一個合理的列車開行方案，動車組的運用效率才能盡可能的提高。動車組的列車開行方案的確定，離不開對我國實際情況的分析。我國正處于規(guī)劃和修建高速鐵路的高峰時期，每年新增的高鐵營業(yè)里程正不斷的擴大我國的高鐵客運服務網(wǎng)，對此，列車開行方案的制定離不開對客流屬性的分析。根據(jù)不同的客流規(guī)模和特性，制定的開行方案中的列車類型、開行距離、開行密度等都有差異，這也就更需要充分的考慮列車運行線的長短、列車擔當任務、檢修任務安排等，力求達到對動車組運用時間的最大化，減少動車組的空費、無效的檢修等待時間，從而在降低運營成本的方面提高動車組的利用率。3.2.2動車組類型我國動車組的發(fā)展時間雖然不算長，但是進步是巨大的，其中動車組的類型也是隨之增加。其中主要是CRH系列動車組，這一系列又分為CRH1、CRH2、CRH3、CRH5，四個主型號，而根據(jù)動車組運營的時速、定員數(shù)量、編組等不同，主型號下又分為若干個子型號。在交路計劃編制的過程中，要求的是同一交路內(nèi)運行線上必須是同一類型的動車組，因此，動車組交路計劃就需要根據(jù)不同的動車組型號進行單獨編制。動車組型號的影響也可以根據(jù)我國現(xiàn)在的高鐵路網(wǎng)來分析，不同的線路根據(jù)其客流的不同，規(guī)劃開行的動車組必定有差異，這就要求尋找最為適合某一線路的動車組型號，不過一般線路修建前的規(guī)劃中，都會有建成后開行運營的動車組數(shù)據(jù)，所以動車組類型對于動車組交路優(yōu)化的影響，就在于如何做到在同一交路計劃內(nèi)，采用最合適的動車組型號達到交路計劃最優(yōu)。3.2.3動車組管理運用模式自從我國鐵路改革為國鐵集團，即中國鐵路總公司，所屬的18個鐵路局也變更為中國鐵路某局集團有限公司，之后，我國動車組的管理變得更加的明確合理，動車組由鐵路總公司購買配置，滿足各鐵路局的需求。之后，各大鐵路局擁有動車組的分配權，可將動車組配屬到下屬的動車組運用段所。由此可以看出，這種管理運用的模式的優(yōu)點十分明顯，即各鐵路局各自管理、獨立使用的好處在于責任明確、檢修質(zhì)量得到了保障，同時，問題也存在，就是動車組的運用比較固定僵化，一些可以共用的檢修備用資源，不能充分利用，還有遇到特殊緊急情況時，不能進行靈活的調(diào)整，去最快的解決問題。按照我國鐵路總公司以及各大鐵路局集團、客專公司的管理模式，編制動車組交路計劃需要明確動車組的歸屬，以及動車組在接續(xù)時的選擇問題，這會直接影響動車組的利用效率，交路計劃必須考慮到這一問題[18]。3.2.4動車組檢修動車組檢修是動車組交路計劃編制同樣不可忽略的一大因素。檢修環(huán)節(jié)是保證動車組安全、高效執(zhí)行列車任務的必要手段，我國出臺的動車組檢修規(guī)程，里面明確的規(guī)定了各類動車組不同級別的檢修內(nèi)容、檢修周期和檢修標準時間，并且在鐵路技術管理規(guī)程中也明確的要求了必須保證動車組只有在技術狀態(tài)良好的情況下?lián)斶\輸任務，并且保證動車組在檢修周期內(nèi)運行，在檢修周期允許范圍內(nèi)要安排動車組進行相應級別的檢修。我國動車組的檢修包括一級檢修到五級檢修，在動車運用段所進行的主要是一二級檢修。一級檢修作為動車組日常檢查修理維護的手段，根據(jù)一級修規(guī)程規(guī)定，檢修里程按動車組型號分為為4000km和5000km，并且允許有10%的上浮，檢修時間間隔為48h，即動車組每兩天必須進行一次一級修。這些因素都能影響動車組交路的優(yōu)化。同時，檢修的影響還存在于動車運用段所的布局位置，因為一級修的日常性，所以動車組需要經(jīng)常出入動車運用段所，這里的運行距離和時間在動車組運用效率的計算中，都是需要考慮的。最后，還有動車運用段所的檢修能力，它是影響動車組運用的關鍵因素。一級修在夜晚進行，檢修能力與段所的設備數(shù)量、技術人員配置等客觀條件掛鉤，所以這些資源在不同動車組段所的配置問題，也是一種優(yōu)化的思路。3.3動車組交路計劃編制方法優(yōu)化模型及算法理論研究本節(jié)主要通過對查閱的資料進行總結(jié)歸納，在有關動車組交路編制方法的優(yōu)化的文獻中，對已有的常用的建模方法，進行詳細的介紹和說明。通過研究發(fā)現(xiàn)，這些模型的建立都有著一些基本的共同點，但是，針對于不同的優(yōu)化目標以及不同的約束條件，后續(xù)采用的設計的算法也是非常的多樣化。以下按不同模型的特點進行介紹。3.3.1模型研究在針對一些特有的具有多個優(yōu)化目標的編制方法時，需要建立的就不再是只有一個目標函數(shù)的優(yōu)化模型了，需要建立的稱之為多目標優(yōu)化模型。在此模型中，由于需要建立兩個及以上的目標函數(shù)，使得問題的規(guī)模以及復雜程度都大幅上升。而出現(xiàn)這一問題的原因就在于，我國動車組交路計劃的優(yōu)化方向不止一個，總結(jié)發(fā)現(xiàn)國內(nèi)研究的較多的優(yōu)化目標有動車組數(shù)量最小、動車組接續(xù)時間最短、里程最大化等。1）運用模式不同的模型我國動車組的運用方式經(jīng)過了長足的研究，進過時間的磨礪和考驗，現(xiàn)在還存在的有不固定區(qū)段、周期式運用方式，同時還有雙修制下的動車組運用方式。不固定區(qū)段運用方式的優(yōu)點在于可以把動車組的利用效率提高到最大，而且，因為是不固定區(qū)段，所以動車組檢修的情況也可以同時考慮到，從而通過建立模型，找到動車組運用數(shù)量的最小數(shù)。但是也存在著問題，不固定區(qū)段運用動車組，意味著運行線路比較復雜，動車組周轉(zhuǎn)以及接續(xù)十分密集，出現(xiàn)不可避免的干擾時，無法進行十分有效的調(diào)整?；蛘哒f調(diào)整起來比較困難。周期式運用方式對比不固定方式，其運行十分規(guī)律，對于運輸計劃的組織十分有利，在這種情況下，模型的建立涉及的問題則變得比較多，如動車組、存車線數(shù)量，動車組段所分布情況都要進行研究，目標則是使用動車組數(shù)量最小或動車組使用的效率。雙修制，即以動車組運行時間和動車組運行里程兩個約束條件，作為標準來確定動車組安全而高效的運行狀況。在這種條件下，增加了交路計劃編制的難度，建立的優(yōu)化數(shù)學模型中，動車組使用數(shù)量和檢修次數(shù)都會隨之增加。2）不同優(yōu)化思路的模型基于最優(yōu)接續(xù)網(wǎng)絡的動車組交路計劃優(yōu)化算法，列車運行過程中的接續(xù)時間是問題的關鍵，求解方法要求的是搜索的算法速度快，因此，動車組使用數(shù)量少，才能達到總的列車運行接續(xù)時間最短，從而完成找到最優(yōu)接續(xù)網(wǎng)絡?；诶锍套畲蠡?，將優(yōu)化目標定為動車組運行里程最大化和列車接續(xù)時間最小化，在動車組一級檢修的里程周期和時間周期的約束條件下，運用精確算法，對優(yōu)化目標進行精確化的求解。基于路段交換的模型，是將多基地動車組的運用計劃轉(zhuǎn)為多旅行商的問題，即TSP，模型需要構造運用計劃網(wǎng)絡，從而找到滿足所有約束條件的回路，得到可行的計劃。為此開發(fā)的算法稱之為概率局域搜索算法，算法可以在建立的網(wǎng)絡上搜索滿足約束條件且對比得出值最小的回路[19-21]。3.3.2算法研究前文已經(jīng)說明了，旅行商問題已被證明是一種NP-hard問題，用于解決這一問題的方法有許多，主要可根據(jù)問題的規(guī)模大小分為兩類，精確算法和啟發(fā)式算法。 ，當遇到規(guī)模大的問題，精確算法的計算復雜性因為指數(shù)爆炸而急劇上升，反而無法在有限的時間內(nèi)做到最優(yōu)。而另一大類的啟發(fā)式算法，經(jīng)過許多學者的研究，可以通過針對不同的特征的問題，不斷的調(diào)整算法，直至算法可以達到在規(guī)定的時間內(nèi)做到最優(yōu)。目前已經(jīng)能比較熟練的運用的啟發(fā)式算法也已經(jīng)在前文中列舉出來了，接下來對不同的算法，進行詳細的分析。1）蟻群算法蟻群算法(AntcolonyAlgorithm,ACA)作為一種比較新型的模擬進化算法,首次出現(xiàn)在1991年的第一屆歐洲人工生命會議上，由意大利的學者M.Dorigo、V.Maniezzo和A.Colorini等人提出，它的提出源于仿生物學家的觀察和研究發(fā)現(xiàn)：螞蟻群體能夠在互相協(xié)作的基礎上，找到巢穴和食物之間的最短的路徑，方法是每只螞蟻都能在運動的過程中在走過的路徑上留下一種可以被同一種群的螞蟻識別的外激素，其包含一些信息，能夠指引后來者找到更好地路徑，而經(jīng)過不斷的重復這一過程，最后形成正反饋，達到最優(yōu)。這一算法的優(yōu)點在于它采用的是分布并行的計算機制，可以結(jié)合其他方法，魯棒性比較強，但是，會經(jīng)常陷入局部最優(yōu)解，導致搜索解的時間變得更長，相比其他算法[22]。2）粒子群算法粒子群算法，全稱粒子群優(yōu)化算法，是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法，由J.Kennedy和R.C.Eberhart等開發(fā)的一種比較新型的進化算法。由于其出現(xiàn)的比較晚，所以應用在解決旅行商問題方面的研究比較少，但是其優(yōu)點也十分明顯，在于算法的實現(xiàn)比較容易、精度比較高、參數(shù)調(diào)整較少等方面，但是這種算法的收斂性還需要進一步的研究，才可以更好的應用到模型中[23]。3）禁忌搜索算法禁忌搜索算法（TabuSearch）是一種亞啟發(fā)式隨機搜索算法，首次在1986年由Glover提出，該算法通過一個初始可行解出發(fā)，并選擇多個特定的搜索方向進行移動，然后對比后得到目標函數(shù)值最合適的那個移動方向。該算法能防止陷入局部最優(yōu)的誤區(qū)，通過引入了禁忌準則以及對已經(jīng)進行的優(yōu)化進行記憶和選擇，形成的表被稱為Tabu表。算法優(yōu)點在于局部的搜索能力很強，同時也有全局的迭代過程，但是缺點也很明顯，太過于依賴初始可行解，并且迭代的尋優(yōu)過程是比較單一的串行搜索[24]。4）模擬退火算法模擬退火算法的提出時間比較早，于1953年由Metropolis提出，但是真正將其應用到組合優(yōu)化的領域是三十年后的1983的Kirkpatrick。這種算法來源于固體退火過程，固體經(jīng)過加熱達到一個初始溫度，然后經(jīng)過足夠長的時間，可以達到一個最后的溫度，即算法中的不斷進行收斂達到的最優(yōu)解。這種算法在組合優(yōu)化領域比較通用，理論上具有概率的全局優(yōu)化性能，可以達到有效的避免陷入局部極小的結(jié)果，但是缺點的在于解決規(guī)模比較大的實際問題時，雖然有模擬退火的冷卻進度表，但還是無法明顯的縮短算法求解的時間[25]。5）遺傳算法遺傳算法(GeneticAlgorithm,GA)，由美國的Johnholland教授通過分析大自然中生物進化規(guī)律而設計出的計算模型，基本思路是模擬自然進化過程來進行搜索最優(yōu)解的方法。其中，優(yōu)化問題的求解過程可以類比成生物體進化的染色體基因的交叉和變異。這種優(yōu)化算法可以針對傳統(tǒng)算法無法解決的復雜的非線性問題，能較快的得出比較好的優(yōu)化的結(jié)果[26]。3.4本章小結(jié)本章分為動車組交路計劃的編制流程、影響因素以及對優(yōu)化過程中的模型初步的介紹三部分內(nèi)容。編制流程部分主要介紹了兩種方法，一是在列車運行圖的基礎上去編制動車組交路計劃，二是列車運行圖未知或者需要調(diào)整的時候，同時進行列車運行圖的鋪畫和動車組交路計劃的編制，這樣可以更加的協(xié)調(diào)的進行，也達到優(yōu)化的目的。影響因素部分從列車開行方案講到動車組的型號等實際條件，進一步明確了編制動車組交路計劃的一些前提和約束條件。后續(xù)關于優(yōu)化模型的建立，對現(xiàn)有的研究動車組交路優(yōu)化的模型進行簡單的對比，從而為本文后續(xù)建立研究模型打下基礎。4動車組交路計劃優(yōu)化模型建立本章在前文研究說明的基礎上，正式進行動車組交路計劃優(yōu)化模型的建立，模型建立的過程中，首先是基礎的描述，包括計劃編制問題的特征、以及旅行商問題的描述等，然后是模型建立過程中重要的部分，包括符號的定義、約束條件的描述以及目標函數(shù)的確定。最后是模型的分析以及求解方式的確定。4.1模型建立的基礎4.1.1模型構建分析針對動車組交路計劃編制問題構建合理的數(shù)學規(guī)劃模型，需要考慮的是各列車運行線之間的滿足的接續(xù)條件和符合我國動車組檢修要求，然后把列車運行圖中的運用任務對其進行組合，模型構建的基本假設和前提如下[27-29]：1）列車運行圖確定是基礎條件，包括了所有的運行線路的數(shù)據(jù)，如始發(fā)和終到車站、時刻以及各站的停留時間；2）動車組交路的總的走行時間和總的走行公里數(shù)滿足我國的一級檢修周期的范圍；3）列車在同一交路內(nèi)進行相互接續(xù)，必須滿足接續(xù)的條件。對于相互接續(xù)的列車，相鄰運行線之間的接續(xù)時間也必須符合接續(xù)的時間上的要求。動車組運用效率的影響因素十分復雜，根據(jù)前文的說明，一些硬性的約束已經(jīng)確定，還存在一些可以優(yōu)化的參數(shù)，接下來將對其進行確定：1）動車組運用方式：由前文對不同動車組運用方式的詳細分析，從固定式到周期式，不同的方式有著其不同的優(yōu)劣，適用的條件也不盡相同，本文擬采用周期性運用方式作為后續(xù)研究的基礎；2）檢修情況：檢修作為一個對動車組交路計劃編制影響力最大的因素之一，其情況需要特別的進行確定。那么本文中關于檢修的情況說明如下：各個檢修基地的建設情況以及布局是確定的，檢修的能力按照每個檢修基地所配置的固定設備確定最大的檢修能力；3）空車回送：空車回送情況存在于后續(xù)列車的始發(fā)車站和前面的列車的終到站不是同一個車站，后續(xù)建立的模型中是允許存在動車組空車回送的情況的，但是也有限制條件的約束，及兩車站距離的限制；4）重聯(lián)問題：本文建立的模型不考慮動車組的重聯(lián)問題。動車組交路計劃編制就是根據(jù)列車運行線之間的接續(xù)條件和檢修要求，將若干列車運行線連接在一起，形成動車組在一次檢修周期內(nèi)的運用內(nèi)容。將各運行線看作點，各運行線之間的接續(xù)看作走行路徑，那么可以把動車組交路問題看作類似旅行商問題，動車組完成運用任務就像旅行商在城市間穿行。4.1.2旅行商問題的說明旅行商問題，也可以稱之為旅行推銷員問題，是一個經(jīng)典的組合優(yōu)化問題，它的定義是：給定了一系列城市和每兩座城市之間的距離，一個旅行商要訪問每一座城市一次并回到起始城市，要求找到達到要求的最短回路。它是組合優(yōu)化中的一個NP難問題，在運籌學和理論計算機科學中非常重要。圖4-1旅行商問題簡圖4.1.3總結(jié)通過前兩個部分的分析和說明，總結(jié)可知，首先本文的動車組交路計劃編制是選取的是第一種編制流程，在列車運行圖確定的基礎上編制，即所有運行線的始發(fā)終到車站和時刻、途經(jīng)車站和停留時間已經(jīng)確定，其次是考慮檢修的動車組交路優(yōu)化模型，因此另一個硬性約束是動車組交路的總走行公里和走行時間必須在一級檢修周期范圍內(nèi)。接下來對于其他的計劃編制的特征以及參數(shù)約束，例如列車接續(xù)條件，也進行了確定和說明。動車組交路計劃編制在這種條件下，成為了一種特殊的旅行商問題（TSP），特殊在于旅行商在旅行過程中走行距離達到一定值時就必須休息，即完成動車組的檢修作業(yè)。由此進入下一步，數(shù)學模型的正式構建。4.2數(shù)學模型建立數(shù)學模型的構建，分為符號的定義、構建列車接續(xù)網(wǎng)絡、約束條件的具體描述以及確定目標函數(shù)。4.2.1模型符號的定義首先，是一些需要說明的集合以及參數(shù)符號，符號的定義如下表4-1所示：表4-1集合及參數(shù)符號定義名稱符號動車組集合L={l1,l2…ln}動車組始發(fā)、終到車站Sid、Sit動車組始發(fā)、終到時間tid、tit動車組車型ci動車組走行里程ri車站間折返作業(yè)最小時間Tmin空車回送的接續(xù)時間T1說明：空車回送的接續(xù)時間存在一個最長時間，記為Tmax，是一個常量，當空車回送的接續(xù)時間等于或者大于Tmax時，不允許空車回送，即T1≥Tmax。根據(jù)我國動車組檢修的規(guī)程，動車組一級檢修的對應的檢修時間約束是48小時，記為Tx，一級檢修對應的里程約束是4000公里，記為Sx，波動范圍確定為±10%，記為±Δs。一級檢修的標準作業(yè)時間是120分鐘，加上在檢修基地停留的時間，定為150分鐘，記為T2，動車組在車站和動車組檢修的動車組運用所之間運行的時間記為T3。定義動車組之間的車型匹配的變量為ψij，當動車組li和lj的車型符合接續(xù)條件時，ψij值為1，否則為0。定義列車運行線之間是否可以進行空車回送，然后進行列車的接續(xù)，匹配的變量為φij，當列車li始發(fā)車站和lj的終到車站之間的距離太遠，導致接續(xù)時間不滿足所允許的最大接續(xù)時間，值為0，否則為1。定義動車組從上次一級檢修結(jié)束后，實際的走行公里數(shù)的變量為Sa，實際的走行時間變量為Ta。定義列車li和lj之間接續(xù)時間為eij，根據(jù)以上的定義，可列出以下eij的數(shù)學表達形式：eij=t定義兩條動車組運行線li和lj之間是否可以安排一級檢修的匹配變量εij，當eij≥T2+T3時，εij值為1，否則為0。模型構建過程，將進行動車組一級檢修的動車組運用所看成特殊的車站，定義某一車站是否可以進行一級檢修的匹配變量為γi，當動車組li的終到車站是動車運用所時，γi值為1，否則為0。決策變量的定義，主要包含兩個，一是列車運行線之間的接續(xù)的變量，定義為xij，二是動車組線路之間是否進行安排一級檢修，定義為yij，以下是兩個決策變量的數(shù)學表達式：xij=1yij=14.2.2約束條件描述動車組交路計劃的編制影響因素復雜且眾多，第一部分的影響因素是硬件和設備上的，例如如動車組的類型、動車組檢修基地的分布情況、規(guī)模大小以及其檢修能力，另一部分影響因素，是一些理論文字上的，包括了動車組運用方式、檢修的具體規(guī)定、動車組運行范圍等，下面對本文要建立的模型的約束條件進行具體的描述：運用約束條件(4.4)即只有在高速鐵路動車組的車型以及空車回送的條件得到滿足時，動車組li和lj才被允許接續(xù)。檢修約束條件(4.5)(4.6)根據(jù)前文的基礎，此模型針對的動車組編制計劃只考慮動車組一級檢修的約束，即動車組在上一次一級檢修結(jié)束開始，累計的走行里程和時間到達檢修規(guī)程規(guī)定的值時，需要進行檢修，才可繼續(xù)進行任務。(4.7)此表達式表示動車組一級檢修的時間必須考慮到檢修時間與動車組從車站到維修基地的花費的時間。(4.8)此表達式表示動車組進行檢修必須在可以進行檢修的車站，即動車組運用所進行。3）唯一性的約束條件(4.9)(4.10)根據(jù)動車組交路計劃的編制理論，動車組需要完成列車運行圖規(guī)定的所有運用任務，同時，一個動車組同一個時間只能擔當一條運行線路。4.2.3目標函數(shù)確定根據(jù)模型建立的條件和實際的要求，為提高編制動車組交路計劃時，動車組的利用率，同時盡可能的減少動車組的使用的數(shù)量，從而達到減少動車組檢修的成本，提高高速鐵路的運營效率的目的，因此建立以下兩個目標函數(shù)：動車組運行線之間接續(xù)時間最短(4.11)動車組運行線之間的接續(xù)時間決定了動車組在各個站停留的時間，接續(xù)時間的縮短，每個動車組交路的運行的時間也會隨之縮短，這對動車組檢修也十分有利。動車組交路數(shù)量最少(4.12)4.3優(yōu)化模型分析及求解探討基本的數(shù)學規(guī)劃模型已經(jīng)完成，由建立的模型分析可知，目標函數(shù)包括動車組接續(xù)時間最短和動車組交路數(shù)量最少兩個，其決策變量也是可以得出是整數(shù)，所以建立的模型是多目標的整數(shù)規(guī)劃模型。接下來對多目標的整數(shù)規(guī)劃模型進行分析，然后得出求解該模型的基本思路。4.3.1整數(shù)規(guī)劃問題求解思路針對整數(shù)規(guī)劃問題，一般來說，大部分的整數(shù)規(guī)劃問題都是NP-hard問題，用于求解整數(shù)規(guī)劃問題的算法比較多，可以根據(jù)問題的實際要求來選擇合適的算法，現(xiàn)在比較常用的求解整數(shù)規(guī)劃問題的方法有分支定界法、割平面法、枚舉法。分支定界法：基本思想是根據(jù)某種策略把問題的可行域分解為越來越小的子域，然后檢查各個子域的整數(shù)解的情況知道找到最優(yōu)解或證明最優(yōu)解不存在。根據(jù)整數(shù)規(guī)劃問題的實際性質(zhì)不同，也有不同的分支定界的技巧。一般求解整數(shù)規(guī)劃問題，先求解整數(shù)規(guī)劃問題的松弛問題的解，通常其不是整數(shù)解，可利用該解對可行域進行不斷的提高下界，降低上界，即先分支、后定界，直至找到最優(yōu)整數(shù)解。割平面法：割平面法是受到整數(shù)規(guī)劃問題的幾何解釋啟發(fā)所形成的，一般，整數(shù)規(guī)劃的最優(yōu)解一定在松弛問題的最優(yōu)解附近，通過增加一些附加的約束，將松弛問題最優(yōu)解附近不含整數(shù)解的可行域的多余部分割去，從而搜尋整數(shù)最優(yōu)解。對于比較復雜的整數(shù)規(guī)劃問題，可能需要比較多大附加約束方程來進行割除，才能找到整數(shù)最優(yōu)解。枚舉法：對于一些比較簡單的，可行域有界且較小時，可以采用窮舉的方法對比得出整數(shù)最優(yōu)解，但是對于可行域無界或很大時，計算量過大，因此對于許多實際的整數(shù)規(guī)劃問題，無法采用這種方法求解。總結(jié)上述三種方法，都是針對比較小規(guī)模的問題，當整數(shù)規(guī)劃問題一旦有比較大的規(guī)模，這三種方法的求解效率會變的比較低下，而本文建立的模型中的整數(shù)規(guī)劃問題的約束條件十分多，可考慮采用精確算法CPLEX求解，CPLEX軟件的優(yōu)點已經(jīng)被很多的學者研究證明了，復雜程度比較低，并且求解的滿意度也算比較高，能達到要求。4.3.2多目標函數(shù)問題求解思路本文設計的規(guī)劃模型就是多目標函數(shù)類型，包括動車組交路數(shù)量和列車運行線接續(xù)總時間。對于這種多目標函數(shù)的規(guī)劃，要求做到每個目標的最優(yōu)，而最后得出的解又是可能是多個，這樣就加大了對比分析的難度，評價也變得更加復雜。目前處理多目標函數(shù)常用的有兩種方法，分別為分層優(yōu)化多目標，以及標量化方法，也稱為權重方法。分層優(yōu)化多目標：分層優(yōu)化的思想就是首先針對一個目標函數(shù)，當其得到較好解的情況下，再去尋找另一目標函數(shù)的最優(yōu)解。結(jié)合本文研究的動車組交路編制問題，涉及的兩個目標函數(shù)中，“動車組運行線之間的接續(xù)時間最短”這一目標通常是可以得出多個最優(yōu)解的，因為是比較典型的指派問題，多個最優(yōu)解構成一個解的集合，然后在考慮另一個目標“動車組交路數(shù)量最少”，得出符合兩個目標函數(shù)的比較滿意的解。此種方法是通過問題分解的方式，對每個目標函數(shù)分別進行了優(yōu)化，降低求解的難度。標量化方法：即權重方法，通過對各個目標的側(cè)重點進行分析，然后給每個目標賦予一個權重，最后對每個目標和權重的積進行求和，這就把多個目標轉(zhuǎn)化為了單目標。對于本文的研究模型，可以將“動車組交路數(shù)量最少”權值賦為m1，“動車組運行線接續(xù)時間最短”權值賦為m2，則可得以下公式：(4.13)(4.14)經(jīng)過分析，本文擬采用第一種方法進行整數(shù)規(guī)劃的求解，首先對“動車組交路的數(shù)量”這一目標函數(shù)進行最優(yōu)化的處理，在模型中表現(xiàn)為對最優(yōu)接續(xù)網(wǎng)絡的構建，接續(xù)網(wǎng)絡的最優(yōu)意味著動車組交路數(shù)量達到最小，然后在最優(yōu)接續(xù)網(wǎng)絡的基礎上，對“動車組運行線接續(xù)時間最短”這一目標進行優(yōu)化。4.4本章小結(jié)本章根據(jù)前文的動車組交路優(yōu)化基本理論以及模型構建部分的知識，通過分析，以及對旅行商問題（TSP）網(wǎng)絡模型構建理論的借鑒，并且考慮動車組交路計劃編制的特點，分步驟進行了約束條件和目標函數(shù)的描述，完成了動車組交路優(yōu)化模型的完整構建，最后還針對模型中的整數(shù)規(guī)劃問題以及多目標函數(shù)進行了求解思路的分析。5動車組交路優(yōu)化模型求解研究動車組交路計劃編制優(yōu)化的模型的算法研究，首先根據(jù)模型的建立過程，是通過經(jīng)典的旅行商問題的類比，所以本文模型的求解也同樣需要借鑒TSP問題的求解。TSP問題的解是最后得出的旅行商經(jīng)過的城市的一種最優(yōu)的排列順序，那么動車組交路最優(yōu)則是動車組經(jīng)過所有車站且完成了所有運輸任務，最后回到動車運用所進行檢修，這一過程中滿足兩個目標，即“動車組交路數(shù)量最少”和“動車組運行線接續(xù)時間最短”。本文擬采用精確算法，然后設計一個較小規(guī)模的動車組交路計劃優(yōu)化編制問題的算例，采用CPLEX軟件，對其進行求解，以此證明建立的模型的優(yōu)化的有效性。5.1模型及算法步驟具體的模型中目標函數(shù)的計算流程如下：步驟一：由設計好的算例數(shù)據(jù)中的列車時刻表，對車次進行安排；步驟二：在動車組集合L中選取空閑時間段包含列車運行線i的起止時間段的動車組，將符合條件的動車組存放在可用車底中；可用車底的確定，方法是在動車組集合L中選取空閑時間段能包含列車運行線i的始發(fā)和終到時間的動車組，存放入可用車底備選用；步驟三：列車次序表的確定，列車運行圖中，在完成第i條運行線的運輸任務后，在可用車底中，選擇滿足一級檢修約束與最小接續(xù)時間約束的動車組，將其指定到第j條運行線，執(zhí)行下一次的運輸任務并記錄下來形成一個列車次序表中；步驟四：將正在進行運輸任務的動車組設為已占用狀態(tài)，完成運輸任務后且滿足一級檢修約束，則設置為可使用狀態(tài)；步驟五：在列車運行線和動車組匹配完后，計算動車組交路數(shù)量最小值，得出最優(yōu)解的集合；步驟六：在最優(yōu)解的集合中，挑選出動車組總接續(xù)時間最短的解。算法的步驟如下：先對動車組根據(jù)時間進行初始化處理，將所有的數(shù)據(jù)導入EXCEL表格中，進行簡單的數(shù)據(jù)處理。即將時刻表數(shù)據(jù)中的時間轉(zhuǎn)換成數(shù)字，例如接續(xù)時間7：00轉(zhuǎn)換成420min、8:00轉(zhuǎn)換成480min，將便于將時間導入模型中進行計算。每一行代表一條運行線，將CPLEX軟件與EXCEL建立連接，把數(shù)據(jù)導入模型中求解，得到的結(jié)果再導出到EXCEL中。5.2算例數(shù)據(jù)確定表5.1基于CPLEX設計的算例數(shù)據(jù)序號車次始發(fā)站終到站發(fā)車時間到站時間運行里程/km運行時間/min1G1SZBWH08:2313:22108004:592G2SZBWH11:2216:17108004:553G3WHSZB13:4118:56108005:154G4WHSZB16:5622:04108005:085G5GZNWH10:3614:38107504:026G6GZNWH10:4815:05107504:177G7WHGZN15:0319:25107504:228G8WHGZN15:2519:39107504:149G9CSNSZB07:3010:5281503:2210G10CSNSZB10:0513:3581503:3011G11SZBCSN14:0517:3981503:3412G12CSNGZN07:0509:5871002:5313G13GZNCSN07:0809:4871002:4014G14CSNGZN07:1910:0971002:5015G15GZNCSN19:4322:3671002:5316G16CSNGZN17:5520:3871002:4317G17GZNCSN19:5222:3771002:4518G18GZNCSN21:0023:3971002:3919G19GZNSZB07:2507:5914500:3420G20SZBGZN19:1819:5214500:3421G21SZBGZN21:1521:5414500:3922G22GZNSZB20:2020:5514500:3523G23SZBGZN22:2523:0314500:38數(shù)據(jù)來源于武深高鐵網(wǎng)絡和列車時刻表，為了符合模型以及CPLEX優(yōu)化算法的步驟，選取的數(shù)據(jù)是經(jīng)過篩選和處理的，不是原本完整的列車運行圖中包括所有車站和到發(fā)時間的龐大的數(shù)據(jù)，表中為了計算的方便，將車站的名字簡單的記為大寫字母的縮寫，時刻為24小時制。一級檢修的對應的檢修時間約束是48小時，記為Tx=2880min，一級檢修對應的里程約束是4000公里，記為Sx，Tmax值為15min。5.3算例計算結(jié)果及分析根據(jù)模型，應用WebSphereILOGCPLEX軟件，將設計的算例數(shù)據(jù)帶入，經(jīng)過在win10系統(tǒng)的pc機上的試運行，得到的交路數(shù)量的表格如下：表5-2交路數(shù)量表序號交路數(shù)量接續(xù)時間檢修次數(shù)189868289058367566454865554415從表格可以看出，動車組交路數(shù)量一次比一次少，根據(jù)模型的求解過程，最優(yōu)接續(xù)網(wǎng)絡的交路數(shù)量為5，進入第二個“接續(xù)時間最短”目標的優(yōu)化，對比第4次和第5次的接續(xù)時間可得到，第五次兩個目標都達到最優(yōu)。由此得到了最終優(yōu)化的動車組交路計劃，交路數(shù)量最少是5，總接續(xù)時間最短為441min，檢修次數(shù)為5次。具體每一天交路的情況如下表：表5-3動車組交路計劃表序號交路計劃中列車車次接續(xù)時間/min跨越天數(shù)1G19-G1-G13-G20-G22-G2111312G13-G10-G11-G16-G188513G9-G2-G4-G239014G12-G5-G7-G158115G14-G6-G8-G17721由表中數(shù)據(jù)可知，交路1由G19→G1→G3→G20→G22→G21組成，動車組從上午的7:25分從GZN站出發(fā)，并且能在當天的晚上21:54回到GZN站，從而滿足進行一級檢修作業(yè)的約束，同樣的情況，交路2、3、4、5都是能做當天返回動車組檢修基地完成一級檢修作業(yè)，同時，做到了最短的動車組接續(xù)時間441min。文中設計的算例也可通過人工的方法進行動車組交路計劃的編制，人工編制要進行的計算量比較大，過程也比較復雜，對交路計劃后續(xù)的調(diào)整更是十分困難。人工方法編制的結(jié)果和本文CPLEX算法引擎計算的結(jié)果如下表：表5-4CPLEX算法和人工編制方法對比交路數(shù)量檢修次數(shù)編制效率CPLEX算法55方便快捷，效率高人工編制56計算復雜，調(diào)整困難，效率低由表5-4可知，人工編制的方法得到的交路數(shù)量和算法求解的相同，都為5，但是檢修次數(shù)為6次，經(jīng)過分析，差距在于人工編制的交路超過了動車組一級檢修的標準。相比之下，CPLEX算法的過程簡單快捷，由于是軟件計算，效率也可以達到很高，而人工編制過程計算復雜，效率低下。最終的結(jié)果也是CPLEX算法在檢修次數(shù)上比人工算法的結(jié)果更優(yōu)，所以本文建立的模型以及運用的算法可用于優(yōu)化動車組交路的編制。5.4本章小結(jié)本章根據(jù)建立的模型，并結(jié)合實際的條件，設計了一個規(guī)模上不算特別大的算例，之后采用精確算法中的CPLEX算法，具體采用WebSphereILOGCPLEX軟件，符合了模型中的各類約束條件。經(jīng)過在電腦上的運行，成功得出了動車組交路計劃的最優(yōu)解，驗證了模型的有效性。6總結(jié)與展望6.1論文總結(jié)動車組交路計劃的編制問題是高鐵運輸計劃中的十分核心的環(huán)節(jié)，與動車組運用計劃的關系也是十分密切。提高動車組的利用效率、降低動車組檢修的成本等目標就是是研究交路計劃的最終目的，因此，本文在通過廣泛閱讀、分析以及總結(jié)國內(nèi)外現(xiàn)有的研究文獻，深刻學習了動車組交路的有關知識理論。從動車組交路計劃的編制流程，到影響交路優(yōu)化的各種復雜的因素，以及學習和理解各種優(yōu)化交路計劃的模型和求解模型的算法。在此基礎上，本文也進行了模型的建立，并設計了算例對其進行了有效性的驗證。具體的主要工作如下：1）根據(jù)現(xiàn)有的動車組交路相關的研究，分析總結(jié)了兩種典型的交路編制流程，即基于列車運行圖和相關的動車組運用管理模式規(guī)定來編制、同時編制列車運行圖和動車組交路計劃的編制流程。2）總結(jié)了深刻影響動車組交路計劃編制的個因素，分別是：列車開行方案、動車組類型、動車組管理運用模式和動車組檢修模式。3）詳細分析了多種針對動車組交路優(yōu)化問題建立的模型，按照模型建立的研究重點的不同，以及對幾種影響因素是否考慮的差異，進行了分類闡述。4）總結(jié)了用于求解動車組交路優(yōu)化問題的精確算法和啟發(fā)式算法兩大類，本文后續(xù)采用的是CPLEX精確算法，對啟發(fā)式算法的優(yōu)缺點也逐一進行了分析。5）通過類比旅行商問題，建立了一個多目標的整數(shù)規(guī)劃模型，并設計根據(jù)模型的約束，以及CPLEX算法的要求，設計了算例并應有模型和算法進行了交路優(yōu)化的求解，結(jié)果顯示構建的模型可用于解決交路優(yōu)化問題。6.2展望本文研究過程中，發(fā)現(xiàn)動車組交路優(yōu)化的問題是一個綜合性問題，在許多研究中都是只考慮一些比較簡單的影響因素，實際上其涉及的影響因素十分復雜且多變，目前仍然有巨大的研究拓展空間。本文由于研究的時間和水平的有限，對于該問題也認識到了不足之處，以下對研究過程中發(fā)現(xiàn)的問題和不足進行總結(jié)。1）在分析現(xiàn)有的動車組交路編制流程時，發(fā)現(xiàn)現(xiàn)有的優(yōu)化研究思路大多都是在列車運行圖已知的條件下，同時也有少部分研究已經(jīng)開始按照動車組交路和列車運行圖協(xié)調(diào)優(yōu)化的思路進行。實際上，既有的交路計劃在編制列車運行圖時就已經(jīng)通過人工的方法進行了確定，大多數(shù)情況下也達到了了最優(yōu)，而如果采用協(xié)調(diào)優(yōu)化的思路，那優(yōu)化的空間能進一步擴大。2）本文建立模型時，考慮的影響因素比較理想化，沒有模擬實際的一些規(guī)模較大的交路計劃編制的條件。其中檢修能力的約束條件是典型的一個例子。動車組的檢修分為五個等級，模型建立的約束條件只考慮了一級檢修的約束。同時，動車組檢修標準時間定為2小時，如果能對動車組檢修的效率進行提高，也能達到更好的交路優(yōu)化效果。3）對設計的規(guī)模比較小的算例進行求解，過程和結(jié)果都比較順利，但是對于實際的動車組交路計劃的編制問題，其規(guī)模會變得十分龐大，約束條件也會變得更加復雜多變，如何將實際的問題一步步的進行分析研究，是之后還要一直進行探索的方向。4）動車組的實際運營過程，會出現(xiàn)一些難以預估的影響，例如線路故障等一些運輸秩序被干擾的問題，這種情況下需要對動車組的交路進行快速的調(diào)整，以求最快的恢復動車組的正常運行。此類應急情況的處理，也可以作為交路優(yōu)化的又一個影響因素，綜合進行研究。致謝參考文獻[1]時永慶.我國鐵路網(wǎng)將升級為"八縱八橫"[R].工程建設標準化,2016,(07):25.[2]TomoshiOtsuki,HideyukiAisu,ToshiakiTanaka,etal.ASearch-basedapproachtoRailwayRollingStockAllocationProblems[J].DiscreteMathematics,AlgorithmsandApplications,2011,3(4):443-456.[3]YasutakaTsuji,MasahiroKuroda,YukiyaKitagawa,etal.AntColonyOptimizationApproachforSolvingRollingStockPlanningforPassengerTrains[C].IEEE/SICEInternationalSymposiumonSystemIntegration(SII),2012:16-18.[4]ZhouYu,ZhouLeishan,WangYun,etal.ApplicationofMultiple-PopulationGeneticAlgorithminOptimizingtheTrain-SetCirculationPlanProblem[J].Complexity,2017:3717654.[5]RichardLusby,M,Haahr,JorgenThorlund,Larsen,etal.ABranch-and-Pricealgorithmforrailwayrollingstock