客運(yùn)專線旅客列車開行方案優(yōu)化研究課件

客運(yùn)專線旅客列車開行方案優(yōu)化研究研究內(nèi)容研究目的從客運(yùn)專線旅客列車開行方案形成的整個(gè)過程出發(fā)，從運(yùn)量預(yù)測、開行方案優(yōu)化和運(yùn)行圖編制三個(gè)主要環(huán)節(jié)入手，對客運(yùn)專線旅客列車開行方案進(jìn)行整體協(xié)調(diào)優(yōu)化，為客運(yùn)專線的設(shè)計(jì)、建設(shè)、運(yùn)營提供更加科學(xué)可靠的理論依據(jù)。研究內(nèi)容研究進(jìn)展和現(xiàn)狀分析，總結(jié)存在的問題和不足研究問題總體描述；闡述運(yùn)量預(yù)測與列車開行方案制定之間的聯(lián)系。影響因素分析；旅客候車和中轉(zhuǎn)換乘時(shí)間確定客車開行方案優(yōu)化模型的建立和推廣遺傳算法設(shè)計(jì)運(yùn)行圖編制的模型和算法設(shè)計(jì)研究現(xiàn)狀旅客列車開行方案優(yōu)化的研究運(yùn)量預(yù)測的研究旅客列車方案圖編制的研究計(jì)算機(jī)輔助系統(tǒng)的研究研究中存在的問題客車開行方案包括的內(nèi)容較多，以往的研究工作多以某一方面作為研究對象，不夠全面；很少用到優(yōu)化的方法來解決實(shí)際工作中的問題，只停留在理論研究階段；認(rèn)識到了開行方案與客流預(yù)測和運(yùn)行圖編制之間的關(guān)系，但鑒于三者的復(fù)雜程度，并沒有進(jìn)行全面的深入研究；不論在理論研究方面，還是實(shí)際應(yīng)用中，都沒有形成一套完整的體系。研究問題的總體描述

列車開行方案的內(nèi)容列車運(yùn)行特性——起訖點(diǎn)、運(yùn)行徑路、途中停站方案等；列車性質(zhì)——列車等級、種類、數(shù)量等；設(shè)備利用情況——列車編組內(nèi)容、車底運(yùn)用、客座利用等。列車開行方案的形成過程客流OD的生成與分析——前提和基礎(chǔ)；列車開行方案的制定與優(yōu)化；旅客列車方案運(yùn)行圖編制——方案的最終形成和具體實(shí)施。開行方案形成過程的對應(yīng)工作運(yùn)量預(yù)測階段需要的列車服務(wù)屬性，是在客流輸送方案制定后才產(chǎn)生的，而且是在運(yùn)行圖編制以后才被確定的；客流輸送方案制定階段所需要的客流參數(shù)，是通過客流預(yù)測得到的；運(yùn)行圖編制階段所需要的列車參數(shù)，必須要在列車輸送方案優(yōu)化后才能得到。子過程需要相關(guān)參數(shù)相關(guān)優(yōu)化內(nèi)容相關(guān)優(yōu)化結(jié)果運(yùn)量預(yù)測服務(wù)屬性（旅行時(shí)間、候車時(shí)間、服務(wù)頻率等）客流預(yù)測路網(wǎng)配流客流OD、客流密度高峰客流分布等客流輸送方案制定客流參數(shù)、運(yùn)行徑路、列車能力利用參數(shù)、時(shí)間消耗參數(shù)等列車輸送方案客流搭乘方案列車數(shù)量、起訖點(diǎn)途中停站運(yùn)行圖編制列車參數(shù)等運(yùn)行圖鋪畫動車組周轉(zhuǎn)列車旅行、停站、接續(xù)時(shí)間；服務(wù)頻率；車組周轉(zhuǎn)及數(shù)量開行方案的優(yōu)化方式列車開行方案單獨(dú)優(yōu)化列車開行方案與運(yùn)行圖編制兩個(gè)階段的綜合優(yōu)化列車開行方案與客流OD生成兩個(gè)階段的綜合優(yōu)化三個(gè)階段的整體綜合優(yōu)化采用統(tǒng)一的綜合優(yōu)化模型和算法來實(shí)現(xiàn)任何一個(gè)都是復(fù)雜的優(yōu)化問題，統(tǒng)一后復(fù)雜程度將大大提高三項(xiàng)工作由不同部門分別獨(dú)立完成的，將其融為一體難度相當(dāng)大采用各個(gè)階段順序優(yōu)化、循環(huán)迭代的形式

