巡檢線路的排班模型

費荔枝++呂恒民

【摘要】該問題屬于最佳推銷員回路問題，文中首先對化工廠的檢測點巡檢進行概述，然后分析化工廠的巡檢現(xiàn)狀，并運用節(jié)約算法、啟發(fā)算法對測站巡檢線路進行優(yōu)化，最后提出最優(yōu)方案。

【關(guān)鍵詞】最佳推銷員回路問題；賦權(quán)圖；近似算法；均衡度

【基金項目】吉安職業(yè)技術(shù)學(xué)院校級科研項目（16JY137）資助

【中圖分類號】TQ086.2；TP274.4 【文獻標(biāo)識碼】B 【文章編號】2095-3089（2017）17-0292-02

一、問題重述

某化工廠有26個點需要進行巡檢以保證正常生產(chǎn)，每個點每次巡檢需要一名工人，巡檢工人的巡檢起始地點在巡檢調(diào)度中心（XJ0022），工人可以按固定時間上班，也可以錯時上班，在調(diào)度中心得到巡檢任務(wù)后開始巡檢。巡檢線路是指從巡檢調(diào)度中心（XJ0022）出發(fā)，走遍所有的點，再回到巡檢調(diào)度中心的路線。

（1）如果采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。

（2）如果巡檢人員每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘，在中午12時和下午6時左右需要進餐一次，每次進餐時間為30分鐘，仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。

（3）如果采用錯時上班，重新討論問題1和問題2，試分析錯時上班是否更節(jié)省人力。

二、問題分析

本題給出了某工廠巡檢線路圖及各個點的巡檢周期、巡檢耗時、兩點之間的連通關(guān)系、行走所需時間，要求的是在不同的條件下，巡檢排班的線路及巡檢人數(shù)、時間表。將每個巡檢點看作一個圖的頂點，各巡檢點之間的線路看作此圖對應(yīng)頂點間的邊，各條線路行走所需要時間看作對應(yīng)邊上的權(quán)，所給線路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點巡檢調(diào)度中心（XJ0022）出發(fā)，使所有頂點都能按要求完成巡檢，使得總權(quán)（路程或時間）最小。

本題是旅行售貨員問題的延伸-多旅行售貨員問題。本題所求的分班巡視的最佳路線，也就是m條經(jīng)過同一點并覆蓋所有其他頂點又使邊權(quán)之和達到最小的閉鏈（閉跡）。

眾所周知，旅行售貨員問題屬于NP完全問題，即求解沒有多項式時間算法。顯然本問題更應(yīng)屬于NP完全問題。有鑒于此，一定要針對問題的實際特點尋找簡便方法，想找到解決此類問題的一般方法是不現(xiàn)實的，對于規(guī)模較大的問題可使用近似算法來求得近似最優(yōu)解。

三、模型假設(shè)

1.巡檢人員行走所用時間總是一定，忽略天氣等因素的影響。

2.各個點巡檢周期、兩點之間的連通關(guān)系總是一定，忽略故障等其他因素的影響；

3.巡視當(dāng)中，各巡檢點的巡檢耗時一定，不會出現(xiàn)特殊情況而延誤時間；

4.每個點每次巡檢只有一名工人；

四、符號說明

w（i，j）：任意兩點i，j間的間距；ei：各點的巡檢耗時，即點權(quán)；V：各巡檢點構(gòu)成的集合。

五、模型建立與求解

巡視線路圖中，每個巡檢點看作圖中的一個節(jié)點，各巡檢點之間的線路看作此圖對應(yīng)頂點間的邊，各條線路行走所需要時間看作對應(yīng)邊上的權(quán)，所給線路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點巡檢調(diào)度中心（XJ0022）出發(fā)，使所有頂點都能按要求完成巡檢，此即最佳推銷員回路問題。

此問題包含兩方面：第一、對頂點分組；第二、在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題。由于單個推銷員的最佳推銷員回路問題不存在多項式時間內(nèi)的精確算法，故多個推銷員的問題也不存在多項式時間內(nèi)的精確算法。我們需要去尋求一種較合理的劃分準(zhǔn)則，對圖（1）進行初步劃分后，分成巡查圈I、巡查圈I、巡查圈I所示的三個組

