基于遗传算法解决线路网巡护问题论述

薛云飞，段 刚

（兰州交通大学，甘肃 兰州 730050）

1 概述

2018年4月16日，美国运筹与管理学会（INFORMS）在其举办的2018商业分析与运筹年会中，表彰了6个队伍，中国石油天然气集团的天然气运输管道优化软件的制作团队就是这六个队伍中的一个。在过去的五年中，中国的天然气总使用量几乎翻了一番，天然气管道长度正以十分迅猛的速度增长。本文针对如何更科学地安排巡护路径来进行研究，采用遗传算法进行算法设计，更科学且贴近实际，能够帮助两区段的巡护管理处节省成本，也能为以后的各线路网维护工作的安排巡护路径工作提供依据，十分具有现实意义。

遗传算法是一种经典的智能进化算法，它是采用模拟生物在自然界中的生存繁衍，逐渐适应其生存环境的方式来获得问题的近似最优值，它会根据问题的目标函数构成一个适应度函数，而问题解的各个可能取值称为染色体，一系列的染色体构成一个种群。这一种群中的各个染色体经过若干代的交叉、变异、选择，逐渐趋于问题的最优解，在满足设定的最大迭代次没有更优值之后进行停止，取值趋向最优解[1]。

2 问题描述及假设

2.1 模型

巡护车辆从起点出发，对所有管道进行维护，每条管道通过的次数必须大于等于1次，每条管道有固定的时间花费，要求制定合理的巡护方案，使得总花费时间最小。

G=（V，E）表示巡护网络，V={0,1,2,...n}，其中 0表示起点，E={（i，j）|i，jV，i≠j}为弧集，Tij表示 vi，vj两点之间的巡护时间,其中vi，vj两点之间存在链且不存在其他点Cij，表示寻护车辆巡护边[Vi，vj]的次数，他要求每条边至少巡护一次。

以上是对简单的巡护模型的目标进行描述，目标函数的意思使得巡护时间最短，且每条边至少要求巡护一次，同时要求能够满足巡护的路径是连续的，由于各种问题要求不同，因此本文未给出详细模型。

2.2 遗传算法算法步骤?

Step1 启动程序，输入参数，使得能够给出一个有N个染色体的初始群体pop(t),其中t=1；

Step2 将群体带入停止规则若停止规则满足，则算法停止；否则，对群体pop(t)中每一个染色体popi(t)计算其适应值；

Step3 从群体pop(t)中随机选一些染色体构成一个种群newpop(t+1)={popj(t)|j=1,2,…,N};

Step4 通过交叉，交叉概率,得到有N个染色体的crosspop(t+1)；

Step5 对每个新个体依变异概率进行变异，形成mutpop(t+1);t=t+1,新的群体pop(t)=mutpop(t);返回步骤2；

Step6 对获得的解的适值进行比较，获得较好的解，输出结果。

3 算例

为了方便理解，本文引入了一个简单的例子，线路网邻接对称矩阵见表1，表示点之间的距离。同时，在本文的基础上，本算例要求线路需要两天内最少巡护一次，且巡护单位巡护完成后要回到出发位置，且工作3～6h之间有休息时间，同时每辆车工作两天至少休息一天。

表1 邻接矩阵

通过本文中描述的过程，得到以下结果：

1）6为始点第一辆车向左巡护6→5→4→3（工作4.5h午休）→2→1总共工作时间7.5h在1休息第二天返回，至此第一辆车工作两天，进行休息；

第三天第二辆车出发巡护向左巡护6→5→4→3（工作4.5h午休）→2→1总共工作时间7.5h在1休息第四天返回，至此第二辆车工作两天，进行休息；

第一辆车第四天休息，第五天继续工作左巡护6→5→4→3（工作4.5h午休）→2→1总共工作时间7.5h在1休息第六天返回；

六天一周期。

2）6为始点第三辆车向右巡护6→7→8→9（工作4.2h午休）→10→11总共工作时间7.2h在11休息第二天返回，第三天休息；

第四辆车第三天从6出发向右巡护6→7→8→9（工作4.2h午休）→10→11总共工作时间7.2h在11休息第四天返回，第五天休息；

第三辆车第四天休息，第五天继续工作向右巡护6→7→8→9（工作4.2h午休）→10→11总共工作时间7.2h在11休息第六天返回；

六天一周期。

结果为总共使用4辆车，巡护时间较短。通过本文，可以较好的得到一个较优的解，能够满足一般巡护需求，因此证明本文能够对今后巡护问题的研究做出一定的贡献。

4 结论

文章旨在对一般的巡护问题进行描述，同时提出了关于巡护问题的见解，对巡护问题的研究解决能够起到一定的作用，巡护问题属于NP问题，构成高质量的启发式算法是十分具有现实意义的，也是今后需要解决的问题。