費(fèi)荔枝++呂恒民

【摘要】該問(wèn)題屬于最佳推銷(xiāo)員回路問(wèn)題，文中首先對(duì)化工廠(chǎng)的檢測(cè)點(diǎn)巡檢進(jìn)行概述，然后分析化工廠(chǎng)的巡檢現(xiàn)狀，并運(yùn)用節(jié)約算法、啟發(fā)算法對(duì)測(cè)站巡檢線(xiàn)路進(jìn)行優(yōu)化，最后提出最優(yōu)方案。

【關(guān)鍵詞】最佳推銷(xiāo)員回路問(wèn)題；賦權(quán)圖；近似算法；均衡度

【基金項(xiàng)目】吉安職業(yè)技術(shù)學(xué)院校級(jí)科研項(xiàng)目（16JY137）資助

【中圖分類(lèi)號(hào)】TQ086.2；TP274.4 【文獻(xiàn)標(biāo)識(shí)碼】B 【文章編號(hào)】2095-3089（2017）17-0292-02

一、問(wèn)題重述

某化工廠(chǎng)有26個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，每個(gè)點(diǎn)每次巡檢需要一名工人，巡檢工人的巡檢起始地點(diǎn)在巡檢調(diào)度中心（XJ0022），工人可以按固定時(shí)間上班，也可以錯(cuò)時(shí)上班，在調(diào)度中心得到巡檢任務(wù)后開(kāi)始巡檢。巡檢線(xiàn)路是指從巡檢調(diào)度中心（XJ0022）出發(fā)，走遍所有的點(diǎn)，再回到巡檢調(diào)度中心的路線(xiàn)。

（1）如果采用固定上班時(shí)間，不考慮巡檢人員的休息時(shí)間，采用每天三班倒，每班工作8小時(shí)左右，每班需要多少人，巡檢線(xiàn)路如何安排，并給出巡檢人員的巡檢線(xiàn)路和巡檢的時(shí)間表。

（2）如果巡檢人員每巡檢2小時(shí)左右需要休息一次，休息時(shí)間大約是5到10分鐘，在中午12時(shí)和下午6時(shí)左右需要進(jìn)餐一次，每次進(jìn)餐時(shí)間為30分鐘，仍采用每天三班倒，每班需要多少人，巡檢線(xiàn)路如何安排，并給出巡檢人員的巡檢線(xiàn)路和巡檢的時(shí)間表。

（3）如果采用錯(cuò)時(shí)上班，重新討論問(wèn)題1和問(wèn)題2，試分析錯(cuò)時(shí)上班是否更節(jié)省人力。

二、問(wèn)題分析

本題給出了某工廠(chǎng)巡檢線(xiàn)路圖及各個(gè)點(diǎn)的巡檢周期、巡檢耗時(shí)、兩點(diǎn)之間的連通關(guān)系、行走所需時(shí)間，要求的是在不同的條件下，巡檢排班的線(xiàn)路及巡檢人數(shù)、時(shí)間表。將每個(gè)巡檢點(diǎn)看作一個(gè)圖的頂點(diǎn)，各巡檢點(diǎn)之間的線(xiàn)路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條線(xiàn)路行走所需要時(shí)間看作對(duì)應(yīng)邊上的權(quán)，所給線(xiàn)路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類(lèi)稱(chēng)之為旅行售貨員問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)巡檢調(diào)度中心（XJ0022）出發(fā)，使所有頂點(diǎn)都能按要求完成巡檢，使得總權(quán)（路程或時(shí)間）最小。

本題是旅行售貨員問(wèn)題的延伸-多旅行售貨員問(wèn)題。本題所求的分班巡視的最佳路線(xiàn)，也就是m條經(jīng)過(guò)同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈（閉跡）。

