收藏本站
《南开大学》 2014年
收藏 | 手机打开

多层与随机设施选址问题的近似算法

吴晨晨  
【摘要】:设施选址问题是组合优化中经典的NP-困难问题之一。除非P=NP,否则这类问题不可能在多项式时间内求得最优解。很多NP-困难问题可以利用近似算法有效求解。近似算法在多项式时间内得到可估计的可行解。在本论文中,我们考虑两阶段随机设施选址问题,带线性惩罚的两阶段随机设施选址问题,2-层设施选址问题和带软容量限制的设施选址问题。 在第二章,我们考虑两阶段随机设施选址问题。在该问题中,被服务的顾客集合依赖于实现的场景及其相应的概率,设施的开设费用依赖于第一/第二阶段。问题的目标是极小化设施开设费用和连接费用之和的期望。与常用的近似比不同,我们考虑估计实现场景解质量的单场景界。利用线性规划舍入技巧,我们得到2.3613单场景界。 在第三章,我们考虑带线性惩罚的两阶段随机设施选址问题。在两阶段随机设施选址问题的基础上,有些顾客可以不被服务。因而需要支付一定的惩罚费用,最终极小化设施开设费用,连接费用以及不被服务的顾客惩罚费用的总期望。我们给出带线性惩罚的随机设施选址问题基于线性规划的3.0294-近似算法。 在第四章,我们考虑2-层设施选址问题。在该问题中,顾客需要连接到具有先后关系的两层设施上。对任意的正常数£0,我们给出一个原始-对偶3(1+ε)-近似算法。区别于标准的原始-对偶算法,需要利用近似分离神谕得到对偶可行解。进一步,利用贪婪调整的技巧,可将近似比改进到2.172(1+£)2。 在第五章,我们考虑带软容量限制的k-层设施选址问题。在该问题中,每个设施都有软容量限制。通过支付多倍的设施开设费用,每个设施的容量可以增加相同倍数。通过k-层设施选址问题的双因子,利用所谓的双因子归约,我们可以得到5.5053-近似算法。
【学位授予单位】:南开大学
【学位级别】:博士
【学位授予年份】:2014
【分类号】:O224

