城市天然氣管網(wǎng)巡檢和搶修協(xié)同動(dòng)態(tài)調(diào)配策略①

董紅召 胡文靜 張 楠 佘翊妮

(浙江工業(yè)大學(xué)智能交通系統(tǒng)聯(lián)合研究所 杭州 310014)

0 引言

提升管道安全保障能力同時(shí)提高工作人員勞動(dòng)效率對(duì)城市天然氣管網(wǎng)運(yùn)行管理有重大意義。當(dāng)前天然氣管網(wǎng)搶修工作人員在管網(wǎng)事故發(fā)生后及時(shí)前往事故現(xiàn)場,但是其等待事故上報(bào)的時(shí)間缺少利用,存在大量時(shí)間空白。與此同時(shí),天然氣管道網(wǎng)絡(luò)規(guī)模逐年增大,僅靠有限的巡檢人力完成日常巡檢維護(hù)工作壓力倍增。為此,嘗試淡化巡檢員工和搶修員工的工作界限,提出巡檢搶修一體化動(dòng)態(tài)協(xié)同調(diào)配策略,讓所有員工協(xié)同完成巡檢搶修工作,以提高天然氣管網(wǎng)巡檢自查率的同時(shí)提高搶修響應(yīng)效率。為使敘述邏輯清晰,下文統(tǒng)稱巡檢員工和搶修員工為檢修單元。

巡檢搶修協(xié)同工作模式的全面實(shí)現(xiàn)受到多方面的阻力。一方面,檢修單元技術(shù)等級(jí)差異明顯、城市擁堵狀況未知、搶修環(huán)境優(yōu)劣程度難以判斷等原因,使得天然氣管道搶修響應(yīng)時(shí)長和搶修完成時(shí)長存在極大不確定性;另一方面,搶修新增、搶修撤銷和搶修任務(wù)需求變化等動(dòng)態(tài)事件的發(fā)生對(duì)調(diào)配策略的整體影響,為管網(wǎng)的最優(yōu)搶修調(diào)度決策增加了難度。另外,因?yàn)闄z修單元同時(shí)參加搶修任務(wù)和日常的巡檢維護(hù)任務(wù),搶修工作量分配的均衡程度造成巡檢工作的完成差異,甚至?xí)绊憮屝薹?wù)質(zhì)量。

近年來,學(xué)者們在應(yīng)急調(diào)度方面研究的側(cè)重點(diǎn)在于急迫性和經(jīng)濟(jì)性[1-3],即建立多目標(biāo)模型時(shí)關(guān)注調(diào)度方法的時(shí)效性和調(diào)配方案的成本[4-5]。關(guān)于不確定條件下的應(yīng)急資源調(diào)度,現(xiàn)有研究側(cè)重點(diǎn)為人力物力資源量化后的不確定性需求。周蕾[6]針對(duì)突發(fā)事件后,應(yīng)急需求的高度時(shí)變、隨機(jī)、復(fù)雜特性,將服務(wù)覆蓋面問題引入到應(yīng)急車輛調(diào)度問題。Wang 等人[7]劃分應(yīng)急調(diào)度需求為確定性需求和需要預(yù)測的不確定性需求,引入概率函數(shù)表示不確定性需求,構(gòu)建考慮需求未滿足度的應(yīng)急調(diào)度優(yōu)化模型。Zhu 等人[8]將調(diào)度對(duì)象的調(diào)度需求劃分為多個(gè)周期,根據(jù)多個(gè)子周期的交通變化,提出時(shí)變多智能體遺傳算法求解的應(yīng)急資源調(diào)度優(yōu)化模型。針對(duì)應(yīng)急救援的動(dòng)態(tài)特性,Shen[9]研究了自然災(zāi)害發(fā)生后短期時(shí)間內(nèi)對(duì)居住場所的需求,以此為研究對(duì)象提出一種短周期時(shí)變分配模型?，F(xiàn)有調(diào)度研究在時(shí)間方面多是基于預(yù)測信息準(zhǔn)確的前提下完成后續(xù)模型的建立,極少有針對(duì)工作時(shí)長不確定性進(jìn)行深入研究,已有研究不能完全適應(yīng)于搶修過程時(shí)間不確定性和具有任務(wù)累計(jì)效應(yīng)的天然氣管網(wǎng)巡檢搶修協(xié)同調(diào)度。綜上所述,面對(duì)天然氣管網(wǎng)管理嚴(yán)峻形勢,巡檢自查和事故搶修的協(xié)同調(diào)配管理以保證燃?xì)夤艿谰W(wǎng)絡(luò)的安全運(yùn)行就凸顯了其迫切性和重要性。因此,結(jié)合動(dòng)態(tài)道路網(wǎng)絡(luò)信息,考慮平衡巡檢自查和事故搶修的天然氣管網(wǎng)動(dòng)態(tài)協(xié)同調(diào)配策略研究不容忽視。

1 巡檢搶修一體化協(xié)同調(diào)配現(xiàn)狀

