巡檢線路排班的優(yōu)化模型

曹西林

摘要：對(duì)化工廠安排工人巡檢問題，是一個(gè)具有一般性的調(diào)度安排問題，在實(shí)際中具有重要作用。本文建立了優(yōu)化模型，采用多TSP問題的思想和原理，將問題等價(jià)變換為尋找區(qū)域劃分?jǐn)?shù)最少的問題，還通過LINGO求解TSP問題給出了每個(gè)工人的最優(yōu)巡檢路線；打破工人區(qū)域限制，對(duì)所有節(jié)點(diǎn)進(jìn)行了人員的初始任務(wù)分配，然后根據(jù)每個(gè)節(jié)點(diǎn)的巡檢周期，得到關(guān)于所有任務(wù)的開始工作時(shí)刻序列，結(jié)束工作時(shí)刻序列，任務(wù)對(duì)應(yīng)節(jié)點(diǎn)序列，并以此建立了巡檢人數(shù)最少和工作量盡量均衡的雙目標(biāo)0-1規(guī)劃模型；對(duì)錯(cuò)時(shí)上班問題，考慮了每個(gè)人上班時(shí)間可調(diào)整情況下，巡檢人數(shù)最少和工作量盡量均衡的雙目標(biāo)0-1規(guī)劃模型，并設(shè)計(jì)算法進(jìn)行求解。

關(guān)鍵詞：巡檢；TSP模型；最優(yōu)路線；優(yōu)化模型

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2018）19-0234-02

1 問題提出

某化工廠的巡檢，需要考慮26個(gè)點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，各個(gè)點(diǎn)的巡檢周期、巡檢耗時(shí)、兩點(diǎn)之間的連通關(guān)系及行走所需時(shí)間（數(shù)據(jù)參見2017年全國大學(xué)生數(shù)學(xué)建模競賽C題附件1）。建立相關(guān)數(shù)學(xué)模型來安排巡檢人數(shù)和巡檢路線。

針對(duì)該問題，需要完成三種情況下的計(jì)算。一是固定上班時(shí)間，不考慮巡檢人員的休息時(shí)間情形；二是固定上班，但巡檢人員有休息情形；三是錯(cuò)時(shí)上班情形。

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

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

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

2 問題分析

針對(duì)問題1， 我們將所有26個(gè)節(jié)點(diǎn)分成若干個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)滿足：（1）按最短路線行走和巡檢，巡檢走完所有節(jié)點(diǎn)并回到開始點(diǎn)，其所花時(shí)間不超過該區(qū)域內(nèi)所有節(jié)點(diǎn)的最小周期。（2）每個(gè)節(jié)點(diǎn)在一個(gè)周期內(nèi)必須巡檢一次，因此要滿足首次到達(dá)該節(jié)點(diǎn)的時(shí)間不能超過該節(jié)點(diǎn)的周期。該問題本質(zhì)上是一個(gè)多TSP問題。我們要建立模型，尋找滿足兩個(gè)條件的最少劃分區(qū)域。

針對(duì)問題2，由于每個(gè)工人工作兩小時(shí)后要休息5-10分鐘，而且中午12點(diǎn)和下午4點(diǎn)要吃飯花30分鐘左右。這樣采用問題1的靜態(tài)劃分方式就不行了，需要采用動(dòng)態(tài)方式，使工人在需要的時(shí)候自動(dòng)在全區(qū)去完成當(dāng)前任務(wù)。我們擬建立一般模型，并設(shè)計(jì)算法進(jìn)行計(jì)算。

針對(duì)問題3，采用錯(cuò)時(shí)上班，每個(gè)人可以在一天的任意時(shí)間上班，只要連續(xù)工作8小時(shí)就可以。我們?nèi)匀唤⒁话隳Ｐ?，并進(jìn)行動(dòng)態(tài)調(diào)整，當(dāng)有任務(wù)而當(dāng)前無法完成時(shí)，就可以增加一個(gè)人去完成。這樣對(duì)可能更能節(jié)省人力，提高效率。

3 模型建立與求解

問題一：

該問題中采用固定上班時(shí)間，不考慮巡檢人員的休息時(shí)間，采用每天三班倒，每班工作8小時(shí)左右。我們考慮將26個(gè)節(jié)點(diǎn)分成若干個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)滿足：（1）按最短路線行走和巡檢，巡檢走完所有節(jié)點(diǎn)并回到開始點(diǎn)，其所花時(shí)間不超過26個(gè)節(jié)點(diǎn)的最小周期35分鐘。（2）同時(shí)由于各節(jié)點(diǎn)周期不同，每個(gè)節(jié)點(diǎn)在一個(gè)周期內(nèi)必須巡檢一次，因此要滿足首次到達(dá)該節(jié)點(diǎn)的時(shí)間不能超過該節(jié)點(diǎn)的周期。我們的任務(wù)就是尋找滿足該條件的最少劃分區(qū)域。本質(zhì)上是一個(gè)多TSP問題。