經(jīng)過分析我們得出每班至少需要四名工人尋遍所有的巡查點。四名工人分別記為A、B、C、D。工人A負(fù)責(zé)巡查圈I，工人B、C負(fù)責(zé)巡查圈II，工人D負(fù)責(zé)巡查圈III。為了耗費的人力資源盡可能的少，并且每名工人在同一時間段內(nèi)工作量盡可能均衡。工人A按路線一進行巡查。工人B、工人C分別按路線二、三進行第一次巡查，工人D按路線四進行第一次巡查。第一次四名工人巡檢路線如下。

經(jīng)過第一次巡查后，我們對巡查路線作進一步的優(yōu)化（如下表），四名工人按照優(yōu)化后的巡檢路線進行巡檢。工人A按巡邏圈Ⅰ進行巡檢（循環(huán)進行，直到換班）；工人B、C按照巡邏圈Ⅱ（3-23路線）交替相向而行進行巡檢；工人D按照巡邏圈Ⅲ進行巡檢（循環(huán)進行，直到換班）。

因為該組檢測路線的每個檢測周期內(nèi)有效的每人檢測的均衡度

所以這種路線的周期內(nèi)的每人檢測的均衡性較好。

根據(jù)巡檢路線并考慮巡檢工人在一時間段內(nèi)的工作量盡量平衡，巡檢時間表如下：

問題二：頂替輪班

由于巡查人員每巡查2小時左右需要休息一次，8小時工作時間內(nèi)共計需要休息3次，每個點大約檢查15次，休息時間是15到30分鐘。

在考慮到工廠巡查的不間斷性，工人要在中午12點和下午6點進餐，因此，在原有4個人的基礎(chǔ)之上，增加一人，實行頂替輪班的方法。每次一個人進餐，另一人頂替進餐者進行巡檢，進餐者用完餐后立刻返回其崗位，讓頂替者到另一路線頂替其他工人進餐，以此類推，該頂替者共計要連續(xù)工作0.5×4=2小時，并且當(dāng)其他工人休息時頂班工作，時間為15×4=1小時，所以頂班工人實際工作時間為3小時。綜合以上分析，在保證工廠巡檢正常進行，第一班0：00-8：00需要工人4人，第二班8：00-16：00需要工人5人，第三班16：00-24：00需要工人5人。如果采用每天三班倒，共計需要14人。其巡查的時間表如下：

問題三：采用錯時上班

由于問題一不考慮巡檢人員的休息時間，也不考慮工人的進餐時間，所以錯時上班對是否節(jié)省時間沒有太大影響。工人每天工作8小時左右，每班需要4人，一天依舊需要12名工人巡檢。

由于問題二中巡檢人員每巡檢2小時左右需要休息一次，在中午12：00和下午6：00需要進餐一次，12：00與下午6：00相距6小時，并且采取錯時上班制，在8：00-16：00和16：00-24：00的兩次巡檢中，只需一名工人頂替這兩班工人的休息和進餐時間，所以第一班0：00-8：00需要工人四名，第二班和第三班8：00-24：00需要工人9名，共計一天需要13人，所以采用錯時上班可以節(jié)省人力。

優(yōu)缺點分析：

優(yōu)點：

1.本文提出的分組準(zhǔn)則簡便易行，可操作性強，且可逐步調(diào)整使分組達到均衡；

2.用均衡度的概念定量的刻畫了分組的均衡性；

3.在用近似算法求近似最佳推銷員回路時，采取了三種不同的方法產(chǎn)生初始圈，使得算法比較完善，得到了誤差很小的近似最優(yōu)解；

缺點

1.時間精確度存在一定誤差。

參考文獻

[1]趙靜，數(shù)學(xué)建模與數(shù)學(xué)實驗（第三版），北京：高等教育出版社，2008.

[2]胡運權(quán)，運籌學(xué)基礎(chǔ)及應(yīng)用（第三版），哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1998.

[3]孫惠泉，圖論及其應(yīng)用，北京：科學(xué)出版社，2004.

作者簡介：費荔枝（1982—），女，碩士，中級.研究方向：生物數(shù)學(xué)。

通訊作者：E-mail：lvhengmin2005@163.com