講演抄録/キーワード |
講演名 |
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 |