史錦堂，黎浩東，曹 恒，鄭亞晶

（1.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044；2.北京交通大學(xué) 綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京 100044；3.陜西交通職業(yè)技術(shù)學(xué)院 軌道交通學(xué)院，陜西 西安 710018；4.華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640）

動車運(yùn)用所（動車所）的調(diào)車作業(yè)計(jì)劃決定了所內(nèi)動車組各項(xiàng)作業(yè)先后順序、占用股道（列位）和占用起訖時刻，是動車所日常生產(chǎn)組織的重要基礎(chǔ)計(jì)劃。隨著我國高速鐵路的蓬勃發(fā)展，部分動車所的檢修能力已經(jīng)接近飽和，逐漸成為制約高速鐵路運(yùn)輸系統(tǒng)能力的重要因素之一。在既有設(shè)施設(shè)備條件下，提升動車所日常調(diào)車作業(yè)計(jì)劃的編制質(zhì)量，對提高其檢修能力和設(shè)施設(shè)備利用水平都具有很重要的現(xiàn)實(shí)意義。

國內(nèi)外部分學(xué)者對動車所調(diào)車作業(yè)問題進(jìn)行了研究。文獻(xiàn)［1］構(gòu)造了三階段的時空網(wǎng)絡(luò)圖來表示列車檢修車間的調(diào)車作業(yè)過程。文獻(xiàn)［2］設(shè)計(jì)了股道連通圖來揭示股道之間的連通關(guān)系，并以減少關(guān)鍵線區(qū)總占用時間和調(diào)車路徑費(fèi)用為優(yōu)化目標(biāo)，建立了包含動車所所有作業(yè)的調(diào)車作業(yè)計(jì)劃模型。文獻(xiàn)［3］以已知動車組占用存車線時間為前提，以提高存車線利用率和減少調(diào)車作業(yè)走行距離為優(yōu)化目標(biāo)，建立了動車所存車線運(yùn)用的0-1 規(guī)劃優(yōu)化模型。文獻(xiàn)［4］以提高動車所股道利用率為目標(biāo)，對盡端式和通過式車場進(jìn)行研究，建立了車場股道占用優(yōu)化模型。文獻(xiàn)［5］以動車組在動車所內(nèi)的總延誤時間最少為目標(biāo)，在考慮動車組執(zhí)行各項(xiàng)作業(yè)的工序不定約束基礎(chǔ)上，建立了動車所調(diào)車作業(yè)計(jì)劃優(yōu)化模型。文獻(xiàn)［6］考慮動車所作業(yè)線雙列位的因素，以最后1 列動車組檢修完成時間最少為目標(biāo)，建立了動車所一級修作業(yè)計(jì)劃優(yōu)化模型。文獻(xiàn)［7］綜合考慮了列位占用和盡端、通過式股道占用時間先后的區(qū)別，構(gòu)建了0-1 整數(shù)線性規(guī)劃模型。文獻(xiàn)［8］以動車組車底出入所時間為聯(lián)系，將動車所內(nèi)部調(diào)車作業(yè)計(jì)劃與外部的高速鐵路樞紐站技術(shù)作業(yè)計(jì)劃協(xié)同編制。文獻(xiàn)［9］針對橫列、盡端式車場布局的動車所，構(gòu)建了一級修調(diào)車作業(yè)整數(shù)規(guī)劃模型。文獻(xiàn)［10］在文獻(xiàn)［9］的基礎(chǔ)上進(jìn)一步考慮了股道雙列位因素。文獻(xiàn)［11］綜合考慮了包含列車檢修、單元重組、股道占用和進(jìn)路排列的調(diào)車計(jì)劃問題，構(gòu)建了混合整數(shù)規(guī)劃模型，并用CPLEX 求解。文獻(xiàn)［12］針對動車所一級修作業(yè)問題，重點(diǎn)考慮了檢修與清洗的靈活工序和列位占用，構(gòu)建了一級修作業(yè)的非線性模型，并設(shè)計(jì)遺傳算法來求解。文獻(xiàn)［13］建立了考慮列位占用的動車所調(diào)車作業(yè)計(jì)劃編制模型，設(shè)計(jì)了基于啟發(fā)式規(guī)則的模擬退火算法求解模型，并在算法中考慮了短編動車組在動車所內(nèi)的重聯(lián)解編作業(yè)。文獻(xiàn)［14］設(shè)計(jì)了鄰域搜索算法來解決荷蘭鐵路中的列車單元調(diào)車問題。文獻(xiàn)［15—16］基于不同視角對動車所的檢修能力進(jìn)行了研究。

