基于TSP動態規劃的巡查線路排班問題研究

李建軍

摘? 要：在很多企業工廠，安排巡檢排班都是很重要的一部分，本文將“巡檢路線排班最佳”轉化為TSP動態規劃問題，用貪婪算法分析每班每人近似最佳路線，畫出賦權圖，然后用C語言編程運行得到可行路線方案，進行均衡度比較從而選定最佳巡查方案。在此基礎上考慮錯時交班得出遍歷圖，應用Mathematica編輯對路線進行模擬分析，從而得到人數最少的配置，使人力資源分配更加高效合理。

關鍵詞：TSP動態規劃;排班問題;遍歷法;均衡度

中圖分類號：TP301.6? ? ? 文獻標識碼：A 文章編號：2096-4706（2019）01-0155-03

Research on Scheduling Problem of Patrol Line Based on

TSP Dynamic Programming

LI Jianjun

（Department of Basic Sciences，Northern Beijing Vocational Education Institute，Beijing? 101400，China）

Abstract：In many enterprises，scheduling of patrol is a very important work. This paper transforms “the best scheduling of patrol route” into the TSP dynamic programming problem. The greedy algorithm is used to analyze the approximate best route of each class，and the weight map is drawn，then the feasible route plan is worked out by C language programming，and the equilibrium degree is compared，so as to select the best patrol plan. On this basis，the ergodic graphcome to consider the staggered office hours，using the Mathematica editor to simulate and analyze the route to obtain the minimum number of configuration，make human resource allocation more efficient and reasonable.

Keywords：TSP dynamic programming;scheduling problem;ergodic method;equilibrium degree

0? 引? 言

很多工廠企業都有工作站點需要進行巡檢以保證正常生產，假設每個點每次巡檢需要一名工人，巡檢起始地點在巡檢調度中心，所有工人可以按固定時間上班，也可以錯時上班，在調度中心得到巡檢任務后開始巡檢。本文通過分析問題建立模型來安排巡檢人數和巡檢路線，使得所有點都能夠按照要求完成巡檢，并且耗費的人力資源盡可能少，同時還應該考慮每名工人在一段時間內的工作量要盡量平衡。

首先調查各檢查點的巡檢周期、巡檢耗時兩點間的聯通關系及行動所需的時間，在不同的條件下，巡檢的最少人數及路線。我們將每個檢查點看作一個圖的頂點，各檢查點之間的聯通關系看作此圖對應頂點的邊，各點行走所需的時間看作對應邊上的權，這樣所給的監察網就轉化為了加權網絡圖。

本問題要針對實際特點尋找通用方法，對于規模較大的問題可使用近似算法來求得近似最優解，故可用TSP動態規劃進行分析。

1? 涉及數學思想

1.1? TSP動態規劃

TSP問題，即旅行商問題，又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求所選擇的路徑路程為所有路徑之中的最小值。旅行推銷員問題是圖論中最著名的問題之一，即“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉回路”，這類難題有一個值得注意的性質：對其中一個問題存在有效算法時，每個問題都會有有效算法。[1]

1.2? 均衡度分析

均衡是平衡的意思，在經濟學中，均衡即表示相關量處于穩定值。在供求關系中，某一商品市場如果在某一價格下，想以此價格買此商品的人均能買到，而想賣的人均能賣出，此時我們就說，該商品的供求達到了均衡。[2]

2? 合理假設

解決此類問題，要對一些情況進行合理假設：假設巡查人員在各點相遇時互不影響;假設經過不巡查點時不浪費時間;假設巡檢員巡檢速度為勻速，不會出現特殊情況;忽略天氣、故障等因素的影響;假設中午用餐時間為30分鐘，每人每天工作8小時;假設工作每天都在循環進行，且工作一致，不存在病假、事假、突發假。

3? 問題分析及模型求解

檢查路線圖，把每個檢查點或調度站之間的聯通關系看作圖中對應節點間的邊，任意兩點間的間距時間看作對應邊上的權，所給的檢查路線網就轉化為加權網絡圖。問題研究步驟如下：

（1）用圖論軟件包求出G中任意兩個頂點間的最短路，構造出完備圖G'（V，E'），，ω（x，y）=Mind（x，y）;

（2）輸入圖G'的一個初始圈;

（3）用對角線完全算法產生一個初始圈;

（4）隨機搜索出G'中若干個初始圈;