在巡檢搶修一體化工作模式下,因?yàn)闄z修單元技術(shù)等級(jí)差異,巡檢搶修協(xié)同工作機(jī)制并不是單純的讓搶修員工和巡檢員工的工作內(nèi)容完全重合。原搶修員工改變固定站點(diǎn)等待管網(wǎng)事故上報(bào)的工作機(jī)制,以預(yù)防、發(fā)現(xiàn)并處理天然氣管網(wǎng)事故為目的協(xié)助原巡檢員工執(zhí)行管網(wǎng)安全巡檢工作,這樣減少了等待任務(wù)上報(bào)的時(shí)間浪費(fèi),可以有效提高管網(wǎng)安全維護(hù)效率。原巡檢員工自查天然氣管網(wǎng)的故障,在發(fā)現(xiàn)管網(wǎng)事故有安全隱患時(shí)提前預(yù)警,聯(lián)系區(qū)域內(nèi)原搶修員工協(xié)作完成問題管道的修復(fù)工作,可以有效簡化管道事故的上報(bào)流程,減少上報(bào)延遲的情況。

當(dāng)前當(dāng)巡檢員工發(fā)現(xiàn)管網(wǎng)搶維修事故,聯(lián)系最靠近事故點(diǎn)位置的原搶修員工執(zhí)行搶修任務(wù)(以下統(tǒng)稱“最短路調(diào)配策略”),該調(diào)配策略充分考慮距離因素,但對(duì)于檢修單元協(xié)同工作與管網(wǎng)事故不確定性大的天然氣管網(wǎng)安全維護(hù)和管理而言存在諸多弊端,導(dǎo)致?lián)屝揄憫?yīng)時(shí)間超過調(diào)度管理部門硬性要求時(shí)間窗情況多、檢修單元工作量差異大、搶修報(bào)修服務(wù)反饋較差等問題。

巡檢搶修一體化工作模式拓寬了管網(wǎng)搶修報(bào)修時(shí)可選調(diào)度人員的范圍,為優(yōu)化調(diào)配創(chuàng)造了機(jī)會(huì)。計(jì)及搶修任務(wù)不確定搶修耗時(shí)和動(dòng)態(tài)事件生成的不確定需求,本文提出綜合考慮搶修效率和檢修工作分配管理的動(dòng)態(tài)協(xié)同優(yōu)化調(diào)配策略。

2 巡檢搶修一體化協(xié)同優(yōu)化調(diào)配策略

天然氣管網(wǎng)搶修事故(下文統(tǒng)稱“搶修任務(wù)”)的優(yōu)化調(diào)配問題是一個(gè)多類型調(diào)配主體匹配多類型任務(wù)的組合優(yōu)化問題[10-11]。已知搶修任務(wù)調(diào)度需求、檢修單元資源配置和搶修任務(wù)地理位置等信息,首先提出搶修任務(wù)可靠性調(diào)配策略,給出搶修響應(yīng)階段不確定的搶修響應(yīng)時(shí)間、搶修執(zhí)行階段不確定的搶修耗時(shí)的可靠確定方法。再提出搶修任務(wù)公平性調(diào)配策略以均衡檢修單元工作量。結(jié)合公平性和可靠性調(diào)配策略,構(gòu)建管網(wǎng)檢修一體化協(xié)同調(diào)配模型,滿足燃?xì)庹{(diào)度管理部門規(guī)定的搶修響應(yīng)硬性時(shí)間窗和搶修任務(wù)調(diào)度需求等約束,得到搶修響應(yīng)時(shí)間短和搶修任務(wù)分配公平2 個(gè)優(yōu)化目標(biāo)的動(dòng)態(tài)調(diào)配策略。

2.1 搶修任務(wù)可靠性調(diào)配策略

國內(nèi)外學(xué)者對(duì)應(yīng)急調(diào)度中不確定因素的確定方法[12-14]進(jìn)行了深入研究,大部分研究都關(guān)注資源需求的不確定性[15-16]。但是城市燃?xì)夤芫W(wǎng)搶修調(diào)度高度依賴于實(shí)時(shí)環(huán)境的影響,如果要及時(shí)反饋接收到的實(shí)時(shí)信息,便需要應(yīng)對(duì)由各種動(dòng)態(tài)事件導(dǎo)致的實(shí)時(shí)道路信息變化、搶修調(diào)度需求變化等,由此提出搶修任務(wù)可靠性調(diào)配策略。計(jì)算搶修任務(wù)的搶修耗時(shí)的預(yù)測區(qū)間,給出搶修響應(yīng)時(shí)間在不同動(dòng)態(tài)環(huán)境背景的求解方法,提高調(diào)配策略的魯棒性。

定義搶修任務(wù)的搶修響應(yīng)時(shí)間為管網(wǎng)事故發(fā)出搶修調(diào)度需求到檢修單元開始執(zhí)行任務(wù)的時(shí)間,主要與到達(dá)搶修任務(wù)現(xiàn)場的行程時(shí)間、檢修單元之間的協(xié)作等待時(shí)間有關(guān)。定義搶修耗時(shí)為搶修任務(wù)從執(zhí)行開始到執(zhí)行完成的時(shí)間。

2.1.1 搶修耗時(shí)可靠經(jīng)驗(yàn)值

