摘 要: | 针对社区疫情防控的消杀作业路径优化问题,设计了一种基于模拟退火算法的启发式算法.首先,提出用于面型消杀任务的作业工艺,建立了问题的整数规划模型;然后,针对问题特点开发了基于模拟退火算法的启发式算法,使用一种可以根据问题规模改变解空间大小的解结构,设计了多种类型的解更新操作,利用Floyd算法计算优化目标值,通过Metropolis准则接受新解.多规模对比计算实验表明:所提出的模拟退火算法在小规模算例的平均求解结果与精确解相差在4%以内,在中规模算例的求解结果比CPLEX平均优化10%~40%,在大规模算例的求解结果比贪婪算法平均优化60%~80%,因此当求解此类问题时该算法能在合理的时间内取得较优的结果.
|