A New Transportation Problem on a Graph with Sending and Bringing-Back Operations
A New Transportation Problem on a Graph with Sending and Bringing-Back Operations
复制标题
带有发送和带回操作的图上新的运输问题
DOI：
10.1007/978-3-030-68211-8_2
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tetsuo Asano
中科院分区：
文献类型：
--
作者：
Daria Pchelina;Nicolas Schabanel;Shinnosuke Seki;Guillaume Theyssier;Tetsuo Asano
本文考虑了一个与传统模型不同的运输问题。假设我们被赋予许多存储（节点）来存储多种商品以及连接它们的道路（边），这些道路被指定为加权图。有些仓库有剩余，有些仓库有短缺。问题是确定是否有运输来消除所有的短缺。对于运输，我们可以使用具有每个节点的装载能力的车辆。每辆车都带着一些商品访问它的一个邻居，这些商品在邻居那里卸载。然后，我们在那里装载一些其他商品，然后将它们带回原始节点。如何设计这样的发送和带回运输，以消除所有的短缺是一个问题。当我们将单轮传输定义为所有节点上的一组传输时，我们关心的是是否存在一轮有效的传输来消除所有的短缺。在证明了问题的NP-完全性后，我们给出了一个输入图是森林的特殊情况下的线性时间算法。
This paper considers a transportation problem which is different from the conventional model. Suppose we are given many storages (nodes) to store multiple kinds of commodities together with roads (edges) interconnecting them, which are specified as a weighted graph. Some storages have surplus and others have shortages. Problem is to determine whether there are transportations to eliminate all of shortages. For transportation we can use a vehicle with the loading capacity at each node. Each vehicle visits one of its neighbors with some commodities which are unloaded at the neighbor. Then, we load some other commodities there, and then bring them back to the original node. How to design such send-and-bring-back transportations to eliminate all shortages is the problem. When we define a single round of transportations to be a set of those transportations at all nodes, whether there is a single round of valid transportations that eliminate all of shortages is our concern. After proving NP-completeness of the problem we present a linear time algorithm for a special case where an input graph is a forest.