李登輝，彭其淵，趙 軍，王 典，鐘慶偉

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756；2.西南交通大學(xué) 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 611756；3.合肥工業(yè)大學(xué) 汽車與交通工程學(xué)院，安徽 合肥 230000；4.中國民用航空飛行學(xué)院 空中交通管理學(xué)院，四川 廣漢 618307)

我國高速鐵路(以下簡稱“高鐵”)調(diào)度指揮通過編制和調(diào)整日計(jì)劃來組織各部門、各工種進(jìn)行日常運(yùn)輸生產(chǎn),日計(jì)劃規(guī)定了一日0:00—24:00的列車開行計(jì)劃、列車運(yùn)行計(jì)劃、動(dòng)車組運(yùn)用計(jì)劃、乘務(wù)運(yùn)用計(jì)劃、施工維修計(jì)劃等內(nèi)容。在日計(jì)劃執(zhí)行過程中,當(dāng)遇到惡劣天氣、列車晚點(diǎn)、設(shè)備故障等干擾導(dǎo)致日計(jì)劃不可行時(shí),需開展應(yīng)急調(diào)度工作,對(duì)日計(jì)劃進(jìn)行調(diào)整。應(yīng)急調(diào)整包括列車開行計(jì)劃、列車運(yùn)行計(jì)劃、車站到發(fā)線運(yùn)用計(jì)劃、動(dòng)車組運(yùn)用計(jì)劃、乘務(wù)運(yùn)用計(jì)劃等的調(diào)整,調(diào)整方案的質(zhì)量關(guān)乎干擾情況下高鐵列車運(yùn)行的秩序、安全、準(zhǔn)點(diǎn),以及行車資源的運(yùn)用效率。當(dāng)前我國高鐵調(diào)度在進(jìn)行應(yīng)急調(diào)整時(shí),調(diào)度員主要憑借經(jīng)驗(yàn)統(tǒng)籌考慮所有計(jì)劃,并對(duì)各項(xiàng)計(jì)劃進(jìn)行人工調(diào)整。基本調(diào)整流程為:①調(diào)度所應(yīng)急部門確定調(diào)整思路;②客運(yùn)調(diào)度員牽頭編制列車開行計(jì)劃調(diào)整方案;③計(jì)劃調(diào)度員根據(jù)調(diào)整方案向車務(wù)段、動(dòng)車(車輛)段、機(jī)務(wù)段、客運(yùn)段等發(fā)布調(diào)度命令;④列車調(diào)度員受局令后編制列車運(yùn)行調(diào)整計(jì)劃(以下簡稱“調(diào)整圖”),并調(diào)整車站到發(fā)線運(yùn)用計(jì)劃;⑤動(dòng)車(車輛)段、機(jī)務(wù)段和客運(yùn)段調(diào)度員受局令后根據(jù)調(diào)整圖分別調(diào)整動(dòng)車組運(yùn)用計(jì)劃和乘務(wù)運(yùn)用計(jì)劃。當(dāng)車站到發(fā)線、動(dòng)車組、乘務(wù)等任意資源無法匹配調(diào)整圖且涉及較大調(diào)整時(shí),由相應(yīng)工種調(diào)度員向應(yīng)急調(diào)度總指揮反饋,并由其修正調(diào)整后交由計(jì)劃調(diào)度重復(fù)上述過程,直到得到全部可行的調(diào)整計(jì)劃?；诮?jīng)驗(yàn)所編制調(diào)整計(jì)劃的質(zhì)量和人工調(diào)整決策的及時(shí)性難以得到有效保證。智能應(yīng)急調(diào)整的實(shí)現(xiàn)要求各項(xiàng)計(jì)劃能夠智能協(xié)同調(diào)整,但立足我國高鐵調(diào)度指揮的實(shí)際特點(diǎn),并參考目前國內(nèi)外在鐵路調(diào)度指揮領(lǐng)域的研究進(jìn)展[1]。為實(shí)現(xiàn)我國高鐵智能應(yīng)急調(diào)整,有必要將整個(gè)應(yīng)急調(diào)整問題分成列車運(yùn)行調(diào)整、動(dòng)車組運(yùn)用調(diào)整和乘務(wù)運(yùn)用調(diào)整等若干既相對(duì)獨(dú)立又相互聯(lián)系的子問題進(jìn)行單獨(dú)解決,而后逐步實(shí)現(xiàn)多個(gè)子問題間的協(xié)同調(diào)整。

本文關(guān)注高鐵在干擾導(dǎo)致區(qū)間中斷情況下調(diào)整圖確定后的動(dòng)車組運(yùn)用調(diào)整問題,在給定調(diào)整圖中為各計(jì)劃列車指派擔(dān)當(dāng)動(dòng)車組、或者為各動(dòng)車組指派運(yùn)用交路。該問題是高鐵智能應(yīng)急調(diào)整的關(guān)鍵問題之一,獲得的動(dòng)車組運(yùn)用調(diào)整計(jì)劃盡量以最小的動(dòng)車組運(yùn)用成本/代價(jià)實(shí)現(xiàn)已確定的調(diào)整圖,同時(shí)還可檢驗(yàn)調(diào)整圖在動(dòng)車組運(yùn)用上的可行性,不能獲得動(dòng)車組的列車需取消,或者反饋調(diào)整其運(yùn)行計(jì)劃后再?zèng)Q策是否需要取消。目前,國外學(xué)者對(duì)動(dòng)車組運(yùn)用調(diào)整問題已展開廣泛研究[1]。文獻(xiàn)[2]首次提出動(dòng)車組運(yùn)用調(diào)整問題,并設(shè)計(jì)滾動(dòng)時(shí)域算法進(jìn)行求解。文獻(xiàn)[3-6]通過考慮動(dòng)態(tài)客流、動(dòng)車組空駛調(diào)撥、旅客延誤、動(dòng)車組檢修等實(shí)際因素,拓展文獻(xiàn)[2]中的動(dòng)車組運(yùn)用調(diào)整問題。文獻(xiàn)[3]研究考慮動(dòng)態(tài)客流的動(dòng)車組運(yùn)用調(diào)整問題,并設(shè)計(jì)兩階段啟發(fā)式迭代方法;文獻(xiàn)[4]綜合考慮動(dòng)車組空駛調(diào)撥、動(dòng)態(tài)客流等需求,建立動(dòng)車組運(yùn)用調(diào)整模型;文獻(xiàn)[5]研究考慮乘客延誤的動(dòng)車組運(yùn)用調(diào)整問題;文獻(xiàn)[6]研究考慮動(dòng)車組檢修的動(dòng)車組運(yùn)用調(diào)整問題,建立3種不同的混合整數(shù)規(guī)劃模型。文獻(xiàn)[7-9]集中在動(dòng)車組運(yùn)用調(diào)整問題的建模方法、算法設(shè)計(jì)兩個(gè)方面。文獻(xiàn)[7-8]建立基于路徑的動(dòng)車組運(yùn)用調(diào)整模型,分別設(shè)計(jì)行列生成算法和分支定價(jià)算法求解;文獻(xiàn)[9]設(shè)計(jì)變鄰域搜索算法求解動(dòng)車組運(yùn)用調(diào)整問題。