服務(wù)屬性（旅行時(shí)間、候車時(shí)間、服務(wù)頻率等）運(yùn)量預(yù)測客流OD、客流密度；高峰客流分布等客流輸送方案制定運(yùn)行徑路、能力利用參數(shù)列車數(shù)量、起訖點(diǎn)、途中停站方案運(yùn)行圖編制列車旅行、停站、接續(xù)時(shí)間；服務(wù)頻率車站參數(shù)、線路參數(shù)等初始參數(shù)客運(yùn)專線旅客列車開行方案優(yōu)化過程關(guān)系圖時(shí)間消耗參數(shù)社會經(jīng)濟(jì)參數(shù)、成本參數(shù)、路網(wǎng)參數(shù)運(yùn)量預(yù)測

用伯克森－泰爾法估計(jì)LOGIT模型中效用函數(shù)的系數(shù)直接需求模型各OD中各種運(yùn)輸方式未來年度無客運(yùn)專線條件下總運(yùn)量預(yù)測運(yùn)量分配模型誘發(fā)運(yùn)量預(yù)測模型各OD中各種運(yùn)輸方式未來年度有客運(yùn)專線條件下總運(yùn)量預(yù)測各OD中各種運(yùn)輸方式未來年度市場份額的預(yù)測各OD中未來年度客運(yùn)專線運(yùn)量的預(yù)測各OD點(diǎn)社會經(jīng)濟(jì)參數(shù)調(diào)查運(yùn)量預(yù)測過程框圖

模型結(jié)構(gòu)中都包含有廣義費(fèi)用，客運(yùn)專線運(yùn)量預(yù)測的結(jié)果取決于其服務(wù)屬性。（1）旅行時(shí)間（2）旅客進(jìn)出站時(shí)間、費(fèi)用（3）旅客在站等候時(shí)間（4）運(yùn)價(jià)水平——從國民經(jīng)濟(jì)、生活水平、支付能力、比價(jià)關(guān)系，以及客運(yùn)專線技術(shù)經(jīng)濟(jì)特性和優(yōu)勢幾個(gè)方面綜合確定。（5）旅客時(shí)間價(jià)值——通過統(tǒng)計(jì)數(shù)據(jù)運(yùn)用效用函數(shù)模型標(biāo)定基年旅客時(shí)間價(jià)值，預(yù)測年度時(shí)間價(jià)值增長率按客運(yùn)專線影響區(qū)GDP的平均增長速度確定。旅行時(shí)間、候車時(shí)間必須通過客運(yùn)專線列車開行方案的制定才能精確得到。影響因素分析基本原則以客流為依據(jù)，城市（車站）為基點(diǎn)，充分利用現(xiàn)有設(shè)備（線路和車輛），努力提高客運(yùn)專線旅客列車開行方案的經(jīng)濟(jì)效益和社會效益。影響因素分析客流及列車徑路

客流OD——客流徑路——列車徑路列車編成及線路能力區(qū)間最大通過能力：最小追蹤間隔時(shí)間、列車種類列車編成：列車運(yùn)行距離、運(yùn)行徑路上沿途車站到發(fā)線有效長、站臺長度、牽出線長度、動車組單元類型、牽引供電水平、追蹤間隔時(shí)間、線路能力公交化運(yùn)營組織方式，保證較高的服務(wù)頻率，采用相對固定、較小編組的形式確定：線路能力——最大客流密度區(qū)段高峰小時(shí)客流量——列車編成——定員經(jīng)濟(jì)效益經(jīng)濟(jì)效益主要來自于客票收入；旅客列車經(jīng)濟(jì)效益核算方法都要確定出客運(yùn)總成本；總成本、票價(jià)和列車定員確定后，總利潤與客座利用率之間存在關(guān)系：總利潤=客票單價(jià)×列車輸送客座能力×客座率－客運(yùn)總成本上座率提高——鐵路收入增加——旅客服務(wù)水平下降——鐵路收入下降保證鐵路收入和旅客服務(wù)水平——確定合理的列車客座利用率旅行時(shí)間——社會效益的體現(xiàn)旅客候車時(shí)間消耗——候車集結(jié)到達(dá)過程列車停站時(shí)間消耗——列車停站方案；同等級車站的途中停站時(shí)間基本相同列車運(yùn)行時(shí)間消耗——列車技術(shù)速度，取決于列車等級旅客換乘時(shí)間消耗——列車服務(wù)頻率及相互列車的接續(xù)時(shí)間始發(fā)客流候車集結(jié)過程分析始發(fā)客流候車集結(jié)過程的特點(diǎn)及其數(shù)學(xué)描述客流到達(dá)的隨機(jī)過程描述