燃?xì)夤芫W(wǎng)的搶修耗時(shí)分析是日常巡檢搶修任務(wù)分配和搶修調(diào)度管理的重要參考因素,搶修耗時(shí)與搶修任務(wù)的調(diào)度需求之間有很強(qiáng)的相關(guān)性。因此,通過調(diào)研將搶修任務(wù)按照實(shí)際搶修調(diào)度需求分為五大類,記為L={1,2,3,4,5},1～5 分別表示任務(wù)類型1～任務(wù)類型5,對(duì)應(yīng)調(diào)度需求為1 名原騎行電瓶車的搶修員工;2 名原騎行電瓶車的搶修員工;1 名原駕駛機(jī)具車的搶修員工;1 名原騎行電瓶車的搶修員工和1 名原駕駛機(jī)具車的搶修員工;2 名原駕駛機(jī)具車的搶修員工?；诖?考慮未知擬合線型的搶修數(shù)據(jù),通過貝葉斯綜合模型法[17]給出搶修耗時(shí)分布模型。管網(wǎng)搶修任務(wù)的搶修耗時(shí)分布確定過程具體如下。

計(jì)算歷史搶修案例數(shù)據(jù)屬于備選線型的先驗(yàn)概率。選取4 條備選線型組成備選線型集合記為M={1,2,3,4},1～4 分別表示伽馬分布、威布爾分布、對(duì)數(shù)正態(tài)分布和廣義極值分布。為得到搶修耗時(shí)變量H屬于線型Mi的先驗(yàn)概率p(Mi),選取4 種評(píng)價(jià)準(zhǔn)則和一個(gè)數(shù)據(jù)樣本X統(tǒng)計(jì)量提出一種綜合評(píng)價(jià)函數(shù)[14]。評(píng)價(jià)指標(biāo)集合記為Q={1,2,3,4,5},1～5分別表示RMSE(均方根誤差最小)準(zhǔn)則、ABS(離差絕對(duì)值和最小)準(zhǔn)則、AIC(信息量最小)準(zhǔn)則、K-S 檢驗(yàn)、標(biāo)準(zhǔn)差(standard deviation)。則綜合評(píng)價(jià)函數(shù)的表達(dá)式為

式中xij表示第i個(gè)備選線型的第j個(gè)評(píng)價(jià)指標(biāo)值,N表示評(píng)價(jià)指標(biāo)個(gè)數(shù),k表示備選線型個(gè)數(shù)。綜合評(píng)價(jià)函數(shù)可以量化多個(gè)備選線型的實(shí)際擬合效果,同時(shí)增加標(biāo)準(zhǔn)差為評(píng)價(jià)指標(biāo)之一,可以描述搶修耗時(shí)數(shù)據(jù)離散程度變化規(guī)律。

計(jì)算數(shù)據(jù)樣本屬于線型Mi的先驗(yàn)概率p(Mi|X)的表達(dá)式為

式中k表示備選線型的個(gè)數(shù),l(X|Mj)表示數(shù)據(jù)樣本X來自線型Mj條件下的似然函數(shù)。由不同備選線型計(jì)算對(duì)應(yīng)加權(quán)后驗(yàn)概率p(Mi|X),由此搶修耗時(shí)變量H的概率密度函數(shù)可以由全概率公式表示為

式中fi(H|Mi)表示屬于第i種待選線型的概率密度函數(shù),可以得到指定頻率P下的搶修耗時(shí)Hp即可表示為

用上述綜合評(píng)價(jià)函數(shù)修正搶修耗時(shí)求解,則考慮樣本數(shù)據(jù)擬合程度的前提下,指定頻率P下的搶修耗時(shí)Hp即可表示為

2.1.2 不同調(diào)度情景的搶修響應(yīng)時(shí)間

時(shí)間的緊迫性是城市天然氣管道事故搶修調(diào)度最突出的特性,縮短搶修任務(wù)的搶修響應(yīng)時(shí)間是搶修調(diào)配策略的關(guān)鍵目標(biāo)函數(shù)之一。

通過調(diào)研并綜合行業(yè)經(jīng)驗(yàn),檢修單元與搶修任務(wù)之間存在多種數(shù)量對(duì)應(yīng)關(guān)系,由此存在多種調(diào)度情景的搶修調(diào)度方案。在有限檢修單元數(shù)量的約束下,為討論不同調(diào)度情景與搶修調(diào)配策略之間的相互影響關(guān)系,分別考慮一般搶修調(diào)配情景和資源沖突搶修調(diào)配情景。一般搶修調(diào)配情景描述為可及時(shí)響應(yīng)的檢修單元的數(shù)量能滿足搶修任務(wù)數(shù)量。資源沖突搶修調(diào)配情景的燃?xì)鈸屝奕蝿?wù)與檢修單元數(shù)量不平衡,如城市工程建設(shè)或季節(jié)原因,可能導(dǎo)致某段時(shí)間內(nèi)的調(diào)度需求大幅增加,隨時(shí)會(huì)出現(xiàn)檢修單元數(shù)量不能滿足搶修任務(wù)的情況。

(1)一般搶修調(diào)配情景的搶修響應(yīng)時(shí)間

