巡檢線路的排班模型

費荔枝++呂恒民

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

【關鍵詞】最佳推銷員回路問題；賦權圖；近似算法；均衡度

【基金項目】吉安職業技術學院校級科研項目（16JY137）資助

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

一、問題重述

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

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

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

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

二、問題分析

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

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

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

三、模型假設

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

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

3.巡視當中，各巡檢點的巡檢耗時一定，不會出現特殊情況而延誤時間；

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

四、符號說明

w（i，j）：任意兩點i，j間的間距；ei：各點的巡檢耗時，即點權；V：各巡檢點構成的集合。

五、模型建立與求解

巡視線路圖中，每個巡檢點看作圖中的一個節點，各巡檢點之間的線路看作此圖對應頂點間的邊，各條線路行走所需要時間看作對應邊上的權，所給線路網就轉化為加權網絡圖，問題就轉化圖論中一類稱之為旅行售貨員問題，即在給定的加權網絡圖中尋找從給定點巡檢調度中心（XJ0022）出發，使所有頂點都能按要求完成巡檢，此即最佳推銷員回路問題。

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

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

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

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

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

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

問題二：頂替輪班

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

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

問題三：采用錯時上班

由于問題一不考慮巡檢人員的休息時間，也不考慮工人的進餐時間，所以錯時上班對是否節省時間沒有太大影響。工人每天工作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人，所以采用錯時上班可以節省人力。

優缺點分析：

優點：

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

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

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

缺點

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

參考文獻

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

[2]胡運權，運籌學基礎及應用（第三版），哈爾濱：哈爾濱工業大學出版社，1998.

[3]孫惠泉，圖論及其應用，北京：科學出版社，2004.

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

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