客流到達(dá)——簡單計(jì)數(shù)過程——齊次泊松過程到達(dá)間隔的隨機(jī)描述在客流的集結(jié)過程是具有強(qiáng)度λ的齊次泊松過程時(shí)，則其到達(dá)間隔時(shí)間是服從指數(shù)分布的隨機(jī)變量序列。到達(dá)數(shù)量的隨機(jī)描述

客流的集結(jié)到達(dá)過程——標(biāo)值點(diǎn)過程候車集結(jié)時(shí)間的確定

，；假設(shè)的期望值收斂，記為。結(jié)論每個(gè)旅客所消耗的平均候車集結(jié)時(shí)間為可用平均上座率來描述，T可用列車服務(wù)頻率來描述。門到站的時(shí)間消耗、購票等其他的額外消耗，暫不考慮。時(shí)間消耗與列車服務(wù)頻率的關(guān)系分析候車時(shí)間消耗與列車服務(wù)頻率的關(guān)系分析旅客全天候候車假定整個(gè)過程的持續(xù)時(shí)間從前日最后一列可服務(wù)于客流的列車出發(fā)時(shí)起，到今日最后一列可服務(wù)于客流的列車出發(fā)時(shí)止。候車集結(jié)時(shí)間消耗完全取決于列車的分布情況。在平均分布時(shí)有：旅客只在日間行車時(shí)間段內(nèi)候車旅客只在同類列車間隔時(shí)間內(nèi)候車或中轉(zhuǎn)換乘時(shí)間消耗與列車服務(wù)頻率的關(guān)系分析

在平均分布情況下，當(dāng)?shù)竭_(dá)列車數(shù)為nu，出發(fā)列車數(shù)為nv

時(shí)，平均旅客中轉(zhuǎn)時(shí)間為td/2nv，它與到達(dá)的列車數(shù)量是無關(guān)的。列車開行方案優(yōu)化模型構(gòu)建

最優(yōu)的旅客列車開行方案（始發(fā)站、終到站、途中停站方案）總要對應(yīng)最優(yōu)客流輸送方案（旅客出行方式選擇問題）相關(guān)邊界假定單向性假設(shè)——直線型客運(yùn)專線某一個(gè)方向的列車開行方案優(yōu)化確定性假設(shè)——客流OD、列車徑路、列車定員、上座率是確定相似性假設(shè)——列車區(qū)間運(yùn)行時(shí)間、定員相同能力假設(shè)——區(qū)間通過能力已確定，車站能力不產(chǎn)生約束客流理性假設(shè)——出行方式的選擇只取決于開行方案系統(tǒng)封閉性假設(shè)——系統(tǒng)狀態(tài)的變化只取決于內(nèi)部影響因素列車類型及組合輸送方案的描述

車站的有序集合；列車種類集合；途中停站集合路段集合；列車接續(xù)方案；中轉(zhuǎn)站集合路段－列車－乘車方案關(guān)聯(lián)矩陣；客流輸送方案－中轉(zhuǎn)站點(diǎn)關(guān)聯(lián)矩陣始發(fā)站點(diǎn)－乘車方案關(guān)聯(lián)矩陣；始發(fā)站點(diǎn)－列車－乘車方案矩陣決策變量的定義