在一般搶修調(diào)配情景,充分考慮時(shí)間緊迫性,優(yōu)先調(diào)度可以及時(shí)響應(yīng)的檢修單元,此時(shí)搶修任務(wù)的搶修響應(yīng)時(shí)間主要與到達(dá)搶修任務(wù)位置的行程時(shí)間和檢修單元之間的協(xié)作等待時(shí)間有關(guān)。易知搶修任務(wù)的剩余修復(fù)時(shí)間Si由搶修耗時(shí)可靠經(jīng)驗(yàn)值Pl與已完成時(shí)間的差值得到。搶修響應(yīng)時(shí)間因?yàn)椴煌娜蝿?wù)類型又分為2 種子情況。

情況1當(dāng)搶修任務(wù)為類型1 或者類型3 時(shí),調(diào)度需求為一個(gè)檢修單元,此時(shí)搶修任務(wù)k的搶修響應(yīng)時(shí)間Rk只包括檢修單元i到達(dá)搶修任務(wù)現(xiàn)場的行程時(shí)間,此時(shí)表達(dá)式為

式中Aik表示檢修單元i與搶修任務(wù)k之間分配關(guān)系的布爾變量,Aik=1 表示檢修單元i執(zhí)行搶修任務(wù)k,否則為0;Rk表示搶修任務(wù)k的搶修響應(yīng)時(shí)間;Jik表示檢修單元i到達(dá)搶修任務(wù)k現(xiàn)場的實(shí)時(shí)行程時(shí)間;I是所有檢修單元集合,T是實(shí)時(shí)新增搶修任務(wù)的集合。

情況2當(dāng)搶修任務(wù)為類型2、類型4 或者類型5 時(shí),調(diào)度需求為由2 個(gè)檢修單元組成的搶修集合,2 個(gè)檢修單元之間存在協(xié)同等待時(shí)間,表示為Wij,此時(shí)搶修任務(wù)的搶修響應(yīng)時(shí)間包括2 部分時(shí)間,即:

(2)資源沖突搶修調(diào)配情景

因?yàn)闄z修單元數(shù)量緊張,有必要考慮所有檢修單元以緩解搶修調(diào)度需求增加但是檢修單元數(shù)量不變產(chǎn)生的調(diào)度壓力。此時(shí)搶修任務(wù)的搶修響應(yīng)時(shí)間主要與負(fù)責(zé)修復(fù)的上一搶修任務(wù)的剩余修復(fù)時(shí)間、到達(dá)搶修任務(wù)位置的行程時(shí)間和檢修單元之間的協(xié)作等待時(shí)間有關(guān)。

情況1當(dāng)搶修任務(wù)為類型1 或者類型3 時(shí),調(diào)度需求為一個(gè)檢修單元,此時(shí)搶修任務(wù)的搶修響應(yīng)時(shí)間為

式中Si表示檢修單元i的剩余搶修時(shí)間。Fi表示檢修單元i是否有剩余搶修任務(wù)的布爾變量,Fi=1表示檢修單元i還在執(zhí)行搶修任務(wù),否則為0。

情況2當(dāng)搶修任務(wù)為類型2、類型4 或者類型5 時(shí),調(diào)度需求為2 個(gè)檢修單元,此時(shí)搶修任務(wù)的搶修響應(yīng)時(shí)間為

2.2 搶修任務(wù)公平性調(diào)配策略

考慮搶修工作量分配的公平性是燃?xì)馐鹿蕮屝拚{(diào)度策略目標(biāo)函數(shù)之一。在多目標(biāo)動(dòng)態(tài)公平調(diào)度[18-19]方面,有少數(shù)學(xué)者會(huì)關(guān)注調(diào)度方案最大程度提高服務(wù)水平[13],但極少有研究關(guān)注搶修任務(wù)分配公平程度對(duì)整體搶修質(zhì)量的反向影響。檢修單元搶修任務(wù)的分配直接影響檢修單元的工作時(shí)長,由此提出搶修任務(wù)公平性調(diào)配策略。給出檢修單元的搶修任務(wù)工作量差異的表示方式,并提出調(diào)度偏好函數(shù)作為工作量分配公平性的評(píng)價(jià)指標(biāo),調(diào)整檢修單元的任務(wù)分配,得到工作分配量更公平合理的調(diào)配策略。

檢修單元之間的搶修工作量的差異程度主要指完成搶修任務(wù)的累計(jì)時(shí)長的差異,因此選取檢修單元累計(jì)搶修耗時(shí)總時(shí)長表示其搶修工作量,記為Ci。因?yàn)榕渲秒娖寇嚨尿T行搶修員工和配置機(jī)具車的駕駛搶修員工承載工作壓力的能力不同,所以有必要考慮調(diào)度主體類型的不同,按檢修單元種類劃分成2 個(gè)集合分別求解,分別記為M和C,其中M表示配置電瓶車的騎行搶修員工集合,C表示配置機(jī)具車的駕駛搶修員工集合,I=M∪C。則求取時(shí)刻的搶修運(yùn)行工和搶修機(jī)具車分別的搶修工作量差異Di表示為

