运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2014年
2期
17-28
,共12页
徐大川%万玮%吴晨晨%徐文青
徐大川%萬瑋%吳晨晨%徐文青
서대천%만위%오신신%서문청
设施选址问题%随机性%容错性%近似算法%原始-对偶算法
設施選阯問題%隨機性%容錯性%近似算法%原始-對偶算法
설시선지문제%수궤성%용착성%근사산법%원시-대우산법
facility location problem%stochastic demands%fault-tolerance%approximation algorithm%primal-dual algorithm
研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现(在第一阶段不知道).两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合(称为场景).并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务.给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小.根据问题的特定结构,给出了原始-对偶(组合)3-近似算法.
研究兩階段隨機容錯設施選阯問題,其中需要服務的顧客在第二階段齣現(在第一階段不知道).兩箇階段中每箇設施的開設費用可以不同,設施的開設依賴于階段和需要服務的顧客集閤(稱為場景).併且在齣現的場景裏的每箇顧客都有相同的連接需求,即每箇顧客需要由r箇不同的設施服務.給定所有可能的場景及相應的概率,目標是在兩箇階段分彆選取開設的設施集閤,將齣現場景的顧客連接到r箇不同的開設設施上,使得包括設施費用和連接費用的總平均費用最小.根據問題的特定結構,給齣瞭原始-對偶(組閤)3-近似算法.
연구량계단수궤용착설시선지문제,기중수요복무적고객재제이계단출현(재제일계단불지도).량개계단중매개설시적개설비용가이불동,설시적개설의뢰우계단화수요복무적고객집합(칭위장경).병차재출현적장경리적매개고객도유상동적련접수구,즉매개고객수요유r개불동적설시복무.급정소유가능적장경급상응적개솔,목표시재량개계단분별선취개설적설시집합,장출현장경적고객련접도r개불동적개설설시상,사득포괄설시비용화련접비용적총평균비용최소.근거문제적특정결구,급출료원시-대우(조합)3-근사산법.
