資源約束下城市軌道交通基礎(chǔ)設(shè)施維修任務(wù)安排優(yōu)化模型

劉葛輝，陳紹寬，劉爽，金華，王丹陽

(北京交通大學(xué)，綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京100044)

0 引言

城市軌道交通基礎(chǔ)設(shè)施包括線路、供電、信號等若干系統(tǒng)，是列車安全和高效運(yùn)行的關(guān)鍵。合理的長期維修任務(wù)安排對基礎(chǔ)設(shè)施的質(zhì)量均衡、降低維修成本和保障正常運(yùn)行具有重要作用，并對短期任務(wù)安排和維修資源分配具有指導(dǎo)意義。

面向長期維修任務(wù)安排的方法通常需要考慮維修任務(wù)的作業(yè)需求和相關(guān)限制。根據(jù)維修任務(wù)特點(diǎn)，主要對周期性任務(wù)[1]、非周期性任務(wù)[2]、混合類型任務(wù)[3]進(jìn)行優(yōu)化編制，且關(guān)注維修任務(wù)的組織集中化和維修資源的分配均衡化。但以鐵路系統(tǒng)基礎(chǔ)設(shè)施為研究對象的優(yōu)化方法較少考慮任務(wù)的作業(yè)沖突，難以直接應(yīng)用于城市軌道交通基礎(chǔ)設(shè)施系統(tǒng)。

城市軌道交通系統(tǒng)要求在固定且有限的維修天窗內(nèi)安排基礎(chǔ)設(shè)施的維修任務(wù)，并避免對運(yùn)營的不良影響[4]。天窗時間限制易導(dǎo)致維修任務(wù)安排沖突，需要調(diào)整任務(wù)作業(yè)時間[5]或分解維修任務(wù)[6]以減少任務(wù)的作業(yè)沖突，故增大了維修任務(wù)安排的復(fù)雜性。針對上述問題，本文考慮城市軌道交通基礎(chǔ)設(shè)施各類維修任務(wù)的作業(yè)要求，引入維修工隊(duì)、天窗時間等維修資源約束，研究城市軌道交通基礎(chǔ)設(shè)施長期維修任務(wù)安排的優(yōu)化方法。

1 問題描述

城市軌道交通基礎(chǔ)設(shè)施包含N個系統(tǒng)，各系統(tǒng)均設(shè)置若干個維修工區(qū)。工區(qū)由一定數(shù)量的相鄰區(qū)間組成，區(qū)間是執(zhí)行維修任務(wù)的最小單元。如圖1所示，全線共分為S個區(qū)間，系統(tǒng)1在全線設(shè)有多個工區(qū)，而系統(tǒng)2只設(shè)一個工區(qū)。長期維修任務(wù)安排的時間被劃分為等間隔的維修時段，考慮到一般維修任務(wù)的周期均以周或月為單位，因此年度維修任務(wù)安排以周為單位劃分得到維修時段，設(shè)P為時段集合，|P| 為時段數(shù)量。

圖1 維修單元和工區(qū)示意圖Fig.1 Diagram of maintenance units and areas

根據(jù)維修任務(wù)的作業(yè)量、作業(yè)周期等差異，將任務(wù)分為日常維修和專項(xiàng)維修[3]。其中，日常維修任務(wù)可在一個時段內(nèi)完成，且存在作業(yè)周期限制，所以同一區(qū)段上的日常維修任務(wù)在安排時段內(nèi)需要重復(fù)執(zhí)行。日常維修任務(wù)間存在包含關(guān)系，定義包含任務(wù)a的集合為Ga(a∈Ga)，其中的任務(wù)不能同時執(zhí)行。專項(xiàng)維修任務(wù)的作業(yè)量較大，需在多個連續(xù)區(qū)間和時段內(nèi)作業(yè)。專項(xiàng)維修任務(wù)包括執(zhí)行周期超過任務(wù)安排時段的任務(wù)和大型維修任務(wù)，不會重復(fù)執(zhí)行。

為優(yōu)化安排時段內(nèi)的總維修費(fèi)用，需在滿足維修任務(wù)需求的前提下，合理安排兩類維修任務(wù)。為便于構(gòu)建模型，提出如下假設(shè)：

