遗传算法在车间物流配送优化中的应用

时 振，李壮阔（桂林电子科技大学，广西 桂林 541004）

1 车间物流配送优化问题的动态规划模型

假设配送中心有K辆搬运设备，每辆搬运设备的载重量为Qk（k=1,2,…,K），其一次配送的最大行驶距离为Dk，需要向L个加工点送货，每个加工点的需求量为qi（i=1,2,…,L），加工点i到j的运距为dij，配送中心到各加工点的距离为d0j（ij=1,2,…,L）。再设nk为第k辆搬运设备配送的加工点数（nk=0表示未使用第k辆搬运设备），用集合Rk表示第k条路径，其中的元素rki表示加工点rki在路径k中的顺序为i，令rk0=0表示配送中心，则可建立如下车间物流配送优化问题的数学模型：

车间物流配送采用动态规划模型，总体描述为：从配送中心用多辆搬运设备向多个加工点送货，每个加工点的位置和需求量一定，每辆搬运设备的载重量一定，要求合理安排搬运设备路线，使总运距最短，并满足以下条件：

（1）每条配送路径上各加工点的需求量之和不超过搬运设备载重量；

（2）每条配送路径的长度不超过搬运设备一次配送的最大行驶距离；

（3）每个加工点的需求必须满足只能由一辆搬运设备送货。

考虑了上述车间物流配送优化问题的约束条件和优化目标后，开始建立车间物流配送优化问题的数学模型，描述如下：

上述模型中，式（1）为目标函数；式（2）保证每条路径上各加工点的需求量之和不超过搬运设备的载重量；式（3）保证每条配送路径的长度不超过搬运设备一次配送的最大行驶距离；式（4）表明每条路径上的加工点数不超过总加工点数；式（5）表明每个加工点都得到配送服务；式（6）为每条路径的加工点的组成；式（7）限制每个加工点仅能由一辆搬运设备送货；式（8）为当第k辆搬运设备服务的客户数≥1时，说明该辆搬运设备参加了配送，则取sign（nk）=1，当第k辆搬运设备服务的客户数＜1时，表示未使用该辆搬运设备，因此取sign（nk）=0。

2 车间物流配送优化问题的遗传算法

遗传算法以群体中的所有个体为操作对象，每个个体对应研究问题的一个解。选择、交叉和变异是遗传算法的三个主要操作算子，另外还有编码方法、初期群体的确定和适应性评估等因素，针对车间物流配送优化问题的特点，构造出求解该问题的遗传算法。

（1）编码方法的确定。根据车间物流配送优化问题的特点，笔者采用了简单直观的自然数编码方法，用0表示配送中心，用1、2、…、L表示各加工点。由于在配送中心有K辆搬运设备，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心。为了在编码中反映车辆配送的路径，采用了增加K－1个虚拟配送中心的方法，分别用L+1、L+2、…、L+K－1表示。这样，1、2、…、L+K－1，这L+K－1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有7个加工点，用3辆搬运设备完成配送任务的问题,则可用1、2、…、9（8、9表示配送中心），这9个自然数的随机排列，表示物流配送路径方案。如个体129638547 表示的配送路径方案为：路径 1：0－1－2－9，路径 2：9－6－3－8，路径 3：8－5－4－7－0，共有 3 条配送路径；个体 573894216 表示的配送路径方案为：路径 1：0－5－7－3－8，路径 2：9－4－2－1－6－0，共有 2 条配送路径。

（2）初始群体的确定。随机产生一种1～L+K－1，这L+K－1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。

（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个加工点都得到配送服务及每个加工点仅由一辆搬运设备配送的约束条件，但不能保证满足每条路径上各加工点需求量之和不超过搬运设备载重量及每条配送路线的长度不超过搬运设备一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示：

式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。

（4）选择操作。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N－1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法产生。具体地说，就是首先计算上代群体中所有个体适应度的总和（ΣFj），再计算每个个体的适应度所占的比例（Fj/Σ Fj），以此作为其被选择的概率。这样的选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。

（5）交叉操作。对通过选择操作产生的新群体，除排在第一位的最优个体外，另N－1个个体要按交叉概率Pc进行配对交叉重组。笔者采用了一种类似OX法的交叉方法，现举例说明：①随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=47|8563|921，B=83|4691|257；②将B的交配区域加到A的前面，A的交配区域加到 B 的前面，得:A′=4691｜478563921｜，B′=8563｜834691257｜；③在 A′、B′中自交配区域后依次删除与交配区相同的自然数，得到最终的两个个体为：A″=469178532，B″=856349127。与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持群体的多样化特性有一定的作用。

（6）变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的多样化，采用了连续多次对换的变异技术，使个体在排列顺序上有较大变化。变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J，对所需变异操作的个体的基因进行J次对换（对换基因的位置也是随机产生的）。

3 用matlab程序进行实验计算和结果分析

根据上述遗传算法编制了matlab程序，并对一个某配送中心使用2辆搬运设备对8个加工点进行送货的车间物流配送优化问题实例进行了实验计算。设搬运设备的载重量为8×103kg，每次配送的最大行驶距离为40km，配送中心与各加工点之间、各加工点相互之间的距离及各加工点的需求量见表1。根据上述实例的特点，在实验计算中采用了以下参数：群体规模取20，交叉概率和变异概率分别取0195和0105，进化代数取50，变异时基因换位次数取5，对不可行路径的惩罚权重取100km。对上述问题，利用计算机随机求解10次，得到的计算结果见表2。

表1 配送中心与加工点之间的距离（/km）及各加工点的需求量

表2 车间物流配送优化问题的遗传算法计算结果

从表中数据可以看出，10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km，其对应的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0。可见，利进遗传算法可以方便有效地求得车间物流配送优化问题的近似最优解。

4 结 论

合理确定车间物流配送是提高服务质量、降低配送成本、增加经济效益的重要手段，而采用启发式算法求解是车间物流配送优化问题重要的研究方向。因此，笔者构造了求解车间物流配送优化问题的遗传算法模型，而且实验结果也表明，遗传算法是一种性能优良的启发式搜索算法，利用该方法可以方便有效地求得物流配送路径优化问题的近似最优解。同时对解决类似的组合优化问题具有一定的参考价值。

[1]陈国良，王煦法,等.遗传算法及其应用[M].北京：人民邮电出版社，1996.

[2]姜大立，杨西龙，杜文.车辆路径问题的遗传算法研究[J].系统工程理论与实践，1999,19(6):40-44.

[3]蔡希贤，夏士智.物流合理化的数量方法[M].武汉：华中工学院出版社，1985.