國外的相關(guān)研究著重考慮了列車單元重組約束，不適用于我國。已有國內(nèi)的相關(guān)研究大多基于假設(shè)對實(shí)際生產(chǎn)作業(yè)進(jìn)行簡化，如假設(shè)動車組只需檢修與清洗等少數(shù)作業(yè)［5?6，9?10，12］、所有動車組的檢修任務(wù)相同［5?7，9?10，12］、所有動車組的檢修工序已知［2，6，9，13］、檢修時不需要考慮列位占用［2，5，8?9］等。這些假設(shè)雖然有利于問題的建模和求解，但也在一定程度上背離了現(xiàn)場實(shí)際，降低了提出方法的適用性與通用性，難以應(yīng)用于實(shí)際工作中。特別是當(dāng)動車所的檢修能力不夠時，如果不考慮多次靈活存車的操作形式，將會大大增加動車組在檢修線上的停留時間，降低計(jì)劃的抗擾動能力［17］。此外，每條股道均設(shè)置了雙列位，這也會進(jìn)一步增加對長、短不同編組列車統(tǒng)一進(jìn)行調(diào)車作業(yè)計(jì)劃編制的難度。

以適用于不同車場布置類型的動車所為前提，本文重點(diǎn)考慮靈活存車、列位占用問題，在統(tǒng)籌各項(xiàng)檢修作業(yè)先后順序安排、進(jìn)路沖突、車場布置類型等現(xiàn)實(shí)情況的基礎(chǔ)上，建立可用于動車所調(diào)車作業(yè)計(jì)劃優(yōu)化的字典排序目標(biāo)規(guī)劃二級模型；以動車所內(nèi)的所有待開展作業(yè)為模型主要索引，通過決策所有作業(yè)的股道占用情況，得出所有待檢修動車組的調(diào)車作業(yè)計(jì)劃；依托某縱列式二級二場布置的動車所設(shè)計(jì)算例，驗(yàn)證模型的正確性以及其統(tǒng)籌調(diào)度所內(nèi)作業(yè)任務(wù)的能力。

1 問題描述

目前，我國鐵路最常見的動車所布置形式為縱列式二級二場和橫列、盡端式，這2 種動車所的具體布置形式如圖1所示。圖中：羅馬數(shù)字為咽喉編號；帶圈阿拉伯?dāng)?shù)字為車場中的不同列位位置。根據(jù)百度地圖的衛(wèi)星圖數(shù)據(jù)統(tǒng)計(jì)，全路54 個動車所中，以這2種布置形式為主體的動車所占85%，且其中過半采用作業(yè)間銜接更為順暢的縱列式布置，即縱列式二級二場布置是我國動車所最典型的布置形式。為適應(yīng)不同編組動車組的檢修作業(yè)，動車所內(nèi)的股道大都設(shè)計(jì)為2 個列位，這樣1 條股道可容納1列長編動車組或者2 列短編動車組，如圖1中，位置①和②分別為通過式車場中靠近Ⅰ和Ⅱ號咽喉的列位集合；位置③和⑤分別為盡端式車場中靠近進(jìn)口位置的列位集合；位置④和⑥分別為盡端式車場中靠近盡端位置的列位集合。

圖1 典型的動車所布置形式

動車所內(nèi)動車組的檢修作業(yè)內(nèi)容主要包括：一級修、二級修、吸污作業(yè)、清洗作業(yè)、探傷作業(yè)、車輪鏇修作業(yè)等，其中二級修又根據(jù)動車組的行駛時間和里程分不同等級的檢修包來執(zhí)行。為了開展上述作業(yè)，動車所設(shè)置了不同功能的車場（線區(qū)），如檢修場、清洗場、吸污場和存車場等；根據(jù)2 端是否都能通行列車，車場又可分為通過式、盡端式等形式。相互連接的車場組成了帶有檢修、存車等功能的動車所，而不同功能、不同形式車場間的不同連接方式，又形成了不同的動車所布置形式。

動車所日常調(diào)車作業(yè)計(jì)劃編制需在給定動車組運(yùn)用計(jì)劃（動車組入所、出所時刻）、檢修計(jì)劃和動車所布局及股道數(shù)量的前提下，解決檢修作業(yè)順序、股道與列位占用和進(jìn)路沖突疏解等3 個方面的問題，確保所有動車組都能及時完成檢修任務(wù)，并力求在關(guān)鍵線區(qū)總占用時長和總存車次數(shù)上達(dá)到最小化。

1）靈活存車思路下的檢修作業(yè)順序安排

動車組入所檢修，必然要在從入所到出所的時間段內(nèi)，按照一定的作業(yè)順序完成既定的作業(yè)任務(wù)，而這也是動車所日常調(diào)車作業(yè)計(jì)劃需首先確定的問題。將檢修、清洗等作業(yè)視為必要作業(yè)，將存車作業(yè)視為非必要作業(yè)，某列動車組從入所到出所的各項(xiàng)作業(yè)流程如圖2所示。圖中：實(shí)線方框表示必要作業(yè)；虛線和點(diǎn)劃線方框表示非必要作業(yè)；五角星表示作業(yè)項(xiàng)目中可能有更多的必要作業(yè)及其前序存車作業(yè)，在此省略；箭頭表示不同作業(yè)間轉(zhuǎn)場形成的調(diào)車運(yùn)行進(jìn)路，包括入所進(jìn)路、出所進(jìn)路和作業(yè)間的調(diào)車進(jìn)路等。

