Transportation Problem Allowing Sending and Bringing Back

• Item type: SIG Technical Reports(1)
• 公開日: 2022-05-12
• タイトル: Transportation Problem Allowing Sending and Bringing Back
• タイトル / 言語: en
• タイトル: Transportation Problem Allowing Sending and Bringing Back
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kanazawa University
• 著者所属(英): en
• 著者所属(英): Kanazawa University
• 著者名: Tetsuo, Asano
• 著者名(英): Tetsuo, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-188, 号 4, 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
• 出版者: 情報処理学会