基于TSP模型改進的巡檢工作調度實證研究

鄒臘英

基于TSP模型改進的巡檢工作調度實證研究

鄒臘英

（江西財經職業學院，江西 九江 332000）

多點巡檢問題在生產生活中非常普遍，如何精準、有效地解決這個問題已迫在眉睫。TSP數學模型是數學中解決旅行經銷商遍歷各城市的經典問題，通過對此模型的改進，并使用LINGO及MATLAB軟件編程，有效地解決了多點巡檢的線路設計及人員調度安排問題，實現了人員安排最優、巡檢時間精確的效果，大大提高了企業運行效率。

巡檢線路；巡檢時間；TSP模型；MATLAB

在生產和生活中，很多工作都與巡檢有關，包括電網巡檢、網絡巡檢、化工廠巡檢及保安巡邏等。多點巡檢是一個涉及面廣而又復雜的問題，涉及到巡檢人員安排、巡檢路線的設定及巡檢點時間的計算，處理不好會直接影響企業效益，甚至造成重大安全事故。如何合理、精準地設計巡檢線路、聘用和安排工人的具體巡檢工作，是一個亟待解決的重要問題。隨著科技的進步，人工手動設計巡檢路線及人員安排因效率過低，已不適應市場需要，信息化設計才是解決問題的主流，既可以提高效率，又計算精確。本文通過改進TSP數學模型，并使用LINGO及MATLAB軟件編程，可以很好地解決多點巡檢問題線路設計及人員安排。

1 TSP問題的介紹

TSP問題即旅行經銷商問題（Traveling Salesman Problem），TSP模型是運籌學的一個著名命題，即一名推銷員準備從某個城市出發，前往多個城市推銷產品，并且經過每個城市恰好1次，最后返回到他的出發地。如何為他設計一條最短的旅行路線這個問題稱為旅行商問題，即TSP問題。

解決TSP問題的關鍵是效率，即遍歷每個地點所用時長最短；其次是約束，即遍歷一圈后每個地點到達且只能到達1次。

根據要求引入0-1整數變量ij（≠），ij=1表示從地點到地點，ij=0表示地點不到地點，ij表示地點到地點的時間，則歷時最短可寫成模型：

2 巡檢工作調度實證研究

2.1 問題描述

某化工廠有26個作業點需要進行巡檢以保證正常生產，各個點的巡檢周期、巡檢耗時、兩點之間的連通關系及行走所需時間在附件中已給出，且每個點每次巡檢需要1名工人，巡檢工人的巡檢起始地點在巡檢調度中心（XJ0022），工人可以按固定時間上班，也可以錯時上班，在調度中心得到巡檢任務后開始從起始點巡檢。現需要建立模型來安排巡檢人數和巡檢路線，使得所有點都能按要求完成巡檢，并且耗費的人力資源盡可能少，同時還應考慮每名工人在一時間段內（如1周或1月等）的工作量盡量平衡。

2.2 問題分析

本案例要解決兩種情況的巡檢線路安排：①固定時間上下班，這種情況下要分多條線路巡檢，因為一條線路巡檢不能滿足巡檢點巡檢周期為35 min的要求；②錯時上下班，可只建立一條線路，這條巡檢線路包含所有巡檢點，讓工人不同時間上班，從而滿足巡檢點巡檢周期為35 min的需求。

2.3 巡檢線路算法分析及模型建立

無論是固定時間上班還是錯時上下班，都要形成巡檢線路，在這個線路循環中都要滿足巡檢點巡檢周期安排，相當于巡檢線路是一個遍歷的過程，在這個過程中要滿足以下要求。每個巡檢點的入點和出點都只能銜接唯一一個點，以保證每個巡檢點遍歷而且不會再形成小圈，所以得到公式：

即每個巡檢點的入點和出點都只有1個，ij=0指第點與第點不連通，ij=1指第點與第點連通。

巡檢線路是個巡回路線，要達到遍歷，又只能有一條巡回路線，即不能含子回路，則i－j+ij≤－1，=1，2，…，；=2，3，…，；≠。

整數規劃模型：

2.4 固定時間上下班情況下巡檢調度研究

在上下班時間固定的條件下，巡檢人員巡檢時間受到巡檢點的巡檢周期影響，每個巡檢工人必須在第一個巡檢點的巡檢周期時間到達之前回到第一個巡檢點，所以，不能建立所有巡檢點遍歷的大循環，只能以第一個巡檢點的巡檢周期時間為一個巡檢圈，找尋巡檢圈的點。