眾所周知，旅行售貨員問(wèn)題屬于NP完全問(wèn)題，即求解沒(méi)有多項(xiàng)式時(shí)間算法。顯然本問(wèn)題更應(yīng)屬于NP完全問(wèn)題。有鑒于此，一定要針對(duì)問(wèn)題的實(shí)際特點(diǎn)尋找簡(jiǎn)便方法，想找到解決此類(lèi)問(wèn)題的一般方法是不現(xiàn)實(shí)的，對(duì)于規(guī)模較大的問(wèn)題可使用近似算法來(lái)求得近似最優(yōu)解。

三、模型假設(shè)

1.巡檢人員行走所用時(shí)間總是一定，忽略天氣等因素的影響。

2.各個(gè)點(diǎn)巡檢周期、兩點(diǎn)之間的連通關(guān)系總是一定，忽略故障等其他因素的影響；

3.巡視當(dāng)中，各巡檢點(diǎn)的巡檢耗時(shí)一定，不會(huì)出現(xiàn)特殊情況而延誤時(shí)間；

4.每個(gè)點(diǎn)每次巡檢只有一名工人；

四、符號(hào)說(shuō)明

w（i，j）：任意兩點(diǎn)i，j間的間距；ei：各點(diǎn)的巡檢耗時(shí)，即點(diǎn)權(quán)；V：各巡檢點(diǎn)構(gòu)成的集合。

五、模型建立與求解

巡視線(xiàn)路圖中，每個(gè)巡檢點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)，各巡檢點(diǎn)之間的線(xiàn)路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條線(xiàn)路行走所需要時(shí)間看作對(duì)應(yīng)邊上的權(quán)，所給線(xiàn)路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類(lèi)稱(chēng)之為旅行售貨員問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)巡檢調(diào)度中心（XJ0022）出發(fā)，使所有頂點(diǎn)都能按要求完成巡檢，此即最佳推銷(xiāo)員回路問(wèn)題。

此問(wèn)題包含兩方面：第一、對(duì)頂點(diǎn)分組；第二、在每組中求最佳推銷(xiāo)員回路，即為單個(gè)推銷(xiāo)員的最佳推銷(xiāo)員問(wèn)題。由于單個(gè)推銷(xiāo)員的最佳推銷(xiāo)員回路問(wèn)題不存在多項(xiàng)式時(shí)間內(nèi)的精確算法，故多個(gè)推銷(xiāo)員的問(wèn)題也不存在多項(xiàng)式時(shí)間內(nèi)的精確算法。我們需要去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖（1）進(jìn)行初步劃分后，分成巡查圈I、巡查圈I、巡查圈I所示的三個(gè)組

經(jīng)過(guò)分析我們得出每班至少需要四名工人尋遍所有的巡查點(diǎn)。四名工人分別記為A、B、C、D。工人A負(fù)責(zé)巡查圈I，工人B、C負(fù)責(zé)巡查圈II，工人D負(fù)責(zé)巡查圈III。為了耗費(fèi)的人力資源盡可能的少，并且每名工人在同一時(shí)間段內(nèi)工作量盡可能均衡。工人A按路線(xiàn)一進(jìn)行巡查。工人B、工人C分別按路線(xiàn)二、三進(jìn)行第一次巡查，工人D按路線(xiàn)四進(jìn)行第一次巡查。第一次四名工人巡檢路線(xiàn)如下。

經(jīng)過(guò)第一次巡查后，我們對(duì)巡查路線(xiàn)作進(jìn)一步的優(yōu)化（如下表），四名工人按照優(yōu)化后的巡檢路線(xiàn)進(jìn)行巡檢。工人A按巡邏圈Ⅰ進(jìn)行巡檢（循環(huán)進(jìn)行，直到換班）；工人B、C按照巡邏圈Ⅱ（3-23路線(xiàn)）交替相向而行進(jìn)行巡檢；工人D按照巡邏圈Ⅲ進(jìn)行巡檢（循環(huán)進(jìn)行，直到換班）。