相比而言,國內(nèi)尚未見到動(dòng)車組運(yùn)用調(diào)整方面的研究,既有相關(guān)研究集中于動(dòng)車組運(yùn)用計(jì)劃編制[10-17]、動(dòng)車組檢修計(jì)劃優(yōu)化[18-19]等問題。動(dòng)車組交路計(jì)劃編制方面,文獻(xiàn)[10]建立基于多旅行商問題的動(dòng)車組交路計(jì)劃模型;文獻(xiàn)[11-13]考慮動(dòng)車組運(yùn)行里程和運(yùn)行時(shí)間周期因素,建立動(dòng)車組交路計(jì)劃編制模型;文獻(xiàn)[14]考慮微調(diào)列車運(yùn)行線,建立動(dòng)車組周轉(zhuǎn)計(jì)劃優(yōu)化模型;文獻(xiàn)[15]考慮動(dòng)車組在樞紐內(nèi)站間、車站內(nèi)線間的調(diào)撥混用,建立動(dòng)車組運(yùn)用計(jì)劃優(yōu)化模型;文獻(xiàn)[16]考慮動(dòng)車組重聯(lián)與分解、檢修、空駛調(diào)撥,建立動(dòng)車組交路計(jì)劃編制模型;文獻(xiàn)[17]綜合考慮動(dòng)車組檢修、熱備以及空駛調(diào)撥等,建立基于接續(xù)可靠性的動(dòng)車組運(yùn)用計(jì)劃優(yōu)化模型。動(dòng)車組檢修計(jì)劃優(yōu)化方面,文獻(xiàn)[18]建立基于路徑的動(dòng)車組檢修計(jì)劃優(yōu)化模型,并設(shè)計(jì)分支定價(jià)算法;文獻(xiàn)[19]考慮檢修規(guī)程、用車需求和檢修能力限制等,建立動(dòng)車組高級(jí)修計(jì)劃優(yōu)化模型。

綜上,目前動(dòng)車組運(yùn)用調(diào)整問題在國外已獲得廣泛關(guān)注和研究,但在國內(nèi)尚未得到高度關(guān)注。國外既有動(dòng)車組運(yùn)用調(diào)整相關(guān)研究未全面刻畫動(dòng)車組檢修、列車停運(yùn)、動(dòng)車組空駛調(diào)撥/回送、熱備動(dòng)車組啟用等在我國高鐵動(dòng)車組調(diào)度中需考慮的要求和常采用的調(diào)度措施,例如,除文獻(xiàn)[3]外均未考慮啟用熱備動(dòng)車組,除文獻(xiàn)[6,8]外均未考慮動(dòng)車組檢修要求,除文獻(xiàn)[4]外均未考慮動(dòng)車組空駛調(diào)撥/回送等,不適用于我國高鐵動(dòng)車組運(yùn)用調(diào)整實(shí)際需求。此外,文獻(xiàn)[4]雖然考慮了動(dòng)車組空駛調(diào)撥,但未對(duì)動(dòng)車組在空駛過程中的運(yùn)行線作出具體安排,所得動(dòng)車組運(yùn)用調(diào)整計(jì)劃的適用性、可行性難以保證。

本文根據(jù)我國高鐵應(yīng)急情況下動(dòng)車組運(yùn)用調(diào)整特點(diǎn)和要求,首次研究干擾導(dǎo)致區(qū)間中斷下調(diào)整圖已確定后的動(dòng)車組運(yùn)用調(diào)整問題,綜合考慮動(dòng)車組檢修要求,以及列車停運(yùn)、動(dòng)車組空駛、熱備動(dòng)車組啟用等調(diào)整措施,在給定調(diào)整圖中同時(shí)確定列車的執(zhí)行狀態(tài)(開行或停運(yùn))、動(dòng)車組調(diào)整交路以及動(dòng)車組空駛調(diào)撥/回送運(yùn)行線。通過為各動(dòng)車組創(chuàng)建1個(gè)接續(xù)網(wǎng)絡(luò),將原問題構(gòu)建為具有多項(xiàng)式規(guī)模的整數(shù)線性規(guī)劃模型,在建模時(shí),利用多商品網(wǎng)絡(luò)流點(diǎn)-弧模型框架建模動(dòng)車組接續(xù)約束,利用調(diào)整圖中各區(qū)間相鄰列車運(yùn)行線間的空隙建模動(dòng)車組空駛運(yùn)行線約束,該模型對(duì)于實(shí)際規(guī)模問題可直接采用商業(yè)優(yōu)化軟件在普通個(gè)人計(jì)算機(jī)上快速求得最優(yōu)解。以鄭州動(dòng)車段實(shí)際數(shù)據(jù)構(gòu)造1組例子驗(yàn)證所提出模型的正確性和有效性。

1 問題描述