圖2 動車組檢修作業(yè)流程

動車組入所后，假如此時某項(xiàng)必要作業(yè)的作業(yè)設(shè)備處于空閑狀態(tài)，將立即進(jìn)行作業(yè)；否則需要在存車場中等待，直至該設(shè)備空閑。當(dāng)動車組某項(xiàng)必要作業(yè)結(jié)束之后，假如下一項(xiàng)必要作業(yè)的作業(yè)設(shè)備處于空閑狀態(tài)，將立即進(jìn)行作業(yè)；否則需要在存車場中等待，直至設(shè)備空閑。假如動車組下一項(xiàng)必要作業(yè)的作業(yè)設(shè)備及相應(yīng)存車場設(shè)備均處于忙碌狀態(tài)，則意味著動車組需停留在當(dāng)前作業(yè)的股道上，等待資源釋放。動車組完成所有必要作業(yè)后，假如存車場中有空閑位置，將進(jìn)入存車線中等待出發(fā)；否則將繼續(xù)停留在當(dāng)前作業(yè)線上，直至規(guī)定的出發(fā)時刻或存車場中出現(xiàn)空閑。

以帶有一級修和清洗這2 項(xiàng)必要作業(yè)的作業(yè)任務(wù)為例，分析其具體流程。若某待檢動車組有這2項(xiàng)必要作業(yè)待開展，那么根據(jù)設(shè)備是否處于空閑狀態(tài)，存車次數(shù)可能為0～3 次，執(zhí)行進(jìn)路次數(shù)可能為3～6 次，則該動車組從入所到出所，所有可能的作業(yè)流程共有以下2×23=16種。

（1）流程1和流程2：到達(dá)→一級修/清洗→清洗/一級修→出發(fā)。

（2）流程3和流程4：到達(dá)→一級修/清洗→清洗/一級修→存車→出發(fā)。

（3）流程5 和流程6：到達(dá)→存車→一級修/清洗→清洗/一級修→出發(fā)。

（4）流程7 和流程8：到達(dá)→一級修/清洗→存車→清洗/一級修→出發(fā)。

（5）流程9 和流程10：到達(dá)→一級修/清洗→存車→清洗/一級修→存車→出發(fā)。

（6）流程11和流程12：到達(dá)→存車→一級修/清洗→存車→清洗/一級修→出發(fā)。

（7）流程13和流程14：到達(dá)→存車→一級修/清洗→清洗/一級修→存車→出發(fā)。

（8）流程15和流程16：到達(dá)→存車→一級修/清洗→存車→清洗/一級修→存車→出發(fā)。

綜合考慮動車所內(nèi)的所有作業(yè)，部分動車組的必要作業(yè)數(shù)量不止2 項(xiàng)。若某待檢修動車組待開展的必要作業(yè)為n項(xiàng)，根據(jù)設(shè)備是否處于空閑狀態(tài)，存車次數(shù)可能為0～(n+1)次，進(jìn)路執(zhí)行次數(shù)可能為(n+1)～(2n+2)次，則該動車組從入所到出所，所有可能的作業(yè)流程共有n！×2n+1種。

由上述分析可知，當(dāng)必要作業(yè)次數(shù)增多時，所有可能的作業(yè)流程數(shù)量將呈指數(shù)級增多，問題的不確定性和復(fù)雜性也隨之大大提高。以上文一級修為例，雖然必要作業(yè)順序只有2 種（先檢修和先清洗），但是考慮了靈活存車之后的所有可能作業(yè)流程卻有16 種之多。此外，相對于必要作業(yè)，增加存車等非必要環(huán)節(jié)會提高調(diào)車作業(yè)量，增加咽喉壓力，影響動車所能力利用。因此，在動車所日常調(diào)車作業(yè)計(jì)劃編制過程中，需盡可能減少動車組的存車次數(shù)以及相應(yīng)的調(diào)車作業(yè)。

2）股道占用與列位占用

股道占用針對所有動車組，列位占用針對短編動車組。當(dāng)2 列待檢短編動車組同時占用同一股道時，根據(jù)車場的布置形式，對動車組的進(jìn)出又有不同調(diào)度規(guī)則。假如當(dāng)前車場為盡端式時，則先進(jìn)入股道的動車組需要等后進(jìn)入的動車組離開后才能離開（“先進(jìn)后出”規(guī)則）；當(dāng)前車場為通過式時，則后進(jìn)入股道的動車組需要等先進(jìn)入的動車組離開后才能離開（“先進(jìn)先出”規(guī)則）；當(dāng)前車場為盡端式與通過式混合連接的形式時，則還需要結(jié)合實(shí)際情況按規(guī)則進(jìn)行調(diào)度。因此，在動車所日常調(diào)車作業(yè)計(jì)劃編制過程中，需根據(jù)不同車場布局形式，決策短編動車組對具體列位的占用關(guān)系。

