龙源期刊网 http://www.qikan.com.cn
改进遗传算法求解VRP问题
作者：梁佳成
来源：《科技创新导报》2012年第36期
摘 要：用遗传算法（GA）求解车辆路径问题，但总体上他们所得解的质量都不高，这是由GA本身局部搜索能力不强所致.针对GA这一缺陷，该文对标准遗传算法改进，用于求解VRP问题，并通过实验计算证明了该算法具有良好的寻优性能。 关键词：改进遗传算法 VRP 忳能
中图分类号：U491.2 文献标识码：A 文章编号：1674-098X（2012）12（c）-0-01 1 VRP数学模型的建立
问题描述如下：1个物流中心和个客户，第k个客户需运输的货物量为，物流中心派出多辆货车，从物流中心将个客户的所有货物运出，求满足货运需求的最短距离车辆运输行程路线。设物流中心派出m辆货车，每辆货车的载重量为q，且q>gi，表示点i到点j的运输成本，物流中心的编号为0，各客户的编号为，另外几个变量定义如下： 货车s由i驶向j；点i的货运任务由s货车完成
由这些参数和变量可以求出VRP问题的数学模型表示为：
每辆货车的载货量不超过车辆载重量；保证通过每一个客户有且仅有一辆车，所有车从物流中心出发，最后回到物流中心；确保每个客户的运输任务仅由1辆货车来完成，所有的运输任务则由m辆货车协同完成。 2 遗传算法改进
改进交叉概率pc和变异概率
fmax是种群中最大的适应度值，favg每一代种群的平均适应度值，fmin每代种群中最小的适应度值，f'要交叉的两个个体种较大的适应度值，f要变异个体的适应度值。，取（0，1）区间的值，在优化过程中，根据需要不断调整。
改进后的交叉概率和变异概率能够随适应度自动改变，够较高的概率产生出较大多样性的子代，即能够高概率产生适应度更高的新个体，使得它们不会处于一种近似停滞不前的状态，从而使算法跳出局部最优解。 3 算法实例计算
龙源期刊网 http://www.qikan.com.cn
采用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。
由以上的试验结果可以看出，采用改进的遗传算法与普通遗传算法分别求解上面应用实例，改进遗传算法优化结果明显优于普通遗传算法。这说明标准遗传算法中标准选择，交叉，变异算子在求解VRP问题时搜索能力较差。将整数编码、改进交叉算子引入改进标准遗传算法后，算法的搜寻能力明显加强，收敛性显著提高，仿真试验结果证明改进后算法的可行性和有效性。 参考文献
[1] 李军，郭耀煌.物流配送车辆优化调度理论与方法[M].中国物资出版社，2001. [2] 欧阳森，王建华，耿英三，等.一种新的改进遗传算法[J].计算机工程与应用，2003，39（11）.