鄒臘英
基于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ì)及人員安排。
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í)最短可寫成模型:
某化工廠有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月等)的工作量盡量平衡。
本案例要解決兩種情況的巡檢線路安排:①固定時(shí)間上下班,這種情況下要分多條線路巡檢,因?yàn)橐粭l線路巡檢不能滿足巡檢點(diǎn)巡檢周期為35 min的要求;②錯(cuò)時(shí)上下班,可只建立一條線路,這條巡檢線路包含所有巡檢點(diǎn),讓工人不同時(shí)間上班,從而滿足巡檢點(diǎn)巡檢周期為35 min的需求。
無論是固定時(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ī)劃模型:
在上下班時(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ì)固定和均衡。
因?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
一般來說,巡檢點(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ì)重新開始。
基于以上實(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
〔編輯:張思楠〕