设施选址中的一些模型与算法

作     者：吴仆 

作者单位：南京航空航天大学 

学位级别：硕士

导师姓名：蒋建林

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：设施选址 NP-难 k-CARD问题 p-中位问题 元启发式算法 

摘      要：本文主要研究用一些元启发式算法来求解一些经典的设施选址问题及其扩展问题。 首先,本文简单阐述了设施选址的发展以及研究现状,介绍了一些经典的设施选址模型,包括Weber问题、集合覆盖问题等。选址问题是常见的优化问题,其中很多都是NP-难问题。已有许多方法来求解设施选址问题,本文首先介绍了几种常见的算法,包括传统方法和元启发式算法。传统方法有Weiszfeld算法、分枝定界法和拉格朗日松弛算法等;元启发式算法有变邻域搜索算法,遗传算法等。 其次,本文综合了点上带权和边上带权的k-CARD问题,提出了一种更为一般和实际的模型,并应用一种新的变邻域搜索方法进行求解。它根据模型的特点划分邻域,通过贪婪算法的思想选择初始点,并且在变邻域过程中采用简单的交换叶子的思想简化算法。这三点极大地提高了变邻域搜索方法求解此推广问题的计算效率。 再次,对于经典模型中的p-中位问题,本文提出一种新的变邻域搜索算法。该算法嵌套使用邻域变换思想,并且在搜索局部最优解时应用了一种基于自然界蜘蛛网模型的蛛网搜索,避免了一些不必要的搜索路径。实验证明该算法求解p-中位问题是有效的。 紧接着,针对一种p不定的推广p-中位问题,本文应用了简单启发式算法、变邻域搜索算法和改进的遗传算法进行求解。在变邻域搜索算法的邻域变换中采用以概率选取邻域的思想;在遗传算法中加入了种群改进策略、局部搜索策略和最优保存策略。实验表明遗传算法求解该推广p-中位问题比另外两种算法有效。 最后,总结全文,指出了未来可行的研究方向。