基于遗传算法的固定费用运输问题研究

吴开信，牟瑞芳

（1.西南交通大学 交通运输学院，四川 成都 610031；2.华侨大学 厦门工学院，福建 厦门 361021）

运输问题是线性规划的重要分支，很多实际问题可以转化为运输模型来求解。简单的线性运输模型仅考虑两组约束条件：即与源节点相关的m个约束条件和与目的节点相关的n个约束条件。固定费用运输问题(FCTP)是运输问题的扩展，它除了要考虑两组约束条件以外，还要考虑每次运输时的固定成本和与运量有关的可变成本，简单的线性运输问题可以看作所有路径的固定成本为零的FCTP问题。简单线性运输问题的解法通常是用表上作业法，对于源节点和目的节点较多的运输问题，表上作业法计算量较大、效率低，而基于遗传算法运输问题的求解将更具有实效性。

由于FCTP问题的目标函数具有不连续性，所以比简单的线性运输问题更难处理，Hirsch和Dantzig证明了其最优解一般在问题约束条件构成的凸集的某个极值点上[1]。在早期的研究中，一些精确解法被运用于求解FCTP问题，如极点排列法和分支定界法等[2]。但这些算法没有充分利用固定费用运输问题的网络特征，只适合于解决规模较小的此类问题。后来一些启发式算法，如拉格朗日松弛法、模拟退火算法等被引入解决FCTP问题，但在实际运用中发现这些算法获得的解质量较差。本文根据FCTP问题的最优解是一个生成树的网络特性，结合遗传算法设计出一种基于运输树的遗传算法，并给出实例得出运用此方法可以快速提高获得最优解的几率。

1 问题的描述

对于FCTP问题，可用以下数学模型表示：

式中：O和D分别表示m个源节点的集合和n个目的节点的集合；cij、fij和xij分别表示源节点i到目的节点j的单位可变成本、总的固定成本和运输数量；条件⑶和条件⑷分别表示产销平衡条件下物资总的供应量和总的需求量，如果是产销不平衡运输问题，可以通过增加一个虚拟产地或虚拟销地转化为产销平衡的运输问题；目标函数表示求总运输成本最小的分配方案[3]。

运输问题可用一个网络二分图来表示，因此可以尝试运用基于运输生成树的遗传算法来进行求解。假设某运输问题有m个源节点和n个目的节点，则FCTP问题的运输网络图具有以下3个特点：①由于约束方程最多有m+n-1个独立方程，即系数矩阵的秩小于等于m+n-1，因此共有m+n-1个基变量，每个变量对应运输表中的1格；②基变量一定能构成1棵运输树，即在运输表中的每一行和每一列中至少存在1个基变量；③基变量不能构成闭合回路。

2 基于运输树的遗传算法

2.1 编码

设集合O表示m个源节点的集合，O={1,2,…,m}，集合D表示n个目的节点的集合，D={m+1,m+2,…,m+n}，则运输网络图中有m+n个节点和mn条边。

运输问题有特殊的数据结构，由图论知识可知，对于1个含m+n个节点的完备图，可以表示(m+n)m+n-2棵标号不同的树，也就是说，我们可以用m+n-2个数字的排列表示m+n个节点的树，其中任何树至少有2片叶子[4]。

在{1,2,…,m+n}共m+n个数字中随机可重复地选取m+n-2个数字按顺序排成1排，构成1个初始染色体，染色体中的基因可以相同。运输树和染色体之间的转换关系按下列法则。

2.1.1 运输树转换成染色体

步骤1：令i是树中最小的叶子节点，j为i的关联节点，选择j为染色体中最右边的数字，再删除节点i和边(i,j)；

步骤2：重复上一步m+n-2次，直至剩下2个节点为止，此时染色体生成。

2.1.2 染色体转换成运输树

设P为一个染色体，S为{1,2,…,m+n}中没有在P里出现的所有数字构成的集合。设i是S中最小的数字，j是P中最左边的数字，重复以下步骤，直至P中没有数字为止。

步骤1：若i∈O和j∈D，则(i,j)构成运输树的1条边，否则选择j后面与i不在同一个集合中的元素k，交换 j 和 k 的位置，此时(i,k)构成运输树的1条边。

步骤2：从S中去掉元素i，若P中仍含有与j相同的元素，则从P中直接去掉元素j即可；否则从P中直接去掉元素 j 后，在S中增加元素j。

步骤3：若P中没有元素了，则S中剩下的最后两个元素构成运输树的第m+n-1条边。

步骤4：分配运行量xij=

步骤5：更新产量ai=ai-xij和销量bj=bj-xij。

步骤6：若没有可行的运量分配，则停止；否则，去掉运量为0的边，对产地r和销地s增加边(r,s)，且xij=ar=bs。

运输树总可以按上面的法则转换为染色体，反之不然，只有可行的染色体才能通过上面的法则转换成运输树。由于初始染色体是从{1，2，…，m+n}中随机可重复地选取m+n-2个数字产生，未必是可行染色体，即初始染色体未必能生成1棵运输树，在此必须根据运输树特殊的数据结构制定可行性准则，对初始染色体进行筛选。

由运输树图形可知，染色体中出现次数为t的基因(节点)与其他节点有t+1个连接，由此对初始染色体可制定以下可行性准则：，其中Lo和LD分别表示染色体中含集合O基因的连接数和含集合D基因的连接数，分别表示集合S中含集合O基因的个数和含集合D基因的个数。