Xijk——以i為O點(diǎn)，j為D點(diǎn)的選擇乘車方案Lk的旅客數(shù)量優(yōu)化目標(biāo)鐵路部門經(jīng)濟(jì)效益：合理的上座率來保障——約束條件（目標(biāo)約束法）；旅客出行成本：票價(jià)和時(shí)間成本所有旅客在途時(shí)間總和最短——優(yōu)化目標(biāo)運(yùn)行時(shí)間消耗停站時(shí)間消耗始發(fā)候車集結(jié)時(shí)間消耗中轉(zhuǎn)時(shí)間消耗

通過前述的各種集合和關(guān)聯(lián)矩陣，可以描述出各種列車的數(shù)量、旅客停站及次數(shù)、旅客中轉(zhuǎn)站及次數(shù)，進(jìn)而得到各種時(shí)間消耗。約束條件客流約束、區(qū)間通過約束、列車服務(wù)能力約束方案可行性約束、變量取值約束模型特點(diǎn)模型為非線性整數(shù)規(guī)劃問題，非線性都集中表現(xiàn)在目標(biāo)函數(shù)模型存在如下組合優(yōu)化的特點(diǎn)列車由沿途經(jīng)由站點(diǎn)的組合形式描述接續(xù)方案由列車的組合描述旅客的出行由接續(xù)方案的組合來描述由于沒有涉及到運(yùn)行圖的實(shí)際編制問題，很多參數(shù)都采用了假設(shè)或平均值求解非常困難——采用現(xiàn)代優(yōu)化算法模型的進(jìn)一步推廣網(wǎng)狀線路結(jié)構(gòu)的推廣分解算法：直線型線路上單方向旅客列車開行方案的優(yōu)化問題各線路旅客列車開行方案在銜接站的協(xié)調(diào)優(yōu)化問題

靜態(tài)模型，不涉及連續(xù)性時(shí)間參數(shù)和變量，較計(jì)算機(jī)編圖更適合采用。必須對列車集合在整個(gè)線路結(jié)構(gòu)上統(tǒng)一確定，列車的運(yùn)行方向不會對問題造成影響?？缇€列車和跨線客流的處理長途跨線客流，自然形成換乘，轉(zhuǎn)化為銜接站上的本線客流；短途跨線客流，具備分離條件的（已確定了列車類型為B類，由既有線的列車開行方案已確定了其輸送方案的除外）可以與本線客流分開考慮，單獨(dú)進(jìn)行優(yōu)化求解；短途跨線客流，若不可分離，可按研究線路的拆分形式進(jìn)行拆分，轉(zhuǎn)化為接入站上的本線客流進(jìn)行統(tǒng)一的優(yōu)化計(jì)算，而后與其他部分合并后確定列車形式。算法設(shè)計(jì)遺傳算法介紹啟發(fā)式隨機(jī)搜索技術(shù)編碼原則完備性、健全性、非冗余性

收斂性全局最優(yōu)算法時(shí)間復(fù)雜度O(O(f)nlnn)GA欺騙問題約束條件的處理拋棄不可行解方法、基于智能編碼的方法、改變遺傳算子法、修補(bǔ)方法、罰函數(shù)法DCPM法——保留部分不可行解方案優(yōu)化模型轉(zhuǎn)換求解思路：用列車開行方案Xi代替xijk構(gòu)造Xi下的列車運(yùn)行網(wǎng)絡(luò)Gi＝(Vi,Ei,Ci,Hi,Pi)在Gi上得到客流N={nij}的最優(yōu)分配方案按上述求解思路，可將原模型描述為：

Z=min{f(Fi)|Gi(Xi)}求解的主要工作：由Xi構(gòu)造GiGi中最小費(fèi)用流fi的計(jì)算個(gè)體編碼處理變量構(gòu)造及個(gè)體編碼含義

Xk＝{xij}k為0-1矩陣行——客運(yùn)專線上車站—區(qū)間—車站的順序結(jié)構(gòu)；行數(shù)mi是固定的由線路結(jié)構(gòu)確定；列——列車在車站通過、停車、始發(fā)、終到或在區(qū)間運(yùn)行的狀態(tài)；列數(shù)mj由線路上所有區(qū)段中的最大列車數(shù)max{min{nq,cq|q}}確定個(gè)體冗余性處理車站取值冗余——車站取值約束