我國高鐵動(dòng)車組基本配屬到各個(gè)動(dòng)車(車輛)段,各動(dòng)車(車輛)段下轄若干動(dòng)車所,段配屬動(dòng)車組分配到各動(dòng)車所進(jìn)行日常運(yùn)用和管理,應(yīng)急情況下不同動(dòng)車所配屬動(dòng)車組可調(diào)撥使用。動(dòng)車組實(shí)行以走行公里周期為主、時(shí)間周期為輔(先到為準(zhǔn))的計(jì)劃預(yù)防修制度,運(yùn)用時(shí)多采用不固定區(qū)段運(yùn)用方式,不允許不同車型的替代;檢修時(shí)原則上在其配屬動(dòng)車所的規(guī)定時(shí)段內(nèi)進(jìn)行,必要時(shí)可委托外動(dòng)車所。在實(shí)際應(yīng)急調(diào)整過程中,需嚴(yán)格按照列車運(yùn)行調(diào)整計(jì)劃中各計(jì)劃列車的車型需求為其指派動(dòng)車組,車型相同且接續(xù)時(shí)間滿足要求的兩列列車才能由同一動(dòng)車組擔(dān)當(dāng),不能獲得動(dòng)車組的列車需取消,或者反饋調(diào)整其運(yùn)行計(jì)劃后再?zèng)Q策是否需要取消。為提高動(dòng)車組運(yùn)用調(diào)整的靈活性及抗干擾能力,可調(diào)撥熱備或空閑動(dòng)車組在計(jì)劃初停放地點(diǎn)或者擔(dān)當(dāng)完一列車后空駛至異地接續(xù)列車,或安排擔(dān)當(dāng)完一列車后的動(dòng)車組空駛回送至異地停放,以供次日運(yùn)用。

本文綜合考慮動(dòng)車組檢修要求以及列車停運(yùn)、動(dòng)車組空駛、熱備車啟用等措施,研究1個(gè)動(dòng)車(車輛)段在其服務(wù)范圍內(nèi)在干擾導(dǎo)致區(qū)間中斷情況下給定調(diào)整圖的動(dòng)車組運(yùn)用調(diào)整問題,服務(wù)線路均為雙線鐵路。為確保動(dòng)車組運(yùn)用調(diào)整計(jì)劃的編制質(zhì)量,從全局出發(fā),將研究的計(jì)劃時(shí)段取為日計(jì)劃對(duì)應(yīng)的整個(gè)時(shí)段。在計(jì)劃時(shí)段內(nèi),干擾發(fā)生前,列車按當(dāng)前列車運(yùn)行計(jì)劃運(yùn)行,動(dòng)車組按當(dāng)前動(dòng)車組運(yùn)用計(jì)劃擔(dān)當(dāng)列車;干擾發(fā)生后,依據(jù)給定的調(diào)整圖調(diào)整動(dòng)車組運(yùn)用計(jì)劃?？紤]到現(xiàn)場應(yīng)急調(diào)整時(shí)可能發(fā)生多起干擾,調(diào)度員需多次調(diào)整日計(jì)劃,對(duì)此,若當(dāng)前的動(dòng)車組運(yùn)用調(diào)整計(jì)劃不可行,則可更新計(jì)劃時(shí)段內(nèi)的干擾信息,重新求解對(duì)應(yīng)的動(dòng)車組運(yùn)用調(diào)整問題,從而動(dòng)態(tài)更新動(dòng)車組運(yùn)用調(diào)整計(jì)劃,確保當(dāng)日日計(jì)劃順利完成。調(diào)整結(jié)束后,調(diào)度員可根據(jù)調(diào)整結(jié)果和次日列車開行方案編制次日動(dòng)車組運(yùn)用計(jì)劃,納入次日日計(jì)劃,或以調(diào)度命令調(diào)整已納入次日日計(jì)劃的動(dòng)車組運(yùn)用方案,從而保證各動(dòng)車組在其運(yùn)用周期內(nèi)正常運(yùn)用。注意,給定調(diào)整圖中未預(yù)先鋪畫空駛運(yùn)行線,若采用動(dòng)車組空駛調(diào)整措施,需額外在給定調(diào)整圖中插空鋪畫動(dòng)車組空駛運(yùn)行線,以為動(dòng)車組空駛作出具體可行的安排。

簡便起見,以1個(gè)只服務(wù)于一條高鐵線路的動(dòng)車段為例,示例線路的列車運(yùn)行計(jì)劃和動(dòng)車組運(yùn)用計(jì)劃見圖1,對(duì)本文所研究的動(dòng)車組運(yùn)用調(diào)整問題進(jìn)行描述。考慮動(dòng)車段下轄1個(gè)動(dòng)車所d,鄰接車站s2,配屬b1型和b2型動(dòng)車組共5列,編號(hào)為k1～k5,其中k1、k4和k5為b1型,剩余為b2型。服務(wù)線路含7個(gè)車站,按列車運(yùn)行上行方向依次編號(hào)為s1～s7。線路一日計(jì)劃開行24列列車,其中,動(dòng)車所d擔(dān)當(dāng)12列(圖1中實(shí)線所示),編號(hào)依次為i1～i12,其中列車i1～i5和i10～i12的圖定車型為b1型,其余列車的圖定車型為b2型,計(jì)劃共由4條動(dòng)車組交路服務(wù),分別由動(dòng)車組k1～k4擔(dān)當(dāng),動(dòng)車組k5熱備并停放在動(dòng)車所d;剩余12列列車(圖1中短劃線所示),由其他動(dòng)車所的動(dòng)車組擔(dān)當(dāng)。按圖1所示的動(dòng)車組運(yùn)用計(jì)劃,每日開始運(yùn)營后,動(dòng)車組k1～k4從各自停放地點(diǎn)出發(fā),擔(dān)當(dāng)完各自的交路后,返回指定地點(diǎn)停放或檢修。

圖1 示例線路的列車運(yùn)行計(jì)劃和動(dòng)車組運(yùn)用計(jì)劃(單位:km)

圖2 示例線路的調(diào)整圖(單位:km)

示例線路的動(dòng)車組運(yùn)用調(diào)整計(jì)劃見圖3。首先,為避免列車i5取消,在列車i8和i10之間插入從動(dòng)車所d到車站s4的空駛運(yùn)行線e1,安排熱備動(dòng)車組k5從動(dòng)車所d出發(fā)經(jīng)e1空駛至車站s4擔(dān)當(dāng)列車i5。其次,因無可用動(dòng)車組而取消列車i7。雖然動(dòng)車組k2可從動(dòng)車所d空駛接續(xù)列車i7,但會(huì)導(dǎo)致更多列車(即列車i8和i9)取消,故取消列車i7。最后,插入從車站s4到動(dòng)車所d的空駛回送運(yùn)行線e2和e3,分別供動(dòng)車組k3和k1返回動(dòng)車所d停放與檢修。

圖3 示例線路的動(dòng)車組運(yùn)用調(diào)整計(jì)劃(單位:km)

