基于TSP模型改進(jìn)的巡檢工作調(diào)度實(shí)證研究

鄒臘英

基于TSP模型改進(jìn)的巡檢工作調(diào)度實(shí)證研究

鄒臘英

（江西財(cái)經(jīng)職業(yè)學(xué)院，江西 九江 332000）

多點(diǎn)巡檢問題在生產(chǎn)生活中非常普遍，如何精準(zhǔn)、有效地解決這個(gè)問題已迫在眉睫。TSP數(shù)學(xué)模型是數(shù)學(xué)中解決旅行經(jīng)銷商遍歷各城市的經(jīng)典問題，通過對(duì)此模型的改進(jìn)，并使用LINGO及MATLAB軟件編程，有效地解決了多點(diǎn)巡檢的線路設(shè)計(jì)及人員調(diào)度安排問題，實(shí)現(xiàn)了人員安排最優(yōu)、巡檢時(shí)間精確的效果，大大提高了企業(yè)運(yùn)行效率。

巡檢線路；巡檢時(shí)間；TSP模型；MATLAB

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

1 TSP問題的介紹

TSP問題即旅行經(jīng)銷商問題（Traveling Salesman Problem），TSP模型是運(yùn)籌學(xué)的一個(gè)著名命題，即一名推銷員準(zhǔn)備從某個(gè)城市出發(fā)，前往多個(gè)城市推銷產(chǎn)品，并且經(jīng)過每個(gè)城市恰好1次，最后返回到他的出發(fā)地。如何為他設(shè)計(jì)一條最短的旅行路線這個(gè)問題稱為旅行商問題，即TSP問題。

解決TSP問題的關(guān)鍵是效率，即遍歷每個(gè)地點(diǎn)所用時(shí)長最短；其次是約束，即遍歷一圈后每個(gè)地點(diǎn)到達(dá)且只能到達(dá)1次。

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

2 巡檢工作調(diào)度實(shí)證研究

2.1 問題描述

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

2.2 問題分析

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

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

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

即每個(gè)巡檢點(diǎn)的入點(diǎn)和出點(diǎn)都只有1個(gè)，ij=0指第點(diǎn)與第點(diǎn)不連通，ij=1指第點(diǎn)與第點(diǎn)連通。

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

整數(shù)規(guī)劃模型：

2.4 固定時(shí)間上下班情況下巡檢調(diào)度研究

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

根據(jù)就近相連的原則，大致分隔出6條巡檢路線。本問題的目標(biāo)函數(shù)是使得每個(gè)巡檢路線形成的巡檢圈內(nèi)的巡檢時(shí)間及行走時(shí)間最短，所以目標(biāo)函數(shù)為：

式（1）中：ij為第點(diǎn)與第點(diǎn)行走所花時(shí)間；j為第點(diǎn)巡檢所花時(shí)間。

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

2.5 錯(cuò)時(shí)上下班情況下的巡檢調(diào)度研究

因?yàn)殄e(cuò)時(shí)上班，所以巡檢人員巡檢時(shí)間不受巡檢點(diǎn)的巡檢周期影響，可以建立所有巡檢點(diǎn)遍歷的大循環(huán)。

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

表1 巡檢點(diǎn)巡檢周期一致下錯(cuò)時(shí)上下班巡檢最優(yōu)線路

巡檢線路具體巡檢點(diǎn)總耗時(shí)/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 巡檢點(diǎn)巡檢周期不一致情況下算法的進(jìn)一步研究

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

2.6.1 每條巡檢線路巡檢點(diǎn)的確定

要想確定巡檢點(diǎn)，首先要找到每個(gè)巡檢點(diǎn)周期與最小巡檢周期的關(guān)系，即按最小巡檢周期倍數(shù)來過濾每條巡檢線路不經(jīng)過的點(diǎn)。

按以上規(guī)律使用for循環(huán)編程，可得到每條巡檢線路經(jīng)過的巡檢點(diǎn)。

2.6.2 巡檢周期不一致下錯(cuò)時(shí)上下班實(shí)證分析

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

3 結(jié)束語

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

綜上所述，使用改進(jìn)的TSP模型及其對(duì)應(yīng)的程序可以很好地解決生活及生產(chǎn)當(dāng)中很多繁雜的巡檢調(diào)度問題，不僅科學(xué)有效，而且精準(zhǔn)可靠，有效地避免了人工調(diào)度中人力、物力的浪費(fèi)，極大優(yōu)化了人員安排及巡檢調(diào)度工作，這些模型在同類巡檢問題的解決中可以廣泛推廣使用。

［1］汪曉銀，鄒庭榮.數(shù)學(xué)軟件與數(shù)學(xué)實(shí)驗(yàn)［M］.北京：科學(xué)出版社，2008.

［2］汪曉銀，周保平.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)［M］.北京：科學(xué)出版社，2010.

［3］韓中庚.數(shù)學(xué)建模方法及其應(yīng)用［M］.北京：高等教育出版社，2005.

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

［5］曹衛(wèi)華，郭正編.最優(yōu)化技術(shù)方法及MATLAB的實(shí)現(xiàn)［M］.北京：化學(xué)工業(yè)出版社，2005.

［6］袁新生，邵大宏，郁時(shí)煉.LINDO和Excel在數(shù)學(xué)建模中的應(yīng)用［M］.北京：科學(xué)出版社，2007.

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

TS48

A

10.15913/j.cnki.kjycx.2019.16.007

2095－6835（2019）16－0020－02

〔編輯：張思楠〕