手机知网App
【共引文献】
中国期刊全文数据库 前10条
1 于浩;相伴随机变量的弱不变原理[J];工程数学学报;1985年02期
2 白亚兰;师海忠;;完全二叉树到星连通圈网络的嵌入[J];甘肃科学学报;2014年03期
3 ;A cross-monotonic cost sharing method for the facility location game with service installation costs[J];Science in China(Series A:Mathematics);2009年11期
4 潘锐;朱大铭;马绍汉;;一般设施定位问题计算复杂度和近似算法研究[J];计算机研究与发展;2007年05期
5 宁钊;石胜飞;李建中;王朝坤;;传感器网络中一种支持多分辨率区域查询的数据存储方法[J];计算机研究与发展;2012年03期
6 易斌;李荣珩;;一个关于求解k-种产品选址问题的近似算法[J];计算机工程与应用;2008年01期
7 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期
8 王守强;;k-median问题反向贪心随机算法[J];计算机科学;2012年07期
9 李委霖;张鹏;朱大铭;;On Constrained Facility Location Problems[J];Journal of Computer Science & Technology;2008年05期
10 权梓杨;何尚录;;求解单背包约束下下模函数半定松驰算法[J];淮阴工学院学报;2013年05期
中国重要会议论文全文数据库 前1条
1 田世俊;李建;朱洪;;多需求目标的UFL问题及其近似算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年
中国博士188bet全文数据库 前10条
1 王大志;面向实际工程问题的粒子群优化算法应用技术的研究[D];东北大学;2009年
2 潘锐;设施选址与K-中间点问题的复杂性与近似算法[D];山东大学;2007年
3 秦进;多商品物流网络设计相关优化模型及算法研究[D];中南大学;2006年
4 裴军;考虑风险控制的供应链优化设计方法与应用研究[D];湖南大学;2008年
5 王继强;若干NP-困难的组合最优化问题的近似算法[D];山东大学;2008年
6 黄海滨;基于网络节点拓扑参数的关键蛋白质识别研究[D];中南大学;2008年
7 王守强;多中心点聚类问题的随机算法[D];山东大学;2010年
8 黄辉林;关于随机场及复杂网络的极限定理[D];上海交通大学;2010年
9 顾满占;若干随机排序问题的算法研究[D];华东理工大学;2010年
10 黎煜;带次模特性的仓库选址问题研究[D];北京交通大学;2012年
中国硕士188bet全文数据库 前10条
1 胡海燕;潍坊市海水淡化厂选址研究[D];山东大学;2011年
2 肖汉;18luck中国站[D];中国海洋大学;2011年
3 宁钊;传感器网络中多分辨率数据存储与区域查询处理算法研究[D];哈尔滨工业大学;2010年
4 路凤敏;几种离散选址模型的算法研究[D];南京航空航天大学;2010年
5 万德龙;校园内服务设施选址问题的研究与评价建模[D];南昌大学;2011年
6 左西年;二维双重定向渗流模型临界概率函数qc(p)的性质[D];首都师范大学;2002年
7 欧阳忠;中国股市及农业板块的弱市场有效性假设的分析和应用[D];中国农业大学;2002年
8 张莉丽;选址问题及其模型与算法研究[D];浙江大学;2006年
9 刘海龙;不确定环境下的物流中心选址问题研究[D];哈尔滨理工大学;2007年
10 陈冲;多产品选址问题的计算复杂性与近似算法[D];湖南师范大学;2008年
【相似文献】
中国期刊全文数据库 前10条
1 周兵;关于图的面服务型选址问题[J];上海机械学院学报;1982年03期
2 马云峰;杨超;张敏;郝春艳;;基于时间满意的最大覆盖选址问题[J];中国管理科学;2006年02期
3 刘文博;;固定容量设备选址问题的求解算法研究[J];辽宁省交通高等专科学校学报;2006年04期
4 代文强;徐寅峰;何国良;;占线中心选址问题及其竞争算法分析[J];系统工程理论与实践;2007年10期
5 胡丹丹;杨超;;在竞争环境中的拥塞设施截流选址问题[J];系统工程理论与实践;2010年01期
6 陈开周;王效俐;;选址问题的新研究[J];系统工程;1990年01期
7 刘汝臣;选址问题研究[J];沈阳工程学院学报(自然科学版);2005年04期
8 华国伟;杨丰梅;黎建强;;两个双目标竞争选址问题模型[J];系统工程理论与实践;2007年01期
9 马云峰;刘勇;杨超;;一类带时间和容量约束的截流选址问题[J];武汉科技大学学报(自然科学版);2007年02期
10 谭素平;易斌;;设施选址问题综述[J];科技信息;2012年22期
中国重要会议论文全文数据库 前8条
1 赵一新;;浅谈博物馆的选址问题[A];浙江省博物馆学会2001年学术研讨会文集[C];2001年
2 王文峰;郭波;刘新亮;;多级覆盖设施选址问题建模及求解方法研究[A];第九届中国管理科学学术年会论文集[C];2007年
3 张敏;杨珺;杨超;;一类带双重机率约束的多目标应急服务设施选址问题[A];第10届计算机模拟与信息技术会议论文集[C];2005年
4 曹振宇;周根贵;徐超;;集中式回收中心的选址问题研究[A];第八届中国青年运筹信息管理学者大会论文集[C];2006年
5 周建;刘宝碇;;有能力约束设备选址问题的新随机模型[A];第七届北京青年科技论文评选获奖论文集[C];2003年
6 李大卫;陆立娟;王莉;;基于矩阵运算的配送中心动态选址问题研究[A];第二十六届中国控制会议论文集[C];2007年
7 曹振宇;周根贵;许琪;;一类简单的维修中心选址问题[A];第四届全国决策科学/多目标决策研讨会论文集[C];2007年
8 周建;;模糊环境下的Minimax选址问题[A];第四届中国青年运筹与管理学者大会论文集[C];2001年
中国重要报纸全文数据库 前10条
1 王小龙;进化算法可解决风电机选址问题[N];科技日报;2011年
2 向劲静;新批设典当行如何选址[N];中国商报;2011年
3 本报记者 杨瑞实习记者 夏蕊蕊;社区旱厕改造不能“一蹴而就”[N];威海日报;2007年
4 记者 胡越;强化服务意识 提升服务质量 千方百计为企业排忧解难[N];洛阳日报;2009年
5 新华社记者 杨骏;法美明争暗斗,国际热核反应堆选址难[N];新华每日电讯;2004年
6 省政协委员、贵州财经大学贵州高校人文社科基地中国西部现代化发展研究中心主任 徐和平;新形势下贵州产业园区选址问题与政策建议[N];贵州政协报;2013年
7 孙扶;人民需要更多公厕[N];东方早报;2014年
8 本报记者 王欣;连锁店老板倾囊传授经营绝招[N];深圳特区报;2005年
9 本报记者 海珍;整治效果有限 迁址迫在眉睫[N];呼和浩特日报(汉);2007年
10 马赛克;“心急”比“星级”更重要[N];光明日报;2004年
中国博士188bet全文数据库 前10条
1 张曦;需求多元化的网络截流设施选址问题研究[D];华中科技大学;2011年
2 胡丹丹;拥塞型设施的选址问题研究[D];华中科技大学;2011年
3 杨珺;网络服务设施的截流—选址问题研究[D];华中科技大学;2005年
4 柏春松;半厌恶型、厌恶型p-中位问题及具有连通约束的选址问题[D];上海大学;2014年
5 万波;公共服务设施选址问题研究[D];华中科技大学;2012年
6 吴晨晨;多层与随机设施选址问题的近似算法[D];南开大学;2014年
7 张敏;易腐物品物流网络服务设施选址问题研究[D];华中科技大学;2006年
8 王星;随机、容错和厌恶型设施选址的算法研究[D];天津大学;2012年
9 马云峰;网络选址中基于时间满意的覆盖问题研究[D];华中科技大学;2005年
10 王丹;竞争环境下的网络设施合作选址研究[D];华中科技大学;2010年
中国硕士188bet全文数据库 前10条
1 王立胜;多类型客户k-种产品的工厂选址问题[D];湖南师范大学;2009年
2 陈冲;多产品选址问题的计算复杂性与近似算法[D];湖南师范大学;2008年
3 李安宇;不受欢迎物流设施选址问题研究[D];北京化工大学;2008年
4 安凤仙;κ-层无容量限制的设施选址问题的一种算法[D];北京邮电大学;2009年
5 马满;连锁网点的选址与设计问题研究[D];华中科技大学;2011年
6 段伟伟;重心选址问题及其反问题的研究[D];青岛大学;2009年
7 姚曼华;水上救助基地选址问题研究[D];大连海事大学;2011年
8 万德龙;校园内服务设施选址问题的研究与评价建模[D];南昌大学;2011年
9 王凤敏;带惩罚的优先设施选址问题的近似算法[D];北京工业大学;2012年
10 王星;κ-层有容量约束设施选址问题的近似算法[D];北京工业大学;2009年