Transportation problem on a graph
Transportation problem on a graph
复制标题
图上的运输问题
DOI：
10.1007/s13160-022-00516-z
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Asano Tetsuo
中科院分区：
文献类型：
--
作者：
Szilard Zsolt Fazekas;Hwee Kim;Ryuichi Matsuoka;Shinnosuke Seki;Hinano Takeuchi;Asano Tetsuo
我们考虑一个定义在节点加权无向图上的运输问题。如果商品的数量存储在一个节点，则权重为正，如果该节点需要该数量，则权重为负。我们希望通过使用在节点或边缘准备的车辆运输商品来满足所有需求，这些车辆只往返于邻居之间。在从一个节点到一个邻居的旅行中，我们可以发送商品，也可以带回一些其他商品。问题是决定我们是否可以通过在几轮中进行一组旅行来满足所有需求。我们定义了三种不同的方案来解决这个问题，并检查它们的性能。我们提出了一个多项式时间的算法来决定是否有一个单一的一轮行程使用一辆车在每个节点，满足所有需求的一种商品的情况下。
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.
登录
查看更多内容
带有发送和带回操作的图上新的运输问题
DOI：
10.1007/978-3-030-68211-8_2
发表时间：
2021
期刊：
WALCOM: Algorithms and Computation. WALCOM 2021. Lecture Notes in Computer Science, vol 12635. Springer, Cham.
影响因子：
--
作者：
Daria Pchelina;Nicolas Schabanel;Shinnosuke Seki;Guillaume Theyssier;Tetsuo Asano
通讯作者：
Tetsuo Asano
影响因子：
3.6
作者：
Gautam M. Appa
通讯作者：
Gautam M. Appa
影响因子：
19.5
作者：
Rubner, Y;Tomasi, C;Guibas, LJ
通讯作者：
Guibas, LJ
DOI：
10.1016/j.dam.2019.02.042
发表时间：
2019
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Jeffery Kline
通讯作者：
Jeffery Kline