朱 颢

（湖州职业技术学院，浙江 湖州 313000）

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

朱 颢

（湖州职业技术学院，浙江 湖州 313000）

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

聚类车辆路径；差分进化算法；遗传算法；混合交叉算子；装载率

1 引言

车辆路径问题（VRP）属于一类经典的组合优化问题，也是NP难问题，自1959年被Dantzig和Ramser[1]首次提出以来，一直受到国内外研究者的广泛关注。聚类车辆路径问题（the Clustered Vehicle Routing Problem，CluVRP）作为有能力约束车辆路径问题（CVRP）的一个变种，由Sevaux M和Sörensen K[2]于2008年首次提出，主要基于如下假设：所有的客户根据其地理位置被预先分成若干个聚类；当某辆车访问某个聚类时，必须连续不断地访问该聚类里的所有客户，只有当其中的每一个客户均被访问完毕，车辆才能返回车场或者访问下一个聚类。……