|xi+1,j-xi-1,j|≤xij≤xi+1,j+xi-1,j(i=2n,n?Z+,j=1,2.…,mj)列排序冗余——字典排序車站限制處理：車站不辦理客運(yùn)業(yè)務(wù)：取消該車站，將相鄰區(qū)間合并車站不辦理列車的始發(fā)和終到作業(yè)取值約束

|xi+1,j-xi-1,j|≤xij≤xi+1,j×xi-1,j(i=2n,n?Z+)弧產(chǎn)生始節(jié)點(diǎn)終節(jié)點(diǎn)費(fèi)用位置始發(fā)弧列車始發(fā)站列車中間停站始發(fā)集結(jié)時(shí)間在弧上中間弧列車中間停站列車前方相鄰?fù)Ｕ就Ｕ緯r(shí)間、始發(fā)集結(jié)時(shí)間在始節(jié)點(diǎn)和弧上終到弧列車中間停站列車終到站停站時(shí)間、始發(fā)集結(jié)時(shí)間在始節(jié)點(diǎn)和弧上直達(dá)弧列車始發(fā)站列車終到站始發(fā)集結(jié)時(shí)間在弧上中轉(zhuǎn)弧旅客中轉(zhuǎn)站V旅客中轉(zhuǎn)站V’中轉(zhuǎn)時(shí)間消耗在弧上列車運(yùn)行網(wǎng)絡(luò)的構(gòu)造初始網(wǎng)絡(luò)構(gòu)造網(wǎng)絡(luò)參數(shù)確定弧的費(fèi)用弧的容量：滿足一定上座率，容量限制為階躍形式cij?{0,cu}節(jié)點(diǎn)外部流量Wi：Wi+表示節(jié)點(diǎn)的發(fā)送量Wi-表示節(jié)點(diǎn)的到達(dá)量中轉(zhuǎn)弧的構(gòu)造中轉(zhuǎn)方案的確定：列車在換乘節(jié)點(diǎn)前、后，具有不同的弧集；弧的容量為0≤cij

≤

cu網(wǎng)絡(luò)的統(tǒng)一化處理重復(fù)弧的處理：合并容量變?yōu)閚cu或n[cu]節(jié)點(diǎn)費(fèi)用的處理始發(fā)集結(jié)消耗費(fèi)用處理節(jié)點(diǎn)外部流量處理

PkGk單源單匯給定流量的有向圖適應(yīng)值函數(shù)的求解適應(yīng)值函數(shù)f就是求解G上給定流量W的最小費(fèi)用流。網(wǎng)絡(luò)的可行化處理不可行性產(chǎn)生的原因：列車在車站所提供服務(wù)能力小于該站始發(fā)客流量；列車在車站所提供服務(wù)能力小于該站終到客流量；列車在區(qū)間所提供服務(wù)能力小于該區(qū)段旅客輸送量（客流密度）；列車在OD所表示兩個(gè)車站提供服務(wù)能力的可達(dá)性關(guān)聯(lián)。處理方法：增加虛擬擴(kuò)容弧—費(fèi)用為Mc>Hmax階躍容量限制的轉(zhuǎn)化

根據(jù)對偶原理網(wǎng)絡(luò)中弧的容量和費(fèi)用可以互相轉(zhuǎn)化。轉(zhuǎn)化為弧eij’：容量限制cij’≤cu；費(fèi)用為凹函數(shù)：hij’(f)=hij(f)+Mh(cu-fij’)fij’；為使得fij’≠0且fij’≠cu的流值不發(fā)生在弧eij’上，要求Mh>2NMc。

帶有凹費(fèi)用的網(wǎng)絡(luò)求解凸費(fèi)用的處理——分段線性近似費(fèi)用為凸時(shí)，總有h1<h2凹費(fèi)用的處理分段線性近似：總會發(fā)生h1>h2

