陳輝

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院， 安徽蕪湖214002)

引言

巡檢線路的優(yōu)化設(shè)計(jì)在電力設(shè)備維護(hù)、社區(qū)安全巡視和車(chē)間設(shè)備檢測(cè)等生產(chǎn)和生活的各個(gè)環(huán)節(jié)都有著重要的應(yīng)用[1-7]，近年來(lái)，結(jié)合無(wú)人機(jī)和智能化手持設(shè)備等現(xiàn)代化技術(shù)手段的使用，大批學(xué)者展開(kāi)了相關(guān)領(lǐng)域的研究。郭國(guó)法等在巡檢地點(diǎn)及巡檢人員經(jīng)過(guò)的路線上安裝RFID閱讀器，用于車(chē)間巡檢人員的跟蹤定位[8]；湯堅(jiān)等提出了利用多旋翼無(wú)人機(jī)RTK差分定位技術(shù)等無(wú)人機(jī)航測(cè)系統(tǒng)技術(shù)，研發(fā)了面向電網(wǎng)巡檢的無(wú)人機(jī)智能操作系統(tǒng)及控制終端[9]；胡萬(wàn)才介紹了一種基于計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，實(shí)現(xiàn)對(duì)機(jī)務(wù)段設(shè)備的巡檢管理[10]。新技術(shù)設(shè)備和檢測(cè)方法不斷引入的同時(shí)，路徑優(yōu)化方面的研究也在不斷推進(jìn)。熊鵬文等提出了一種基于改進(jìn)概率地圖法的電力線巡檢飛行機(jī)器人路徑規(guī)劃方法[11]；柳長(zhǎng)安等提出了一種適用于核電站巡檢與應(yīng)急機(jī)器人的有效局部路徑優(yōu)化方法[12]；還有部分學(xué)者將巡檢業(yè)務(wù)抽象為VRP問(wèn)題(車(chē)輛路徑問(wèn)題)進(jìn)行求解，以總耗費(fèi)時(shí)間和巡檢車(chē)輛數(shù)量為優(yōu)化目標(biāo)，利用蟻群算法和遺傳算法等智能算法得到最優(yōu)巡檢方案[13-16]。2017年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題考察了某化工廠有26個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，每個(gè)點(diǎn)每次巡檢需要一名工人，工人可以按固定時(shí)間上班，也可以錯(cuò)時(shí)上班[17]。本文提出在保證正常安全生產(chǎn)的前提下，這種巡檢線路的優(yōu)化問(wèn)題與VRP問(wèn)題并不等價(jià)，建立了確定巡檢人數(shù)和優(yōu)化巡檢路線的數(shù)學(xué)模型，通過(guò)求解模型得到了車(chē)間生產(chǎn)安全巡檢的完整解決方案，使得所有點(diǎn)都能按要求完成巡檢，并且耗費(fèi)的人力資源盡可能少，同時(shí)還應(yīng)考慮每名工人在一時(shí)間段內(nèi)的工作量盡量平衡。本文求解檢路線設(shè)計(jì)和值班安排的方法、策略在邊境線執(zhí)行巡邏問(wèn)題、醫(yī)院病房護(hù)理巡視等場(chǎng)景下都可以直接應(yīng)用。

1 問(wèn)題分析

通常，某生產(chǎn)車(chē)間有若干個(gè)關(guān)鍵點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，每個(gè)點(diǎn)每次巡檢需要一名檢測(cè)工人耗費(fèi)一定的檢測(cè)時(shí)間，而且每個(gè)點(diǎn)必須在一個(gè)確定的時(shí)間周期內(nèi)重復(fù)檢測(cè)。檢測(cè)工人按三班倒上班，保障機(jī)器每天24小時(shí)不間斷地安全運(yùn)行，每天可以固定時(shí)間上班，也可以錯(cuò)時(shí)上班，在調(diào)度中心得到巡檢任務(wù)后開(kāi)始巡檢。此時(shí)，需要安排巡檢人數(shù)和巡檢路線，使得所有點(diǎn)都能在每個(gè)巡檢周期內(nèi)得到檢測(cè)，并且耗費(fèi)的人力資源盡可能少，同時(shí)還應(yīng)考慮每名工人在一時(shí)間段內(nèi)(如一周或一月等)的工作量盡量平衡。