(1)已知全部日常和專項(xiàng)維修任務(wù)的信息，不考慮安排時段中新增任務(wù)的情況。

(2)專項(xiàng)維修任務(wù)在連續(xù)多個時段中執(zhí)行時，各時段內(nèi)的作業(yè)量相同。

(3)專項(xiàng)維修任務(wù)需要專用的工隊(duì)和維修設(shè)備，不與日常維修任務(wù)共享維修資源。

2 模型構(gòu)建

通過合理安排線路中各類基礎(chǔ)設(shè)施的日常和專項(xiàng)維修任務(wù)，最小化年度維修任務(wù)的總費(fèi)用。兩類任務(wù)的作業(yè)要求和資源需求有較大的差異，因此需分別計(jì)算維修費(fèi)用。構(gòu)建目標(biāo)函數(shù)為

式中：C為總費(fèi)用，包括日常維修任務(wù)費(fèi)用C1，專項(xiàng)維修任務(wù)費(fèi)用C2和天窗時間占用懲罰費(fèi)用C3。各項(xiàng)費(fèi)用將按照任務(wù)類型分別計(jì)算，同時定義各約束條件。

2.1 日常維修任務(wù)費(fèi)用

線路中各區(qū)間的日常維修任務(wù)類型和作業(yè)要求存在差異，因?yàn)椴煌瑓^(qū)間的基礎(chǔ)設(shè)施存在類型和數(shù)量上的區(qū)別。設(shè)區(qū)間s的任務(wù)集為Ac,s，bas和nas為任務(wù)a的執(zhí)行周期上限和距離上一次執(zhí)行的間隔；cas和cs,as為執(zhí)行費(fèi)用和組合維修的折減費(fèi)用(cs,as

決策變量為維修任務(wù)的執(zhí)行時間和執(zhí)行方式，x1,asp僅在任務(wù)a在區(qū)間s和時段p內(nèi)執(zhí)行時取1；xs,asp僅在任務(wù)組合執(zhí)行時取1。此外，設(shè)qasp表示任務(wù)的最后一次執(zhí)行時段為時段p。

日常維修任務(wù)費(fèi)用為

式(2)第1 部分表示任務(wù)的執(zhí)行費(fèi)用，第2 部分表示末期懲罰費(fèi)用，任務(wù)最后一次執(zhí)行的時段越晚，懲罰費(fèi)用越低。

基本約束為

式(3)和式(4)判斷任務(wù)的執(zhí)行方式，相鄰區(qū)間上同時安排的任務(wù)被視為組合執(zhí)行，其中，u表示與s相鄰的區(qū)間；式(5)避免任務(wù)重復(fù)執(zhí)行，其中，h表示包含a的任務(wù)；式(6)和式(7)計(jì)算最后一次執(zhí)行任務(wù)的時段；式(8)計(jì)算作業(yè)時間占用天窗時間的比例；式(9)為決策變量約束。

任務(wù)執(zhí)行時段約束為

式(10)和式(11)要求任務(wù)的連續(xù)執(zhí)行間隔滿足執(zhí)行周期上限，其中，l表示開始時段；式(12)保證特殊任務(wù)在規(guī)定時段執(zhí)行。

工隊(duì)作業(yè)時間約束為

式(13)計(jì)算單一工隊(duì)的可作業(yè)時間；式(14)保證各工區(qū)中任務(wù)總作業(yè)時間不超過工隊(duì)的可作業(yè)時間。

2.2 專項(xiàng)維修任務(wù)費(fèi)用

對于專項(xiàng)維修任務(wù)集Ap，設(shè)Ts,a和Te,a為任務(wù)a(a∈Ap)的建議開始和結(jié)束時段；Sa為作業(yè)區(qū)間集合；fa為天窗時間占用比例；ca為單一時段中的執(zhí)行費(fèi)用。

專項(xiàng)維修任務(wù)的執(zhí)行取決于開始時間和持續(xù)時段。yap僅在任務(wù)a在時段p內(nèi)開始執(zhí)行時取1；da為作業(yè)時段數(shù)量。通過上述變量可得輔助決策變量，x2,asp為任務(wù)a在時段p內(nèi)在區(qū)間s上執(zhí)行；x2,ap為任務(wù)a在時段p內(nèi)執(zhí)行；dab為任務(wù)a和b最小的作業(yè)時段數(shù)量。

專項(xiàng)維修任務(wù)費(fèi)用為

式中：Ap,S和Ap,NS分別為需要同時和不同時執(zhí)行的任務(wù)對集合；zD,ap為任務(wù)a在非建議時段中的p時段執(zhí)行；zR,p為時段p內(nèi)超出限制數(shù)量PR,p的任務(wù)數(shù)量；zM,sp為區(qū)間s在始點(diǎn)p內(nèi)超出限制數(shù)量PM,sp的任務(wù)數(shù)量；zS,abp和zNS,abp均為任務(wù)對(a,b) 在時段p內(nèi)同時執(zhí)行；cD,a、cR,p、cM,sp、cS,ab、cNS,ab分別為各項(xiàng)約束的單位懲罰費(fèi)用。

式(15)第1 部分表示任務(wù)的執(zhí)行費(fèi)用，第2～第6部分分別為執(zhí)行時段約束、作業(yè)能力約束、任務(wù)互斥約束、任務(wù)同時和不同時執(zhí)行約束的懲罰費(fèi)用。設(shè)置懲罰費(fèi)用的目的是避免專項(xiàng)維修任務(wù)的規(guī)模和工作量存在的不確定導(dǎo)致約束沖突。

各約束對應(yīng)的變量分別為

其余約束為

式(21)～式(23)表示任務(wù)執(zhí)行的輔助變量；式(24)計(jì)算任務(wù)的天窗時間占用比例，每增加一個作業(yè)時段會增加ga倍的作業(yè)量；式(25)～式(28)為決策變量約束。

2.3 天窗時間占用懲罰費(fèi)用

日常和專項(xiàng)維修任務(wù)均會占用有限的天窗時間，記Fsp(Fsp≤1) 為區(qū)間s在時段p中維修任務(wù)占用的天窗時間比例上限，zO,sp和cO,sp分別為超出上限的時間比例和單位懲罰費(fèi)用。天窗時間占用懲罰費(fèi)用和相關(guān)約束為

3 并行混合求解算法

所建基礎(chǔ)設(shè)施維修任務(wù)安排優(yōu)化模型屬于NP-Hard的混合整數(shù)規(guī)劃問題，模型規(guī)模隨著基礎(chǔ)設(shè)施系統(tǒng)、區(qū)間和任務(wù)數(shù)量的增加呈指數(shù)增長。為便于求解，應(yīng)用分治方法將式(29)～式(31)分解為

得到如表1所示的2 個可并行求解子模型(k=1,2)。進(jìn)一步應(yīng)用并行混合求解算法求解，算法流程如圖2所示。

表1 分解后的子模型結(jié)構(gòu)和算法Table 1 Framework and solution algorithm of two sub-models

圖2 并行混合求解算法流程圖Fig.2 Flowchart of parallel hybrid solution method

3.1 自適應(yīng)鄰域搜索算法

根據(jù)子模型2的特點(diǎn)和自適應(yīng)鄰域搜索算法框架[7]，設(shè)計(jì)算法中鄰域搜索機(jī)制，包括任務(wù)的破壞和修復(fù)算子。

破壞算子在當(dāng)前代選擇并移除q個任務(wù)：

(1)隨機(jī)選擇任務(wù)；

(2)優(yōu)先選擇作業(yè)時間da超出必要時段數(shù)量int(fa)多的任務(wù)；

(3)優(yōu)先選擇產(chǎn)生懲罰費(fèi)用(C2中第2～第6項(xiàng))多的任務(wù)。

修復(fù)算子用于重新安排被移除的q個任務(wù)，算子只生成安排任務(wù)的順序，應(yīng)用貪心算法最小化每次添加任務(wù)時增加的費(fèi)用。

(1)按照任務(wù)占用比例fa由大至小安排；

(2)按照時段[Ts,a,Te,a] 內(nèi)Sa中平均剩余可占用天窗時間比例從小到大安排；

(3)按照時段[Ts,a,Te,a] 內(nèi)Sa中平均剩余可安排任務(wù)數(shù)量由小到大安排。

3.2 占用約束更新機(jī)制

迭代過程中，需要更新子模型的天窗時間占用比例約束以實(shí)現(xiàn)優(yōu)化。根據(jù)第g代的時間占用比例約束和求解結(jié)果Gk,sp來更新第g+1 代中的占用比例約束，其中，Gk,sp為子模型k中的實(shí)際時間占用比例，即

更新機(jī)制為

在第1次更新時，需設(shè)0.5Fsp。

4 案例研究

4.1 案例背景

以某地鐵線路為研究對象，線路共分為52 個區(qū)間，基礎(chǔ)設(shè)施中線路、供電、信號、機(jī)電系統(tǒng)設(shè)置5個維修工區(qū)，建安系統(tǒng)設(shè)置1個維修工區(qū)。年度維修任務(wù)安排在52 個時段中，時段內(nèi)可作業(yè)天數(shù)Qsp為7 d，每天可作業(yè)時間Tsp為5 h，時間占用比例限制Fsp為0.9，天窗時間占用沖突的懲罰費(fèi)用cO,sp為1000元。

日常維修任務(wù)共有29 項(xiàng)，基本參數(shù)如表2所示。包含其他任務(wù)和需要多個工隊(duì)的任務(wù)費(fèi)用分別為基礎(chǔ)費(fèi)用的2.5倍和4.0倍，組合維修的折減費(fèi)用為任務(wù)執(zhí)行費(fèi)用的4%。專項(xiàng)維修任務(wù)共有200項(xiàng)，基本情況如表3所示，同時作業(yè)和非同時作業(yè)的任務(wù)各有50 對。任務(wù)限制作業(yè)數(shù)量zR,p和zM,sp取值分別為6和3 項(xiàng)，占用比例擴(kuò)展系數(shù)ga為0.1。任務(wù)的執(zhí)行費(fèi)用和各項(xiàng)懲罰費(fèi)用如表4所示。

表2 日常維修任務(wù)參數(shù)Table 2 Parameters of routing maintenance tasks

表3 專項(xiàng)維修任務(wù)的時間占用比例和作業(yè)區(qū)間數(shù)量統(tǒng)計(jì)Table 3 Number of sections and occupation ratios of special maintenance tasks

表4 專項(xiàng)維修任務(wù)費(fèi)用參數(shù)Table 4 Cost parameters of special maintenance tasks

4.2 優(yōu)化結(jié)果

并行混合求解算法的求解過程如圖3所示。初始解(第1代)中2個子模型均應(yīng)用時間占用比例限制的上限，所以存在較高的天窗時間占用沖突，為49.99。在1～3 代中，占用沖突快速下降，但逐漸嚴(yán)格的占用約束增大了維修任務(wù)的費(fèi)用(C1和C2)。第4～6 代中，總時間占用沖突略有增加，但維修任務(wù)費(fèi)用減少，使總費(fèi)用下降?？傎M(fèi)用逐漸趨于穩(wěn)定并在第6代時實(shí)現(xiàn)收斂。

圖3 求解過程中目標(biāo)值的變化示意圖Fig.3 Variation of objectives in solution procedure

求解結(jié)果如表5所示，維修安排結(jié)果的總費(fèi)用為263168.0 元，其中85.89%來自維修任務(wù)，14.11%為懲罰費(fèi)用，時間占用沖突占懲罰費(fèi)用的51.32%。維修安排結(jié)果共包括200 項(xiàng)專項(xiàng)維修任務(wù)和7902 項(xiàng)日常維修任務(wù)，其中6625 項(xiàng)任務(wù)實(shí)現(xiàn)與相同任務(wù)組合。

表5 求解結(jié)果和費(fèi)用構(gòu)成Table 5 Solution results and cost composition

為驗(yàn)證并行混合求解算法效果，使用求解器(Gurobi)對綜合優(yōu)化模型進(jìn)行求解，結(jié)果如表6所示。線性化后的綜合優(yōu)化模型共包括1976048 個決策變量和3390464個約束條件，求解器只能得到模型的理論下界。并行混合求解算法可在2.1 h內(nèi)得到可行解，與下界的差異為2.44%，說明并行混合求解算法具有較好的求解效率和精度。

表6 求解算法對比結(jié)果Table 6 Results of different solution methods

4.3 天窗時間占用約束的影響分析

3 種不同天窗時間占用約束下的求解結(jié)果如表7所示，存在沖突的時空分布如圖4所示。由于維修任務(wù)的集中安排可減少費(fèi)用，在不考慮占用約束時(情形B)，維修任務(wù)安排結(jié)果中存在大量且顯著的沖突，平均值為0.326。獨(dú)立考慮兩類維修任務(wù)的占用約束時(情形C)，占用沖突明顯下降但沖突的數(shù)量降低不明顯。情形A 中，聯(lián)合約束使得沖突數(shù)量和比例均有明顯下降，平均占用沖突可降至0.089，維修任務(wù)的可實(shí)施性較高。占用沖突的減少會增加任務(wù)的執(zhí)行費(fèi)用和懲罰費(fèi)用，日常維修任務(wù)費(fèi)用的變化較小，因?yàn)殪`活的任務(wù)間隔可避免任務(wù)安排在存在占用沖突的時段和區(qū)段內(nèi)。上述結(jié)果說明，考慮任務(wù)的占用約束可有效降低沖突發(fā)生的數(shù)量和規(guī)模，降低進(jìn)一步調(diào)整維修安排的復(fù)雜性。

表7 不同天窗時間占用約束下的求解結(jié)果Table 7 Solution results with different time occupation constraints

圖4 存在沖突的時間占用分布Fig.4 Distribution of conflicting time occupations

4.4 靈敏度分析

作為重要的維修資源，天窗時間將直接影響任務(wù)的可執(zhí)行性。如圖5所示，隨著天窗時間的減小，總費(fèi)用C逐漸增大，天窗時間每減少20 min，總費(fèi)用增大約4.0%。當(dāng)天窗時間減少為240 min時，模型無法得到可行解，需要增加工隊(duì)數(shù)量以同時執(zhí)行更多的任務(wù)。天窗時間對專項(xiàng)維修任務(wù)費(fèi)用C2的影響較大，因?yàn)閷ｍ?xiàng)維修任務(wù)的作業(yè)量較大，需要更多的作業(yè)時段以減少在每個時段的時間占用。

圖5 天窗時間對維修安排的影響Fig.5 Impact of maintenance interval on maintenance task arrangement

維修任務(wù)的時間占用沖突與沖突的懲罰費(fèi)用直接相關(guān)，如圖6所示。隨著懲罰費(fèi)用的增加，占用沖突顯著減小，懲罰費(fèi)用增至5000 元時占用沖突可降至7.81，說明維修任務(wù)安排結(jié)果的時間占用沖突存在較大的優(yōu)化空間。同時，為降低天窗時間占用沖突，任務(wù)的執(zhí)行費(fèi)用會增加，導(dǎo)致總費(fèi)用快速增加，因此需要平衡占用沖突和任務(wù)執(zhí)行費(fèi)用，實(shí)現(xiàn)合理的維修任務(wù)安排。

圖6 時間占用懲罰費(fèi)用對維修安排的影響Fig.6 Impact of occupation penalty on maintenance task arrangement

5 結(jié)論

本文得到的主要結(jié)論如下：

(1)提出的維修任務(wù)安排優(yōu)化模型可在滿足任務(wù)執(zhí)行需求的基礎(chǔ)上有效降低維修費(fèi)用，相比不考慮任務(wù)作業(yè)時間的方法能夠降低81.74%的天窗時間占用沖突，提高維修任務(wù)的可執(zhí)行性。

(2)天窗時間長度對維修任務(wù)安排有顯著影響，縮短天窗時間需要增加維修工隊(duì)數(shù)量以保證維修任務(wù)需求。天窗時間的占用沖突會隨著懲罰費(fèi)用的增加而顯著減小，但需要平衡沖突規(guī)模與維修任務(wù)費(fèi)用之間的關(guān)系。