基于改进单亲遗传算法的车辆路径优化问题研究

陈晓桐

摘 要：单亲遗传算法随着种群的进化，单亲遗传算法的突变、逆序、变异使得算法在局部搜索的能力逐步减弱。为了克服该缺点，文中提出了一种基于贪心思想的重组算子。在进化过程中它不断地对父代和子代的染色体进行筛选，保留最优，加快了整体的收敛速度。

关键词：VRP；PGA；贪心算法

DOI：10.16640/j.cnki.37-1222/t.2018.19.182

1 单亲遗算法

单亲遗算法（PGA）是通过选择和变异算子繁衍后代，取消了传统序号编码GA的交叉算子，只在一条染色体上操作基因重组的遗传算法，简化了操作，提高了计算效率，并且不需要出示群体的多样性，也不存在“早熟收敛”，是一种适合求解组合问题的新型遗传算法[1]。

2 单亲遗传算法的改进

引入贪心算法，进行局部调整操作。即在进行变异操作后，对变异后的个体进行适应度值计算，如果适应度大于上一代的适应度值，变异后个体代替变异前个体，否则放弃变异后个体，保留原先个体。通过此种方法的局部寻优，找到局部最优。因此，在求VRP时，既利用单亲遗传算法的优势来确保全局搜索的能力，又利用了贪心算子来保证局部搜索能力。这种混合型算法，不仅使收敛速度得到提高，还能够尽可能快的寻求到问题的最优解。

3 基于改进PGA的VRP问题研究

3.1 问题描述及模型建立

本文研究对象是物流中心，n个零售商，m辆运输车辆，每个零售需求量为Ci。假定每辆车容量为Q，零售商有优先级，配送成本分为固定和可变成本。其优化的目标是在满足需求，求车辆的运货路线，使得总运输成本最低。根据约束条件和参数变量，数学表达式如下：

（1）

s.t

（2）

（3）

当时， （4）

3.2 关键算法的设计

3.2.1 适应度值计算

GA中最重要的数据是适应度值。是进化时优胜劣汰的依据。计算过程如下：

（1） i=1，v=1；（2） 按照个体中零售商编号依次将第i次序的零售商加入到车v的配送路线中；（3）若车v运输货物量总和超过车辆运载量，至步骤4，否则转至步骤2，且i=i+1；（4）将配送路线中的零售商按优先级进行排序；（5）计算车v配送成本；（6） v=v+1；（7）若配送车辆已用完，或者所有零售商都已得到配送，则结束，输出适应度，否则回到步骤2。

3.2.2 变异算子

本文中采用帶贪心算法的基因串逆转算子，具体过程如下：（1）随机选择一段基因串片段；（2）将选择的基因串片段逆序翻转；（3）计算变异后的个体适应度，如果大于变异前个体适应度，则用变异后个体代替变异前个体，否则放弃编译后个体。

3.2.3 改进后的单亲遗传算法的步骤

（1）初始种群的产生；（2）计算初始群体的个体的适应值；（3）保留最优个体；（4）轮盘赌算法选择子代个体；（5）采用贪心算法思想，利用基因串逆转操作进行个体的变异，只将变异后适应度得到改进的染色体保留；（6）完成群体的更新，新群体由保留下来的最优解个体和新的个体组成；（7）将初始设定的代数作为判断运算是否终止的依据，满足终止条件，则终止运算，并输出结果，否则返回到步骤2。

四 实证分析

本文案例中，车辆数量为5，运载量为15，启动成本为30。种群规模取m=30，最大迭代次数为300，零售商的需求量为[1 4 2 1 2 3 4 1 1 2 3 2 1 2 3 4 3 4 2 3 1 4 3 2 4 2 1 4 3 2]，配送优先级为[1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 2 2 2 2]得出配送总成：758.36。

为了验证改进单亲遗传算法在车辆路径问题的优势，本文做了仿真比较。由图2可以看出改进遗传算法的收敛速性和解的精确度方面都高于基本的单亲遗传算。所以改进单亲遗传引入贪心算法，能提前获得大量的优良基因，所花时间、迭代次数和最优结果等方面都优于一般GA。

参考文献：

[1]占焱发.基于遗传算法的物流配送车辆路径问题研究[D].北京交通大学博士学位论文2010.

[2]傅成红.多周期库存路径问题及其算法研究[D].中南大学博士学位论文，2010.