巡檢線路排班的優化模型

曹西林

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

關鍵詞：巡檢；TSP模型；最優路線；優化模型

中圖分類號：TP391 文獻標識碼： A 文章編號：1009-3044（2018）19-0234-02

1 問題提出

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

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

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