式中Ci表示檢修單元i的搶修工作時(shí)長月累計(jì)值,Di表示檢修單元i的搶修量差異值,Pl表示2.1.2節(jié)中計(jì)算的搶修耗時(shí)可靠經(jīng)驗(yàn)值,L表示搶修任務(wù)類型。因?yàn)閾屝薰ぷ髁康牟町惓潭却髮?duì)檢修單元整體工作完成情況來講,會(huì)降低日常巡檢工作完成進(jìn)度,甚至影響搶修任務(wù)完成質(zhì)量。構(gòu)建調(diào)度偏好函數(shù)記為Ψ(Di),近似刻畫搶修任務(wù)分配與檢修單元整體工作進(jìn)程的負(fù)相關(guān)性[14-15],調(diào)度偏好函數(shù)表達(dá)式為

式中a0表示調(diào)度偏好函數(shù)趨勢參數(shù),b0表示調(diào)度偏好函數(shù)平穩(wěn)參數(shù),a0、b0均為常數(shù)。

3 巡檢搶修協(xié)同調(diào)配模型的構(gòu)建

基于以上分析,同時(shí)考慮公平性和可靠性2 個(gè)方面調(diào)配策略,構(gòu)建考慮可靠度的巡檢搶修動(dòng)態(tài)協(xié)同調(diào)配模型:

式中M為原騎行電瓶車的搶修員工,C為原駕駛機(jī)具車的搶修員工。目標(biāo)函數(shù)式(15)表示實(shí)現(xiàn)檢修單元從收到新?lián)屝奕蝿?wù)到到達(dá)搶修任務(wù)現(xiàn)場的總時(shí)長最小,體現(xiàn)搶修調(diào)度方案的響應(yīng)效率和執(zhí)行效率。目標(biāo)函數(shù)式(16)表示最大化檢修單元的調(diào)度偏好,即最小化搶修調(diào)度過程中檢修單元之間額外工作量的差異,體現(xiàn)搶修調(diào)度方案的公平性。

約束式(17)～(21)分別表示情況類型為1～5的搶修任務(wù)對(duì)應(yīng)需要調(diào)度的搶修集合組合方式約束,約束式(22)是根據(jù)燃?xì)饧瘓F(tuán)給出的搶修調(diào)度到達(dá)搶修任務(wù)現(xiàn)場的硬性時(shí)間窗,檢修單元必須在30 min 的有效響應(yīng)時(shí)間之內(nèi)到達(dá)搶修任務(wù)現(xiàn)場。約束式(23)表明,一個(gè)檢修單元同一時(shí)間最多只能搶修一個(gè)搶修任務(wù)。

4 雙基因位組合動(dòng)態(tài)遺傳算法求解

以上建立的燃?xì)鈸屝迍?dòng)態(tài)調(diào)度模型屬于非線性、多目標(biāo)的離散組合優(yōu)化問題[20],同時(shí)管網(wǎng)搶修任務(wù)協(xié)同調(diào)度過程中動(dòng)態(tài)事件的發(fā)生是離散不確定性的。參考國內(nèi)外學(xué)者研究,滾動(dòng)時(shí)域法是解決時(shí)變條件下的協(xié)同調(diào)度模型的有效方法[21],因此將滾動(dòng)時(shí)域法與遺傳算法相結(jié)合,得到優(yōu)化動(dòng)態(tài)調(diào)配策略。動(dòng)態(tài)算法求解的本質(zhì)就是將問題劃分為多個(gè)靜態(tài)問題,因此靜態(tài)子問題的求解和時(shí)域劃分是動(dòng)態(tài)問題求解的關(guān)鍵。

設(shè)計(jì)優(yōu)化的多基因位組合動(dòng)態(tài)遺傳算法求解[22-23],先求解動(dòng)態(tài)問題劃分后的初始靜態(tài)子問題的解,然后在調(diào)度時(shí)域劃分基礎(chǔ)上使用動(dòng)態(tài)算子描述問題發(fā)生的動(dòng)態(tài)不確定性事件。算法流程圖如圖1所示。

圖1 雙基因位組合動(dòng)態(tài)遺傳算法流程圖

4.1 遺傳算法求解靜態(tài)調(diào)配策略

步驟1提出雙基因位實(shí)數(shù)編碼方式初始化種群編碼,輸入搶修任務(wù)集合,隨機(jī)產(chǎn)生搶修單元組合和任務(wù)分配方案Mijk。編碼策略示例如圖2 所示,表示搶修任務(wù)1 同時(shí)調(diào)配1 號(hào)和34 號(hào)檢修單元,…,第n個(gè)搶修任務(wù)調(diào)度40 號(hào)檢修單元。

圖2 染色體編碼策略

步驟2動(dòng)態(tài)調(diào)用第三方騎行和駕駛路徑規(guī)劃接口獲得實(shí)時(shí)行程時(shí)間,以同條染色體上的連續(xù)雙基因位作為單位計(jì)算染色體的適應(yīng)度,即得到初始搶修任務(wù)集的實(shí)時(shí)行程時(shí)間和規(guī)劃路線。選擇算子采取動(dòng)態(tài)適應(yīng)度函數(shù)值和錦標(biāo)賽法結(jié)合選擇子代個(gè)體。采用自適應(yīng)交叉算子和自適應(yīng)變異算子,其交叉和變異概率隨著種群平均適應(yīng)度值的增加呈現(xiàn)減少趨勢,以提高算法的求解速度,對(duì)應(yīng)的概率計(jì)算公式如式(24)所示,利用設(shè)計(jì)的交叉和變異概率函數(shù)更新染色體,執(zhí)行步驟3。