記集合V={Vi|i=1,2,…n}為巡檢點(diǎn)。G(V,E)為巡檢路線連通圖，其中E?V×V為連通圖的邊。ti為檢測(cè)第i個(gè)巡檢點(diǎn)的耗時(shí)，zi為第i個(gè)巡檢點(diǎn)的巡檢周期，即巡檢點(diǎn)Vi必須在小于等于zi的時(shí)間間隔內(nèi)被檢測(cè)一次，以保證正常生產(chǎn)安全。一個(gè)典型的26個(gè)巡檢點(diǎn)任務(wù)采用每天三班倒，具體情況如圖1所示，同時(shí)需要兼顧人力資源使用量、工作量的平衡、人員的休息和用餐以及錯(cuò)時(shí)上班等因素[17]。

為滿足巡檢任務(wù)要求，對(duì)應(yīng)的路線規(guī)劃和人員值班安排應(yīng)滿足如下條件。

(1)巡檢點(diǎn)必須嚴(yán)格地滿足全天24小時(shí)在巡檢周期內(nèi)得到檢測(cè)，包括交接班過(guò)程。

(2)巡檢人員在每班開(kāi)始工作時(shí)在巡檢調(diào)度中心領(lǐng)取任務(wù)，再到指定路線巡檢，巡檢過(guò)程中不需要再回到調(diào)度中心。

(3)工作時(shí)間包括趕往指定巡檢路線的行走時(shí)間，上、下班時(shí)間以進(jìn)入、離開(kāi)調(diào)度中心為準(zhǔn)。

(4)巡檢人員如在巡檢過(guò)程中發(fā)現(xiàn)巡檢點(diǎn)出現(xiàn)異常，不需要回到調(diào)度中心匯報(bào)(可以通過(guò)無(wú)線通訊)，按既定路線繼續(xù)巡檢。

圖1 巡檢連通圖

這種巡檢線路排班的規(guī)劃和車(chē)輛路徑問(wèn)題(Vehicle Routing Problem，VRP)有類似之處[18]，但并不完全相同。主要差別在于車(chē)輛路徑問(wèn)題是通過(guò)規(guī)劃行車(chē)路線，由配送中心向各站點(diǎn)提供貨物，使得客戶的需求得到滿足的同時(shí)，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的[19]，問(wèn)題求解的結(jié)果為單次行程的路徑。巡檢線路排班的規(guī)劃還需要兼顧多次巡檢圈次、各個(gè)班次的銜接問(wèn)題，以及值班人員的休息和工作量平衡。這包含兩方面的內(nèi)容，路徑的規(guī)劃和人員值班的時(shí)間安排。

2 巡檢路線的規(guī)劃

巡檢路線規(guī)劃思路是將巡檢聯(lián)通圖分解為若干TSP問(wèn)題，每條TSP通路由一個(gè)值班人員巡檢，這就要求每條通路上所有巡檢點(diǎn)的巡檢周期不能大于這個(gè)值班人員單次巡檢的工作時(shí)間。通過(guò)0-1指派來(lái)安排某檢測(cè)點(diǎn)由經(jīng)過(guò)該點(diǎn)的哪位工作人員負(fù)責(zé)檢測(cè)。

2.1 巡檢路線分析

記巡檢人員為RYi，i=1,2,…,m，

i=1,2,…,m，j=1,2,…,n

i=1,2,…,m，(Vq,Vh)?E

每個(gè)巡檢人員安排的巡檢任務(wù)時(shí)間為SJi，包括路程時(shí)間和所負(fù)責(zé)的檢測(cè)點(diǎn)檢測(cè)時(shí)間，則

(1)

其中，tj為檢測(cè)第j個(gè)巡檢點(diǎn)的耗時(shí)，dqh為從第q個(gè)巡檢點(diǎn)到第h個(gè)巡檢點(diǎn)所用的時(shí)間。

對(duì)于每一個(gè)指定的巡檢人員RYi，通過(guò)Xiqh指定的邊應(yīng)該構(gòu)成一個(gè)回路，這個(gè)回路上的每一點(diǎn)的出度和入度相同，

(Vj,Vh)?E，(Vk,Vj)?E

(2)

uij-uih+nixijh≤ni-1，(Vj,Vh)?E

(3)

其中，ni為人員i走過(guò)的路徑長(zhǎng)度。

2.2 巡檢路線約束條件

巡檢人員RYi路線上需要其檢測(cè)站點(diǎn)的檢測(cè)周期不能大于路線時(shí)間，否則無(wú)法及時(shí)檢測(cè)：

SJiYij≤zjYij，i=1,2,…,m

j=1,2,…,n

(4)

其中，zj為第j個(gè)巡檢點(diǎn)的巡檢周期。

每一個(gè)檢測(cè)站都需要有人員負(fù)責(zé)檢修：

