巡檢路線排班優化研究

董 慧，李國芳，李慧娟，楊慧琳

(安徽工業經濟職業技術學院，合肥 230001)

1 問題提出

2017年全國大學生數學建模競賽D題探討了在節省人力資源耗費和實現工作量平衡的前提下如何安排巡檢人數及路線，該題在基本巡檢要求下需解決三個問題，即分別給出在固定上班時間、錯峰上班時間下的巡檢人數、路線和時間表，并分析何種方式更節省人力，具體要求可見全國大學生數學建模競賽官網。

2 問題分析

2.1 問題1分析

三班倒固定上班時間，不防設為0:00—8:00、8:00—16:00和16:00—24:00。

巡檢線路圖的設計要考慮巡檢人數、路線、總時間等因素。通過分析，首先確定每班至少4人，然后通過Kruskal算法構建最小生成樹，再將圖分為若干子圖，進而構建優化模型，給出巡檢路線及時間表。

2.2 問題2分析

0:00—8:00不需要進餐，結合問題1的結論，此時只需考慮是否能滿足休息時間的要求即可。8:00—16:00、16:00—24:00需要進餐，但情況類似，只選其一討論。所有點按要求完成巡檢至少需要4人同時在崗，因要有進餐時間，每班至少5人。按每班5人、6人依次討論給出巡檢路線和時間表。通過是否滿足休息、進餐時間及人數多少等因素評價每班5人、6人的優劣。

2.3 問題3分析

由問題2知，每班5人比6人進餐時間長，若想節省人力應通過錯時上班，盡量安排每班5人，同時解決進餐時間長的問題。利用上下班時間點避開就餐時間段，對不同錯時上班的情況重新對問題2進行討論。

3 模型假設

A.所有測試所得數據有效。

B.不考慮工人停頓、缺席、請假以及不同工人行走快慢等情況。

C.假設剛到上班時間工人即刻工作。

D.假設巡檢點不會出現設備故障。

4 模型建立與求解

4.1 問題1的建模與求解

4.1.1 數據預處理

根據巡檢點周期表，巡檢周期為35 min的有18個點，超過35 min的僅8個點。以35 min為一個周期T來討論，超過35 min的8個點暫不參與巡檢，最后單獨討論。重新處理巡檢圖，得圖1。

圖1

4.1.2 確定每班人數

4.1.3 巡檢線路和時間表

三個班情況一樣，只討論0:00—8:00班的情況。

將圖1抽象為賦權連通圖G(V,E,ω)，其中V為巡檢點集，E為邊集，ω={ωij},ωij表示第i個巡檢點和第j個巡檢點的最短耗時。此外，給點賦權，令υ={vi}，vi為第i個巡檢點的周期。

1)找出最小生成樹

利用Kruskal算法，找出圖的最小生成樹(見圖2)。算法為：①選e1∈E(G)，使e1是邊權值最小的邊。②若e1,e2,…,ei已選好，則從E(G)-{e1,e2,…,ei}中選取ei+1，使得：ⅰ){e1,e2,…,ei,ei+1}中無圈；ⅱ)ei+1是E(G)-{e1,e2,…,ei}中邊權值最小的邊；ⅲ)直到選得e|V|-1為止。

圖2

圖3

2)分解圖G

根據最小生成樹(圖2)將圖G分成4塊(見圖3)，分解原則為：①分解點為V22(V22表示第22個巡檢點)或盡量接近V22。②分解后的各子圖盡量為連通圖。③分解所得的4個子圖頂點周期和盡可能小于35。④生成的子圖容易形成圈或接近圈。

3)構建優化模型

綜上，建立優化模型(1)：

利用Dijkstra算法給出巡檢線路，經過適當調整可得到4組3個周期的巡檢路線表(見表1)、巡檢時間表(見表2)。

表1 巡檢路線表

表2 巡檢時間表

4.2問題2的建模與求解

