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

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