论文部分内容阅读
本文讨论的主要内容是设施选址问题。论文首先简单介绍了设施选址问题在现代社会生活中的作用和发展进程，然后介绍了一些经典的设施选址问题和求解算法。常见的设施选址问题包括 p-中位问题、p-中心问题、经典的无容量限制设施选址问题等。多数设施选址问题属于NP-Hard问题，目前已有很多方法来求解这类问题，主要分为精确算法与启发式算法。常见的精确算法有分支定界法、拉格朗日松弛算法等；启发式算法主要有遗传算法、粒子群优化算法、禁忌搜索算法等。随后给出了本文的研究意义和主要工作。 论文主要研究了两类设施选址问题，一类是经典的无容量限制设施选址问题（Uncapacitated Facility Location Problem，简称UFLP）；另一类为无容量限制的可靠性设施选址问题（Reliability for the Uncapacitated Facility Location Problem，简称RUFLP）。针对上述两类设施选址问题，本文分别给出了基于遗传算法的求解方法，因此论文第二部分对传统的遗传算法进行了介绍。 针对UFLP，提出了一种改进的遗传算法，该算法较之传统的遗传算法有如下改进：（1）提出了新的自适应交叉概率，并与均匀交叉相结合，使交叉算子不仅更有针对性，而且具有自适应性，从而提高进化效率；（2）在已有的自适应变异概率设计方法下进行改进，设计出一种更合理的自适应变异算子。最后通过数值试验说明本文提出的遗传算法在求解大规模UFLP时具有很好的效果。 随着设施选址问题的不断发展，新的选址模型也不断涌现，尤其是可靠性设施选址问题的提出具有非常重要的意义。国外对可靠性设施选址问题的研究模型大多基于p-中位问题而提出的，其假设条件比较严格，模型比较复杂。本文提出的无容量限制的可靠性设施选址模型放宽了假设条件，降低了问题的复杂度。针对RUFLP，提出了基于遗传算法的分阶段近似算法，并证明了该算法对求解RUFLP是可行的。 最后，对论文进行了总结，并对设施选址问题以后的研究进行了展望。