论文摘要
固定费用运输问题是一种特殊的线性规划问题。与线性运输问题的特征相似,固定费用运输问题也需满足供应与需求约束,且具有运输网络特征,但固定费用的出现使得目标函数出现不连续性,从而导致其成为一个NP难问题。该问题的求解目标是在满足目的地需求的同时,分配每个源地可用供应量,以使得分配后所产生的总的变化成本和固定成本之和最小。求解固定费用运输问题的方法很多。起初人们用一些精确算法来求解,例如切平面法,极点排列法,分枝定界法等。但这些方法被证明低效且计算费时,只适合求解较小规模问题。为了克服计算时间过长的问题,一些启发式方法被用于求解该问题,例如拉格朗日松驰法,邻近极点法等。虽然这些方法计算耗时较少,但所获得的解的质量较差。近年来,相继出现一些现代启发式遗传算法求解该问题,例如基于矩阵排列编码的遗传算法、禁忌搜索算法、利用边集编码的遗传算法等。经实验证明,它们也各有其优点与不足。本论文的总体框架如下:第一章简要介绍了运输问题的四个研究分支,深入分析了固定费用运输问题的背景、国内外研究现状及各类求解方法。第二章深入讨论了智能优化算法的基本概念和定理,如标准遗传算法,免疫遗传算法等,并给出了技术路线、实现方法和研究内容。第三章介绍了基于Prüfer数编码的生成树方法,分析了它的优点与不足。第四章提出了一种森林补充式多点交叉操作的遗传算法。为了进一步改进智能优化算法求解固定费用运输问题的性能,利用其解是运输图的一棵生成树的特性,对采用先根遍历边构成有序边集编码的生成树,提出了一种新的森林补充式多点交叉操作的启发式遗传算法。通过理论证明和不同类型和规模实验检测实验,结果表明该算法所得解的质量优于基于边集编码的遗传算法。该算法丰富了近似求解固定费用运输问题的思路。第五章提出了一种求解固定费用运输问题的免疫遗传算法。为了进一步体现该遗传算法的性能,与基于矩阵编码的遗传算法和基于边集编码的遗传算法进行了对比,实验结果表明,免疫遗传算法的综合性能优于其他两种方法。该算法丰富了近似求解固定费用运输问题的思路。
论文目录
相关论文文献
标签：固定费用运输问题论文; 免疫遗传算法论文; 多点交叉论文; 森林论文; 生成树论文;