巡检线路的哈密顿圈分割模型及算法

Segmentation Model and Algorithm of Hamiltonian Cycle in Patrol Line

为求解带有时间周期约束和任务均分的多旅行商问题(MTSP),根据图论基本原理,借助最短距离树,结合贪婪算法和几何启发式算法,采用哈密顿圈分割覆盖的方法,建立了任务均分的巡检路线安排优化模型,设计了求解近似最优解的算法步骤,计算出近似最优的巡检人数和巡检路线安排,并计算了每位巡检人员的实际工作时间、巡检冗余时间和平均工作时间。进一步分析了不休息、休息、用餐等不同情形下的人员安排、巡检路线和工作量等情况。

To resolve the MTSP issue that is limited by time and in which tasks are averaged,an optimization model for a patrol line arrangement of averaged tasks was built by using the shortest path tree and combining greedy algorithm and the geometric Manhattan Distance and adopting segmentation and covering of Hamiltonian cycle,and steps of algorithm were designed to solve near optimum solution to calculate approximately optimal quantity of patrol persons and patrol route arrangement.And actual working time and redundant time on patrol and average working time of every patrol personnel were worked out.Further,person arrangement,patrol route and workload were analyzed under working,rest and dining.