根據就近相連的原則，大致分隔出6條巡檢路線。本問題的目標函數是使得每個巡檢路線形成的巡檢圈內的巡檢時間及行走時間最短，所以目標函數為：

式（1）中：ij為第點與第點行走所花時間；j為第點巡檢所花時間。

使用上述模型中的約束，由編寫的LINGO程序得到具體的巡檢線路安排。在固定時間上下班的情況下，總共需要6個工人同時上下班，工人在巡檢調度中心（XJ0022）打卡上班后各自到自己的巡檢線路上進行巡檢工作，時間相對固定和均衡。

2.5 錯時上下班情況下的巡檢調度研究

因為錯時上班，所以巡檢人員巡檢時間不受巡檢點的巡檢周期影響，可以建立所有巡檢點遍歷的大循環。

在巡檢點巡檢周期一致的情況下，即每個巡檢點巡檢周期都為35 min，利用巡檢線路模型，只要將模型中的巡檢點改為==26，由LINGO軟件編程得到整個26個點的遍歷，整個遍歷需要耗時135 min，在錯時上下班情況下僅需要安排4名巡檢員巡檢（共140 min）。每名巡檢人員的巡檢線路如表1所示。

表1 巡檢點巡檢周期一致下錯時上下班巡檢最優線路

巡檢線路具體巡檢點總耗時/min 線路22?19?20?21?4?2?1?3?5?7?146?10?1113?16?18?15?12?26?17?8?25?924?23?22135

2.6 巡檢點巡檢周期不一致情況下算法的進一步研究

一般來說，巡檢點的巡檢周期不盡相同，則研究巡檢點巡檢周期不盡相同的情況更具有復雜性和普遍性。要解決巡檢點巡檢周期不盡相同的問題，首先要確定每一條巡檢線路所經過的巡檢點有哪些。

2.6.1 每條巡檢線路巡檢點的確定

要想確定巡檢點，首先要找到每個巡檢點周期與最小巡檢周期的關系，即按最小巡檢周期倍數來過濾每條巡檢線路不經過的點。

按以上規律使用for循環編程，可得到每條巡檢線路經過的巡檢點。

2.6.2 巡檢周期不一致下錯時上下班實證分析

按照上述介紹的方法確定好每條巡檢線路的巡檢點后，采用巡檢調度模型，利用LINGO軟件計算可得出每條線路的巡檢點和時間節點，巡檢點巡檢周期不一致情況下，雖然線路巡檢點不一致，但是會產生循環，就本例而言，20條不同巡檢線路后就會重新開始。

3 結束語

基于以上實例得出，無論是固定時間上下班，還是錯時上下班的巡檢工作的調度，改進的TSP模型都能成功地求解，并科學、精準地安排員工的巡檢工作。在固定時間上下班的情況下，TSP模型的求解比較被動，需要預先估算巡檢線路的條數，再利用LINGO編程求解，求得的巡檢線路不一定最優，但在錯時上下班的情況下，改進的TSP模型的作用被發揮得淋漓盡致，不需要任何手動的輔助，就能精準計算員工巡檢線路的具體巡檢點及巡檢精確時間，為巡檢工作調度提供科學、有效的幫助。

綜上所述，使用改進的TSP模型及其對應的程序可以很好地解決生活及生產當中很多繁雜的巡檢調度問題，不僅科學有效，而且精準可靠，有效地避免了人工調度中人力、物力的浪費，極大優化了人員安排及巡檢調度工作，這些模型在同類巡檢問題的解決中可以廣泛推廣使用。

［1］汪曉銀，鄒庭榮.數學軟件與數學實驗［M］.北京：科學出版社，2008.

［2］汪曉銀，周保平.數學建模與數學實驗［M］.北京：科學出版社，2010.

［3］韓中庚.數學建模方法及其應用［M］.北京：高等教育出版社，2005.

［4］敬振毅，張澤兵，董霖.MATLAB7.0實用寶典［M］.北京：中國鐵道出版社，2008.

［5］曹衛華，郭正編.最優化技術方法及MATLAB的實現［M］.北京：化學工業出版社，2005.

［6］袁新生，邵大宏，郁時煉.LINDO和Excel在數學建模中的應用［M］.北京：科學出版社，2007.

［7］謝金星，薛毅.優化建模與LINDO/LINGO軟件［M］.北京：清華大學出版社，2005.

TS48

A

10.15913/j.cnki.kjycx.2019.16.007

2095－6835（2019）16－0020－02

〔編輯：張思楠〕