| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2022-05-19 13:35 Transportation Problem Allowing Sending and Bringing Back ○Tetsuo Asano（Kanazawa Univ.）  COMP2022-2 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | This paper considers a transportation problem on a weighted graph. The weights specify the amounts of commodities at nodes, which are positive if the amounts are stored at nodes and negative if the amounts are needed at nodes. To meet all demands we use vehicles, one at each node, with some loading capacity to and from neighbors. In a trip using a vehicle we can send commodities from a node to a neighbor along an edge and also bring back some other commodities from the neighbor. In this paper we are interested in feasibility problem, which is to decide whether there is a single round of trips that meet all demands. We prove the feasibility problem is NP-complete even in the easiest case of a one-commodity transportation problem with unbounded capacity. We also present several different polynomial-time algorithms for other cases. |
|
| キーワード | （和） | NP-complete / algorithm / transportation problem / vehicle / / / / |
| （英） | / / / / / / / | |
| 文献情報 | 信学技報, vol. 122, no. 33, COMP2022-2, pp. 9-16, 2022年5月. | |
| 資料番号 | COMP2022-2 | |
| 発行日 | 2022-05-12 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2022-2 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2022-05-19 - 2022-05-20 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2022-05-COMP-AL |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Transportation Problem Allowing Sending and Bringing Back |
| サブタイトル（英） | |
| キーワード(1)（和/英） | NP-complete / |
| キーワード(2)（和/英） | algorithm / |
| キーワード(3)（和/英） | transportation problem / |
| キーワード(4)（和/英） | vehicle / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 浅野 哲夫 / Tetsuo Asano / アサノ テツオ |
| 第1著者 所属（和/英） | 金沢大学 (略称： 金沢大) Kanazawa University (略称： Kanazawa Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-05-19 13:35:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2022-2 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.33 |
| ページ範囲 | pp.9-16 |
| ページ数 | 8 |
| 発行日 | 2022-05-12 (COMP) |
[研究会発表申込システムのトップページに戻る]