動(dòng)車組運(yùn)用調(diào)整問題需滿足一定安全和能力約束,包括各動(dòng)車組只能擔(dān)當(dāng)車型相同、接續(xù)時(shí)間滿足要求的列車,計(jì)劃末各動(dòng)車所/車站的各車型動(dòng)車組數(shù)量須與計(jì)劃初相同,插入的空駛運(yùn)行線(如e2、e3)需滿足兩兩之間以及與相鄰列車運(yùn)行線的到發(fā)間隔約束,各動(dòng)車組走行公里與運(yùn)用時(shí)間不能超過檢修周期等。同時(shí),動(dòng)車組運(yùn)用調(diào)整應(yīng)盡量減小對(duì)給定調(diào)整圖、動(dòng)車組運(yùn)用計(jì)劃的影響,并盡量提高動(dòng)車組運(yùn)用效率,降低運(yùn)用成本。目前現(xiàn)場對(duì)動(dòng)車組運(yùn)用調(diào)整質(zhì)量缺乏形成共識(shí)的度量指標(biāo),基于筆者與我國高鐵動(dòng)車調(diào)度員的交流,并參照國外動(dòng)車組運(yùn)用調(diào)整研究[2-8]的做法,提出4個(gè)目標(biāo)項(xiàng):①最小化調(diào)整圖中計(jì)劃列車的取消數(shù)量,以最大程度實(shí)現(xiàn)調(diào)整圖;②最小化動(dòng)車組總接續(xù)偏差,即動(dòng)車組運(yùn)用調(diào)整計(jì)劃與日計(jì)劃在各動(dòng)車組接續(xù)上的偏差,以控制對(duì)日動(dòng)車組運(yùn)用計(jì)劃的影響;③最小化動(dòng)車組總走行車公里,以減少動(dòng)車組空駛次數(shù)和運(yùn)行成本;④最小化動(dòng)車組總運(yùn)用時(shí)間,以避免動(dòng)車組空駛在途經(jīng)車站的無效等待時(shí)間,提高運(yùn)用效率。通過引入權(quán)重系數(shù),將4個(gè)目標(biāo)項(xiàng)線性加權(quán)求和為一個(gè)目標(biāo)函數(shù)。注意,根據(jù)現(xiàn)場反饋,高質(zhì)量的動(dòng)車組運(yùn)用調(diào)整計(jì)劃應(yīng)按字典序逐步優(yōu)化上述4個(gè)目標(biāo)項(xiàng),在求解具體問題時(shí),可根據(jù)4個(gè)目標(biāo)項(xiàng)的取值范圍合理設(shè)置對(duì)應(yīng)權(quán)重系數(shù)的取值,確保各目標(biāo)項(xiàng)的最小加權(quán)值(零值除外)不小于其后續(xù)目標(biāo)項(xiàng)的最大加權(quán)值,以實(shí)現(xiàn)按字典序優(yōu)化的目的。此外,若啟用熱備動(dòng)車組擔(dān)當(dāng)調(diào)整圖中的列車,必然會(huì)產(chǎn)生動(dòng)車組接續(xù)偏差,并當(dāng)啟用的熱備車需空駛至異地接續(xù)列車或存放時(shí)也會(huì)增加走行車公里,所以通過逐步最小化上述第二和第三個(gè)目標(biāo)項(xiàng)可刻畫熱備動(dòng)車組的啟用代價(jià)和運(yùn)行成本,故不再單獨(dú)為熱備動(dòng)車組引入目標(biāo)項(xiàng)。

綜上,本文問題可描述為:給定考慮動(dòng)車段及其下轄動(dòng)車所、服務(wù)范圍內(nèi)所有列車(含本段和外段擔(dān)當(dāng)列車)、日列車運(yùn)行計(jì)劃和動(dòng)車組運(yùn)用計(jì)劃、計(jì)劃初配屬動(dòng)車組分布及其運(yùn)用狀態(tài),以及從干擾發(fā)生時(shí)刻起的調(diào)整圖,動(dòng)車組運(yùn)用調(diào)整問題研究的是在給定調(diào)整圖中同時(shí)確定本段擔(dān)當(dāng)列車的執(zhí)行狀態(tài)(開行或停運(yùn))、動(dòng)車組調(diào)整交路、以及動(dòng)車組空駛調(diào)撥/回送運(yùn)行線,使得插入的動(dòng)車組空駛運(yùn)行線與其他正常開行列車的運(yùn)行線無沖突、各動(dòng)車組滿足檢修規(guī)定,且列車取消數(shù)量、動(dòng)車組總接續(xù)偏差、動(dòng)車組總走行車公里、動(dòng)車組總運(yùn)用時(shí)間的線性加權(quán)和最小。

動(dòng)車組運(yùn)用調(diào)整是復(fù)雜的實(shí)時(shí)決策優(yōu)化問題,為了明確所研究問題的邊界并便于讀者理解和后續(xù)方法闡述,基于我國高鐵調(diào)度應(yīng)急調(diào)整實(shí)際做法,提出以下假設(shè):

(1)在調(diào)整圖中確定動(dòng)車組運(yùn)用調(diào)整計(jì)劃時(shí),若再允許改變列車到發(fā)時(shí)刻容易導(dǎo)致給定調(diào)整圖不可行,規(guī)定由本段擔(dān)當(dāng)?shù)牧熊嚲凑照{(diào)整圖運(yùn)行,由外段擔(dān)當(dāng)?shù)牧熊嚲袆?dòng)車組服務(wù)且按照調(diào)整圖正常開行。

(2)干擾發(fā)生前,各列車按日計(jì)劃運(yùn)行,各動(dòng)車組按日計(jì)劃擔(dān)當(dāng)列車。

(3)考慮在現(xiàn)場各動(dòng)車段/所的配屬動(dòng)車組基本按固定周期循環(huán)運(yùn)用與檢修,為盡快恢復(fù)動(dòng)車組正常運(yùn)用秩序,規(guī)定在日計(jì)劃中有檢修任務(wù)的動(dòng)車組需在計(jì)劃時(shí)段內(nèi)終到日計(jì)劃為其檢修安排的動(dòng)車所。

