Transportation Problem on a Graph

• Item type: SIG Technical Reports(1)
• 公開日: 2022-05-12
• タイトル: Transportation Problem on a Graph
• タイトル / 言語: en
• タイトル: Transportation Problem on a Graph
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kanazawa University
• 著者所属(英): en
• 著者所属(英): Kanazawa University
• 著者名: Tetsuo, Asano
• 著者名(英): Tetsuo, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We consider a transportation problem defined on a node-weighted undirected graph. Weight is positive if the amount of commodity is stored at a node, and negative if the amount is needed at the node. We want to meet all demands by transporting commodities using vehicles prepared either at nodes or edges which only travel to and from neighbors. In a trip from a node to a neighbor we can send commodities and also bring back some other commodities. Problem is to decide whether we can meet all demands by carrying out a set of trips in a few rounds. We define three different schemes to solve the problem and examine their performances. We present a polynomial-time algorithm for deciding whether there is a single round of trips using one vehicle at each node that meet all demands for one-commodity case. Although extension to multi-commodity case is unknown, we can also extend it to multiple rounds as far as the number of iterations is bounded by a constant.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider a transportation problem defined on a node-weighted undirected graph. Weight is positive if the amount of commodity is stored at a node, and negative if the amount is needed at the node. We want to meet all demands by transporting commodities using vehicles prepared either at nodes or edges which only travel to and from neighbors. In a trip from a node to a neighbor we can send commodities and also bring back some other commodities. Problem is to decide whether we can meet all demands by carrying out a set of trips in a few rounds. We define three different schemes to solve the problem and examine their performances. We present a polynomial-time algorithm for deciding whether there is a single round of trips using one vehicle at each node that meet all demands for one-commodity case. Although extension to multi-commodity case is unknown, we can also extend it to multiple rounds as far as the number of iterations is bounded by a constant.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-188, 号 3, p. 1-8, 発行日 2022-05-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会