3）進(jìn)路沖突疏解

在股道聯(lián)通關(guān)系上，橫列、盡端式布置［5，9?10］的動車所股道聯(lián)通都只能通過唯一的咽喉，相對簡單；而縱列式二級二場布置涉及2 個車場的連接，股道聯(lián)通關(guān)系較為復(fù)雜，調(diào)車路徑也更為復(fù)雜。假設(shè)縱列式二級二場布置的動車所內(nèi)設(shè)有足夠的中轉(zhuǎn)線，能夠保證動車組在需要轉(zhuǎn)線時都能夠順利轉(zhuǎn)線（盡端式股道在盡端處的列位除外，即圖1中位置④和⑥的列位）。例如圖1（a）中，中轉(zhuǎn)線設(shè)在通過式車場內(nèi)的某條股道，中轉(zhuǎn)線的兩頭連接兩端的Ⅰ和Ⅱ號咽喉，假設(shè)某動車組停在位置①的列位上等待轉(zhuǎn)線到位置③，若位置②有車停留而阻擋轉(zhuǎn)線，動車組可以按Ⅰ號咽喉→中轉(zhuǎn)線→Ⅱ號咽喉的路徑到達(dá)位置③；否則可以按位置②→Ⅱ號咽喉的路徑直接到達(dá)位置③。

可行的調(diào)車作業(yè)計(jì)劃需要嚴(yán)格避免進(jìn)路沖突，即2 條敵對進(jìn)路的執(zhí)行時間不能交叉重疊。為簡化模型中對調(diào)車進(jìn)路沖突的檢查與疏解，本文假設(shè)同一時刻至多只能執(zhí)行1條進(jìn)路［10］，即相鄰2次執(zhí)行進(jìn)路的中間間隔時間必須大于某個特定的安全間隔時間，通過留足準(zhǔn)備時間的形式確保調(diào)車作業(yè)過程安全。

2 模型構(gòu)建策略

為使構(gòu)建得到的模型能夠?qū)崿F(xiàn)多目標(biāo)下的順序優(yōu)化，避免設(shè)置單一目標(biāo)帶來的局限性，且動車組檢修任務(wù)不同的情況下模型能夠統(tǒng)籌調(diào)度動車所內(nèi)所有作業(yè)任務(wù)，需考慮以下2 個因素，分別是多目標(biāo)下的模型分級處理能力和動車組檢修任務(wù)不同時的建模對象異質(zhì)性影響。

1）多目標(biāo)下模型的分級處理能力

動車所內(nèi)開展檢修、洗車、鏇修等作業(yè)的股道數(shù)量較少，成為制約檢修能力的瓶頸，而存車股道資源一般較為豐富，所以動車組結(jié)束關(guān)鍵線區(qū)的作業(yè)后，應(yīng)盡快騰空當(dāng)前股道，進(jìn)入存車場中等待。此外，存車作業(yè)為非必要作業(yè)，存車次數(shù)越少，必要作業(yè)之間轉(zhuǎn)線越順暢，調(diào)車作業(yè)量和動車所咽喉區(qū)時間占用也相應(yīng)越少，即減少存車次數(shù)有利于降低調(diào)車成本、提高動車所檢修能力利用率，使動車所能夠容納更多的動車組開展檢修作業(yè)?；谖墨I(xiàn)［2］，考慮以最小化關(guān)鍵線區(qū)總占用時間和最小化總存車次數(shù)共同作為目標(biāo)，但一般情況下減少關(guān)鍵線區(qū)總占用時間反而會增加存車線區(qū)停留時間，導(dǎo)致總存車次數(shù)增加，因此這2個目標(biāo)互斥。

區(qū)別于將不同的目標(biāo)函數(shù)進(jìn)行線性加權(quán)轉(zhuǎn)化為單目標(biāo)的處理方式，字典排序目標(biāo)規(guī)劃（Lexico?graphic Goal Programming）［18?19］模型在求解多目標(biāo)問題時，為各目標(biāo)函數(shù)賦予相應(yīng)優(yōu)先級［20］，在順序求解過程的第一階段，優(yōu)先級最高的目標(biāo)是唯一目標(biāo)，接下來的階段，再將下一級的目標(biāo)作為唯一的目標(biāo)，以此類推。由此，考慮基于目標(biāo)規(guī)劃理論，建立字典排序目標(biāo)規(guī)劃模型，結(jié)合對2 個目標(biāo)的分析，分別確立第一優(yōu)先級和第二優(yōu)先級。

