The point-to-point delivery and connection problems: complexity and algorithms
The point-to-point delivery and connection problems: complexity and algorithms
复制标题
点对点传送和连接问题：复杂性和算法
DOI：
10.1016/0166-218x(92)90258-c
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
D. Simchi
中科院分区：
文献类型：
--
作者：
Chung;S. McCormick;D. Simchi
我们考虑点对点交付问题的计算复杂性。这些问题涉及从每个来源运送一件物品，顶级目的地可能与来源预先匹配（固定目的地情况），或者来源的物品可能会发送到任何目的地（非固定目的地情况）。网络可以是有向的或无向的。一次最多可以在弧线上共享一辆卡车，并且成本与所使用的卡车数量成线性关系。我们还考虑密切相关的点对点连接问题，即找到连接源与目的地的最小成本弧子集。我们发现，对于 allK≤2，这两个问题的所有变体都是强 NP 困难的，但在某些情况下，如果 pi 是固定的，或者如果底层网络是一侧有源、另一侧有目的地的网格，则存在多项式算法。
We consider the computational complexity of point-to-point delivery problems. These problems involve shipping one item from each one ofpsources topdestinations might be prematched to sources (the fixed destination case), or a source's item might go to any destination (the nonfixed destination case). The networks can be directed or undirected. Up toKitems at once can share a truck on an arc, and costs are linear in the number of trucks used. We also consider the closely related point-to-point connection problems, which are to find a minimum cost arc subset connecting sources with destinations. We find that all variations of both problems are strongly NP-hard for allK≤2, but that there are polynomial algorithms in some cases ifpis fixed, or if the underlying network is a grid with sources on one side, destinations on the other.