论文部分内容阅读
设施选址模型在生活,经济,管理,交通运输甚至军事等领域都有着非常广泛的应用.设施选址模型包含离散选址模型、网络选址模型和连续选址模型.本文对单设施连续选址问题和多设施连续选址问题分别提出了具有收敛性的算法.第一章绪论中分别介绍了本课题的研究背景、研究现状和本文的主要工作.第二章介绍了三种连续设施选址问题:单设施选址问题,多设施选址分配问题和多设施交互选址问题.第三章中对单设施连续选址问题(Weber问题)进行推广,提出了广义单设施选址问题(GVWP):平面被直线分为两个区域,不同区域用不同的尺度度量距离. GVWP与一般设施选址问题不同在于:1)GVWP对约束选址问题与无约束选址问题都适应;2)GVWP使用更一般的距离度量尺度代替了范数.在此章中,该问题被分为如下的三个子问题:两个子问题首先通过等价变换转化成线性变分不等式,然后用Projection-Contraction(PC)算法进行求解;第三个子问题先分解为几个凸的子问题,然后用黄金搜索法求解凸的子问题.最后的数值实验结果证实了该算法的有效性.第四章主要讨论在需求区域下的多设施选址问题,目标是寻求多个设施,使得设施与需求区域的加权距离和最小,其中距离为设施到需求区域的最近距离.本章的模型对设施进行了约束,并选用尺度代替常用的范数以能够度量对称和非对称距离.基于Cooper算法的基础上,本章提出一个新的交替选址-分配启发式算法.在选址阶段,需求区域下的单设施选址问题首先转化为线性变分不等式,然后用PC算法进行求解.在分配阶段,依据最近中心再分配算法将需求区域分配给设施.最后证明了该启发式算法的收敛性,数值实验也证实了该算法的有效性.第五章主要考虑到生活实际中设施有约束限制以及设施间存在相互运输(交互)的情况,提出一个约束多设施选址模型.目标是在平面上的约束区域内寻求多个设施,使得这些设施到需求点以及各个设施间的加权距离和最小.本章提出了基于变分不等式方法的交替选址-分配启发式算法解决此模型:在分配步,采用最近中心再分配算法将顾客分配给设施;在选址步,先将子问题转化为等价的变分不等式问题,再用投影收缩方法求解相应的变分不等式问题.本章给出了该算法收敛性证明.最后的数值试验证实了该算法的有效性.第六章主要是处理多设施选址问题中的退化现象:存在一个设施或更多设施没有提供服务,即没有需求或顾客分配给这些设施.针对多设施选址问题中的退化问题,本章提出了贪婪需求点算法、贪婪簇算法和混合算法进行改进.数值试验表明了算法的有效性.最后对全文进行了总结,并提出了展望.