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

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

作　　者：罗玉宏 李莉 

机构地区：[1]上海对外经贸大学统计与信息学院,上海201620

出　　处：《计算机工程与科学》2018年第1期58-65,共8页Computer Engineering & Science

基　　金：上海市教委科研创新重点项目(12ZS170);上海市高校"085工程"项目

摘　　要：通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的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.

关 键 词：物流网络 节点带权Steiner树 最小树 参数算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301.5[自动化与计算机技术—计算机科学与技术]