邱 靖，彭莞云，于学媛，吴瑞武

（1.云南农业大学 教务处，云南 昆明 650201；2.云南农业大学 植物保护学院，云南 昆明 650201；3.云南农业大学 基础与信息工程学院，云南 昆明 650201）

GA在交巡警服务平台调度模型的应用

邱 靖1，彭莞云2，于学媛1，吴瑞武3

（1.云南农业大学 教务处，云南 昆明 650201；2.云南农业大学 植物保护学院，云南 昆明 650201；3.云南农业大学 基础与信息工程学院，云南 昆明 650201）

为能更好地解决交巡警服务平台的调度问题，利用图论和遗传算法的理论及方法，建立了交巡警服务平台调度模型。根据具体实验数据，利用该模型找到了交巡警管辖范围分配方案及全封锁的最佳调度方案。得出了服务平台到进出口最远节点的距离为8015.46米，最快需要用时480.93秒才能实现路口全封锁。同时，根据均衡度原则和出警时间最少原则，认为新增交巡警服务平台4个，其具体位置在91，61，66，52 4个节点处。

遗传算法；交巡警服务平台；最短路径；调度模型

1 模型假设

1）出警时道路恒畅通（无交通事故、交通堵塞、天气原因等发生），警车行驶正常，速度恒定为60 km/h；

2）假设区域内的每条道路都是双向通行，不考虑转弯对结果的影响；

3）路口节点即为网络拓扑图中的顶点。

2 最短路径问题理论基础

2.1 图论描述

无向图G（V，A，W）中，V为顶点集合，文献8中A区总共有92条道路，因此V={v1，v2，…，v92}；

2.2 均衡度

国民党在意识形态层面的劣势固然有其先天的缺陷，但与其领袖蒋介石也脱不了关系。正如有论者指出的那样，虽然蒋介石的自我角色定位是豪杰、圣贤、革命领袖，但却缺乏足够的现代色彩。蒋介石是一个缺乏浪漫、幻想和激情的人，其人性格偏向保守、中庸，其政治家个性远胜于革命家气质。上述特质决定了蒋介石是一个缺乏意识形态魅力的领袖。

问题要求交巡警尽快赶到出事地点并且工作量尽量能均衡，说明交巡警到达出事地点的路程短，且每个交巡警平台分配管辖的范围合理。均衡度的定义[8]如式（3）：

式（3）中Ci为Vi的最佳路线，w（Ci）为Ci的权，α0为该巡警服务平台的实际工作量均衡度，α为最大容许工作量均衡度。显然0≤α0≤1，α0越小，说明分组的均衡性越好。

最佳调度方案即寻求一种较合理的最佳路线，使得每个交巡警平台满足均衡性条件。

在交巡警服务平台分配和调度时应遵循以下准则：

1）同一干枝上及其分枝上的点分在同一个交巡警服务平台；

2）离交巡警服务平台最近的点分在一组；

3）一个交巡警服务平台不能太多的点，也即服从均衡度原则。

3 基于遗传算法的交巡警服务平台分配调度模型

遗传算法借助生物进化理论，体现了优胜劣汰思想，通过交叉及变异操作保证了种群的多样性，具有较强的全局搜索能力和并行处理能力[9-10]。而粒子群的编码方式和适应度函数的选择决定了算法的时间和空间复杂度以及搜索性能的好坏。本研究编码方式采用长度可变的实数编码方式，粒子编码由路径经过的节点号决定，染色体的长度为最短路径的节点数，但长度最大为所有节点数，且粒子群中个体不存在重复基因。适应度函数的选择，起点到终点距离最短，适应度函数如式（4）所示：

3.1 初始化种群

随机产生一组粒子群，设置交叉和变异概率以及粒子群的局部和全局最优位置。为保持种群的多样性，产生初始种群采用随机算法。以20个交巡警服务平台（起点）到各个节点（终点）的最短距离。其思路是：以其中一个交巡警服务平台出发，随机选取与该服务平台相连的节点作为下一次搜索的起点，如此循环，直到找到该终点。为避免环路，在算法中设计了一个标记，看这个节点是否被选中，如已选，就搜索另外的节点。

3.2 选择算子

选择算子采用家族内选择和顺序选择方式结合，家族内选择是将适应度最小的两个个体直接进入下一代，不再进行交叉和变异操作，而将适应度值最大的两个个体淘汰。其余的个体进行交叉和变异操作。

3.3 交叉操作