因?yàn)樵摻M檢測(cè)路線(xiàn)的每個(gè)檢測(cè)周期內(nèi)有效的每人檢測(cè)的均衡度

所以這種路線(xiàn)的周期內(nèi)的每人檢測(cè)的均衡性較好。

根據(jù)巡檢路線(xiàn)并考慮巡檢工人在一時(shí)間段內(nèi)的工作量盡量平衡，巡檢時(shí)間表如下：

問(wèn)題二：頂替輪班

由于巡查人員每巡查2小時(shí)左右需要休息一次，8小時(shí)工作時(shí)間內(nèi)共計(jì)需要休息3次，每個(gè)點(diǎn)大約檢查15次，休息時(shí)間是15到30分鐘。

在考慮到工廠(chǎng)巡查的不間斷性，工人要在中午12點(diǎn)和下午6點(diǎn)進(jìn)餐，因此，在原有4個(gè)人的基礎(chǔ)之上，增加一人，實(shí)行頂替輪班的方法。每次一個(gè)人進(jìn)餐，另一人頂替進(jìn)餐者進(jìn)行巡檢，進(jìn)餐者用完餐后立刻返回其崗位，讓頂替者到另一路線(xiàn)頂替其他工人進(jìn)餐，以此類(lèi)推，該頂替者共計(jì)要連續(xù)工作0.5×4=2小時(shí)，并且當(dāng)其他工人休息時(shí)頂班工作，時(shí)間為15×4=1小時(shí)，所以頂班工人實(shí)際工作時(shí)間為3小時(shí)。綜合以上分析，在保證工廠(chǎng)巡檢正常進(jìn)行，第一班0：00-8：00需要工人4人，第二班8：00-16：00需要工人5人，第三班16：00-24：00需要工人5人。如果采用每天三班倒，共計(jì)需要14人。其巡查的時(shí)間表如下：

問(wèn)題三：采用錯(cuò)時(shí)上班

由于問(wèn)題一不考慮巡檢人員的休息時(shí)間，也不考慮工人的進(jìn)餐時(shí)間，所以錯(cuò)時(shí)上班對(duì)是否節(jié)省時(shí)間沒(méi)有太大影響。工人每天工作8小時(shí)左右，每班需要4人，一天依舊需要12名工人巡檢。

由于問(wèn)題二中巡檢人員每巡檢2小時(shí)左右需要休息一次，在中午12：00和下午6：00需要進(jìn)餐一次，12：00與下午6：00相距6小時(shí)，并且采取錯(cuò)時(shí)上班制，在8：00-16：00和16：00-24：00的兩次巡檢中，只需一名工人頂替這兩班工人的休息和進(jìn)餐時(shí)間，所以第一班0：00-8：00需要工人四名，第二班和第三班8：00-24：00需要工人9名，共計(jì)一天需要13人，所以采用錯(cuò)時(shí)上班可以節(jié)省人力。

優(yōu)缺點(diǎn)分析：

優(yōu)點(diǎn)：

1.本文提出的分組準(zhǔn)則簡(jiǎn)便易行，可操作性強(qiáng)，且可逐步調(diào)整使分組達(dá)到均衡；

2.用均衡度的概念定量的刻畫(huà)了分組的均衡性；

3.在用近似算法求近似最佳推銷(xiāo)員回路時(shí)，采取了三種不同的方法產(chǎn)生初始圈，使得算法比較完善，得到了誤差很小的近似最優(yōu)解；

缺點(diǎn)

1.時(shí)間精確度存在一定誤差。

參考文獻(xiàn)

[1]趙靜，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（第三版），北京：高等教育出版社，2008.

[2]胡運(yùn)權(quán)，運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用（第三版），哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1998.

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

作者簡(jiǎn)介：費(fèi)荔枝（1982—），女，碩士，中級(jí).研究方向：生物數(shù)學(xué)。

通訊作者：E-mail：lvhengmin2005@163.com