求解车辆路径问题的协同进化遗传算法

姚卫粉

摘要：通过对车辆路径问题的分析，建立车辆路径问题数学模型。针对遗传算法优化车辆路径问题易陷入局部最优解以及收敛速度慢等问题，引入基于动态小生境的协同进化模型。最后，将动态小生境协同进化算法应用于所建立的模型中。实验结果表明：动态小生境协同进化遗传算法可有效避免遗传算法的早熟现象，并在一定程度上提高优化车辆路径问题的求解效率。

关键词：车辆路径问题；协同进化遗传算法；动态小生境；早熟

DOIDOI：10.11907/rjdk.143490

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2015）001005702

0 引言

车辆路径问题（Vehicle Routing Problem，VRP）由Dantzig 和Ramser[1]于1959年第一次提出。该问题是指在客户需求位置已知的情况下，确定车辆在各客户间的行程路线，然后使得车辆路线最短或运输成本最低。车辆路径问题是个NP难题，在寻找满足约束条件最优解的过程中，需要很大的设计空间。设计空间是多维而非连续的，所以用来系统的搜索整个空间的规范搜索集很难找到，导致很难得到全局最优解。关于车辆路径问题的优化算法大致可以分为两类，一类是精确算法，另一类是启发式算法。目前，针对车辆路径问题，主要采用启发式算法。比如，树状搜寻法[2]、节省法[3]、扫描法[4]、遗传算法[5]等。由于精确算法难以用于求解复杂的车辆路径问题，而启发式算法也只是基于直观或经验构造的算法，所以只能求出问题的某一特殊类型或者是规模较小时的近似最优解。由于这些问题的存在，本文将基于动态小生境的协同进化遗传算法引入到车辆路径问题中，从而更好地解决车辆路径优化问题。

1 车辆路径问题数学模型

对于单配送中心问题，设配送中心共有N个客户，1个中心仓库，K辆车。每个客户的需求量和时间窗都有固定的限制，且均只被某辆车服务一次，每辆车只服务于一条路径。每辆车载重为Q且从配送中心出发，服务所有客户后回到配送中心。建立数学模型如下：

minZ=∑ni=0∑nj=0∑kk=1CijXijk（1）

∑ni=1qiyik≤Q；k=1，…，K（2）

∑Kk=1y0k=K（3）

∑Kk=1yik=1；i=1，…，n（4）

∑ni=1xi0k=1；k=1，…，K（5）

∑ni=0xijk=yjk；j=1，…n；k=1，…，K（6）

∑nj=0xijk=yik； i=1，…，n；k=1，…，K（7）

上述模型中，Z为运输距离；i，j为客户编号；n为客户量，k为车辆的顺序；Cij为从点i到点j的费用；xijk为1时，表示车辆从i出发到j，否则为0；需求点i的需求量为qi，yik为1时表示客户i的任务由车辆k来完成，否则为0。

式（1）表示以运行总成本最低的目标函数；式（2）保证车辆装载货物的总重量不超过车辆的载重；式（3）为每辆车都从配送中心出发；式（4）为每个客户指被一辆车服务并且所有的车都得到服务；式（5）为车辆完成任务后回到配送中心。

2 基于动态小生境的协同进化模型

协同进化是指生物与生物、生物与环境之间在进化过程中的相互依赖、相互协调的依存关系。动态小生境集具有共享和协同进化的优点，通过进化过程形成峰值就是小生境，对于所有个体利用动态来分类这个峰值就是动态小生境。动态小生境集的动态性体现在种群被动态地分为若干个子种群，小生境的动态性由小生境的核心部分决定。协同进化模型能够自动的实现小生境的定位，这个动态模型能够消除分布不均匀的优化解，所以能够加快计算的速度，进而加快了各子种群的进化速度。

动态小生境的协同进化模型如图1所示。

图1 基于动态小生境的协同进化模型

3 动态小生境协同进化遗传算法

（1）编码设计，生成初始种群。此问题采用自然数编码，这种编码比较直观，能够保证算法的性能，减小了编码后的计算量。

（2）适应度计算。染色体编码的欧式距离为：

d（cx，cy）=∑Lk=1（cx-cy）2（8）

其中，cx，cy为任意的两条染色体，k为个体索引，L为染色体长度。

个体cx相对于个体cy的共享函数为

sh（d（cx，cy））=1-d（cx，cy）ασ0，0

其中，σ0为定义的小生境峰半径，α为共享函数的形状参数，α>0。

小生境数为：

mdsh，j=∑Nyshdcx，cy，x=1，…，N.（10）

N为种群规模大小。动态小生境的动态适应度函数为：

fdsh，i=fimdsh，i，其中，fdsh，i和fi为共享适应度和初始适应度。

染色体交叉操作示例如图2所示。

（3）操作算子。①选择算子——选择算子采取线性排序选择策略同时采取排挤机制的选择策略，保留精英个体；②交叉算子——通过交叉算子可以调整车辆路径，交叉操作是在两个完全不同的个体之间进行的，具体的交叉操作如图2：③变异算子——因为变异的可能性很小而且变异只起到辅助作用，所以对每代种群以变异概率pm进行变异，交换两点基因值。

图2 染色体交叉操作示例

4 实验分析与结论

为了检验动态小生境协同进化遗传算法的性能，下面用该方法对车辆路径优化问题中的典型测试问题F系列：F-70， F-120和C系列：C-50， C-140等4个问题进行仿真实验。结果见表1和表2。

根据基于动态小生境的协同进化遗传算法对车辆路径优化测试问题的仿真实验结果及其与其它优化方法的对比结果表明，这种改进算法对车辆路径优化显现出了良好的优化性能，优化结果明显优于常规遗传算法，为车辆路径优化问题的解决提供了一条可供借鉴的新思路。