式中μ0為交叉概率約束參數(shù),pc表示交叉和變異概率,yfit表示每一代種群所有個(gè)體的適應(yīng)度值。

步驟3基于以上更新后的染色體,可以得到搶修人員與搶修任務(wù)之間的分配關(guān)系,從而得到搶修調(diào)配方案和調(diào)度路徑結(jié)果,依此更新所有檢修單元集合的狀態(tài)。判斷是否滿足巡檢搶修協(xié)同調(diào)配模型的多約束條件,如果滿足,進(jìn)入下一步判斷;否則,轉(zhuǎn)到步驟2。

步驟4判斷是否滿足算法終止條件或者算法運(yùn)行達(dá)到預(yù)先設(shè)置的迭代次數(shù),若滿足終止運(yùn)算,得到種群的歷史最佳結(jié)果,等待下一次輸入;否則,轉(zhuǎn)到步驟2。

4.2 動(dòng)態(tài)算子修正

基于4.1 節(jié)對(duì)靜態(tài)初始調(diào)配策略的求解,當(dāng)有動(dòng)態(tài)事件發(fā)生時(shí)會(huì)影響整體的調(diào)配策略,本文主要考慮搶修任務(wù)新增、搶修任務(wù)撤銷和搶修任務(wù)未按時(shí)完成3 種動(dòng)態(tài)事件。因此提出動(dòng)態(tài)算子表征動(dòng)態(tài)事件的發(fā)生,完善算法框架,修正為動(dòng)態(tài)算法。

將整個(gè)調(diào)度時(shí)域劃分為多個(gè)調(diào)度子時(shí)域,在子時(shí)域區(qū)間之間,搶修任務(wù)存在已完成、未執(zhí)行和未完成3 種情況。將整個(gè)調(diào)配策略劃分為多個(gè)調(diào)配子區(qū)間,在已有染色體編碼策略基礎(chǔ)上,以一個(gè)連續(xù)雙基因位為基因單位,記為G0。將算法內(nèi)部的整個(gè)調(diào)度策略按n個(gè)基因單位為單位,n={1,…T},T表示搶修任務(wù)數(shù)量,即nG0為單位長度劃分為多個(gè)調(diào)配子區(qū)間。當(dāng)有動(dòng)態(tài)事件發(fā)生時(shí),采用未固定請求插入方法,根據(jù)初始調(diào)配策略,搶修單元i被分配執(zhí)行搶修任務(wù)k,但是由于檢修單元還在處理上一個(gè)搶修任務(wù)或者實(shí)時(shí)道路擁堵等原因,檢修單元i和搶修任務(wù)k之間的分配關(guān)系還沒有成立,即Aik=0,此時(shí)稱為未固定請求。

未固定請求插入法具體為檢查現(xiàn)有調(diào)配策略結(jié)果中所有可以新增、減少或替換搶修任務(wù)對(duì)應(yīng)檢修單元集合的可行插入調(diào)配子區(qū)間。這里的可行位置主要指滿足2 點(diǎn)需求的調(diào)配子區(qū)間:(1)檢修單元和搶修任務(wù)之間的分配關(guān)系還沒有成立;(2)滿足4.1 節(jié)中改進(jìn)雙基因位遺傳算法已經(jīng)設(shè)置好的所有約束條件。

基于此,以動(dòng)態(tài)雙基因的形式,將動(dòng)態(tài)事件映射為動(dòng)態(tài)算子。如圖3 所示,取n=1,在調(diào)配子區(qū)間之間,當(dāng)有新的動(dòng)態(tài)事件信息插入,清除初始搶修調(diào)度策略結(jié)果中的對(duì)未固定請求的考慮,然后再將新的動(dòng)態(tài)事件信息和為固定請求一同插入到更新的搶修調(diào)配策略中,初始化出一個(gè)新的搶修任務(wù)的調(diào)度策略,計(jì)算所有可行插入位置的適應(yīng)度函數(shù),選擇最小適應(yīng)度值的未知插入,并迭代更新保存現(xiàn)在的搶修調(diào)度策略結(jié)果。

圖3 動(dòng)態(tài)算子實(shí)現(xiàn)未固定請求插入法

5 實(shí)例驗(yàn)證與分析

以杭州燃?xì)饧瘓F(tuán)搶修案例數(shù)據(jù)為例,結(jié)合真實(shí)數(shù)據(jù)和部分仿真參數(shù)設(shè)置,將設(shè)計(jì)的遺傳算法應(yīng)用于求解所構(gòu)模型,對(duì)比分析巡檢搶修一體化協(xié)同優(yōu)化調(diào)配策略與最短路調(diào)配策略,并選擇評(píng)判標(biāo)準(zhǔn)以量化巡檢搶修一體化協(xié)同優(yōu)化調(diào)配策略的優(yōu)越性。巡檢搶修協(xié)同調(diào)配模型和雙基因位組合動(dòng)態(tài)遺傳算法部分程序用Python 3.0 編寫,路徑規(guī)劃部分程序由C#編寫,實(shí)驗(yàn)運(yùn)行環(huán)境為Intel(R) Core(TM) i7-8565U CPU。