(4)鑒于目前在現(xiàn)場各動(dòng)車所一般只允許其配屬動(dòng)車組按照運(yùn)用計(jì)劃在完成一日運(yùn)輸任務(wù)后回到所內(nèi)重聯(lián)或分解,耗時(shí)數(shù)小時(shí),同時(shí)只有個(gè)別動(dòng)車所在日間個(gè)別車站內(nèi)開展了動(dòng)車組重聯(lián)/分解運(yùn)用實(shí)驗(yàn)[20],耗時(shí)30 min左右,且在技術(shù)、作業(yè)組織、規(guī)則制度等上還存在許多不適應(yīng)性,本研究不考慮動(dòng)車組的重聯(lián)/分解運(yùn)用。

(5)本段配屬動(dòng)車組在擔(dān)當(dāng)列車、空駛調(diào)撥/回送過程中,不考慮司機(jī)等乘務(wù)班組數(shù)量約束。

2 動(dòng)車組接續(xù)網(wǎng)絡(luò)構(gòu)造

T、t分別為考慮動(dòng)車段服務(wù)范圍內(nèi)所有列車(含本段和外段擔(dān)當(dāng)?shù)牧熊?的集合及其索引;K、k分別為考慮動(dòng)車段配屬的可用于在日計(jì)劃中擔(dān)當(dāng)列車的動(dòng)車組集合及其索引,每列動(dòng)車組k∈K有1個(gè)3元組屬性(ξk,δk,qk),分別為動(dòng)車組k的車型、配屬動(dòng)車所和計(jì)劃初停放地點(diǎn)。為方便建模,根據(jù)給定的調(diào)整圖,利用動(dòng)車組接續(xù)規(guī)則(車型匹配、接續(xù)時(shí)間要求等),抽象動(dòng)車組k∈K從發(fā)車到收車運(yùn)用過程中的全部接續(xù),包括干擾發(fā)生前已按日計(jì)劃執(zhí)行的全部接續(xù)和干擾發(fā)生后的全部可行接續(xù)兩部分,構(gòu)建動(dòng)車組k的接續(xù)網(wǎng)絡(luò)Gk=(Nk,Ak),其中Nk和Ak分別為Gk的頂點(diǎn)集和弧集。注意,動(dòng)車組空駛會(huì)增大動(dòng)車組運(yùn)用成本,因而實(shí)際調(diào)度中只有在必要情況下在一定運(yùn)營里程范圍內(nèi)才允許發(fā)生。鑒于此,本文在生成動(dòng)車組接續(xù)網(wǎng)絡(luò)時(shí)設(shè)置了動(dòng)車組空駛調(diào)撥走行公里閾值,可根據(jù)實(shí)際情況取值。同時(shí),為滿足次日日計(jì)劃開行列車對(duì)動(dòng)車組的需求,不對(duì)動(dòng)車組空駛回送走行公里進(jìn)行限制,使動(dòng)車組能從其擔(dān)當(dāng)列車的終到站空駛回送至其配屬動(dòng)車段下轄任意動(dòng)車所或其他計(jì)劃停放地點(diǎn),從而保證次日日計(jì)劃開行列車均能有動(dòng)車組擔(dān)當(dāng)。

基于圖2所示的調(diào)整圖,以動(dòng)車組k5為例闡述接續(xù)網(wǎng)絡(luò)Gk=(Nk,Ak)的構(gòu)建方法。動(dòng)車組k5的接續(xù)網(wǎng)絡(luò)G5見圖4。為方便描述,該例中假設(shè)動(dòng)車組空駛調(diào)撥走行公里閾值為180 km。

圖4 動(dòng)車組k5的接續(xù)網(wǎng)絡(luò)

(4)引入虛擬終點(diǎn)nsink以構(gòu)造單源單匯接續(xù)網(wǎng)絡(luò)Gk,在圖4中以頂點(diǎn)8表示。

3 數(shù)學(xué)模型

3.1 符號(hào)定義

除第2節(jié)已定義的符號(hào)以外,本節(jié)模型使用的其他符號(hào)及其定義見表1～表3。

表1 集合、索引定義

表2 參數(shù)定義

表3 決策變量定義

3.2 目標(biāo)函數(shù)

根據(jù)第1節(jié)問題描述及3.1節(jié)符號(hào)定義,目標(biāo)函數(shù)可表達(dá)為

(1)

式中:α1、α2、α3和α4為權(quán)重,用于權(quán)衡4個(gè)目標(biāo)項(xiàng)的重要性,在實(shí)際實(shí)施時(shí),為實(shí)現(xiàn)按字典序逐步優(yōu)化這四個(gè)目標(biāo)項(xiàng),可首先求出各個(gè)目標(biāo)項(xiàng)下的最優(yōu)解及其對(duì)應(yīng)的4個(gè)目標(biāo)項(xiàng)的取值;其次獲得各目標(biāo)項(xiàng)的最小值、最大值和取值范圍;接著以各目標(biāo)項(xiàng)的最小加權(quán)值(零值除外)不小于其后續(xù)目標(biāo)項(xiàng)的最大加權(quán)值為條件,設(shè)置4個(gè)目標(biāo)權(quán)重的取值。

3.3 約束條件

3.3.1 動(dòng)車組接續(xù)約束

動(dòng)車組接續(xù)約束為

(2)

(3)

(4)

(5)

(6)

3.3.2 動(dòng)車組數(shù)量平衡約束

為滿足次日列車開行需要,計(jì)劃末各動(dòng)車組停放地點(diǎn)的各車型動(dòng)車組的數(shù)量需與計(jì)劃初相同,即動(dòng)車組數(shù)量平衡約束,表示為

?s∈Sdepot?b∈B

(7)

3.3.3 動(dòng)車組空駛運(yùn)行線約束

按第1節(jié)問題描述,在動(dòng)車組運(yùn)用調(diào)整過程中,若需安排動(dòng)車組空駛至異地接續(xù)列車或停放,需在給定調(diào)整圖中為這些空駛動(dòng)車組插空鋪畫空駛運(yùn)行線,涉及的約束包括基本約束和間隔約束。

(1)基本約束

基本約束包括始發(fā)時(shí)刻約束、區(qū)間運(yùn)行時(shí)分約束、車站停站時(shí)間約束、終到時(shí)刻約束,表示為

(8)

(9)

(10)

?(s,s′)∈Qi,j

(11)

(12)

(13)

(2)間隔約束

圖5 動(dòng)車組空駛接續(xù)示意圖

?(s,s′)∈Qi,j

(14)

?(i,j)∈Adead

(15)

?(s,s′)∈Qi,j

