最佳灾情巡视路线的数学模型

本文将求最佳巡视路线问题转化为图论中求最佳推销员回路的问题,并用近似算法去寻求近似最优解。对分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分组的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路,对问题1得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为 216.4公里,191.1 公里,192.3公里,总路程为599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时,对问题3,求出完成巡视的最短时间为6.43 小时,并用较为合理的分组的准则,分成 22个组。对问题 4,研究了在不影响分组的均衡条件下,T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。