| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-08-25 15:30 ［招待講演］グラフ上での持ち込みと持ち帰りを許す輸送問題 ○浅野哲夫（金沢大）  COMP2021-10 |
|
| 抄録 | （和） | 輸送問題として分類される問題は数多く存在する．本文で考察するのは，車両を用いた持ち込みと持ち帰りを許す場合の輸送問題である．入力は重み付きのグラフの形で与えられる．グラフの節点には多種類の商品に関して，供給できる量と需要量の情報が蓄えられているものとする．各節点では１台の車両が運搬用に用意されているが，積載量には上限が存在する．各節点の車両を隣接する節点の一つに送り，かつ別の商品を持ち帰ることによって全ての需要を満たすことができるかどうかを判定したい．簡単のため輸送のコストは無視する．残念ながら，一般のグラフに対してはNP-完全であり，効率の良いアルゴリズムは望めないが，定数個以内のサイクルしか含まないグラフに対しては多項式時間で解けることを示す． |
| （英） | There are a number of problems classified as a transportation problem. In this paper we consider one of allowing sending and bringing-back commodities. Input is given as a weighted graph. Suppose amounts of supplies and demands are specified at each node and each node has one vehicle to carry commodities with bounded capacity. We want to see whether we can meet all demands by sending and bringing-back commodities. Cost is neglected. Unfortunately the problem is NP-complete for a general graph, but we present a polynomial-time algorithm for a graph containing a constant number of cycles. | |
| キーワード | （和） | 輸送問題 / アルゴリズム / 供給量 / 需要量 / NP-完全 / 多項式時間アルゴリズム / / |
| （英） | transportation problem / algorithm / supply / demand / NP-complete / polynoial-time algorithm / / | |
| 文献情報 | 信学技報, vol. 121, no. 149, COMP2021-10, pp. 9-9, 2021年8月. | |
| 資料番号 | COMP2021-10 | |
| 発行日 | 2021-08-18 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2021-10 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2021-08-25 - 2021-08-26 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2021-08-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフ上での持ち込みと持ち帰りを許す輸送問題 |
| サブタイトル（和） | |
| タイトル（英） | Transportation Problem on a Graph Allowing Sending and Bringing-back |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 輸送問題 / transportation problem |
| キーワード(2)（和/英） | アルゴリズム / algorithm |
| キーワード(3)（和/英） | 供給量 / supply |
| キーワード(4)（和/英） | 需要量 / demand |
| キーワード(5)（和/英） | NP-完全 / NP-complete |
| キーワード(6)（和/英） | 多項式時間アルゴリズム / polynoial-time algorithm |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 浅野 哲夫 / Tetsuo Asano / アサノ テツオ |
| 第1著者 所属（和/英） | 金沢大学 (略称： 金沢大) Kanazawa University (略称： Kanazawa Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-08-25 15:30:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2021-10 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.149 |
| ページ範囲 | p.9 |
| ページ数 | 1 |
| 発行日 | 2021-08-18 (COMP) |
[研究会発表申込システムのトップページに戻る]