環(huán)形排列的動(dòng)車(chē)組運(yùn)用和檢修一體化優(yōu)化模型

該列車(chē)使用計(jì)劃包括具體的旅行時(shí)間、出發(fā)時(shí)間、車(chē)站、運(yùn)營(yíng)路線和各級(jí)維護(hù)，是客運(yùn)線路的基本運(yùn)營(yíng)計(jì)劃之一。由于動(dòng)車(chē)組在客運(yùn)專線的固定成本投資中占有較大比重,折舊費(fèi)用和維修費(fèi)用都較高,因此如何合理使用動(dòng)車(chē)組,減少動(dòng)車(chē)組的使用數(shù)量是動(dòng)車(chē)組運(yùn)用計(jì)劃的首要目標(biāo)。借鑒國(guó)內(nèi)外動(dòng)車(chē)組使用經(jīng)驗(yàn)以及近年來(lái)對(duì)于動(dòng)車(chē)組應(yīng)用的研究發(fā)現(xiàn),動(dòng)車(chē)組不固定區(qū)段運(yùn)用是效率較高的運(yùn)用模式。文獻(xiàn)首次提出動(dòng)車(chē)組不固定區(qū)段使用模式,并利用緊湊指派的思想通過(guò)模擬方法得到動(dòng)車(chē)組運(yùn)用方案;文獻(xiàn)在不固定區(qū)段使用的基礎(chǔ)上提出采用回送車(chē)的方法,通過(guò)靈活調(diào)配合適的動(dòng)車(chē)組來(lái)完成各次運(yùn)輸任務(wù)使得各個(gè)車(chē)次之間的接續(xù)時(shí)間盡可能短,從而達(dá)到提高使用效率的目的;文獻(xiàn)在平日動(dòng)車(chē)組運(yùn)用計(jì)劃已知的條件下,通過(guò)衡量各列車(chē)之間接續(xù)質(zhì)量,以一定概率優(yōu)先滿足高質(zhì)量的列車(chē)接續(xù)為原則,不斷生成好的交路段,構(gòu)成假日動(dòng)車(chē)組運(yùn)用計(jì)劃;文獻(xiàn)首先利用文獻(xiàn)中算法構(gòu)造出初始單基地動(dòng)車(chē)組運(yùn)用計(jì)劃,進(jìn)而通過(guò)列車(chē)分組將其分解成多基地動(dòng)車(chē)組運(yùn)用計(jì)劃,并通過(guò)路段交換方法不斷構(gòu)造新的動(dòng)車(chē)組運(yùn)用計(jì)劃;文獻(xiàn)將動(dòng)車(chē)組運(yùn)用計(jì)劃編制問(wèn)題分為交路段生成和基于交路段的交路生成兩個(gè)問(wèn)題分步求解;文獻(xiàn)將動(dòng)車(chē)組的接續(xù)運(yùn)行與檢修計(jì)劃制定過(guò)程轉(zhuǎn)化為T(mén)SP問(wèn)題,并運(yùn)用計(jì)算機(jī)模擬方法確定給定列車(chē)運(yùn)行圖條件下合理配置動(dòng)車(chē)組套數(shù)、存車(chē)線數(shù)量及動(dòng)車(chē)段設(shè)備規(guī)模等。本文在不固定動(dòng)車(chē)組運(yùn)用區(qū)段的前提下,以全部列車(chē)形成的環(huán)形排列為動(dòng)車(chē)組交路,在環(huán)形排列中以檢修時(shí)間間隔和里程間隔為約束,列車(chē)接續(xù)費(fèi)用最少為優(yōu)化目標(biāo),建立動(dòng)車(chē)組運(yùn)用計(jì)劃和檢修計(jì)劃的一體化優(yōu)化模型。通過(guò)引入罰值函數(shù)和三交換鄰域結(jié)構(gòu),設(shè)計(jì)求解模型的模擬退火算法,最后進(jìn)行實(shí)例分析。1u2009必要的檢修時(shí)間間隔動(dòng)車(chē)組運(yùn)用計(jì)劃問(wèn)題可簡(jiǎn)單地?cái)⑹鋈缦?給定一些列車(chē),運(yùn)用若干動(dòng)車(chē)組承擔(dān)這些列車(chē)的運(yùn)輸任務(wù),需要安排動(dòng)車(chē)組的運(yùn)用交路,滿足以下要求:使得動(dòng)車(chē)組數(shù)量盡可能少,接續(xù)費(fèi)用盡可能少;按要求在動(dòng)車(chē)組的交路中安排日常檢修和一級(jí)檢修;使得動(dòng)車(chē)組之間所承擔(dān)的運(yùn)行里程均勻。對(duì)于給定的n列列車(chē)l1,l2,…,ln,列車(chē)li(i=1,2,?,n)的始發(fā)和終到站分別為sdi和sai,出發(fā)和到達(dá)時(shí)刻分別為tdi和tai,運(yùn)行里程為dYi,運(yùn)行時(shí)間為ΤYi=(tai-tdi)modΤ(1)式中,T為一天內(nèi)的總時(shí)間。當(dāng)動(dòng)車(chē)組完成列車(chē)li的運(yùn)輸任務(wù)后緊接著承擔(dān)列車(chē)lj的運(yùn)輸任務(wù)時(shí),一項(xiàng)主要費(fèi)用為接續(xù)時(shí)間。運(yùn)輸任務(wù)的接續(xù)時(shí)間可以分為本站接續(xù)和異站接續(xù)兩種情形來(lái)計(jì)算,即當(dāng)列車(chē)li的終到站sai與列車(chē)lj的始發(fā)站sdj相同時(shí),需要花費(fèi)的最小接續(xù)時(shí)間間隔為標(biāo)準(zhǔn)接續(xù)時(shí)間Tbj;當(dāng)sai與sdj不相同時(shí),需要花費(fèi)的最小接續(xù)時(shí)間間隔為標(biāo)準(zhǔn)接續(xù)時(shí)間Tbj與站sai至站sdj的運(yùn)行時(shí)間TYij之和,其中ΤYij={dij/vdij≤DXΜdij>DX(2)式中,dij為站sai至sdj的里程;v為動(dòng)車(chē)組的運(yùn)行速度;DX為異站接續(xù)的最大里程限制值;M為充分大的罰值,表明太遠(yuǎn)的兩個(gè)站之間不允許進(jìn)行接續(xù)的限制。所以,接續(xù)時(shí)間ΤJij={tdj-taitdj-tai≥Τbj,sai=sdjortdj-tai≥Τbj+ΤYij,sai≠sdjtdj-tai+Τtdj-tai＜Τbj,sai=sdjortdj-tai＜Τbj+ΤYij,sai≠sdj(3)其實(shí),動(dòng)車(chē)組的數(shù)量最少與總接續(xù)時(shí)間最少是等價(jià)的,這是因?yàn)榭偨永m(xù)時(shí)間與列車(chē)總運(yùn)行時(shí)間之和等于動(dòng)車(chē)組數(shù)量的T倍,而列車(chē)運(yùn)行時(shí)間始終是常數(shù)。另一項(xiàng)接續(xù)費(fèi)用為接續(xù)里程dij,簡(jiǎn)便起見(jiàn),可以將接續(xù)費(fèi)用綜合表示為Cij=ΤJij+ω?dij(4)式中,ω為動(dòng)車(chē)組運(yùn)行單位里程的費(fèi)用折合成單位時(shí)間費(fèi)用的折算系數(shù)。動(dòng)車(chē)組運(yùn)行一段時(shí)間以后需要進(jìn)行必要的檢修,檢修項(xiàng)目分為日常檢修、一級(jí)檢修、二級(jí)檢修、三級(jí)檢修、大修等。日常檢修、一級(jí)檢修需要在動(dòng)車(chē)組運(yùn)行交路中完成,其他維修由專門(mén)的維修計(jì)劃實(shí)施,在研究動(dòng)車(chē)組交路時(shí)僅限于討論日常檢修和一級(jí)檢修的安排問(wèn)題。日常檢修的作業(yè)內(nèi)容較為簡(jiǎn)單,作業(yè)時(shí)間也較短,可以安排在白天或晚上進(jìn)行;檢修車(chē)站必須具有日常檢修設(shè)備;兩次日常檢修之間的列車(chē)?yán)塾?jì)行駛里程應(yīng)在日常檢修期望里程的規(guī)定波動(dòng)范圍內(nèi),雖然沒(méi)達(dá)到規(guī)定行駛里程要求,但兩次日常檢修之間間隔時(shí)間已達(dá)到日常檢修的最長(zhǎng)期望檢修時(shí)間間隔的規(guī)定波動(dòng)范圍,也應(yīng)該進(jìn)行檢修。通常,日常檢修在動(dòng)車(chē)組運(yùn)行3000km或2天以內(nèi)必須進(jìn)行一次。一級(jí)檢修的作業(yè)內(nèi)容相對(duì)復(fù)雜,作業(yè)時(shí)間也較長(zhǎng),常常限制在白天進(jìn)行;檢修車(chē)站必須具有一級(jí)檢修設(shè)備;兩次一級(jí)檢修之間的列車(chē)?yán)塾?jì)行駛里程應(yīng)在一級(jí)檢修期望里程的規(guī)定波動(dòng)范圍內(nèi),雖然沒(méi)達(dá)到規(guī)定行駛里程要求,但兩次一級(jí)檢修之間間隔時(shí)間已達(dá)到一級(jí)檢修的最長(zhǎng)期望檢修時(shí)間間隔的規(guī)定波動(dòng)范圍,也應(yīng)該進(jìn)行檢修。通常,一級(jí)檢修在動(dòng)車(chē)組運(yùn)行30000km或30天以內(nèi)必須進(jìn)行一次。記日常檢修的期望里程為D0,波動(dòng)范圍為±ΔD0;期望時(shí)間為τ0,波動(dòng)范圍為±Δτ0。同樣記一級(jí)檢修的期望里程為D1,波動(dòng)范圍為±ΔD1;期望時(shí)間為τ1,波動(dòng)范圍為±Δτ1。根據(jù)日常檢修和一級(jí)檢修在時(shí)間和地點(diǎn)上的要求,在列車(chē)li與lj之間的接續(xù)時(shí)間內(nèi)是否可以完成這些檢修任務(wù)是完全確定的,引入?yún)⒆兞喀読j和ψij來(lái)描述列車(chē)li與列車(chē)lj之間是否能夠完成日常檢修和一級(jí)檢修,其中φij={1li與lj之間可以完成日常檢修0否則(5)ψij={1li與lj之間可以完成一級(jí)檢修0否則(6)2交路維修交路由于所有動(dòng)車(chē)組構(gòu)成一個(gè)大交路能夠很好的滿足動(dòng)車(chē)組運(yùn)用的均衡性,所以動(dòng)車(chē)組的運(yùn)用交路就是列車(chē)l1,l2,…,ln的環(huán)形排列l(wèi)u(1),lu(2),…,lu(n),日常檢修方案和一級(jí)檢修方案可以分別引入變量xu(i)u(i+1)(i=1,2,…,n)和yu(i)u(i+1)(i=1,2,…,n)來(lái)表示,具體含義為xu(i)u(i+1)={1lu(i)與lu(i+1)之間安排日常檢修0否則(7)yu(i)u(i+1)={1lu(i)與lu(i+1)之間安排一級(jí)檢修0否則(8)變量xu(i)u(i+1)應(yīng)滿足相關(guān)約束:其一,日常維修必須在具備條件的兩次列車(chē)接續(xù)時(shí)間內(nèi)維修,即xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,?,n(9)其二,在整個(gè)交路中至少進(jìn)行一次日常維修,即n∑i=1xu(i)u(i+1)≥1(10)其三,在每次日常維修后的規(guī)定行程范圍或規(guī)定時(shí)間范圍內(nèi)進(jìn)行下一次日常維修。記p′(d,j)、q′(d,j)分別為環(huán)形排列l(wèi)u(1),lu(2),…,lu(n)中與運(yùn)行線j剛好滿足日常檢修里程下限和上限的運(yùn)行線序號(hào),p′(τ,j)、q′(τ,j)分別為環(huán)形排列l(wèi)u(1),lu(2),…,lu(n)中與運(yùn)行線j剛好滿足日常檢修時(shí)間下限和上限的運(yùn)行線序號(hào),則對(duì)于j=1,2,…,n,當(dāng)xu(j-1)u(j)=1時(shí),min{q′(d,j),q′(τ,j)}∑i=min{p′(d,j),p′(τ,j)}xu(i)u(i+1)=1成立的條件是p′(d,j)、q′(d,j)、p′(τ,j)、q′(τ,j)滿足以下4個(gè)約束:p′(d,j)-1∑i=jdYu(i)＜D0-ΔD0≤p′(d,j)∑i=jdYu(i)(11)q′(d,j)∑i=jdYu(i)≤D0+ΔD0＜q′(d,j)+1∑i=jdYu(i)(12)p′(τ,j)-1∑i=j(ΤYu(i)+ΤJu(i)u(i+1))＜τ0-Δτ0≤p′(τ,j)∑i=j(ΤYu(i)+ΤJu(i)u(i+1))(13)q′(τ,j)∑i=j(ΤYu(i)+ΤJu(i)u(i+1))≤τ0+Δτ0＜q′(τ,j)+1∑i=j(ΤYu(i)+ΤJu(i)u(i+1))(14)上述兩組約束保證交路內(nèi)至少進(jìn)行一次日常維修,同時(shí)任何一次日常維修以后的規(guī)定時(shí)間內(nèi)一定進(jìn)行下一次日常維修,這樣的約束下一定可以獲得合乎要求的日常維修方案。另外,在考慮接續(xù)時(shí)間盡可能少的情況下,不會(huì)形成兩個(gè)及其以上的維修交路(最少接續(xù)時(shí)間下自然形成的多個(gè)維修交路除外)。變量yu(i)u(i+1)也應(yīng)滿足類(lèi)似約束。綜上所述,動(dòng)車(chē)組運(yùn)用計(jì)劃的數(shù)學(xué)模型如下:minn∑i=1Cu(i)u(i+1)(15)s.t.xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,…,n(16)n∑i=1xu(i)u(i+1)≥1(17)min{q′(d,j),q′(τ,j)}∑i=min{p′(d,j),p′(τ,j)}xu(i)u(i+1)=1?若{xu(j-1)u(j)=1∑i=jp′(d,j)-1du(i)Y＜D0-Δ0D≤∑i=jp′(d,j)du(i)Y∑i=jq′(d,j)du(i)Y≤D0+Δ0D＜∑i=jq′(d,j)+1du(i)Y∑i=jp′(τ,j)-1(Τu(i)Y+Τu(i)u(i+1)J)＜τ0-Δ0τ≤∑i=jp′(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)∑i=jq′(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)≤τ0+Δ0τ＜∑i=jq′(τ,j)+1(Τu(i)Y+Τu(i)u(i+1)J)j=1,2,?,n(18)yu(i)u(i+1)≤ψu(yù)(i)u(i+1)i=1,2,?,n(19)∑i=1nyu(i)u(i+1)≥1(20)∑i=min{p?(d,j),p?(τ,j)}min{q?(d,j),q?(τ,j)}yu(i)u(i+1)=1?若{yu(j-1)u(j)=1∑i=jp?(d,j)-1du(i)Y＜D1-Δ1D≤∑i=jp?(d,j)du(i)Y∑i=jq?(d,j)du(i)Y≤D1+Δ1D＜∑i=jq?(d,j)+1du(i)Y∑i=jp?(τ,j)-1(Τu(i)Y+Τu(i)u(i+1)J)＜τ1-Δ1τ≤∑i=jp?(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)∑i=jq?(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)≤τ1+Δ1τ＜∑i=jq?(τ,j)+1(Τu(i)Y+Τu(i)u(i+1)J)j=1,2,?,n(21)xu(i)u(i+1),yu(i)u(i+1)=0,1i=1,2,?,n(22){u(1),u(2),?,u(n)}={1,2,?,n}的環(huán)形排列(23)式中,p?(d,j)、q?(d,j)分別為環(huán)形排列l(wèi)u(1),lu(2),…,lu(n)中與運(yùn)行線j剛好滿足一級(jí)檢修里程下限和上限的運(yùn)行線序號(hào);p?(τ,j)、q?(τ,j)分別為環(huán)形排列l(wèi)u(1),lu(2),…,lu(n)中與運(yùn)行線j剛好滿足一級(jí)檢修時(shí)間下限和上限的運(yùn)行線序號(hào)。在模型(式(15)～式(23))中,u(i)表明lu(i)為排列在位置i的列車(chē);列車(chē)lu(i)的前一列列車(chē)為lu(i-1),后一列列車(chē)為lu(i+1)。若i-1<0,則i-1表示i-1+n;若i+1>n,則i+1表示i+1-n,這一項(xiàng)環(huán)形排列的運(yùn)算特征在全文都是如此,其他地方不再做特殊說(shuō)明。3模型式15的建立為便于求解模型(式(15)～式(23)),設(shè)法消去約束條件(式(17),式(18),式(20),式(21)),將其以罰值的形式轉(zhuǎn)入目標(biāo)函數(shù)中,構(gòu)建一個(gè)與之等價(jià)的優(yōu)化模型。特此,對(duì)于式(17)和式(20),引入函數(shù)X={0∑i=1nxu(i)u(i+1)≥11∑i=1nxu(i)u(i+1)=0(24)Y={0∑i=1nyu(i)u(i+1)≥11∑i=1nxu(i)u(i+1)=0(25)所以,式(17)和式(20)可以通過(guò)罰值M1和M2轉(zhuǎn)化成目標(biāo)函數(shù)中新的一項(xiàng)Μ1X+Μ2Y式(18)可以通過(guò)罰值M3轉(zhuǎn)化成目標(biāo)函數(shù)中新的一項(xiàng)Μ3∑j=1n(xu(j-1)u(j)(∑i=min{p′(d,j),p′(τ,j)}min{q′(d,j),q′(τ,j)}xu(i)u(i+1)-1)2)(26)式(21)可以通過(guò)罰值M4轉(zhuǎn)化成目標(biāo)函數(shù)中新的一項(xiàng)Μ4∑j=1n(yu(j-1)u(j)(∑i=min{p?(d,j),p?(τ,j)}min{q?(d,j),q?(τ,j)}yu(i)u(i+1)-1)2)(27)綜上所述,模型式(15)～式(23)可以轉(zhuǎn)化為如下等價(jià)的罰函數(shù)模型min∑i=1nCu(i)u(i+1)+Μ1X+Μ2Y+Μ3∑j=1n(xu(j-1)u(j)(∑i=min{p′(d,j),p′(τ,j)}min{q′(d,j),q′(τ,j)}xu(i)u(i+1)-1)2)+Μ4∑j=1n(yu(j-1)u(j)(∑i=min{p?(d,j),p?(τ,j)}min{q?(d,j),q?(τ,j)}yu(i)u(i+1)-1)2)(28)s.t.xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,…,n(29)yu(i)u(i+1)≤ψu(yù)(i)u(i+1)i=1,2,?,n(30)xu(i)u(i+1),yu(i)u(i+1)=0,1i=1,2,?,n(31){u(1),u(2),?,u(n)}={1,2,?,n}的環(huán)形排列(32)這些約束條件就是模型式(15)～式(23)中的約束條件(式(16),式(19),式(22),式(23))。動(dòng)車(chē)組運(yùn)用計(jì)劃的罰函數(shù)模型(式(28)～式(32))目標(biāo)函數(shù)中p′(d,j)、q′(d,j)、p′(τ,j)、q′(τ,j)、p?(d,j)、q?(d,j)、p?(τ,j)、q?(τ,j)為j的函數(shù),與當(dāng)前環(huán)形排列相關(guān),相應(yīng)地消去約束條件式(18)和式(21)。4環(huán)式列車(chē)在列車(chē)之間的接頭關(guān)系基于三交換模擬退火算法求解動(dòng)車(chē)組運(yùn)用計(jì)劃模型(式(28)～式(32))的框架如圖1所示,其中,初始環(huán)形排列狀交路可通過(guò)隨機(jī)選擇交路起點(diǎn),并將各列車(chē)在不考慮檢修條件的前提下連成交路得到,模擬退火計(jì)劃表參考文獻(xiàn)確定,而三交換鄰域系的構(gòu)造是算法實(shí)現(xiàn)的關(guān)鍵。由于篇幅有限,下面將具體敘述三交換鄰域的構(gòu)造方法。邊交換法、點(diǎn)交換法、單點(diǎn)移動(dòng)法等都是一些有效的鄰域系構(gòu)造方法,但注意到模型所求解的是有向環(huán)形排列,其中點(diǎn)對(duì)應(yīng)于列車(chē),點(diǎn)之間的有向弧對(duì)應(yīng)于列車(chē)之間的接續(xù),而二交換法(置換兩條邊)對(duì)應(yīng)顛倒2列列車(chē)的接續(xù)關(guān)系,勢(shì)必難于繼承原有優(yōu)化結(jié)果,所以,這里采用三交換法(置換三條邊),除交換邊對(duì)應(yīng)的列車(chē)接續(xù)關(guān)系發(fā)生變化外,其他