(5)

RYi負(fù)責(zé)檢修的站點(diǎn)必須在其經(jīng)過(guò)的路線上：

(Vj,Vh)?E

(6)

通過(guò)上述分析，在目標(biāo)函數(shù)為每個(gè)巡檢路線的工作時(shí)間盡量均衡情況下，由(1)式～(6)式得到巡檢路線搜索模型，

min maxSJi

(7)

S.T.

i=1,2,…,m，(Vj,Vh)?E

(Vj,Vh)?E，(Vk,Vj)?E

uij-uih+nixijh≤ni-1，(Vj,Vh)?E

SJiYij≤zjYij，i=1,2,…,m，j=1,2,…,n

2.3 巡檢路線求解

上述模型可以在Lingo中實(shí)現(xiàn)[20]。針對(duì)文獻(xiàn)[17]中的問(wèn)題，在使用計(jì)算機(jī)進(jìn)行求解時(shí)，還可以根據(jù)實(shí)際情況進(jìn)行手工干預(yù)。如可以將圖1中的22→21→4→3→2→1→2→19→20→22指定給人員1，23→24→9→25→17→8→6→3→2→4→23指定給人員2等。經(jīng)過(guò)若干次調(diào)試，可以得到巡檢路線安排，如圖2所示。具體參數(shù)見(jiàn)表1，表1中路線標(biāo)示為陰影的部分代表經(jīng)過(guò)該檢測(cè)點(diǎn)而不進(jìn)行檢測(cè)。

圖2 巡檢路線示意圖

表1 (單位：分鐘)

路線223→24→9→25→17→8→6→3→2→4→23實(shí)際耗時(shí)時(shí)間31224321010201312304035周期3535341203550

路線325→17→8→6→10→12→15→26→25實(shí)際耗時(shí)時(shí)間0121320506220623035周期353535480

路線411→15→18→16→13→11實(shí)際耗時(shí)時(shí)間3722233252031周期3535353580

路線56→14→6→5→7→6→10→6實(shí)際耗時(shí)時(shí)間31310222240525032周期35353572080120

由表1可知，每班次安排5人即可完成所有26個(gè)檢測(cè)點(diǎn)的巡檢任務(wù)。在5條路線中，有兩條路線的巡檢時(shí)間剛好為35分鐘，一條為34分鐘，其余分別為32分鐘和31分鐘，由于所有的路程和巡檢總時(shí)間為145分鐘，這種路線安排效率較高。

3 巡檢時(shí)間安排

3.1 固定上班時(shí)間巡檢時(shí)間安排

如果采用每天三班倒按固定時(shí)間上班，所有工人嚴(yán)格執(zhí)行8∶00早班開(kāi)始從調(diào)度中心出發(fā)，趕赴各巡檢路線開(kāi)始值班。根據(jù)前文的分析，每班安排5人即可滿足巡檢要求。為使得耗費(fèi)的人力資源盡可能少，需要選擇每條巡檢路線上距離調(diào)度中心處路徑最短的起止點(diǎn)，讓上一班次人員繼續(xù)巡檢(換班人員正在趕去的路上)產(chǎn)生的加班時(shí)間盡可能小。每個(gè)班次8小時(shí)，合計(jì)480分鐘，每條路線巡檢周期為35分鐘，在固定上班情況下(不能提前上班)，每班工作人員必須巡檢滿14次直到接班人員達(dá)到指定位置。具體情況見(jiàn)表2。如巡檢路線1，就近選擇22檢測(cè)點(diǎn)為路線起始點(diǎn)，490分鐘后，檢測(cè)完14次，在22∶00下班，加班時(shí)間為10分鐘。此時(shí)，每次換班時(shí)，所有檢測(cè)點(diǎn)提前了10分鐘檢測(cè)。

表2 固定上班時(shí)間巡檢時(shí)間安排

注：有效工作時(shí)間去除了巡檢過(guò)程中等待的時(shí)間。

3.2 固定上班時(shí)間輪班安排

不同線路工作人員的加班時(shí)間不同。為保證每個(gè)人員工作時(shí)間盡量均衡，需要在一定的周期(這里取一周7天)內(nèi)安排在不同的路線上輪班，第一天如果在工作加班時(shí)間較長(zhǎng)的路線4上巡檢，第二天可以調(diào)換到工作時(shí)間較短的路線5上。因?yàn)榘垂潭〞r(shí)間上班，三班倒的早、中、晚每班情形相同，只需按同一方案輪班。為給出優(yōu)化的輪班方案，建立指派問(wèn)題的優(yōu)化模型。記