由問題1知，每個人在一周期巡檢的時間均未超過35 min，記未達到的部分為一個周期節約的時間，統計前4個周期節約的時間列表如下：

人員前三個周期節約的總時間(105 min)前四個周期節約的總時間(140 min)甲67乙46丙33丁1010

甲乙丁工作4個周期可騰出5 min休息，但丙不能，即丙2 h無法進行休息，為使所有巡檢人員在2 h都能至少休息5 min，只有通過增加巡檢人數實現。

4.2.1 0:00—8:00班情況

此班無需進餐，只需增加1人即可實現。具體可參考4.2.2建模，不再贅述。

4.2.2 8:00—16:00班情況

由于在12點與18點左右進餐，此處只討論8:00—16:00情況。所有點都能按要求完成巡檢，至少要有4人同時在崗，因而要保證中午12時左右能輪換進餐，每班至少需要5人。按輪流進餐方式依次討論5人、6人的情況。

4.2.2.1 每班5人的情況

由于進餐時間為30 min，在問題1的基礎上增加1人后，每人每次巡檢1輪時間降低且在30 min左右，為方便討論，工人在巡檢1個周期結束再去進餐。即：當有人去進餐時，其余4人巡檢結束或休息結束，可以按問題1的路線進行巡檢，將進餐工人的工作分擔掉。

類似問題1的方法，首先將圖G分成5塊(分解原則同4.1.3)，然后構建優化模型(2)：

其中，ω(Ck)為分塊后第k組的回路路程，a為均衡度，Vi為第i個子圖的點集。

利用Dijkstra算法給出巡檢線路，經過適當調整得到表3-4。5人工作時，每次1人去進餐，11:00—13:30進餐，共2.5h。

表3 巡檢路線表

表4 巡檢時間表

4.2.2.2 每班6人的情況

類似4.2.2.1的方式，可得出每班6人時的巡檢路線圖和時間表，見表5～6。6人工作時，分3組輪流進餐，每次兩人，11:30—13:00進餐，共1.5 h。

表5 巡檢路線表

表6 巡檢時間表

4.2.2.3 每班5人、6人情況評價

每班5人時，人數少，但進餐時間長，且最后1人進餐已13:00。每班6人時，進餐時間短，第1人、最后1人開始進餐時為11:30、12:30。從人性化角度考慮，建議每班6人。

4.3 問題3的求解

4.3.1 錯時上班時，針對問題1討論

為保證所有點都能按要求完成巡檢，至少要4人。問題1每班4人，已是最少人數，錯時上班，人數明顯會超過4人，并不節省人力。

4.3.2 錯時上班時，針對問題2討論

進餐只在12時和18時左右進行，三班中，第一班無需進餐且已是最少人數，為節省人力，只能減少第二、三班人數。

由模型(2)的討論可知，安排進餐每0.5 h輪1次。安排5人時，就餐時間為11:00—13:30。假設錯時上班的時間應是0.5 h的倍數，為節省人力，每班應不占用上班時間進餐，即到就餐時間，員工下班或上班時已吃完，故錯時上下班時間點，應正好在此時間段內。

假設錯時上班時間為0:00—8:30、8:30—18:00、18:00—24:00。0:00—8:30無需進餐，安排5人巡檢。8:30—18:00只考慮12時進餐，18時下班時無需進餐，按4.2.2.1情況討論，此時安排6人。18:00—24:00考慮巡檢員上班時已進完餐，工作時間無需進餐，安排6人。其他情況討論，見表7。

表7 不同錯時上班時間下每班人數安排表

由表7可知，第4種討論，按3:00—11:00、11:00—19:00、19:00—3:00排班時，最節省人力，每班均安排5人。

問題2，錯時上班更節省人力。

5 結語

本研究提出的分組準則簡便易行，可操作性強，用均衡度的概念較好刻畫了分組的均衡性。但模型建立時的考慮過于理想化，數據處理和求解過程中出現的誤差也會影響模型求解的精確度，這些問題后續都需進一步改進。