出現(xiàn)固定費(fèi)用把eij’的費(fèi)用用一條直線近似，得到新的參數(shù)：有固定費(fèi)用的最小費(fèi)用流計(jì)算——隱枚舉法有負(fù)費(fèi)用的最小費(fèi)用流求解在有容量限制的網(wǎng)絡(luò)中，負(fù)費(fèi)用的存在不會給最小費(fèi)用流帶來更多的新問題，不需要進(jìn)行特殊處理。網(wǎng)絡(luò)G容量供給特性的分析能力過剩方案——能力過剩網(wǎng)絡(luò)；能力緊缺方案——能力緊缺網(wǎng)絡(luò)；能力平衡方案——供需平衡網(wǎng)絡(luò)。在非能力過剩網(wǎng)絡(luò)中，去掉運(yùn)行弧的容量階躍約束而改為平凡的容量上限，不會出現(xiàn)違反階躍容量限制的可行流，因此不會影響最優(yōu)解的性質(zhì)。保證個(gè)體不構(gòu)成能力過剩網(wǎng)絡(luò)，必須滿足能力約束實(shí)際工作與方案優(yōu)化之間的比較分析實(shí)際新建客運(yùn)專線列車開行方案制定的通常做法。

【推論1】把滿足客流和技術(shù)條件的始發(fā)客流，以直達(dá)列車的形式先輸送至目的地而形成的開行方案不一定是最優(yōu)的。

【推論2】在運(yùn)能短缺的情況下，當(dāng)給定一個(gè)列車開行方案后，對于有條件的客流采用直達(dá)列車輸送總是最優(yōu)的。推論1是對全局最優(yōu)的敘述；推論2是對局部最優(yōu)的敘述，兩者并不矛盾?，F(xiàn)行的列車方案制定步驟和方法，可得出局部最優(yōu)方案遺傳策略的選擇和確定遺傳操作設(shè)計(jì)個(gè)體冗余性處理非能力過剩網(wǎng)絡(luò)的約束處理協(xié)同對稱群體交叉遺傳操作——不可行解的優(yōu)化信息利用和處理其他輔助遺傳操作：初始群體飄移、輔助終止條件判斷算法步驟城際客專旅客列車開行方案的制定列車始發(fā)、終到站均相同，為城際客專的起訖點(diǎn)；城際客運(yùn)專線上每個(gè)區(qū)間內(nèi)列車的開行數(shù)量都是相同的；每列動車組類型相同，只有沿途停站方案不同；客流不產(chǎn)生換乘；在客流密度較小的區(qū)段，上座率會小于限定值。城際客專列車開行方案優(yōu)化問題——確定一個(gè)在給定客流OD情況下的最優(yōu)列車停站組合方案。利用上述方法求解，可以得到該算法的整體復(fù)雜度為O(αn4lnβn)，(α<1,β<1)。列車運(yùn)行圖編制模型及算法客運(yùn)專線網(wǎng)描述用節(jié)點(diǎn)、單向弧及其關(guān)系描述約束條件列車區(qū)間運(yùn)行時(shí)間約束列車停站時(shí)分約束列車追蹤間隔時(shí)間約束列車越行條件約束列車區(qū)間越行控制約束天窗時(shí)間約束列車到發(fā)時(shí)刻特殊要求約束車站到發(fā)線數(shù)量約束模型構(gòu)造目標(biāo)函數(shù)列車總旅行時(shí)間最小動車組總消耗時(shí)間最小把列車總旅行時(shí)間最小作為模型的優(yōu)化目標(biāo)。動車組總消耗時(shí)間最小等價(jià)于動車組總停留接續(xù)時(shí)間最小，它對應(yīng)于動車組最優(yōu)運(yùn)用計(jì)劃。在求得總旅行時(shí)間最小的列車運(yùn)行圖后，再求解此基礎(chǔ)上的最優(yōu)動車組運(yùn)用計(jì)劃。算法分解算法—解決客運(yùn)專線網(wǎng)的分解把客運(yùn)專線網(wǎng)分解為相對獨(dú)立的子線路分步建模求解。分解關(guān)鍵在于線路交會點(diǎn)的選擇。時(shí)空局域滾動算法—解決簡單線路上模型的求解在運(yùn)行圖時(shí)空局域內(nèi)設(shè)置窗口，在窗口中進(jìn)行運(yùn)行線尋優(yōu)，并通過滾動“窗口”動態(tài)地完成問題的求解，把原問題分解為規(guī)模較小的連續(xù)子問題進(jìn)行處理，逐步得到原問題的解。列車初始布點(diǎn)方法—解決初始解的構(gòu)造特點(diǎn)分析布點(diǎn)的對象不同列車種類少布點(diǎn)的范圍不同布點(diǎn)