RYi，i=1,2,…,5為巡檢人員。

DAYj，j=1,2,…,7為一周的各天。

Wk，k=1,2,…,5為5條不同的路線。

Tk，第k條路線上的工作時(shí)間，見(jiàn)表3。

則，每個(gè)人員在一周工作的時(shí)間總長(zhǎng)為

(9)

每人每天安排且只能安排一條線路

(10)

每天每個(gè)線路上安排且只能安排一人

(11)

目標(biāo)是使得SCi，i=1,2,…,5盡可能均勻。由(10)式和(11)式得到輪班安排優(yōu)化模型：

minVar(SCi)

(12)

s.t.

計(jì)算所得的排班結(jié)果見(jiàn)表3。

表3 固定上班時(shí)間的人員路線分配表

如在周一1-5路線上安排編號(hào)分別為4、3、5、1、2的工作人員，其余類推，則人員一周的工作時(shí)間分別為3466分鐘、3466分鐘、3467分鐘、3467分鐘和3466分鐘，因此每個(gè)人員工作時(shí)間得到了較大程度的均衡。每天平均工作時(shí)間為8.2524小時(shí)或8.2548小時(shí)。每天的早、中、晚班都可以類似安排。如果考慮均衡的是有效工作時(shí)間，可以類似得到人員一周的有效工作時(shí)間均衡為2963.78分鐘、2978.00分鐘、2945.06分鐘、2982.38分鐘和2967.14分鐘。

3.3 錯(cuò)時(shí)上班時(shí)間巡檢時(shí)間安排

按固定時(shí)間上班，下一班次接班人員不能提前上班，每個(gè)路線上的人員必須在一個(gè)班次內(nèi)巡檢完成14個(gè)周期，導(dǎo)致每條線路上的所有檢測(cè)點(diǎn)在換班時(shí)被提前了10分鐘檢測(cè)。這種“浪費(fèi)”是由于每個(gè)班次的上班時(shí)間8小時(shí)折合480分鐘不能被35分鐘整除導(dǎo)致的。計(jì)算出每天時(shí)長(zhǎng)24小時(shí)和35分鐘的最小公倍數(shù)為L(zhǎng)CM(24×60,35)=10 080分鐘，折合10 080/60=168小時(shí)，合計(jì)168/24=7天。這意味著，一周的時(shí)間段長(zhǎng)度是路線巡檢周期35分鐘的整數(shù)倍，共計(jì)288個(gè)圈次。如果沒(méi)有固定上班時(shí)間，可以事先在一周的時(shí)間段內(nèi)固定這288個(gè)圈次的檢測(cè)時(shí)間節(jié)點(diǎn)，按照錯(cuò)時(shí)上班，每個(gè)路線上的人員可以提前上班到達(dá)檢測(cè)路線，嚴(yán)格按巡檢時(shí)間節(jié)點(diǎn)到達(dá)巡檢路線，這樣可以避免提前10分鐘檢測(cè)造成的“浪費(fèi)”?？紤]到早、中、晚班次人員工作時(shí)間需要均衡，將這288個(gè)圈次安排在一周的時(shí)間內(nèi)(表4)。

表4 錯(cuò)時(shí)上班每周班次巡檢圈數(shù)安排

一周內(nèi)每條路線在每個(gè)班次開(kāi)始檢測(cè)的時(shí)間見(jiàn)表5。

表5 錯(cuò)時(shí)上班每班次所有路線開(kāi)始檢測(cè)的時(shí)間

除去從調(diào)度中心走到各路線起始點(diǎn)的時(shí)間，得到各路線在各班次的提前上班時(shí)間。再根據(jù)各路線的實(shí)際工作時(shí)間，可以計(jì)算出各班次的下班時(shí)間(表6)。根據(jù)這種上下班安排，每周可以節(jié)約總的工作總量為35×6×5=1050分鐘。

表6 錯(cuò)時(shí)上班每天不同班次所有路線上的人員上下班時(shí)間表(路線1)

4 結(jié)束語(yǔ)

