交通网络中路径求解遗传算法设计研究

Study on Genetic Algorithm for Finding Path in Traffic Network

交通网络最短路径集合的获得在交通网络计算中具有很重要的作用,然而现有的算法大部分没有考虑交叉口延误,并且不适用于路径集合的计算,求解大型网络效果不理想.针对这一问题对遗传算法的编码方法进行分析,考虑编码空间及路径解空间的大小,采用了基于路径的编码方法;并采用一种考虑节点有延误的变异方法,克服了此种编码方法变异操作的复杂性.最后利用网络随机发生器产生了一组网络,利用设计的算法及基于优先权的遗传算法分别进行了求解,并对两种算法的计算结果进行了对比分析,说明了该遗传算法的有效性.

Obtaining of the shortest path set plays an important role in traffic network calculation.However,most of existing algorithms do not consider the delay in the intersection and are not suitable for finding path set,and the effect of them is not ideal.By considering above problems,the encoding method of genetic algorithm（GA）is analyzed and encoding space and solution space are compared.After that,the encoding method based on path is adopted and a mutation operator is designed considering the intersection delay to overcome the complexity.At last,the designed GA and the GA of priority-based encoding method are used in a group of networks,which are generated by using a random network generator,and the calculation results of them are also analyzed.The result verifies the efficiency of the designed GA.