张亚楠 王浩鑫
西安理工大学 710048
摘要
本文解决的是在不同条件下确定某县所有乡（镇）、村巡视的最优路线，将公路网图抽象为一个赋权图G，然后转化为最佳旅行商问题。
对于问题一，首先依据一定规则将图G划分为三个较均衡的子图，然后在每个子图运用改良圈算法求最佳旅行商回路，并检验三组间路程均衡度，若不满足要求则根据一定调整规则调整分组，直到满足要求。本文得到的最短总路程为602.7公里。
对于问题二，在24小时之内完成巡视的条件下，我们使在各组巡视时间尽可能均衡，得到组数下限为4组。在分4组的情况下采用与问题一相同的求解思路得出最优巡视路线。完成巡视的时间分别为22.59小时、22.64小时、22.95小时、23.20小时。
一、问题重述
1.1需要解决的问题
根据公路网示意图（公路边的数字为该路段的公里数），解决以下问题：
问题一：若分三组（路）巡视，设计总路程最短且各组尽可能均衡的巡视路线。
问题二：假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间t=1 小时，汽车行驶速度V=35 公里/小时。要在24 小时内完成巡视，至少应分几组？给出这种分组下你认为最佳的巡视路线。
二、问题分析
2.1问题一的分析
先计算所有乡（镇）、村到县镇府的最短路径，并画出路径图，以县政府O为顶点分为三部分，分别在每部分计算最优旅行商回路；再调整三部分的划分，原则是使其更均衡。
2.2问题二的分析
在各组巡视路线尽可能均匀的前提下，首先判断组数的下限值，得出最少为4组，然后将问题一路径图分为4组，采用问题一的思想求解最佳巡视路线。
三、模型假设
1.假设所有乡（镇）、村及县政府在同一平面；
2.假设不考虑公路受灾害损坏情况；
3.假设邻县村可以经过且无需停留。
.png)
.png)
.png)
5.1.2根据检验结果调整分组
本文制定如下调整规则：
①参考已得的回路路径；②路径较长的组的部分巡视任务分给路径较短的组；③在巡视区域相邻的组间进行调整，且在区域的边界处调整。
再次采用最优旅行商回路求解方法，求得最优回路。
计算均衡度为a=11.73%
均衡度变大，但没有超出范围，但调整分组后的总路程变小，所以最短总路程为602.7公里。
.png)
本文通过改良圈算法中的二边逐次修正法来求解四个子图的最优旅行商回路，由MATLAB计算的回路路径及其所用时间。
.png)
（3）均衡度检验
代入表6.2时间值，根据问题一的均衡度定义，得出a=2.6%
6.1.3根据计算结果调整分组
若均衡度不满足要求，则制定如下调整规则：
①参考图6.3已得的回路路径；②所用时间较长的组的部分巡视任务分给所用时间较短的组；③在巡视区域相邻的组间进行调整，且在区域的边界处调整。
6.1.4结果分析
表6.2每组的时间均小于24h，且均衡度较小，所以采用图6.2划分方式及回路路径。
特殊情况T=0，t=0时，巡视时间的均衡度只受V的影响。
因此为了尽快完成巡视任务，在确定最佳巡视路线方案时，各组所分配的路程、乡村尽可能均衡，减少停留时间t、T和提高速度是提高巡视效率比较好的办法。 十、参考文献
主要参考文献：
[1]司首奎,孙兆亮.数学建模算法与应用第2版.国防工业出版社