根据交叉概率的值判定粒子是否进行交叉操作，由于最短路径中不存在短路和回路现象，因此采用单点交叉。将两父代个体相同节点后或前的基因组进行交叉，形成新的个体，从而保证了粒子群的多样性。如交叉过程出现回路或短路，则不执行交叉操作。

3.4 变异操作

根据变异概率判定是否对粒子进行变异操作，随机生成i j两个节点（不包括起点和终点）的变异位置，重新搜索一条连接两节点的路径执行变异操作，如变异过程出现回路或短路，则不执行变异操作。

4 模型求解

问题1：根据文献中的数据以及利用遗传算法建立的模型，利用mat lab实现了该算法模型，得到了该A区20个交巡警服务平台的有效管辖分配方案，其分配方案见表1。

表1 20个巡警服务平台管辖范围分配结果表

问题2：主要解决以最快的速度完成对13条交通要道全封锁，问题可以转换为求离交巡警服务平台路程最远的路口路程最短，即时间最少。其最佳调度方案见如表2

表2 交巡警服务平台最佳调度方案

由表2可知，其最长总路程为8015.46米，因此最快需要480.93秒才能实现路口全封锁。

问题3：根据第一问题的分析来看，该区现有的交巡警服务平台的工作量明显不均衡且有些地方出警时间过长等情况，根据服务均衡度的原则及出警时间最少的原则，建立的模型同模型一，得到如下增加平台的具体方案，如表3所示。

表3 增加不同交巡警平台数均衡度和最长出警时间比较

从表3分析来看，增加的服务平台点数为4个更合理，其具体位置为91，61，66，52这4个位置。

5 结束语

研究对交巡警服务平台的分配问题进行了分析，利用遗传算法建立了相应的模型，并得到了较好的分配方案和全封锁方案以及服务平台点数，从分析研究看，该方法对解决最短距离问题具有较强的合理性和实用性。

[1]李妍妍.Dijkstra最短路径分析算法的优化实现[J].测绘与空间地理信息，2014，37（5）:172-173，190.

[2]张慧档，贺昱曜，张奇志.基于混沌神经网络的最短路径路由算法[J].计算机工程，2006，32（17）:12-14.

[3]黎忠文，覃志东，王全宇，等.游戏引擎最短路径搜索优化遗传算法设计[J].计算机应用研究，2014，31（1）:76-79.

[4]夏正冬，卜天明，张居阳.SPFA算法的分析及改进[J].计算机科学，2014，41（6）:180-183，213.

[5]陈香，李璞，刘啸泽.交巡警服务平台的设置与调度[J].Electronic Test，2014（4）:155-157.

[6]张成堂.城市交巡警平台的设置与调度优化模型[J].重庆理工大学学报（自然科学），2012，26（11）:63-69.

[7]2011高教社杯全国大学生数学建模竞赛题目[EB/OL］.[2011-09-09]．http://www.mcm.edu.cn/html_cn/node/a1ffc4c 5587c8a6f96eacefb8dbcc34e.html.

[8]谷云东，赵峰.均衡度公理化定义的改进 [J].模糊系统与数学，2008，22（3）:130-135.

[9]韩丹丹，袁媛.基于银行承兑汇票的Max-NPV项目调度研究[J].西安工业大学学报，2014（9）：755-759.

[10]江涛.基于动态规划框架下的水电系统优化调度[J].西安工程大学学报，2015（4）:420-425.

Application of GA in traffic and patrol police service platform of dispatching model

QIU Jing1，PENG Wan-yun2，YU Xue-yuan1，WU Rui-wu3
（1.Teaching Affairs Office，Yunnan Agriculture University，Kunming 650201，China；2.College of Plant Protection，Yunnan Agriculture University，Kunming 650201，China；3.College of Foundation and Information Engineering，Yunnan Agriculture University，Kunming 650201，China）

In order to better solve the scheduling problem of traffic and patrol police service platform，using the theory and method of graph theory and genetic algorithm，established a patrol service platform scheduling model.According to the specific experimental data，the use of the model had been jurisdiction assignment scheme of traffic and patrol police，and the optimal scheduling scheme of full blockade.It obtained that the farthest node distance of servicing platform to import and export is 8015.46 meters，and it realized the full blockade that the fastest need 480.93.At the same time，according to the principle of balance degree and the least time the police，it consider that traffic and patrol police service platform should be added four platforms，its location in the 91，61，66，52 nodes.

genetic algorithm（GA）；traffic and patrol police service platform；shortest route；scheduling model

TN02

A

1674－6236（2016）15-0032-03

2015-07-24 稿件编号：201507165

邱 靖（1979—），女，四川达州人，硕士，讲师。研究方向：人工智能和计算机应用。