基于TSP動(dòng)態(tài)規(guī)劃的巡查線路排班問題研究

李建軍

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

關(guān)鍵詞：TSP動(dòng)態(tài)規(guī)劃;排班問題;遍歷法;均衡度

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

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

首先調(diào)查各檢查點(diǎn)的巡檢周期、巡檢耗時(shí)兩點(diǎn)間的聯(lián)通關(guān)系及行動(dòng)所需的時(shí)間，在不同的條件下，巡檢的最少人數(shù)及路線。我們將每個(gè)檢查點(diǎn)看作一個(gè)圖的頂點(diǎn)，各檢查點(diǎn)之間的聯(lián)通關(guān)系看作此圖對(duì)應(yīng)頂點(diǎn)的邊，各點(diǎn)行走所需的時(shí)間看作對(duì)應(yīng)邊上的權(quán)，這樣所給的監(jiān)察網(wǎng)就轉(zhuǎn)化為了加權(quán)網(wǎng)絡(luò)圖。

本問題要針對(duì)實(shí)際特點(diǎn)尋找通用方法，對(duì)于規(guī)模較大的問題可使用近似算法來求得近似最優(yōu)解，故可用TSP動(dòng)態(tài)規(guī)劃進(jìn)行分析。

1? 涉及數(shù)學(xué)思想

1.1? TSP動(dòng)態(tài)規(guī)劃

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

1.2? 均衡度分析

均衡是平衡的意思，在經(jīng)濟(jì)學(xué)中，均衡即表示相關(guān)量處于穩(wěn)定值。在供求關(guān)系中，某一商品市場如果在某一價(jià)格下，想以此價(jià)格買此商品的人均能買到，而想賣的人均能賣出，此時(shí)我們就說，該商品的供求達(dá)到了均衡。[2]

2? 合理假設(shè)

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

3? 問題分析及模型求解

檢查路線圖，把每個(gè)檢查點(diǎn)或調(diào)度站之間的聯(lián)通關(guān)系看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，任意兩點(diǎn)間的間距時(shí)間看作對(duì)應(yīng)邊上的權(quán)，所給的檢查路線網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖。問題研究步驟如下：

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

（2）輸入圖G'的一個(gè)初始圈;

（3）用對(duì)角線完全算法產(chǎn)生一個(gè)初始圈;

（4）隨機(jī)搜索出G'中若干個(gè)初始圈;

（5）對(duì)第（2）、（3）、（4）步所得的每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈;

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

二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第（2）、（3）、（4）步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果。

3.1? 工作人員不錯(cuò)時(shí)排班統(tǒng)一班次安排

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

將此圖中各個(gè)巡檢員的路線歷時(shí)情況應(yīng)用Excel表格統(tǒng)計(jì)每個(gè)巡檢員的路線、巡檢時(shí)間及其路程，從而得到以下線路圖和每條線路一圈所需時(shí)間，如表1所示。

排班問題考慮工作強(qiáng)度要相對(duì)均衡，計(jì)算此方案各巡視人員的勞動(dòng)時(shí)間的標(biāo)準(zhǔn)差S：

均衡差異度λ≤30%在合理范圍內(nèi)，我們安排每班5人，24小時(shí)需要3班共計(jì)15人?？紤]到人員上班習(xí)慣，方案一巡檢時(shí)間為第一班，00：00-8：00;第二班，8：00-16：00;第三班，16：00-24：00。

3.2? 考慮錯(cuò)時(shí)排班優(yōu)化人力資源配置

采用錯(cuò)時(shí)上班，可以更加節(jié)省人力資源分配，在此條件下將問題轉(zhuǎn)變?yōu)門SP動(dòng)態(tài)規(guī)劃問題，在MATLAB環(huán)境下對(duì)迪克斯特拉（Dijkstra）算法編程求出最短路線，并用遍歷法得到最優(yōu)遍歷圖，再利用Excel表格對(duì)數(shù)據(jù)進(jìn)行整合分析，與3.1中方案進(jìn)行均衡度計(jì)算與縱向比較。

根據(jù)實(shí)際工作的經(jīng)驗(yàn)及上述分析，在分組時(shí)應(yīng)遵從以下準(zhǔn)則：

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

（2）將相鄰的干枝上的點(diǎn)分在同一組;

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

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

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

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

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

統(tǒng)計(jì)動(dòng)態(tài)班次路線、巡檢時(shí)間及路程，以12個(gè)人為基礎(chǔ)班次，后補(bǔ)倆人為特殊班次，這倆人反方向收尾，直到完成所有的檢核點(diǎn)的檢查，得到時(shí)間安排表。如表2所示。

計(jì)算此方案各巡視人員的勞動(dòng)時(shí)間的標(biāo)準(zhǔn)差S，從而得到這種動(dòng)態(tài)分配方案的均衡差異度λ為9.2%，由此可知錯(cuò)時(shí)上班工作時(shí)間的分配方案更為均衡，也更加節(jié)省人力，更有效率。

4? 模型評(píng)價(jià)與推廣

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

參考文獻(xiàn)：

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

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

[3] 朱旭，李換琴，籍萬新.MATLAB軟件與基礎(chǔ)數(shù)學(xué)實(shí)驗(yàn) [M].西安：西安交通大學(xué)出版社，2008.