根據(jù)上面可確定的每個(gè)節(jié)點(diǎn)初次到達(dá)時(shí)刻。設(shè)第[i]個(gè)節(jié)點(diǎn)初次到達(dá)時(shí)刻為[ti]，該點(diǎn)巡檢周期為[Ti]，則該點(diǎn)后面的任務(wù)序列為[t=ti+ki.Ti] ，其中[ki=480-tiTi]，其中[]表示向下取整。這里[ki]表示不超過8小時(shí)的最大巡檢次數(shù)。對(duì)附件中的初始分配，可計(jì)算得到所有26個(gè)節(jié)點(diǎn)可計(jì)算得到任務(wù)序列為258個(gè)。

首先利用Floyd算法和附件所給出的連通圖，計(jì)算出所有節(jié)點(diǎn)兩兩之間的最短路，即相互到達(dá)的最小時(shí)間，給定初始人數(shù)[m]，根據(jù)問題1，開始可取[m=5]進(jìn)行計(jì)算。將[m]個(gè)人進(jìn)行初始分配，分配方式可采用前面介紹方式進(jìn)行，共同對(duì)26個(gè)節(jié)點(diǎn)進(jìn)行首次巡檢，得到每個(gè)節(jié)點(diǎn)的首次訪問時(shí)間。設(shè)第[i]個(gè)節(jié)點(diǎn)的首次巡檢時(shí)間為為[ti]，該點(diǎn)巡檢周期為[Ti]，則該點(diǎn)后面需要完成的的任務(wù)序列為[t=ti+ki.Ti] ，其中[ki=480-tiTi]。當(dāng)如果全天考慮時(shí)（問題3），只需要取總時(shí)間為24*60=1440分鐘。其中[]表示向下取整。這里[ki]表示不超過8小時(shí)的最大巡檢次數(shù)。

利用循環(huán)計(jì)算，我們可以很容易統(tǒng)計(jì)出每個(gè)人工作時(shí)間，每個(gè)人每次執(zhí)行的任務(wù)及所在的節(jié)點(diǎn)序號(hào)。

我們將每天分為3班。第一班知需要每工作兩小時(shí)左右休息5～10分鐘；第二班不但休息，還含有12時(shí)需要吃飯花30分鐘左右；第三班也是不但需要休息，還含有下午6時(shí)需要吃飯花30分鐘左右。我們計(jì)算結(jié)果為：第一班需要人數(shù)為5人，第二班需要人數(shù)為6人，第三班需要人數(shù)為6人，總共需要20人，比問題1多了2人，各班任務(wù)均衡度都比問題1均衡度55.28更好。說明動(dòng)態(tài)調(diào)整也更有利于工作量均衡。

問題三：

對(duì)錯(cuò)時(shí)上班，對(duì)每個(gè)人不再有固定開始上班時(shí)間。可以根據(jù)任務(wù)需要隨時(shí)參與巡檢，只要工作滿8小時(shí)，則下班不再工作。

則在問題2前面模型中，初始時(shí)不再讓所有人都在開始時(shí)刻上班。設(shè)第[i]個(gè)人最后一次巡檢時(shí)刻[di]，則：

通過該算法，我們同樣可以計(jì)算得到需要的結(jié)果信息。這里我們考慮在問題1情形（不休息），采用初始6人參與分派任務(wù)方式。得到初始安排以后剩余的總?cè)蝿?wù)有828項(xiàng)。計(jì)算得到總共需要安排人員15人。每個(gè)人的任務(wù)安排見表13。人員序號(hào)按工作先后編號(hào)。

問題2情形（含休息和吃飯），我們采用初始6 人分配任務(wù)，采用錯(cuò)時(shí)上班。得到初始安排以后剩余的總?cè)蝿?wù)有828項(xiàng)。計(jì)算得到最終需要17人。

從該結(jié)果來，對(duì)問題1情形，每天總?cè)藬?shù)仍然為15人，但任務(wù)的均衡性得到大大改善，由原來的55.28降為23.42，大大得到改善。對(duì)問題2需要工作和吃飯情形，每天需要總工人數(shù)為17人，而問題2按固定班次計(jì)算總?cè)藬?shù)為19人，這樣按錯(cuò)時(shí)安排，總?cè)藬?shù)比原來問題的總?cè)藬?shù)減少2人，均衡性也比起最小的均衡度35.23小，說明其均衡性也得到改善。

4 模型的評(píng)價(jià)與推廣

對(duì)化工廠安排工人巡檢問題，是一個(gè)具有一般性的調(diào)度安排問題，在實(shí)際中具有重要作用。本文對(duì)問題1采用多TSP劃分區(qū)域，求解后人員使用操作簡單，每個(gè)工作在自己固定區(qū)域巡檢。所建雙目標(biāo)規(guī)劃模型合理地表達(dá)了問題，便于使用和利用模型來驗(yàn)證、求解。

該模型簡單明了，容易理解，可以靈活的運(yùn)用，具有很強(qiáng)的使用價(jià)值，因此可以將該模型推廣于相關(guān)行業(yè)的排班和人員安排。

參考文獻(xiàn)：

[1] 戴朝壽.數(shù)學(xué)建模簡明教程[M].北京：高等教育出版社，2008.

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

[3] 肖華勇.實(shí)用數(shù)學(xué)建模與軟件應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社，2008.