(16)

?(s,s′)∈Qi,j

(17)

(18)

(19)

(20)

3.3.4 動(dòng)車組檢修約束

(21)

(22)

(23)

式(22)中,左側(cè)第一項(xiàng)和第二項(xiàng)分別表示各動(dòng)車組k∈K在計(jì)劃時(shí)段內(nèi)擔(dān)當(dāng)列車的走行公里和空駛調(diào)撥/回送的走行公里,兩者之和為其計(jì)劃時(shí)段內(nèi)的累計(jì)走行公里。式(23)中,各動(dòng)車組k∈K在計(jì)劃時(shí)段內(nèi)的運(yùn)用時(shí)間為其在計(jì)劃末停放地點(diǎn)的實(shí)際到達(dá)時(shí)刻減去計(jì)劃初在初始停放地點(diǎn)的實(shí)際出發(fā)時(shí)刻。

3.4 整體模型與求解

綜上,高鐵在干擾導(dǎo)致區(qū)間中斷情況下調(diào)整圖已確定后的動(dòng)車組運(yùn)用調(diào)整問題可構(gòu)建為以下數(shù)學(xué)優(yōu)化模型RSRM為

RSRM式(1)

s.t. 式(2)～式(23)

?(i,j)∈Ak?t∈Ttrain

4 計(jì)算測試

以2017年鄭州動(dòng)車段配屬動(dòng)車組運(yùn)用為背景構(gòu)造1組例子,驗(yàn)證所提出模型的正確性和有效性。文中所有算例均在Intel(R) Core(TM) i5-7600 3.5 GHz CPU,16.0 GB RAM的個(gè)人計(jì)算機(jī)上采用優(yōu)化求解器CPLEX 12.8求解,求解器參數(shù)為默認(rèn)設(shè)置。

4.1 算例生成

2017年,鄭州動(dòng)車段下轄兩個(gè)動(dòng)車運(yùn)用所(鄭州所和鄭州東所),配屬動(dòng)車組有CRH2A、CRH380A、CRH380B、CRH380AL、CRH380A重聯(lián)和CRH380B重聯(lián)6種車型,共45列。其中熱備動(dòng)車組為1列CRH380AL型動(dòng)車組,日常停放于鄭州東所。根據(jù)鄭州動(dòng)車段服范圍內(nèi)某日調(diào)度日計(jì)劃構(gòu)造的動(dòng)車組運(yùn)用物理網(wǎng)絡(luò)見圖6,其中鄭焦、鄭機(jī)等城際鐵路未畫出。該物理網(wǎng)絡(luò)包含區(qū)間309個(gè),車站300個(gè),其中始發(fā)/終到站31個(gè),其余為中間站;通過/始發(fā)/終到/管內(nèi)動(dòng)車組列車共471列,其中本段擔(dān)當(dāng)164列。

圖6 動(dòng)車組運(yùn)用物理網(wǎng)絡(luò)

區(qū)間中斷下動(dòng)車組運(yùn)用調(diào)整的難度同時(shí)受導(dǎo)致區(qū)間中斷的干擾的發(fā)生地點(diǎn)、時(shí)刻和持續(xù)時(shí)間的影響,干擾發(fā)生在關(guān)鍵區(qū)間、發(fā)生時(shí)刻越早、持續(xù)時(shí)間越長,動(dòng)車組運(yùn)用調(diào)整難度可能越大;相反,干擾發(fā)生在邊緣區(qū)間、發(fā)生時(shí)刻晚、持續(xù)時(shí)間短,動(dòng)車組運(yùn)用調(diào)整難度則可能越小。為評(píng)估所提出方法對(duì)不同干擾場景下動(dòng)車組運(yùn)用調(diào)整的優(yōu)化性能,結(jié)合本段服務(wù)范圍內(nèi)京廣高鐵和徐蘭高鐵的基本情況,通過調(diào)整導(dǎo)致區(qū)間中斷干擾的發(fā)生地點(diǎn)、時(shí)刻和持續(xù)時(shí)間,共構(gòu)造18個(gè)干擾場景,對(duì)應(yīng)18個(gè)例子,干擾信息如下:

(1)干擾1～6:在9:00、12:00、13:30,由于某種原因?qū)е戮V高鐵安陽東站—鶴壁東站區(qū)間線路出現(xiàn)故障,導(dǎo)致區(qū)間通行能力全部喪失,故障持續(xù)時(shí)間分別為60、120 min。

(2)干擾7～12:在9:00、12:00、13:30,由于某種原因?qū)е戮V高鐵許昌東站—漯河西站區(qū)間線路出現(xiàn)故障,導(dǎo)致區(qū)間通行能力全部喪失,故障持續(xù)時(shí)間分別為60、120 min。

(3)干擾13～18:在9:00、12:00、13:30,由于某種原因?qū)е滦焯m高鐵澠池南站—洛陽龍門站區(qū)間線路出現(xiàn)故障,導(dǎo)致區(qū)間通行能力全部喪失,故障持續(xù)時(shí)間分別為60、120 min。

為方便描述不同干擾下的例子,引入1個(gè)三元組(a,b,c)表示例子,其中,a表示中斷區(qū)間編號(hào),安陽東站—鶴壁東站區(qū)間、許昌東站—漯河西站區(qū)間、澠池南站—洛陽龍門站區(qū)間的編號(hào)依次為(1,2)、(3,4)和(5,6),b表示干擾發(fā)生時(shí)刻,c表示干擾持續(xù)時(shí)間。上述18種干擾對(duì)應(yīng)例子的三元組表示結(jié)果見表4。其中,不同例子的調(diào)整圖按照文獻(xiàn)[21]中的基于事件-活動(dòng)網(wǎng)絡(luò)的整數(shù)規(guī)劃模型進(jìn)行求解,限于調(diào)整圖編制不是論文重點(diǎn)以及篇幅限制,不再贅述。

表4 干擾的三元組表示

