基于改进遗传算法的车辆调度系统
摘 要
遗传算法是近年来发展比较迅速的一种优化算法，旨在解决很多NP完全的问题，本文基于遗传算法以及传统的运行商问题进行了叙述，然后针对车辆调度这一现实问题进行模型构建，接着通过利用遗传算法在编码、选择、交叉、编译操作的具体实施，最后通过测试对比得到良好的结果。
【关键词】遗传算法 车辆调度 交叉 变异
1 相关知识介绍
旅行商问题（Traveling Salesman Problem， 汽车调度），是一个著名的组合优化问题，该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决汽车调度问题在计算理论和实际应用上都有很高的价值。本文主要介绍了应用遗传算法来解决汽车调度问题。
2 车辆调度问题的模型与描述
汽车调度问题也可以看成是旅行商问题的一种，该问题主要描述为n个城市（地点），以及城市之间的两两距离，使得汽车在经过城市之间进行调度时能够使得运行距离最短并能够保证完成调度任务。简单的说就是寻求一组能够通往各个地点之间的最短路径集合。
搜索整数子集X = {1，2，…，n} （X 集合表示1-n编号的地点） 的一个排列л（X） = {v1，v2，…，vn}，使
T= ∑d（vi，vi+1） + d（vi，vn）
取最小值。式中的d （vi，vi +1） 表示城市vi 到城市vi+1的距离。
3 对汽车调度的遗传基因编码方法
在求解汽车调度问题时，本文提出了基于顺序表示（ordinal representation）的遗传基因编码方法。该方法首先将城市几何排列成一个顺序表，对于一辆车经过的一条路径，可以顺序的经过每一个城市，而所经过的城市的顺序可以看做是一个遗传因子的表现形式，当没经过一个城市的时候，该城市节点就从该顺序表中被剔除出去，当所有的城市都被处理过后，把上面的遗传因子连接组合起来构成一段基因，比如，顺序表C = （1，2，3，4，5，6，7，8，9），一条旅程为5-1-7-8-9-4-6-3-2。按照这种编码方法，这条旅程的编码为表L=（5 1 5 5 5 3 3 3 2 1）。
4 选择、交叉算子
每个基因个体的适应度以比例的形式转换为被选中的概率，将轮盘划分成n个扇区并进行n次选中，这样会产生n个0到1之间的随机数，每个随机数会指示轮盘中的某一个随机位置，而指向位置的扇区表明该对应个体被选中，所以适应度越高扇区就会越大，这样被选中的概率就会越高。
单点交叉又称为简单交叉，是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉运算的示意图如图1所示。
5 实验结果
10个点的汽车调度问题的测试数据如下：
0 ，23 ，93 ，18 ，40 ，34 ，13 ，75 ，50 ，35 ，
23 ，0 ，75 ，4，72 ，74 ，36 ，57 ，36 ，22 ，
93 ，75 ，0 ，64 ，21 ，73 ，51 ，25 ，74 ，89 ，
18 ，4 ，64 ，0 ，55 ，52 ，8 ，10 ，67 ，1，
40 ，72 ，21 ，55 ，0 ，43 ，64 ，6，99 ，74 ，
34 ，74 ，73 ，52 ，43 ，0，43 ，66 ，52 ，39 ，
13 ，36 ，51 ，8 ，64 ，43 ，0 ，16 ，57 ，94 ，
75 ，57 ，25 ，10 ，6 ，66 ，16 ，0 ，23 ，11 ，
50 ，36 ，74 ，67 ，99 ，52 ，57 ，23 ，0 ，42 ，
35 ，22 ，89 ，1 ，74 ，39 ，94 ，11 ，42 ，0 ，
采用遗传算法求解汽车调度的结果如表1。
6 结论
从上面的测试可以进一步证明，在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地产生新个体。虽然随着群体的进化过程会产生越来越多的优良个体。最终的结果也是收敛的，可见通过利用遗传算法可以很好的解决汽车调度问题。
参考文献
[1]王小平，曹立明编著.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社，2002.1.
[2]周明，孙树编著.遗传算法原理及应用[M].北京：国防工业出版社，1999.6.
[3]谢政，李建平编著.网络算法与复杂性理论[M].长沙：国防科技大学出版社，1995.
[4]陈国良等.遗传算法及其应用[M].北京：人民邮电出版社，1995.
[5]刘勇等.非数值并行算法（二）——遗传算法[M].北京：科学出版社，1995.
[6]刘值义等.遗传学[M].北京：人民教育出版社，1982.
作者简介
冯浩然（1991-）男，云南省保山市人。现为公安海警学院在校大学本科生，主修专业为电子信息工程。
作者单位
公安海警学院 浙江省宁波市 315801
