Transportation Problem Allowing Sending and Bringing Back
Transportation Problem Allowing Sending and Bringing Back
复制标题
允许发送和带回的运输问题
DOI：
10.1142/s0129054122500289
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Asano Tetsuo
中科院分区：
文献类型：
--
作者：
Asano Tetsuo
本文研究了赋权图上的运输问题。权重指定节点处的商品数量，如果数量存储在节点处，则权重为正，如果数量在节点处需要，则权重为负。为了满足所有需求，我们使用车辆，每个节点一辆，具有一定的负载能力，往返于邻居。在一次交通运输中，我们可以将商品从一个节点沿着沿着一条边送到另一个节点，也可以从另一个节点带回一些其他的商品，本文研究的是可行性问题，即是否存在一次满足所有需求的交通运输。我们证明了可行性问题是NP-完全的，即使在最简单的情况下，一种商品的运输问题与无限的能力。我们还提出了几种不同的多项式时间算法的其他情况下。
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.