2）動車組檢修任務(wù)不同時的建模對象異質(zhì)性影響

動車所內(nèi)，不同動車組所需的檢修作業(yè)互有差異，部分動車組需要進(jìn)行日常的一級修檢修作業(yè)，部分動車組需要進(jìn)行二級修，還有部分動車組只需在存車線上停留而無須進(jìn)行檢修。如果采用動車組作為構(gòu)建模型的主要索引，往往會引發(fā)所有動車組待檢作業(yè)項(xiàng)目均相同的假設(shè)，難以決策出每列動車組在動車所內(nèi)的股道占用情況。區(qū)別于這種構(gòu)模方式，本文以動車所內(nèi)的所有待開展作業(yè)為構(gòu)建模型的主要索引，通過決策所有作業(yè)的股道占用情況，最終得出每列動車組的調(diào)車作業(yè)計(jì)劃。

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

根據(jù)模型構(gòu)建策略，圍繞動車所內(nèi)的所有待開展作業(yè)設(shè)計(jì)決策變量，在分析不同子問題的基礎(chǔ)上形成模型約束條件，以最小化關(guān)鍵線區(qū)總占用時間為第一優(yōu)先級目標(biāo)，以最小化總存車次數(shù)為第二優(yōu)先級目標(biāo)，構(gòu)建目標(biāo)規(guī)劃模型。

3.1 參數(shù)和變量定義

在某調(diào)車作業(yè)計(jì)劃期內(nèi)，定義如下集合與索引：O為動車所內(nèi)所有作業(yè)的集合，O={1，2，…，n，n+1，…，2n，2n+1，…，2n+m}，n為所有待檢修動車組待開展的所有必要作業(yè)數(shù)量，m為所有待檢動車組的數(shù)量，p與q為集合O的索引；A為動車所內(nèi)所有必要作業(yè)的集合，A={1，2，…，n}，A?O；I為動車組集合，i為集合I的索引；Il為長編動車組集合，Il?I；Hj為作業(yè)類j的作業(yè)股道集合，包括檢修線集合、清洗線集合、吸污線集合和存車線集合等，h為集合Hj的索引；k為股道占用無沖突情形的索引，k∈{1，2，3}。

集合O中，第1～n項(xiàng)表示所有待檢修動車組待開展的所有必要作業(yè)，即圖2中的實(shí)線方框；第(n+1)～2n項(xiàng)表示所有必要作業(yè)對應(yīng)的前序存車作業(yè)，即圖2中的虛線方框（若某必要作業(yè)之前無存車作業(yè)，則按照存車作業(yè)時間為0 計(jì)算；若忽略轉(zhuǎn)線時間，則某存車作業(yè)的結(jié)束時刻是對應(yīng)必要作業(yè)的開始時刻）；第(2n+1)～(2n+m)項(xiàng)表示所有動車組出所前可能會進(jìn)行的存車作業(yè)，即圖2中的點(diǎn)劃線方框（同樣，若進(jìn)行完必要作業(yè)后直接離開，按照最后1 項(xiàng)存車作業(yè)時間為0 計(jì)算）。如此，編制動車所日常調(diào)車作業(yè)計(jì)劃時，可以在尋求目標(biāo)最優(yōu)的同時靈活分配每輛動車組存車作業(yè)的次數(shù)、次序和每次存車作業(yè)的時長，達(dá)到“靈活存車”的目的。

考慮2 列動車組對同一股道的占用關(guān)系，股道占用無沖突的情形共有3 種。以作業(yè)p比作業(yè)q先占用股道為例，這3 種情形如圖3所示。圖中：tarp和tdpp分別為作業(yè)p所屬的動車組進(jìn)入和離開作業(yè)股道的時刻，是模型的決策變量。

圖3 作業(yè)p比作業(yè)q先占用股道且占用無沖突的3種情形

由圖3可知：情形1 中2 項(xiàng)作業(yè)占用時間沒有重疊；情形2 和情形3 分別表示2 列不同的短編動車組同時占用同一股道2 個列位的情形，且2 項(xiàng)作業(yè)的股道占用時間存在重疊；情形2 中作業(yè)p先進(jìn)后出，但這只有在作業(yè)p與作業(yè)q所屬動車組均為短編且占用股道屬于盡端式車場時才會出現(xiàn)；情形3中作業(yè)p先進(jìn)先出，但這只有在作業(yè)p與作業(yè)q所屬的動車組都為短編并且占用股道屬于通過式車場時才會出現(xiàn)。

