基于混合差分遗传算法的聚类车辆路径问题研究

Study on Clustered VRP Based on Hybrid Differential Genetic Algorithm

针对所有客户被预先分配给若干聚类的聚类车辆路径问题,建立了相应的整数规划模型,提出基于差分进化和遗传算法的两级混合算法。在聚类层,运用差分进化算法进行优化,染色体基于聚类编号进行编码,采用扫描算法初始化种群,结合聚类层的编码特点,设计了基于升序排列的变异算子,在交叉环节考虑传统差分进化算法的缺陷,设计了考虑聚类服务数和装载率的混合交叉算子;在客户层,运用遗传算法进行优化,染色体基于客户编号进行编码,交叉策略采用基因子段的整体交叉,变异时采用位置交换、逆序、插入等策略。最后,利用标准测试库中的实例进行仿真,并与已知最优值进行对比分析,结果表明,算法具有一定的可行性和有效性。

In this paper, in view of the routing problem of all the customer vehicles assigned to certain clusters in advance, we built the corresponding integer programming model, and proposed the bi-level hybrid algorithm based on the differential evolution and GA, according to which, at the cluster level, the differential evolution algorithm was used for optimization purpose, the mutation operator was designed based on ascending sort and considering the inadequacy of the traditional differential evolutionary algorithm in the crossover link, the hybrid crossover operator was designed to account for the quantity of clustering service and loading rate; at the customer level, the GA was used for optimization purpose, the chromosomes encoded based on customer numbering and different strategies adopted during the mutation. At the end, we had a simulation study regarding an empirical case from the standard test library and compared the result with the established optimal value to show the feasibility and validity of the algorithm of this paper.