（5）對第（2）、（3）、（4）步所得的每個H圈，用二邊逐次修正法進行優化，得到近似最佳H圈;

（6）在第（5）步求出的所有H圈中，找出權最小的一個，此即要找的最佳H圈的近似。

二邊逐次修正法的結果與初始圈有關，故本算法第（2）、（3）、（4）步分別用三種方法產生初始圈，以保證能得到較優的計算結果。

3.1? 工作人員不錯時排班統一班次安排

求解算法采用三步完成，第一步，先利用貪婪算法盡量使從調度點出發到各檢查點的時間最短;第二步，對各路線的時間再進行調整，進一步優化直到時間不能減少為止;第三步，在保證時間不超過最小周期35分鐘情況下對各路線再進行調整直到時間不能縮短為止。針對某一26巡查點工廠，通過C語言程序計算，得到如下線路行進圖（如圖1所示）。

將此圖中各個巡檢員的路線歷時情況應用Excel表格統計每個巡檢員的路線、巡檢時間及其路程，從而得到以下線路圖和每條線路一圈所需時間，如表1所示。

排班問題考慮工作強度要相對均衡，計算此方案各巡視人員的勞動時間的標準差S：

均衡差異度λ≤30%在合理范圍內，我們安排每班5人，24小時需要3班共計15人。考慮到人員上班習慣，方案一巡檢時間為第一班，00：00-8：00;第二班，8：00-16：00;第三班，16：00-24：00。

3.2? 考慮錯時排班優化人力資源配置

采用錯時上班，可以更加節省人力資源分配，在此條件下將問題轉變為TSP動態規劃問題，在MATLAB環境下對迪克斯特拉（Dijkstra）算法編程求出最短路線，并用遍歷法得到最優遍歷圖，再利用Excel表格對數據進行整合分析，與3.1中方案進行均衡度計算與縱向比較。

根據實際工作的經驗及上述分析，在分組時應遵從以下準則：

（1）盡量把同一干枝上及其分支上的點分在同一組;

（2）將相鄰的干枝上的點分在同一組;

（3）盡量將長的干枝與短的干枝分在一組。

從22點出發去其它點，要使時間較短應盡量走22點到該點的最短間距時間，故用圖論軟件包求22點到其余頂點的最短間距時間，這些最短間距時間構成一棵22點為樹根的樹，將從22點出發的樹枝稱為干枝，如圖所示，從22點出發到其它點共有3條枝干，計算出以下遍歷圖（如圖2所示），通過遍歷檢查得出總時間。

已知每個人工作8小時，一個人走完全程用時136分，列式為：8×60=480分，480/136=3次余72分。

每人（每班四人，每天三班）從22點出發，到下班時間人在16點，并且已巡視完畢，另派兩人跟其他人反方向巡檢直到到達16點（其中這兩人為特殊班次），其中每個人每次巡檢時間為64分列式為：64×12=768分，768分=12.8小時。

這種方案中所需人數為：3×4+2=14人。

統計動態班次路線、巡檢時間及路程，以12個人為基礎班次，后補倆人為特殊班次，這倆人反方向收尾，直到完成所有的檢核點的檢查，得到時間安排表。如表2所示。

計算此方案各巡視人員的勞動時間的標準差S，從而得到這種動態分配方案的均衡差異度λ為9.2%，由此可知錯時上班工作時間的分配方案更為均衡，也更加節省人力，更有效率。

4? 模型評價與推廣

在排班問題中，本文提出的分組準則簡便易行，可操作性強，且可逐步調整使分組達到均衡;排版問題用均衡度的概念定量使得分組方案得到了量化比較;在用近似算法求近似最佳巡檢員回路時，采取了兩種不同的方法，使得算法比較完善，得到了誤差很小的近似最優解。但是，此模型分析將人的因素理想化未考慮路程會影響時間的任何因素，這是日后需完善探索的方向。本模型對交警巡查路線、快遞員送件線路、以及便民菜店的設置線路等這些最優化問題提供了可參考分析方案。

參考文獻：

[1] Cook W. 迷茫的旅行商：一個無處不在的計算機算法問題：mathematics at the limits of computation [M].北京：人民郵電出版社，2013.

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

[3] 朱旭，李換琴，籍萬新.MATLAB軟件與基礎數學實驗 [M].西安：西安交通大學出版社，2008.