5.1 數(shù)據(jù)來源及參數(shù)設(shè)置

選擇杭州燃?xì)夤芫W(wǎng)搶修歷史案例為數(shù)據(jù)來源,對(duì)2019 年1 月1 日至2020 年6 月30 日的2375 條搶修案例歷史有效數(shù)據(jù)進(jìn)行分析。分別繪制5 種類型搶修單元的搶修耗時(shí)時(shí)長的密度概率直方圖,通過非參數(shù)估計(jì)的方法繪制相應(yīng)的核密度估計(jì)曲線,由第2 節(jié)的貝葉斯綜合法,可以得到搶修耗時(shí)時(shí)長與4 種備選線型的擬合圖,曲線參數(shù)如表1所示,具體的擬合曲線如圖4 所示,圖4(a)～(e)分別對(duì)應(yīng)5 種類型的搶修任務(wù)。

圖4 搶修任務(wù)搶修耗時(shí)時(shí)長分布

表1 搶修任務(wù)的待選線型擬合參數(shù)表

給出所有工作人員配置數(shù)量,其中原騎行電瓶車的搶修員工集合I的數(shù)量為67,原駕駛機(jī)具車的搶修員工集合C的數(shù)量為20,調(diào)度偏好函數(shù)中的系數(shù)分別設(shè)置為0.05、2,算法相關(guān)參數(shù)設(shè)置為種群個(gè)數(shù)為50,最大迭代步數(shù)為100,算法接入路徑規(guī)劃第三方接口選擇高德地圖應(yīng)用程序接口。因?yàn)闅v史數(shù)據(jù)所依托路網(wǎng)信息與實(shí)時(shí)路網(wǎng)信息不能保證完全相同,因此通過控制時(shí)間段、節(jié)假日、天氣優(yōu)劣等因素影響減小實(shí)驗(yàn)誤差,并多次實(shí)驗(yàn)求取平均值。

5.2 路徑規(guī)劃對(duì)搶修響應(yīng)時(shí)間對(duì)比分析

為驗(yàn)證檢修協(xié)同動(dòng)態(tài)調(diào)配策略的路徑優(yōu)化結(jié)果對(duì)搶修響應(yīng)時(shí)間的影響,取杭州市上城區(qū)路網(wǎng)作為研究對(duì)象,并分別對(duì)道路交叉口節(jié)點(diǎn)標(biāo)記為J1,J2,J3,…,J117,繪制路網(wǎng)有效信息圖,如圖5 所示。以一個(gè)搶修任務(wù)為例,用帶嘆號(hào)的三角符號(hào)表示,通過原調(diào)配策略、由改進(jìn)的調(diào)配策略模型對(duì)該搶修任務(wù)的調(diào)配結(jié)果,得到的檢修單元路徑規(guī)劃結(jié)果,可視化在路網(wǎng)有效信息圖上,調(diào)度策略對(duì)路徑的選擇對(duì)比如圖6 所示。

圖5 路網(wǎng)有效信息圖

圖6 檢修單元路徑規(guī)劃示意圖

不同調(diào)配策略的路徑規(guī)劃結(jié)果對(duì)應(yīng)的路程時(shí)間和路程距離如表2 所示。通過對(duì)比可以看出,原調(diào)配策略依賴人工經(jīng)驗(yàn),關(guān)注路程最短導(dǎo)致行程時(shí)間長,從而會(huì)影響搶修響應(yīng)的效率。另一方面,原調(diào)配策略因?yàn)槿鄙賹?duì)檢修單元任務(wù)分配量維度的思考,造成任務(wù)分配的公平性比改進(jìn)調(diào)配策略低。

表2 調(diào)配方案優(yōu)化前后信息對(duì)比表

5.3 檢修動(dòng)態(tài)協(xié)同調(diào)配策略累計(jì)效果分析

為探究最短路調(diào)配策略和檢修協(xié)同動(dòng)態(tài)調(diào)配策略在較長應(yīng)用周期下的結(jié)果差別,以杭州燃?xì)饧瘓F(tuán)提供的真實(shí)搶修數(shù)據(jù)為例,選擇數(shù)據(jù)信息較為完整的2020 年6 月1 日至2020 年6 月30 日的歷史搶修案例數(shù)據(jù)進(jìn)行驗(yàn)證,共157 條歷史有效數(shù)據(jù)。

求解2 個(gè)策略下?lián)屝奕蝿?wù)的搶修響應(yīng)時(shí)間和檢修集合累計(jì)搶修耗時(shí)方差,以比較2 種策略的搶修效率和工作分配均衡程度。為了得到更直觀的對(duì)比效果,將圖7 中的搶修任務(wù)順序進(jìn)行調(diào)整,按照最短路調(diào)配策略得到的搶修響應(yīng)時(shí)間由小到大排序,進(jìn)而得到一個(gè)月內(nèi)搶修任務(wù)總體趨勢上升的響應(yīng)時(shí)間折線圖。圖8 為選擇區(qū)間內(nèi)按序發(fā)生的搶修任務(wù),由此可以得到如下結(jié)論。