例子參數(shù)按以下規(guī)則設(shè)置。結(jié)合測試算例的4個(gè)目標(biāo)項(xiàng)的取值范圍,見表5。目標(biāo)權(quán)重按α1=108,α2=106,α3=1,α4=1進(jìn)行設(shè)置。由表5可知,在所設(shè)置的目標(biāo)權(quán)重下,各目標(biāo)項(xiàng)的最小加權(quán)值(零除外)不小于其后續(xù)目標(biāo)項(xiàng)的最大加權(quán)值,例如:第1個(gè)目標(biāo)項(xiàng)的最小加權(quán)值(零除外)為108,大于其后續(xù)3個(gè)目標(biāo)項(xiàng)的最大加權(quán)值(分別為20×106,<1.2×106,<4×104),其余目標(biāo)項(xiàng)同理,從而可按字典序逐步優(yōu)化4個(gè)目標(biāo)項(xiàng)。此外,相似的目標(biāo)權(quán)重設(shè)置規(guī)則也被既有相關(guān)文獻(xiàn)[2-8]所采用。根據(jù)列車運(yùn)行計(jì)劃和動(dòng)車組運(yùn)用計(jì)劃數(shù)據(jù),同向列車的最小發(fā)車間隔取3 min,最小到達(dá)間隔取2 min,車站最小動(dòng)車組接續(xù)作業(yè)時(shí)間取15 min,動(dòng)車組走行公里周期取5 500 km,運(yùn)行時(shí)間周期取2 880 min。動(dòng)車組空駛發(fā)車、空駛接續(xù)的走行公里閾值設(shè)為500 km。由于篇幅限制,區(qū)間長度、區(qū)間運(yùn)行時(shí)分、列車相關(guān)信息等其他參數(shù)不再列出。

表5 計(jì)算結(jié)果

4.2 計(jì)算結(jié)果

CPLEX使用模型RSRM可將表4中所有例子求解到最優(yōu),計(jì)算結(jié)果見表5。其中,第1列為例子編號(hào),第2列和第3列分別為模型RSRM的變量數(shù)和約束數(shù);第4列～第8列分別為CPLEX找到的最優(yōu)目標(biāo)函數(shù)值、以及對(duì)應(yīng)的列車取消數(shù)量、動(dòng)車組總接續(xù)偏差、動(dòng)車組總走行車公里和動(dòng)車組總運(yùn)用時(shí)間。第9列～第11列分別為CPLEX找到最優(yōu)解中的動(dòng)車組空駛調(diào)撥數(shù)量、動(dòng)車組空駛回送數(shù)量和是否啟用熱備動(dòng)車組(1表示是,0表示否)。最后1列為CPLEX求解模型RSRM到最優(yōu)耗費(fèi)的時(shí)間。

由表5可知,不同干擾情況對(duì)動(dòng)車組運(yùn)用調(diào)整的影響不相同。區(qū)間(5,6)于中午12:00發(fā)生持續(xù)2 h的干擾對(duì)動(dòng)車組運(yùn)用調(diào)整影響最大,例子((5,6),12:00,120)的目標(biāo)函數(shù)值均大于其他例子。干擾地點(diǎn)和發(fā)生時(shí)刻相同情況下,通常干擾持續(xù)時(shí)間越長,列車取消數(shù)量越多、動(dòng)車組總接續(xù)偏差越大、動(dòng)車組空駛數(shù)量越多,這是因?yàn)檩^長的干擾持續(xù)時(shí)長使得較多的動(dòng)車組無法按日計(jì)劃運(yùn)用,導(dǎo)致要么取消列車、要么改變動(dòng)車組接續(xù),并造成動(dòng)車組較多的空駛運(yùn)行。

不同例子的計(jì)算結(jié)果還具有以下特點(diǎn):

(1)例子((1,2),12:00,60)和((1,2),12:00,120)等共10個(gè)例子的最優(yōu)解中均無動(dòng)車組空駛調(diào)撥,原因可能是潛在的空駛發(fā)車/接續(xù)弧由于其相應(yīng)的空駛走行公里超過閾值而未被包含在弧集合Ak中、或者集合Ak即使包含空駛發(fā)車/接續(xù)弧,但不能優(yōu)化目標(biāo)函數(shù)值。

(2)熱備動(dòng)車組和空閑動(dòng)車組均可用來空駛調(diào)撥至異地接續(xù)某些列車。比如,例子((1,2),9:00,60)和((1,2),9:00,120)的最優(yōu)解中空駛調(diào)撥次數(shù)為1,且啟用熱備動(dòng)車組,表明在這兩個(gè)例子對(duì)應(yīng)的干擾下,調(diào)撥了熱備動(dòng)車組空駛至異站接續(xù)從該站始發(fā)的列車。例子((3,4),9:00,120)、((3,4),12:00,60)等6個(gè)例子的最優(yōu)解中在啟用熱備動(dòng)車組的同時(shí),空駛調(diào)撥次數(shù)大于1,表明在這些例子對(duì)應(yīng)的干擾情況下,除啟用了熱備動(dòng)車組外,也調(diào)撥了擔(dān)當(dāng)完列車任務(wù)的空閑動(dòng)車組空駛至異地接續(xù)列車。

在計(jì)算時(shí)間方面,CPLEX使用模型RSRM對(duì)各測試?yán)幼疃嘣?0 s內(nèi)快速獲得最優(yōu)解,為各例子提供最優(yōu)的動(dòng)車組運(yùn)用調(diào)整計(jì)劃,可見該模型可較好地滿足現(xiàn)場調(diào)度員的實(shí)時(shí)決策的需求。

4.3 空駛運(yùn)行線的可行性分析

為分析模型RSRM的可行性,展示例子((1,2),9:00,60)的最優(yōu)解中的動(dòng)車組空駛運(yùn)行線(以京廣高鐵為例),如圖7中E1和E2所示。圖7展示了鄭州動(dòng)車段配屬動(dòng)車組擔(dān)當(dāng)?shù)?條交路(片段)在區(qū)間中斷下的執(zhí)行狀態(tài)。在日動(dòng)車組運(yùn)用計(jì)劃中,列車G507終到漢口站接續(xù)由該站始發(fā)的列車G518。區(qū)間安陽東—鶴壁東在9:00發(fā)生中斷并持續(xù)1 h,導(dǎo)致列車G507終到漢口站時(shí)晚點(diǎn),其擔(dān)當(dāng)動(dòng)車組無法再按日計(jì)劃接續(xù)列車G518。對(duì)于列車G518,由于滿足空車走行公里閾值和動(dòng)車組接續(xù)時(shí)間的要求,特調(diào)撥在鄭州東動(dòng)車所停留的熱備動(dòng)車組CRH380AL于10:37始發(fā),經(jīng)空駛運(yùn)行線E1至漢口站擔(dān)當(dāng)列車G518,從而避免列車G518取消。由于動(dòng)車組數(shù)量平衡約束要求,擔(dān)當(dāng)列車G507的動(dòng)車組在完成剩余列車擔(dān)當(dāng)任務(wù)后在漢口站經(jīng)空駛運(yùn)行線E2回送至其配屬的鄭州東所(入所時(shí)刻為15:31)。由圖7可知,空駛運(yùn)行線E1、E2在各途經(jīng)區(qū)間與其他列車運(yùn)行線均滿足出發(fā)間隔和到達(dá)間隔要求,可見所提出模型RSRM可正確確定出各空駛動(dòng)車組在途的可行運(yùn)行線。

