设施选址是运筹学研究的重要内容之一,在过去的四十多年中,其数学理论的研究吸引了众多离散优化和连续优化学者的关注.它在通讯、复杂网络、运输和管理科学等学科中有着广泛的应用,具有重大的经济、社会和军事意义.设施选址问题的目标是在满足某些需求（顾客）的前提下,确定设施（资源）所在位置使得相应的总费用达到最小.起初,选址问题主要研究服务型设施（如医院、邮局等）的相关选址问题.近年来,人们提出了厌恶型（如垃圾处理站、化工厂等）、半厌恶型（如飞机场等）和候补型等更加符合实际意义的一些新的选址问题和模型.本文研究了几类离散选址问题.利用图论及组合优化算法,我们对几类特殊图的厌恶型、半厌恶型和候补型p-中位问题进行了研究,通过分析某些特殊图的拓扑结构,设计了相应p-中位问题的多项式时间算法.第一章,简述了厌恶型、半厌恶型以及候补型选址问题的研究背景、有关概念术语和主要研究进展.第二章,研究了块图和区间图的p-maxian问题,其中块图和区间图的边长均为单位边长.首先,对块图,证明了如果一个集合X含有块图上距离最远的两点且|X|=p,则集合X是p-maxian问题的一个最优解；以此为基础,给出了块图的p-maxian问题的线性时间算法（有关结果已在《Journal Combinatorial Optimization》上发表）.其次,对区间图,证明了如果一个区间集合X含有区间模型中分别拥有最小右端点和最大左端点的两个区间且|X|=p,则X是p-maxian问题的一个最优解；由此证明了区间图的p-maxian问题是线性时间可解的（该文即将被《Discrete Applied Mathematics》接收）.第三章,研究了区间图的半厌恶型2-中位问题和顾客为子树结构的树的半厌恶型1-中位问题.对于区间图的半厌恶型2-中位问题,讨论了其两类模型：MWD模型和WMD模型,并分别给出了O（n2）的多项式时间算法（该文已被《运筹学学报》接收）.对于顾客为子树结构的树的半厌恶型1-中位问题,此时每个顾客被假定具有某种子树结构,因而被视为“广义”顾客.对于该问题,我们设计了它的一个多项式时间算法（有关结果已在《Theoretical Computer Science》上发表）.第四章,研究了圈和块图上的候补型2-中位问题.首先,证明了一般图上的候补型p-中位问题满足顶点最优性.对于圈的候补型2-中位问题,我们给出了一个O（n2）的多项式时间算法.对于块图的候补型2-中位问题,通过找出块图的最优解与其框架结构上的最优解之间的联系,并对树的候补型2-中位问题的已有算法进行改造,我们最终设计出了时间复杂度为O（n log n+m）的多项式时间算法.