2024-03-29T17:07:25Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001759622022-10-21T05:24:51Z00581:08417:08429
離散型・時間/費用トレードオフ最小全域木問題Discrete Time/Cost Tradeoff Minimum Spanning Tree Problemjpn[一般論文] 時間/費用トレードオフ,プロジェクトスケジューリング,最小全域木,ラグランジュ緩和,釘付けテスト,分枝限定法http://id.nii.ac.jp/1001/00175928/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=175962&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of Japan防衛大学校情報工学科陸上自衛隊片岡, 靖詞村崎, 暢彦無向グラフにおいて,各枝にはモードと呼ばれる時間と費用のペアが与えられており,モードは複数ある.そして,あるモードは時間はかかるが費用は安い,別のモードは短時間で済むが費用は高いというトレードオフの関係があるものする.これらの枝モードからたかだか1つを選ぶことで,限られた予算内で,総時間を最小にする全域木を求める問題を考える.時間と費用は与えられたモードからしか選べないことから,この問題を離散型・時間/費用トレードオフ最小全域木問題と呼ぶことにする.時間/費用トレードオフという問題設定は,プロジェクトスケジューリングの分野では古くから研究がなされているが,ネットワーク計画法に同様の設定を導入した問題はほとんどみあたらない.この問題に対し,ラグランジュ緩和をもとに上下界値を求め,釘付けテストを行う.釘付けテストの効果は高く,分枝限定法においても,ごくわずかな枝やモードを決定変数の対象とすればよく,先行研究よりも効率良く解くことに成功した.また,時間と費用というモードの間に凸関数・凹関数・線形関数のような特性のあるモデルについても詳細に計算機実験を行い,各特性がアルゴリズムや最適解の構造に及ぼす影響についても調べた.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.AN00116647情報処理学会論文誌5711244524552016-11-151882-77642016-11-11