離散型・時間/費用トレードオフ最小全域木問題

• Item type: Journal(1)
• 公開日: 2016-11-15
• タイトル: 離散型・時間/費用トレードオフ最小全域木問題
• タイトル / 言語: en
• タイトル: Discrete Time/Cost Tradeoff Minimum Spanning Tree Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] 時間/費用トレードオフ，プロジェクトスケジューリング，最小全域木，ラグランジュ緩和，釘付けテスト，分枝限定法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 防衛大学校情報工学科
• 著者所属: 陸上自衛隊
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, National Defense Academy
• 著者所属(英): en
• 著者所属(英): Japan Grand Self Defense Force
• 著者名: 片岡, 靖詞; 村崎, 暢彦
• 著者名(英): Seiji, Kataoka; Masahiko, Murasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 無向グラフにおいて，各枝にはモードと呼ばれる時間と費用のペアが与えられており，モードは複数ある．そして，あるモードは時間はかかるが費用は安い，別のモードは短時間で済むが費用は高いというトレードオフの関係があるものする．これらの枝モードからたかだか1つを選ぶことで，限られた予算内で，総時間を最小にする全域木を求める問題を考える．時間と費用は与えられたモードからしか選べないことから，この問題を離散型・時間/費用トレードオフ最小全域木問題と呼ぶことにする．時間/費用トレードオフという問題設定は，プロジェクトスケジューリングの分野では古くから研究がなされているが，ネットワーク計画法に同様の設定を導入した問題はほとんどみあたらない．この問題に対し，ラグランジュ緩和をもとに上下界値を求め，釘付けテストを行う．釘付けテストの効果は高く，分枝限定法においても，ごくわずかな枝やモードを決定変数の対象とすればよく，先行研究よりも効率良く解くことに成功した．また，時間と費用というモードの間に凸関数・凹関数・線形関数のような特性のあるモデルについても詳細に計算機実験を行い，各特性がアルゴリズムや最適解の構造に及ぼす影響についても調べた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider an undirected graph. For each edge, a pair of parameters, time and cost, which we call mode, is given. Normally there exist a number of modes on each edge, and these modes are on the relationship of tradeoff, such that one mode is slow-time and low-cost, and another mode is rapid-time and high-cost. By choosing at most one mode from each edge, we consider a problem of finding a spanning tree that minimizes total time within budget constraint. As the useable modes are prescribed in advance, we call this problem the discrete time/cost tradeoff minimum spanning tree problem. The relationship of time/cost tradeoff is often seen in the subject of project scheduling problems and these problems have been studied before. But in the subject of network programming problems, we seldom see studies that have this kind of tradeoff relationship among modes. For this problem, we propose upper and lower bounds procedures based on Lagrangian relaxation, and apply these bounds to the pegging test. The effectiveness of the pegging test is so high that, by eliminating many fixed variables and reducing the size of problem, the branch-and-bound algorithm succeeds in solving the problem quicker than the results of past research. Furthermore, we observe several models with specific time/cost relationships, such as convex, concave and linear functions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 57, 号 11, p. 2445-2455, 発行日 2016-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764