陈晓桐

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

关键词：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，零售商有优先级，配送成本分为固定和可变成本。其优化的目标是在满足需求，求车辆的运货路线，使得总运输成本最低。……