基于對這3 種情形的分析，進(jìn)一步定義如下模型參數(shù)：tai與tdi分別為動車組i的入所時刻與出所時刻；gp為作業(yè)歸屬動車組參數(shù)，其值等于作業(yè)p所屬的某動車組的索引；rp為作業(yè)歸屬作業(yè)類參數(shù)，其值等于作業(yè)p所屬的某作業(yè)類的索引；tmin為按標(biāo)準(zhǔn)完成作業(yè)p所需要的最少時間，存車作業(yè)所需的最少時間取0；φj為布爾參數(shù)，作業(yè)類j的作業(yè)線區(qū)為通過式布置時取1，為盡端式布置時取0；Δt為在同一咽喉前后相鄰執(zhí)行的2 條進(jìn)路的安全間隔時間或者2 列動車組先后占用同一股道的安全間隔時間；M為1個足夠大的正數(shù)，在本模型中取本次計(jì)劃期的時間長度。

除了和外，再定義如下決策變量：xph為布爾變量，作業(yè)p在股道h上作業(yè)時取1，否則取0；為布爾變量，作業(yè)p比作業(yè)q先占用同一股道且無沖突時其值取1，否則取0；u+p和分別為實(shí)際作業(yè)時長與標(biāo)準(zhǔn)作業(yè)時間之間的正偏差與負(fù)偏差量，均為正整數(shù)；v+p和分別為存車次數(shù)與0（不存車）之間的正偏差與負(fù)偏差量，均為布爾值。

3.2 模型建立

3.2.1 第一優(yōu)先級模型

按照字典排序目標(biāo)規(guī)劃根據(jù)目標(biāo)優(yōu)先級來順序求解的理論，第一優(yōu)先級模型的目標(biāo)是最小化關(guān)鍵線區(qū)總占用時間，即目標(biāo)函數(shù)Z1為最小化實(shí)際作業(yè)時間與標(biāo)準(zhǔn)作業(yè)時間之間的正偏差量。

該模型的約束條件有6 個，分別是進(jìn)出動車所時間約束、作業(yè)時間標(biāo)準(zhǔn)約束、動車組作業(yè)時間約束、占用車場約束、進(jìn)路沖突約束和列位占用約束。為簡便表示約束，若無特殊標(biāo)注，均認(rèn)為動車組與作業(yè)的作用范圍為集合的全部，即在約束條件中省略?i∈I，?p∈O。

1）進(jìn)出動車所時間約束

此時需同時滿足以下3種情況。

最后1項(xiàng)存車作業(yè)的結(jié)束時刻為離所時刻，即

第1項(xiàng)存車作業(yè)的開始時刻為到所時刻，即

所有作業(yè)的作業(yè)時間總和等于動車組在動車所停留時間段，即

2）作業(yè)時間標(biāo)準(zhǔn)約束

此時實(shí)際作業(yè)時長應(yīng)不小于相應(yīng)的最低作業(yè)時間標(biāo)準(zhǔn)，即

存車作業(yè)的作業(yè)時間標(biāo)準(zhǔn)通常設(shè)為0，但若存在某些動車組只進(jìn)行存車過夜、不進(jìn)行檢修清洗的情況，也可以將這些存車作業(yè)的時間標(biāo)準(zhǔn)設(shè)為其他值。

3）動車組的作業(yè)時間約束

假設(shè)將轉(zhuǎn)線時間并入作業(yè)時間內(nèi)［5，7］，即相鄰2 項(xiàng)作業(yè)之間沒有時間間隔，那么此時需同時滿足以下3種情況。

必要作業(yè)的開始時刻等于前序存車作業(yè)的結(jié)束時刻，即

最后1 項(xiàng)必要作業(yè)的結(jié)束時刻是最后1 項(xiàng)存車作業(yè)的開始時刻，即

同一動車組的任意2 項(xiàng)作業(yè)的時間段無重疊，即

4）占用車場約束

此時動車組僅停留在某1 條屬于當(dāng)前作業(yè)線區(qū)的股道上，而不會停留在不屬于當(dāng)前作業(yè)線區(qū)的股道，即

5）進(jìn)路沖突約束

當(dāng)某動車組的第1 項(xiàng)作業(yè)開始或任意1 項(xiàng)作業(yè)結(jié)束時，必然會產(chǎn)生調(diào)車作業(yè)進(jìn)路，不同動車組的作業(yè)之間可能會發(fā)生進(jìn)路沖突，因此還需要保證相鄰2 次調(diào)車作業(yè)之間留有安全時間間隔，避免進(jìn)路沖突的發(fā)生，即

6）列位占用約束

首先，同一時刻占用同一股道的動車組不會超過2列，即

需要注意的是，前述股道占用的3 種情形是基于作業(yè)p比作業(yè)q先占用股道的設(shè)定，事實(shí)上，作業(yè)q有可能比作業(yè)p先占用股道，因此同理可知，另有3 種股道占用方式，共計(jì)6 種情形。也就是說，對于占用同一股道的2 列待檢動車組，假如都將進(jìn)行同一類型的2項(xiàng)作業(yè)p和q，無論是p在前還是q在前，2 列動車組作業(yè)無沖突下的股道實(shí)際占用情形必然在這6種情形之中且必然唯一，即

