本站原创摘 要：用遗传算法（GA）求解车辆路径问题,但总体上他们所得解的质量都不高,这是由GA本身局部搜索能力不强所致.针对GA这一缺陷,该文对标准遗传算法改进,用于求解VRP问题,并通过实验计算证明了该算法具有良好的寻优性能.
关 键 词 ：改进遗传算法能
中图分类号：U491.2 文献标识码：A 文章编号：1674-098X（2012）12（c）-0-01
1.数学模型的建立
问题描述如下：1个物流中心和个客户,第k个客户需运输的货物量为,物流中心派出多辆货车,从物流中心将个客户的所有货物运出,求满足货运需求的最短距离车辆运输行程路线.设物流中心派出m辆货车,每辆货车的载重量为q,且q>gi,表示点i到点j的运输成本,物流中心的编号为0,各客户的编号为,另外几个变量定义如下：
货车s由i驶向j；点i的货运任务由s货车完成
由这些参数和变量可以求出问题的数学模型表示为：
每辆货车的载货量不超过车辆载重量；保证通过每一个客户有且仅有一辆车,所有车从物流中心出发,最后回到物流中心；确保每个客户的运输任务仅由1辆货车来完成,所有的运输任务则由m辆货车协同完成.
2.遗传算法改进
改进交叉概率pc和变异概率
fmax是种群中最大的适应度值,fg每一代种群的平均适应度值,fmin每代种群中最小的适应度值,f'要交叉的两个个体种较大的适应度值,f要变异个体的适应度值.,取（0,1）区间的值,在优化过程中,根据需要不断调整.
改进后的交叉概率和变异概率能够随适应度自动改变,够较高的概率产生出较大多样性的子代,即能够高概率产生适应度更高的新个体,使得它们不会处于一种近似停滞不前的状态,从而使算法跳出局部最优解.
3.算法实例计算
采用matlab 6.0进行程序仿真,以9个客户为例进行求解.
9家客户（依次用1,2,等,9来表示）之间的距离（km）如表1所示,各客户的需求量（kg）如表2所示.每辆货车的容量为12 t,在保证车辆不超载,并且保证每家客户的送货量的前提下,找出对这9家客户进行配货的最短路径.
参数初始化：
（1）车辆数
按照参考文献对m进行评估.
其中,[ ]表示对括号内的数字取整,0< （2）进化代数G等于50,初始群体p等于50,pw等于1000. （3）车辆载重限制等于12 t 改进遗传算法运行总距离746 km,普通遗传算法运行总距离830 km. 由以上的试验结果可以看出,采用改进的遗传算法与普通遗传算法分别求解上面应用实例,改进遗传算法优化结果明显优于普通遗传算法.这说明标准遗传算法中标准选择,交叉,变异算子在求解问题时搜索能力较差.将整数编码、改进交叉算子引入改进标准遗传算法后,算法的搜寻能力明显加强,收敛性显著提高,仿真试验结果证明改进后算法的可行性和有效性.