可行性初始染色体可以编制计算机程序在java环境下执行生成。

2.2 适应函数

适应度是1个群体中个体生存机会选择的惟一确定性指标，适应度较高的个体遗传到下一代的概率较大。适应函数可表示为：

2.3 选择策略

采用最优方式实现选择操作，即在父代种群中适应度最大的染色体在子代中至少出现1次，然后按照轮盘赌选择的方式进行选择操作，以保证优良的染色体进入到下一代。

2.4 单点交叉操作

在父代A和父代B中作如下交叉操作：随机选择1个交叉点r，把每个染色体分成2个子集，前面子集中的元素及顺序不变，后面子集相互交换元素。

2.5 变异操作

可使用位移变异法，即在可行染色体中随机选择基因串，插入随机选定的位置。由于变异操作只是产生基因位置的改变，所以变异后的染色体仍然满足可行性准则。

3 实验及其结果分析

某公司下设3个工厂生产某种产品，每日的产量分别是O1=7 t，O2=4 t，O3=9 t，该公司把生产的产品运往4个销售点，各个销售点每日的销量为D4=3 t，D5=6 t，D6=5 t，D7=6 t。已知从各个工厂运往各个销售点的单位可变成本和固定成本见表1，求总运费最少的运输方案。

表1 产量、销量、单位可变成本和固定成本表

求解步骤：

（1）根据题意建立数学模型，确定适应函数。

（2）按可行性规则，在java程序环境下在{1,2,…,7}中随机可重复地选取5个数字生成初始可行性染色体，进而组成初始种群，本文可选取种群规模为30。

如某一个初始染色体为{2,6,3,7,1}时，Lo=6，，即满足可行性规则，对应的运输树见图1，对应的运输分配量见表2。

图1 初始染色体{2,6,3,7,1}对应的运输树

表2 初始染色体{2,6,3,7,1}对应的运输分配量

适应度为：(4×3+95)+(3×10+76)+(3×1+51)+(1×2+65)+(6×4+89)+(3×5+89)=551。

（3）选择操作。父代种群中适应度最大的染色体在子代中至少出现1次，然后按照赌盘选择的方式进行选择操作。

（4）交叉操作。选用单点位移交叉，交叉概率为Pc=1。

如某一个初始染色体为{1,5,2,6,3}时，Lo=6，，即满足可行性规则

对应的运输树见图2，对应的运输分配量见表3。

图2 初始染色体{1,5,2,6,3}对应的运输树

表3 初始染色体{1,5,2,6,3}对应的运输分配量

符合可行性准则的父代染色体通过交叉操作总可产生可行的子代，通过解码得到相应的运输树。

例如：父代1＜2,6,3,|7,1＞和父代2＜1,5,2,|6,3＞通过交叉操作，得到子代1＜2,6,3,|6,3＞和子代2＜1,5,2,|7,1＞。

对于子代1＜2,6,3,|6,3＞，Lo=5，=1，LD=3，=3，满足可行性准则，子代1的解码图见图3。

图3 子代1的解码图

由于x26=0，x36=0，节点7还需求3个单位，而节点1还有2个单位没有分配，节点2还有1个单位没有分配，所以增加边(1,7)和（2,7），x17=2，x27=1。对应的运输树如图4表示。

图4 子代1的运输树

对于子代2＜1,5,2,|7,1＞，Lo=5，=1，LD=4，=2，即满足可行性规则，子代2对应的运输分配量见表4。

表4 子代2＜1,5,2,|7,1＞对应的运输分配量

同理，由于x17=0，x25=0，节点7还需求2个单位，节点6还需求1个单位，而节点3还有3个单位没有分配，所以增加边(3,6)和（3,7），x36=1，x37=2。子代2的运输树见图5。

图5 子代2的运输树

（5）变异操作。使用位移变异规则，变异概率选取Pm=1/6。最大代数目取M=100。通过上述遗传操作过程，可以得出该问题的最优染色体为{3,5,2,6,1}，解码得：x16=6,x17=7,x25=0,x26=4,x34=3,x35=6,目标函数值为508。

4 结论

遗传算法是模拟自然选择和生物进化遗传过程而提出并发展起来的搜素算法，此法能以较大概率寻求到问题的最优解，因而受到不同领域研究人员的重视[5]。本文针对固定费用运输问题的特点提出基于运输树的遗传算法，给出了能表示基解的染色体编码方法，制定了染色体有效性判断规则，并通过计算机程序生成有效初始种群，利用选择、交配、变异规则最终得出满意解。最后运用实例对算法的有效性进行了验证。

[1] Murty KG. Solving the fixed charge problem by ranking the extreme points[J]. Operations Research，1968，16：268-279.

[2] Palekar US, Karwan MK, Zionts S. A branch-and-bound method for the fixed charge transportation problem[J].Management Science，1990，36(9)：1092-1105.

[3] 郭耀煌. 运筹学[M]. 成都：西南交通大学出版社，2000.

[4] 玄光男，程润伟. 遗传算法与工程优化[M]. 北京：清华大学出版社，2005.

[5] 刑文训，谢金星. 现代优化计算方法[M]. 北京：清华大学出版社，1999.