然后，針對圖3中的3 種情形，進(jìn)一步分析時間先后對列位占用的約束。

當(dāng)實(shí)際占用情形為情形1時有

當(dāng)實(shí)際占用情形為情形2時有

當(dāng)實(shí)際占用情形為情形3時有

最后，結(jié)合動車所的具體布置形式，還有可能出現(xiàn)以下4種例外情況。

假如作業(yè)p和作業(yè)q的作業(yè)線區(qū)為通過式時（φrp=1），則不可能出現(xiàn)情形2，即

假如作業(yè)p和作業(yè)q的作業(yè)線區(qū)為盡端式時（φrp=0），則不可能出現(xiàn)情形3，即

假如作業(yè)p和作業(yè)q歸屬的動車組中存在長編動車組，則不可能出現(xiàn)情形2和情形3，即

假如作業(yè)p和作業(yè)q不屬于同一作業(yè)類或p=q時，則前述3種情形均不可能出現(xiàn)，即

需要注意的是，本模型只求解了短編動車組共同占用通過式車場股道的起訖時刻。通過式車場的股道2 端各連接有1 處咽喉，且這2 處咽喉都可用于轉(zhuǎn)線作業(yè)，因此，實(shí)踐中具體占用哪個列位可視咽喉的忙碌情況和現(xiàn)場的作業(yè)條件來決定，給動車所調(diào)度員提供一定的靈活選擇空間。

3.2.2 第二優(yōu)先級模型

設(shè)Z*1為第一優(yōu)先級模型的最優(yōu)值，為確保第二優(yōu)先級模型的求解不會導(dǎo)致更多的關(guān)鍵線區(qū)總占用時間，需將式（1）作為約束條件加入到第二優(yōu)先級模型中。在同樣需滿足約束式（2） —式（24）的前提下，第二優(yōu)先級模型的目標(biāo)是最小化總存車次數(shù)，即目標(biāo)函數(shù)Z2為最小化總存車次數(shù)正偏差量。

4 算例分析

參考文獻(xiàn)［2］中的算例，依托圖1（a）縱列式二級二場布置的某動車所，設(shè)計(jì)算例并運(yùn)用CPLEX 進(jìn)行求解。該動車所的配置有盡端式檢修線4 條，盡端式輪對鏇修線1 條，通過式清洗線2條，通過式吸污線1條，通過式存車線10條。檢修作業(yè)內(nèi)容規(guī)范見表1。在檢修當(dāng)日17：00—第3日7：00 的某計(jì)劃期期間，在動車所內(nèi)進(jìn)行檢修維護(hù)的動車組共有14列，檢修計(jì)劃見表2。表中股道占用和執(zhí)行進(jìn)路的安全間隔時間Δt按照平均時間計(jì)算，設(shè)為5 min。

為減少調(diào)車次數(shù)，參考文獻(xiàn)［2］，將在相同線區(qū)開展的若干作業(yè)合并進(jìn)行，例如將編號為2 的動車組的“一級修”與“18 萬km 檢修包”這2 項(xiàng)同在檢修線區(qū)進(jìn)行的作業(yè)合并進(jìn)行，作業(yè)總時長為6 h。這樣處理之后，必要作業(yè)共有34 項(xiàng)，最大可能總存車次數(shù)為48次。

在配置i7-8 550U CPU 和16 GB RAM 的計(jì)算機(jī)上，運(yùn)用Visual Studio 2019 平臺編程，調(diào)用數(shù)學(xué)求解工具CPLEX 實(shí)現(xiàn)對目標(biāo)規(guī)劃二級模型的求解［21］，并通過CPLEX內(nèi)置的最大求解時間參數(shù)和優(yōu)化間隙（Optimality Gap）參數(shù)設(shè)定求解程序的效率和質(zhì)量。

將動車所設(shè)備數(shù)據(jù)以及表1和表2數(shù)據(jù)代入程序中，計(jì)算動車組各項(xiàng)作業(yè)所占用的股道以及占用起訖時刻，第一優(yōu)先級模型求解耗時104 s，此時生成的作業(yè)計(jì)劃關(guān)鍵線區(qū)占用總時長為5 880 min，各動車組總存車次數(shù)為40 次。分析可知，動車組對關(guān)鍵線區(qū)占用總時長已達(dá)到理論最小值，但是總存車次數(shù)接近理論最大值，調(diào)車成本較高，仍有較大的優(yōu)化空間。

表1 某動車所檢修作業(yè)內(nèi)容規(guī)范

表2 某動車所檢修計(jì)劃

