費荔枝++呂恒民
【摘要】該問題屬于最佳推銷員回路問題,文中首先對化工廠的檢測點巡檢進(jìn)行概述,然后分析化工廠的巡檢現(xiàn)狀,并運用節(jié)約算法、啟發(fā)算法對測站巡檢線路進(jìn)行優(yōu)化,最后提出最優(yōu)方案。
【關(guān)鍵詞】最佳推銷員回路問題;賦權(quán)圖;近似算法;均衡度
【基金項目】吉安職業(yè)技術(shù)學(xué)院校級科研項目(16JY137)資助
【中圖分類號】TQ086.2;TP274.4 【文獻(xiàn)標(biāo)識碼】B 【文章編號】2095-3089(2017)17-0292-02
一、問題重述
某化工廠有26個點需要進(jìn)行巡檢以保證正常生產(chǎn),每個點每次巡檢需要一名工人,巡檢工人的巡檢起始地點在巡檢調(diào)度中心(XJ0022),工人可以按固定時間上班,也可以錯時上班,在調(diào)度中心得到巡檢任務(wù)后開始巡檢。巡檢線路是指從巡檢調(diào)度中心(XJ0022)出發(fā),走遍所有的點,再回到巡檢調(diào)度中心的路線。
(1)如果采用固定上班時間,不考慮巡檢人員的休息時間,采用每天三班倒,每班工作8小時左右,每班需要多少人,巡檢線路如何安排,并給出巡檢人員的巡檢線路和巡檢的時間表。
(2)如果巡檢人員每巡檢2小時左右需要休息一次,休息時間大約是5到10分鐘,在中午12時和下午6時左右需要進(jìn)餐一次,每次進(jìn)餐時間為30分鐘,仍采用每天三班倒,每班需要多少人,巡檢線路如何安排,并給出巡檢人員的巡檢線路和巡檢的時間表。
(3)如果采用錯時上班,重新討論問題1和問題2,試分析錯時上班是否更節(jié)省人力。
二、問題分析
本題給出了某工廠巡檢線路圖及各個點的巡檢周期、巡檢耗時、兩點之間的連通關(guān)系、行走所需時間,要求的是在不同的條件下,巡檢排班的線路及巡檢人數(shù)、時間表。將每個巡檢點看作一個圖的頂點,各巡檢點之間的線路看作此圖對應(yīng)頂點間的邊,各條線路行走所需要時間看作對應(yīng)邊上的權(quán),所給線路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖,問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題,即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點巡檢調(diào)度中心(XJ0022)出發(fā),使所有頂點都能按要求完成巡檢,使得總權(quán)(路程或時間)最小。
本題是旅行售貨員問題的延伸-多旅行售貨員問題。本題所求的分班巡視的最佳路線,也就是m條經(jīng)過同一點并覆蓋所有其他頂點又使邊權(quán)之和達(dá)到最小的閉鏈(閉跡)。
眾所周知,旅行售貨員問題屬于NP完全問題,即求解沒有多項式時間算法。顯然本問題更應(yīng)屬于NP完全問題。有鑒于此,一定要針對問題的實際特點尋找簡便方法,想找到解決此類問題的一般方法是不現(xiàn)實的,對于規(guī)模較大的問題可使用近似算法來求得近似最優(yōu)解。
三、模型假設(shè)
1.巡檢人員行走所用時間總是一定,忽略天氣等因素的影響。
2.各個點巡檢周期、兩點之間的連通關(guān)系總是一定,忽略故障等其他因素的影響;
3.巡視當(dāng)中,各巡檢點的巡檢耗時一定,不會出現(xiàn)特殊情況而延誤時間;
4.每個點每次巡檢只有一名工人;
四、符號說明
w(i,j):任意兩點i,j間的間距;ei:各點的巡檢耗時,即點權(quán);V:各巡檢點構(gòu)成的集合。
五、模型建立與求解
巡視線路圖中,每個巡檢點看作圖中的一個節(jié)點,各巡檢點之間的線路看作此圖對應(yīng)頂點間的邊,各條線路行走所需要時間看作對應(yīng)邊上的權(quán),所給線路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖,問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題,即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點巡檢調(diào)度中心(XJ0022)出發(fā),使所有頂點都能按要求完成巡檢,此即最佳推銷員回路問題。
此問題包含兩方面:第一、對頂點分組;第二、在每組中求最佳推銷員回路,即為單個推銷員的最佳推銷員問題。由于單個推銷員的最佳推銷員回路問題不存在多項式時間內(nèi)的精確算法,故多個推銷員的問題也不存在多項式時間內(nèi)的精確算法。我們需要去尋求一種較合理的劃分準(zhǔn)則,對圖(1)進(jìn)行初步劃分后,分成巡查圈I、巡查圈I、巡查圈I所示的三個組
經(jīng)過分析我們得出每班至少需要四名工人尋遍所有的巡查點。四名工人分別記為A、B、C、D。工人A負(fù)責(zé)巡查圈I,工人B、C負(fù)責(zé)巡查圈II,工人D負(fù)責(zé)巡查圈III。為了耗費的人力資源盡可能的少,并且每名工人在同一時間段內(nèi)工作量盡可能均衡。工人A按路線一進(jìn)行巡查。工人B、工人C分別按路線二、三進(jìn)行第一次巡查,工人D按路線四進(jìn)行第一次巡查。第一次四名工人巡檢路線如下。
經(jīng)過第一次巡查后,我們對巡查路線作進(jìn)一步的優(yōu)化(如下表),四名工人按照優(yōu)化后的巡檢路線進(jìn)行巡檢。工人A按巡邏圈Ⅰ進(jìn)行巡檢(循環(huán)進(jìn)行,直到換班);工人B、C按照巡邏圈Ⅱ(3-23路線)交替相向而行進(jìn)行巡檢;工人D按照巡邏圈Ⅲ進(jìn)行巡檢(循環(huán)進(jìn)行,直到換班)。
因為該組檢測路線的每個檢測周期內(nèi)有效的每人檢測的均衡度
所以這種路線的周期內(nèi)的每人檢測的均衡性較好。
根據(jù)巡檢路線并考慮巡檢工人在一時間段內(nèi)的工作量盡量平衡,巡檢時間表如下:
問題二:頂替輪班
由于巡查人員每巡查2小時左右需要休息一次,8小時工作時間內(nèi)共計需要休息3次,每個點大約檢查15次,休息時間是15到30分鐘。
在考慮到工廠巡查的不間斷性,工人要在中午12點和下午6點進(jìn)餐,因此,在原有4個人的基礎(chǔ)之上,增加一人,實行頂替輪班的方法。每次一個人進(jìn)餐,另一人頂替進(jìn)餐者進(jìn)行巡檢,進(jìn)餐者用完餐后立刻返回其崗位,讓頂替者到另一路線頂替其他工人進(jìn)餐,以此類推,該頂替者共計要連續(xù)工作0.5×4=2小時,并且當(dāng)其他工人休息時頂班工作,時間為15×4=1小時,所以頂班工人實際工作時間為3小時。綜合以上分析,在保證工廠巡檢正常進(jìn)行,第一班0:00-8:00需要工人4人,第二班8:00-16:00需要工人5人,第三班16:00-24:00需要工人5人。如果采用每天三班倒,共計需要14人。其巡查的時間表如下:
問題三:采用錯時上班
由于問題一不考慮巡檢人員的休息時間,也不考慮工人的進(jìn)餐時間,所以錯時上班對是否節(jié)省時間沒有太大影響。工人每天工作8小時左右,每班需要4人,一天依舊需要12名工人巡檢。
由于問題二中巡檢人員每巡檢2小時左右需要休息一次,在中午12:00和下午6:00需要進(jìn)餐一次,12:00與下午6:00相距6小時,并且采取錯時上班制,在8:00-16:00和16:00-24:00的兩次巡檢中,只需一名工人頂替這兩班工人的休息和進(jìn)餐時間,所以第一班0:00-8:00需要工人四名,第二班和第三班8:00-24:00需要工人9名,共計一天需要13人,所以采用錯時上班可以節(jié)省人力。
優(yōu)缺點分析:
優(yōu)點:
1.本文提出的分組準(zhǔn)則簡便易行,可操作性強(qiáng),且可逐步調(diào)整使分組達(dá)到均衡;
2.用均衡度的概念定量的刻畫了分組的均衡性;
3.在用近似算法求近似最佳推銷員回路時,采取了三種不同的方法產(chǎn)生初始圈,使得算法比較完善,得到了誤差很小的近似最優(yōu)解;
缺點
1.時間精確度存在一定誤差。
參考文獻(xiàn)
[1]趙靜,數(shù)學(xué)建模與數(shù)學(xué)實驗(第三版),北京:高等教育出版社,2008.
[2]胡運權(quán),運籌學(xué)基礎(chǔ)及應(yīng)用(第三版),哈爾濱:哈爾濱工業(yè)大學(xué)出版社,1998.
[3]孫惠泉,圖論及其應(yīng)用,北京:科學(xué)出版社,2004.
作者簡介:費荔枝(1982—),女,碩士,中級.研究方向:生物數(shù)學(xué)。
通訊作者:E-mail:lvhengmin2005@163.com