圖7 不同調(diào)度策略月?lián)屝揄憫?yīng)時(shí)間對(duì)比

圖8 不同調(diào)度策略月?lián)屝薰匠潭葘?duì)比

(1)巡檢搶修一體化協(xié)同優(yōu)化調(diào)配策略考慮城市道路信息動(dòng)態(tài)變化的情況,拓寬了調(diào)度可選的檢修單元的范圍。考慮動(dòng)態(tài)時(shí)間對(duì)初始調(diào)配策略影響,因此其搶修響應(yīng)時(shí)間明顯比最短路調(diào)配策略更短,本文所提策略提高了87.35%搶修任務(wù)的搶修響應(yīng)時(shí)間。

(2)檢修集合累計(jì)搶修耗時(shí)方差總體呈震蕩下降趨勢,因?yàn)榭紤]可靠度的燃?xì)夤秸{(diào)配策略對(duì)搶修單元整體利用率最高,所以該調(diào)度策略在這個(gè)背景下平衡所有搶修單元工作差異方面具有更大優(yōu)勢。搶修任務(wù)的分配公平度得到明顯優(yōu)化,并且優(yōu)化效果隨時(shí)間累計(jì)呈變大趨勢,相較于最短路調(diào)配策略,該策略的搶修集合累計(jì)搶修耗時(shí)方差最低降低比率分別為2.26%、2.13%,最高降低比率分別為43.72%、42.31%,平均降低比率分別為26.39%、22.28%。

6 結(jié)論

為了切實(shí)保障城市天然氣管網(wǎng)安全,并優(yōu)化員工工作負(fù)荷管理,在考慮燃?xì)鈷炀W(wǎng)事故動(dòng)態(tài)不確定性的基礎(chǔ)上,得到高效率和高質(zhì)量的巡檢搶修協(xié)同優(yōu)化調(diào)配策略。本研究細(xì)分2 種調(diào)度情景,給出對(duì)應(yīng)搶修響應(yīng)時(shí)間的求解方法。綜合考慮多種評(píng)價(jià)指標(biāo),給出未知擬合線型的搶修耗時(shí)時(shí)長分布函數(shù);在模型構(gòu)建中綜合考慮調(diào)配策略結(jié)果與搶修工作量分配的相關(guān)性,實(shí)現(xiàn)搶修工作量差異程度的量化,均衡了工作周期內(nèi)動(dòng)態(tài)新增搶修工作量的分配公平程度,提供了任務(wù)分配方式定量分析的新角度;考慮搶修任務(wù)新增、搶修任務(wù)撤銷和搶修任務(wù)未按時(shí)完成3 種動(dòng)態(tài)事件對(duì)調(diào)配策略的影響,在獲取實(shí)時(shí)道路信息的同時(shí),結(jié)合滾動(dòng)時(shí)域法和改進(jìn)遺傳算法完善動(dòng)態(tài)算法框架,實(shí)現(xiàn)了動(dòng)態(tài)調(diào)配問題的求解。

結(jié)合實(shí)驗(yàn)結(jié)果可得,提出的調(diào)度方法有效縮短了天然氣管網(wǎng)搶修任務(wù)的搶修響應(yīng)時(shí)間并提高了調(diào)度方案的求解效率,縮減了檢修單元的工作空白時(shí)間,平衡了檢修單元的工作負(fù)荷,從而科學(xué)優(yōu)化了檢修單元的工作負(fù)荷管理。天然氣管網(wǎng)巡檢搶修協(xié)同動(dòng)態(tài)優(yōu)化調(diào)配策略可為解決多階段、多類型任務(wù)、存在不確性時(shí)間的實(shí)時(shí)動(dòng)態(tài)應(yīng)急搶修調(diào)度問題的建模和求解提供參考,為天然氣背景的搶修調(diào)度管理提供理論分析支持,從而有效提高天然氣管網(wǎng)的安全保障能力。

研究內(nèi)容不僅可以解決同一時(shí)刻發(fā)生的單搶修任務(wù)的調(diào)度,也可以應(yīng)對(duì)同一時(shí)刻發(fā)生多起搶修任務(wù)的情況。但是因?yàn)闅v史數(shù)據(jù)中同一時(shí)刻發(fā)生多搶修任務(wù)的情況極少,故難以驗(yàn)證模型在多任務(wù)時(shí)的性能,因此需要持續(xù)獲取有效數(shù)據(jù)用模型進(jìn)一步驗(yàn)證并行多搶修任務(wù)情況,從而優(yōu)化多任務(wù)同時(shí)發(fā)生的巡檢搶修一體化協(xié)同調(diào)配策略作為后續(xù)研究方向之一。模型中搶修單元的分類主要根據(jù)獲取數(shù)據(jù)關(guān)注搶修單元載具的不同,還可以通過更深的調(diào)研,把搶修單元的搶修運(yùn)行工年齡和搶修任務(wù)工作經(jīng)驗(yàn)等特征加入模型的考慮中,精細(xì)化搶修單元類型與搶修調(diào)度之間的影響關(guān)系。