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

(北京交通大學，綜合交通運輸大數(shù)據(jù)應用技術交通運輸行業(yè)重點實驗室，北京100044)

0 引言

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

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

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

1 問題描述

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

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

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

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

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

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

(3)專項維修任務需要專用的工隊和維修設備，不與日常維修任務共享維修資源。

2 模型構建

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

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

2.1 日常維修任務費用

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

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

日常維修任務費用為

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

基本約束為

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

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

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

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

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

2.2 專項維修任務費用

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

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

專項維修任務費用為

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

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

各約束對應的變量分別為

其余約束為

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

2.3 天窗時間占用懲罰費用

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

3 并行混合求解算法

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

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

表1 分解后的子模型結構和算法Table 1 Framework and solution algorithm of two sub-models

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

3.1 自適應鄰域搜索算法

根據(jù)子模型2的特點和自適應鄰域搜索算法框架[7]，設計算法中鄰域搜索機制，包括任務的破壞和修復算子。

破壞算子在當前代選擇并移除q個任務：

(1)隨機選擇任務；

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

(3)優(yōu)先選擇產(chǎn)生懲罰費用(C2中第2～第6項)多的任務。

修復算子用于重新安排被移除的q個任務，算子只生成安排任務的順序，應用貪心算法最小化每次添加任務時增加的費用。

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

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

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

3.2 占用約束更新機制

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

更新機制為

在第1次更新時，需設0.5Fsp。

4 案例研究

4.1 案例背景

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

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

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

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

表4 專項維修任務費用參數(shù)Table 4 Cost parameters of special maintenance tasks

4.2 優(yōu)化結果

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

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

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

表5 求解結果和費用構成Table 5 Solution results and cost composition

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

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

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

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

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

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

4.4 靈敏度分析

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

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

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

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

5 結論

本文得到的主要結論如下：

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

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