| 講演名 | 2019-06-14 反復深化深さ優先探索を用いた最小費用流問題解法評価 秋葉 知昭(千葉工大), 高橋 奈津美(青学大), 山本 久志(首都大東京), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究ではネットワーク最適化問題の一つである最小費用流問題に注目する．この問題はネットワークのエッジに流量とコストが付与された多目的最適化問題であり，特定ノードの需要量を満たす制約がある．この問題の解法の一つとしてPrimal-Dual法が知られているが，Primal-Dual法は双対問題の緩和による近似解法であるため，より厳密解に近い解が得られるPrimal-Dual法の改善が求められる．本研究では反復深化深さ優先探索を用いた Primal-Dual 法による最小費用流問題の解法を評価した． |
| 抄録(英) | In this study, I considered to treat the network of a transporting route problem with minimum cost that it satisfied flow at the specific node. So, I proposed to solve the minimum cost flow problem by using iterative deepening depth-first search in order to find efficient route with reduction cost in the network. |
| キーワード(和) | 多目的ネットワーク / 最小費用流問題 / Primal-Dual法 / 反復深化深さ優先探索 |
| キーワード(英) | Multi Objective Network / Minimum Cost-Flow Problem / Primal-Dual Algorithm / Iterative Deepening DFS |
| 資料番号 | R2019-13 |
| 発行日 | 2019-06-07 (R) |
| 研究会情報 | |
| 研究会 | R |
|---|---|
| 開催期間 | 2019/6/14(から1日開催) |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 信頼性一般 |
| テーマ（英） | Overall reliability engineering |
| 委員長氏名（和） | 安里 彰(富士通) |
| 委員長氏名（英） | Akira Asato(Fujitsu) |
| 副委員長氏名（和） | 土肥 正(広島大) |
| 副委員長氏名（英） | Tadashi Dohi(Hiroshima Univ.) |
| 幹事氏名（和） | 田村 信幸(法政大) / 井上 真二(関西大) |
| 幹事氏名（英） | Nobuyuki Tamura(Hosei Univ.) / Shinji Inoue(Kansai Univ.) |
| 幹事補佐氏名（和） | 岡村 寛之(広島大) / 横川 慎二(電通大) |
| 幹事補佐氏名（英） | Hiroyuki Okamura(Hiroshima Univ.) / Shinji Yokogawa(Univ. of Electro-Comm.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reliability |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 反復深化深さ優先探索を用いた最小費用流問題解法評価 |
| サブタイトル（和） | |
| タイトル（英） | Evaluation for the Algorithm of Minimum Cost-Flow Problem by Using Iterative Deepening Depth- First Search |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多目的ネットワーク / Multi Objective Network |
| キーワード(2)（和/英） | 最小費用流問題 / Minimum Cost-Flow Problem |
| キーワード(3)（和/英） | Primal-Dual法 / Primal-Dual Algorithm |
| キーワード(4)（和/英） | 反復深化深さ優先探索 / Iterative Deepening DFS |
| 第 1 著者 氏名（和/英） | 秋葉 知昭 / Tomoaki Akiba |
| 第 1 著者 所属（和/英） | 千葉工業大学(略称：千葉工大) Chiba Institute of Technology(略称：CIT) |
| 第 2 著者 氏名（和/英） | 高橋 奈津美 / Natsumi Takahashi |
| 第 2 著者 所属（和/英） | 青山学院大学(略称：青学大) Aoyama Gakuin University(略称：AGU) |
| 第 3 著者 氏名（和/英） | 山本 久志 / Hisashi Yamamoto |
| 第 3 著者 所属（和/英） | 首都大学東京(略称：首都大東京) Tokyo Metropolitan University(略称：TMU) |
| 発表年月日 | 2019-06-14 |
| 資料番号 | R2019-13 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | R-82 |
| ページ範囲 | pp.25-30(R), |
| ページ数 | 6 |
| 発行日 | 2019-06-07 (R) |