文献

J-GLOBAL ID：201802237637624250   整理番号：18A0510396

一般化上界制約条件を用いた集合多重被覆問題のための緩和ヒューリスティックス【Powered by NICT】

Relaxation heuristics for the set multicover problem with generalized upper bound constraints

著者 (3件)： Umetani Shunji (Osaka University, Suita, Osaka, 565-0871, Japan) ,  Arakawa Masanao (Fujitsu Limited, Kawasaki 211-8588, Japan) ,  Yagiura Mutsunori (Nagoya University, Nagoya 464-8601, Japan)
資料名： Computers & Operations Research  (Computers & Operations Research)
巻： 93  ページ： 90-100  発行年： 2018年 
JST資料番号： H0216B  ISSN： 0305-0548  CODEN： CMORAP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： (i)multicoverと(ii)一般化上限(GUB)制約を導入した集合被覆問題(SCP)の拡張を考察した。従来SCPでは,課金手法はインスタンスのサイズを減らすために導入され,そのような還元技術に基づくいくつかの効率的な発見的アルゴリズムは,大規模な事例を解くために開発されてきた。しかし,GUB制約はしばしば価格決定法の有効性は低下し,それらはしばしば一緒に評価した変数を含む溶液を妨げるからである。この問題を克服するために,インスタンスのサイズにおける変数の新しい評価方式は,GUB制約を考慮した紹介したを低減するための発見的アルゴリズムを開発した。も解の品質を犠牲にすることなく,近傍の候補の数を減少させることを2フリップ近傍局所探索アルゴリズムの効率的な実装を開発した。多種多様な優れた解を訪問し探索をガイドするために,これまでに得られた二以上の解を組み合わせて新しい解を生成する経路再リンク手法を提案した。ベンチマークインスタンス上の計算の比較によれば,提案した方法は,少数の有望な変数を適切に選択することができ,硬GUB制約を有する大規模例に対しても非常に効率的に行う。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *発見的方法 ,  *被覆問題 ,  価格決定 ,  品質 ,  近傍探索法 ,  *緩和現象 ,  *多重化 ,  探索アルゴリズム ,  近傍 ,  発見的アルゴリズム ,  *上界 ,  決定

著者キーワード (5件)： 組合せ最適化 ,  集合被覆問題 ,  メタヒューリスティックス ,  局所探索 ,  Lagrange緩和

分類 (2件)： 工程管理  (KB03030P) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (8件)： 一般化 ,  上界 ,  制約条件 ,  集合 ,  多重 ,  被覆問題 ,  緩和 ,  ヒューリスティックス