（计算机软件与理论专业论文）用智能优化算法求解固定费用运输问题.pdf

，m 勺够，_ ，= l ，2 ，n f = 1 勺o ，f = l ，2 ，m ：= 1 ，2 ，n 舯酬2 忙裟 ( 1 1 9 ) ( 1 2 0 ) ( 1 2 1 ) 其中疗 ) 可看作原运输问题的目标函数，从源点f 到目的结点，的总单位运输 成本；幽表示与路径( f ，) 相关的固定成本；f 是一个0 1 变量，用来描述源 点i 到目的结点j 的运输活动是否发生；xi 劫是在路径( f ，) 上的未知运输量； 口f 表示源结点f 的可用能力；6 ，表示目的结点7 的需求。 f c t p 问题的难点主要在于参数朋和，z 的大小。k e 肌i n 垂o n 和u n g e r 报道了实 例难度与最优解的f c 比例( 固定成本与可变成本之比) 之间的强对应关系，指明 f c 【3 ，l o 的问题更难【5 i 。p a l e k a r ，k 删a n 和z i o n t s 提出了f c 比例可由难度比例 d 伽+ 刀一1 ) 勿近似代替，其中d 是所有需求的总和，万和刀分别是平均可变成本 和平均固定成本。试验结果表明最难实例的c 3 0 ，6 0 】。 固定费用运输问题是一个n p - h a r d 问题【7 】。h i r s c h 和d a j l t z i g 首先研究并证明 了f c t p 的最优解在问题约束条件构成的凸集的某个极点上【8 】，即最优解是运输图 的一棵生成树。求解f c t p 最常用的方法是将其构造成一个混合整数网络规划问题 来求解。一些精确算法用于求解f c t p ，如割平面法f 9 】，极点排列法【lo 】或分枝定 界法j 等，但这些方法均未利用f c t p 特殊的网络结构，被证明既低效又耗时， 只适合求解较小规模问题。 为了克服计算时间过长的问题，一些启发式方法用于求解f c t p ，如l a 野a n g e 松驰法【12 1 ，邻接极点法【l3 】等。虽然这些方法计算耗时较少，但所获得的解的质量 较差，在实际应用中会消耗很多不必要的费用。 近年来，一些现代启发式遗传算法用于求解f c t p 。m i c h a l e w i c z 等人首先讨 论了使用遗传算法来解决线性和非线性运输问题，使用矩阵来构建染色体的表示。 他们设计了基于矩阵的杂交和变异编码的遗传算法【1 4 j ；g o t t l i e b 和p a u l m a n n 提出 了基于矩阵排列编码的遗传算法【1 5 j 。s u i l 等提出了禁忌搜索启发式方法【1 6 】。g e n 和l i 使用树型编码的p r u f e r 数( p r u f e rn u m b e r ) 作为设计染色体的可行性标准， 提出了用p r n f e r 数编码运输的遗传算法【 】。但g o t t l i e b ，r a i d l 等证明：在用p n i 衙 数编码生成树的遗传算法中，单点交叉的遗传性和变异操作的区域性都较低，当 问题规模较大时，p m f e r 数编码方法很难获得最优解或近似最优解，解的质量随问 题规模的增大而急剧下降【l8 1 。r a i d l 提出了利用边集编码的遗传算法，用聊+ 咒1 条 边表示生成树【19 1 。苏生、战德臣等提出了采用集中邻域搜索机制和局别最优逃逸 机制的遗传局部搜索算法【2 0 1 和基于有序边集编码的遗传算i ! 去【2 ，这是目前国内最 新的研究成果。 1 2 2 多目标运输问题 多目标运输问题( m u l t i p l e o b j e c t i v e 缸锄s p o r t a t i o n p r o b l e m ，简称m t p ) 在经济 决策中，往往需要多个目标的表示。一般来说，可以考虑包含所有目标的效用体 系的最大化。然而，模型的使用经常需要有关结构性的或中间目标的具体规范。 或许，需要设计目标的相对重要性，或关于单个或多个目标所要求( 允许) 达到 的最小( 最大) 化水平规范，且要求这类规范最小化。 在一般运输问题中，目标是最小化总运输成本。基本假设是：管理主要与成 本最小化相联系。但这个假设并不总是有效的。g e n ，l i 和i d a 【2 ，3 4 】认为，在运输问 题中可能有多个目标。例如：运输计划合同的履行，联合合同的履行，提供各类 工厂和运输队稳定的雇工水平，许多工厂问工作的平衡，运输风险最小化和成本 最小化。 在运输问题中，例如：最小化运输成本、最小化对于优先顾客的平均装运时 间、最大化生产量、最小化燃料消耗等多目标，在实际情况下往往是必要的。一 般地说，一个多目标线性规划问题可以写成： 所戤z ，= 一z( 1 2 2 ) m a x 勿= c 2 工( 1 2 3 ) ( 1 2 4 ) m a x 俐= c ( 1 2 5 ) s t x s ( 1 2 6 ) 其中，g 是目标数，c 。是第f 个目标函数的向量的系数( 梯度) ，s 为可行域， z ，是第f 个目标函数值( 目标值) 。聊甜表示目标是同时求所有目标的最大化。 因为多目标问题很少存在同时使得所有目标最大化的解，所以处于这样的情 况：最大程度地最大化每个目标。许多研究者对多目标运输问题( m u l t i p l eo b j e c t i v e t r a n s p o r t a t i o np r o b l e m ) 感兴趣，并提出了许多解决它的方法。 具有m 个工厂和7 z 个仓库的传统多目标运输问题可以描述如下： m i