物流网络中节点带权的Steiner最小树的参数算法

A parameterized algorithm for minimum node weighted Steiner tree in logistics networks

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是:首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。

By optimizing logistics transport network,logistics costs can be effectively reduced.The logistics network optimization problem of centralized distribution can be transformed into the minimum nodeweighted Steiner tree problem,which is an NP-hard problem.In this paper,a new heuristic solution algorithm P-NSMT is proposed by using parameter theory.The idea of the algorithm is as follows:the algorithm first builds a minimum spanning tree with connected terminal nodes,and then adds the Steiner node into the tree so as to reduce the total weight of the spanning tree,and lastly generates a minimum Steiner tree whose total number does not exceedparameter k.Experiments show that the PNSMT algorithm outperforms other algorithms in terms of accuracy and time efficiency,and is especially suitable for the logistics networkswith large network size and fewer terminal delivery nodes.