圖7 例子((1,2),9:00,60)的動(dòng)車組空駛運(yùn)行線

4.4 空駛調(diào)撥策略的效果分析

圖8 使用與不使用動(dòng)車組空駛調(diào)撥策略的對(duì)比

由圖8可知,與不使用空駛調(diào)撥策略相比,使用空駛調(diào)撥策略可使8個(gè)例子即((1,2),9:00,60)、((1,2),9:00,120)、((3,4),9:00,120)、((3,4),12:00,60)、((3,4),12:00,120)、((5,6),9:00,120)、((5,6),12:00,60)和((5,6),12:00,120)的列車取消數(shù)量有所減少,減少數(shù)量最小1列,最多2列;結(jié)合表5可知,這些例子的最優(yōu)解中均調(diào)撥了熱備動(dòng)車組空駛至異地?fù)?dān)當(dāng)列車,表明調(diào)撥熱備動(dòng)車組空駛至異地?fù)?dān)當(dāng)列車是動(dòng)車組運(yùn)用調(diào)整中減少列車取消數(shù)量的有效措施。除上述例子外,其他例子使用空駛調(diào)撥策略與否,獲得的動(dòng)車組運(yùn)用調(diào)整計(jì)劃不變。結(jié)合表5進(jìn)一步表明,相同干擾下,采用空駛調(diào)撥策略較不采用該策略可拓寬動(dòng)車組運(yùn)用調(diào)整問題的解空間,進(jìn)一步保證問題的可行性,獲得更高質(zhì)量的解。需指出的是,使用動(dòng)車組空駛調(diào)撥策略也將增大調(diào)度指揮難度,增加動(dòng)車組運(yùn)用成本,在實(shí)際動(dòng)車組調(diào)度調(diào)整決策時(shí),應(yīng)綜合考慮各項(xiàng)因素確定是否采用合適的空駛調(diào)撥策略。

5 結(jié)論

本文研究了我國高鐵在干擾導(dǎo)致區(qū)間中斷情況下給定調(diào)整圖的動(dòng)車組運(yùn)用調(diào)整問題,綜合考慮動(dòng)車組檢修要求,以及動(dòng)車組空駛調(diào)撥/回送、熱備動(dòng)車組啟用等調(diào)整措施,通過為各動(dòng)車組創(chuàng)建接續(xù)網(wǎng)絡(luò),構(gòu)建了該問題的整數(shù)線性規(guī)劃模型。針對(duì)鄭州動(dòng)車段實(shí)際數(shù)據(jù)構(gòu)造的1組例子的計(jì)算結(jié)果表明,商業(yè)優(yōu)化軟件使用該模型可在普通個(gè)人計(jì)算機(jī)上快速求得實(shí)際規(guī)模例子的最優(yōu)動(dòng)車組運(yùn)用調(diào)整計(jì)劃,所得動(dòng)車組運(yùn)用調(diào)整交路和動(dòng)車組空駛調(diào)撥/回送運(yùn)行線均可行,滿足所有動(dòng)車組運(yùn)用與檢修規(guī)則且與正常開行列車無時(shí)空沖突,可用于輔助現(xiàn)場動(dòng)車組運(yùn)用調(diào)整決策;此外,啟用熱備動(dòng)車組空駛至異地?fù)?dān)當(dāng)列車有助于在動(dòng)車組運(yùn)用調(diào)整時(shí)減少列車取消數(shù)量,但因會(huì)增大調(diào)度指揮難度和動(dòng)車組運(yùn)用成本,調(diào)度員應(yīng)結(jié)合實(shí)際情況綜合考慮是否采用該項(xiàng)調(diào)整措施。

論文側(cè)重于研究干擾導(dǎo)致區(qū)間中斷情況下的動(dòng)車組運(yùn)用調(diào)整,若相應(yīng)的調(diào)整圖已確定,其他干擾情況(例如大風(fēng)導(dǎo)致區(qū)間限速、信號(hào)設(shè)備故障、列車晚點(diǎn)等)與該情況下動(dòng)車組運(yùn)用調(diào)整的主要區(qū)別在于動(dòng)車組空駛運(yùn)行線建模(見3.3.3節(jié)),下一步可將所提出的模型拓展于描述更多干擾情況下的動(dòng)車組運(yùn)用調(diào)整問題,以提高模型的適用性。其次,模型中引入了大量約束來刻畫空駛運(yùn)行線插入決策,使得模型較為復(fù)雜,下一步可嘗試簡約模型約束并設(shè)計(jì)高效的求解算法,以便滿足解決更大規(guī)模動(dòng)車組運(yùn)用調(diào)整問題的需求。隨著我國動(dòng)車組在站內(nèi)重聯(lián)/分解技術(shù)的進(jìn)步,將來可將所構(gòu)建的模型拓展來解決考慮動(dòng)車組重聯(lián)/分解的動(dòng)車組運(yùn)用調(diào)整問題,以進(jìn)一步提高動(dòng)車組運(yùn)用的抗干擾能力和效率。此外,論文所研究動(dòng)車組運(yùn)用調(diào)整問題需將對(duì)應(yīng)干擾情況下已確定的調(diào)整圖作為輸入,高速鐵路調(diào)度指揮涉及列車、動(dòng)車和動(dòng)車司機(jī)等多個(gè)專業(yè)工種,各工種的調(diào)度調(diào)整決策相互影響和制約,將來可研究多工種協(xié)同調(diào)整決策問題,例如列車運(yùn)行與動(dòng)車組運(yùn)用協(xié)同調(diào)整問題,逐步實(shí)現(xiàn)高速鐵路智能綜合應(yīng)急調(diào)整。