本文主要解決了對(duì)工廠巡檢點(diǎn)進(jìn)行及時(shí)巡檢的問(wèn)題，同時(shí)兼顧人力資源使用量、工作量的平衡、人員的休息等因素。建立并求解路線搜索的數(shù)學(xué)模型，設(shè)計(jì)了巡檢路線，每條路線的工作人員工作時(shí)長(zhǎng)不超過(guò)巡檢點(diǎn)的巡檢周期。通過(guò)求解指派問(wèn)題模型還解決了工作量均衡問(wèn)題。最后指出，錯(cuò)時(shí)上班的關(guān)鍵作用在于，在三班倒換班交接時(shí)，可以錯(cuò)開(kāi)各路線巡檢周期的重疊，這是固定時(shí)間上班時(shí)無(wú)法避免的，同時(shí)計(jì)算了錯(cuò)時(shí)上班每周節(jié)約的工作總量。這些結(jié)果在邊境線執(zhí)行巡邏問(wèn)題、醫(yī)院病房護(hù)理巡視問(wèn)題、通訊網(wǎng)絡(luò)設(shè)施檢測(cè)等場(chǎng)景下都有應(yīng)用參考價(jià)值。

[1] 趙娟平.基于GPS的電力巡檢系統(tǒng)[J].微計(jì)算機(jī)信息,2007,23(1):252-253.

[2] 毛豐江,李正中,路勇.基于RFID數(shù)據(jù)終端的智能化小區(qū)物業(yè)巡檢系統(tǒng)[J].微計(jì)算機(jī)信息,2006(14):212-214.

[3] 顧海紅.大型港口機(jī)械巡檢周期的確定[J].水運(yùn)工程,2007(8):52-55.

[4] 張國(guó)立.海底管道巡檢船的設(shè)計(jì)和功能配置[J].中國(guó)造船,2016,57(1):54-60.

[5] 石遠(yuǎn)鵬,姜建軍,鄭德宇,等.輸電線路巡檢的路徑規(guī)劃與建模[J].應(yīng)用科技,2011,38(11):18-21.

[6] 高振豪,蘇貴影,李彥華,等.工作要素在裝配線中分配與其平衡率的研究[J].四川理工學(xué)院學(xué)報(bào):自然科學(xué)版,2017,30(6):89-92.

[7] 張民悅,連愛(ài)玲.修理設(shè)備可修且部件修復(fù)非新的溫貯備可修系統(tǒng)[J].四川理工學(xué)院學(xué)報(bào):自然科學(xué)版,2017,30(4):74-80.

[8] 郭國(guó)法,盧運(yùn)栓,張開(kāi)生.適用于車(chē)間巡檢定位的改進(jìn)RFID定位算法[J].實(shí)驗(yàn)室研究與探索,2016,35(12):29-33.

[9] 湯堅(jiān),楊驥,宮煦利.面向電網(wǎng)巡檢的多旋翼無(wú)人機(jī)航測(cè)系統(tǒng)關(guān)鍵技術(shù)研究及應(yīng)用[J].測(cè)繪通報(bào),2017(5):67-70.

[10] 胡萬(wàn)才.設(shè)備智能巡檢管理系統(tǒng)設(shè)計(jì)與應(yīng)用[J].鐵道機(jī)車(chē)車(chē)輛,2009,29(5):63-65.

[11] 熊鵬文,宋愛(ài)國(guó),東輝.基于效率與安全機(jī)制的核電站巡檢與應(yīng)急機(jī)器人的局部路徑優(yōu)化方法[J].機(jī)器人,2015,37(2):196-203.

[12] 柳長(zhǎng)安,劉春陽(yáng).電力線巡檢飛行機(jī)器人路徑規(guī)劃方法[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2010(1):117-120.

[13] 劉志碩,申金升,關(guān)偉.車(chē)輛路徑問(wèn)題的混合蟻群算法設(shè)計(jì)與實(shí)現(xiàn)[J].管理科學(xué)學(xué)報(bào),2007(3):15-22.

[14] 尹曉峰,杜艷萍.車(chē)輛路徑問(wèn)題的蟻群算法研究[J].太原科技大學(xué)學(xué)報(bào),2005,26(4):279-283.

[15] 何冰,季建華,劉新平,等.基于遺傳算法的城市輸電網(wǎng)絡(luò)巡視路徑優(yōu)化選擇問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究,2013,30(8):2276-2279.

[16] 李銘鈞,甘團(tuán)杰,賴奎,等.考慮桿塔風(fēng)險(xiǎn)概率的輸電線路巡檢路徑優(yōu)化方法[J].電網(wǎng)與清潔能源,2016,32(10):61-67.

[17] 全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽2017年賽題[DB/OL].http://mcm.blyun.com/front/detailTopic.

[18] DANTIZIG G,RINSER J.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[19] PAOLO T,DANIELE V.The vehicle routing problem[M].philadephia:Society for Industrial and Applied Mathematics,2002.

[20] 謝金星,薛毅.優(yōu)化建模與LINDO LINGO軟件[M].北京:清華大學(xué)出版社,2005.