將第二優(yōu)先級模型的最大求解時間設(shè)置為150 s，在不降低第一優(yōu)先級模型關(guān)鍵線區(qū)總占用時間的前提下，計(jì)算生成的較優(yōu)解即作業(yè)計(jì)劃總存車次數(shù)為25 次，相比第一優(yōu)先級模型的求解結(jié)果減少存車次數(shù)15 次，減少總存車次數(shù)達(dá)37.5%，此時的完整股道占用情況見表3。為便于計(jì)算，以計(jì)劃期當(dāng)日17：00 為時刻0，將時間轉(zhuǎn)化為整數(shù)形式，例如計(jì)劃期當(dāng)日17：00—第3日7：00 可轉(zhuǎn)化為0—2 280 min。表3中：小括號內(nèi)數(shù)字為動車組編號；方括號內(nèi)為該動車組對股道占用的開始時刻至占用結(jié)束時刻。

從表3中可以看出：股道利用方面，大部分股道的占用情形為圖3中情形1，2 列短編動車組同時占用同一股道的情況共出現(xiàn)5次（盡端式車場檢修線M2 出現(xiàn)圖3中情形2，通過式車場吸污線P1和存車線S2，S3，S6 分別出現(xiàn)情形3 共4 次），表明本文模型有效利用了股道的雙列位條件，提高了股道利用率；靈活存車方面，大部分動車組完成檢修作業(yè)僅需存車1～2次，僅有2列動車組（動車組1和動車組6）需要存車3次，表明本文模型能夠有效地降低動車組總存車次數(shù)以及相應(yīng)的調(diào)車作業(yè)，使檢修完畢的動車組盡快騰出當(dāng)前作業(yè)股道，在檢修資源日益緊張局面下，這有利于提高檢修資源利用率，降低計(jì)劃編制難度。

表3 優(yōu)化后的動車所股道占用情況

在實(shí)際工作中，決策者往往要求在短時間內(nèi)得到可行且較優(yōu)的計(jì)劃，因此需要謀求求解時間與求解質(zhì)量之間的平衡。例如，將第二優(yōu)先級模型的求解時長增加到600 s 后，求得的總存車次數(shù)為24次，僅較之前減少1 次，優(yōu)化效果不夠明顯。因此，求解時間的設(shè)定需要結(jié)合實(shí)際情況來設(shè)定，也可以同時設(shè)置求解時長參數(shù)和優(yōu)化間隙值參數(shù)來約束求解效率與求解質(zhì)量。

5 結(jié) 語

以適用于帶有不同車場布置類型的動車所為前提，重點(diǎn)考慮靈活存車、列位占用問題，在統(tǒng)籌各項(xiàng)檢修作業(yè)先后順序安排、進(jìn)路沖突、車場布置類型等現(xiàn)實(shí)情況的基礎(chǔ)上，建立了可用于動車所調(diào)車作業(yè)計(jì)劃優(yōu)化的字典排序目標(biāo)規(guī)劃二級模型，第一優(yōu)先級模型以最小化關(guān)鍵線區(qū)總占用時間為目標(biāo)，第二優(yōu)先級模型以最小化總存車次數(shù)為目標(biāo)。二級模型中，以動車所內(nèi)的所有待開展作業(yè)為模型主要索引，通過決策所有作業(yè)的股道占用情況，得出所有待檢修動車組的調(diào)車作業(yè)計(jì)劃。

依托采用縱列式二級二場布置的某動車所設(shè)計(jì)算例，運(yùn)用數(shù)學(xué)求解工具CPLEX 完成算例求解，證明第一優(yōu)先級模型生成的動車所調(diào)車作業(yè)計(jì)劃雖然實(shí)現(xiàn)了關(guān)鍵線區(qū)總占用時間最優(yōu)，但存在總存車次數(shù)過多的問題；第二優(yōu)先級模型在不降低關(guān)鍵線區(qū)總占用時間的前提下，減少存車次數(shù)達(dá)37.5%，降低了調(diào)車成本。通過目標(biāo)規(guī)劃二級模型，能夠統(tǒng)籌調(diào)度動車所內(nèi)的所有作業(yè)任務(wù)，有效壓縮關(guān)鍵線區(qū)總占用時間和不必要的存車作業(yè)次數(shù)，為動車所調(diào)車計(jì)劃的自動化編制提供理論參考。

需要注意的是，本文只考慮了咽喉同時單進(jìn)路的情況，后續(xù)將會針對平行作業(yè)的同時多進(jìn)路情況進(jìn)行下一步研究，將調(diào)車進(jìn)路細(xì)化到對道岔、列位等設(shè)備的占用。此外，如何將動車所內(nèi)部調(diào)車計(jì)劃與動車組運(yùn)用計(jì)劃、車站計(jì)劃聯(lián)合編制也是下一階段的研究方向。

本文提出的模型索引方式不僅可用于運(yùn)輸調(diào)度，還可用于工業(yè)界加工處理一批帶有不同作業(yè)內(nèi)容的工件的場景，從而更為高效地處理柔性作業(yè)車間調(diào)度或柔性流水車間調(diào)度問題。