计算机工程与科学2018，Vol.40Issue(1)：58-65,8.DOI:10.3969/j.issn.1007-130X.2018.01.009
物流网络中节点带权的Steiner最小树的参数算法
A parameterized algorithm for minimum node weighted Steiner tree in logistics networks
摘要
Abstract
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树/最小树/参数算法Key words
logistics network/node weighted Steiner tree/minimum spanning tree/parameterized algorithm分类
信息技术与安全科学引用本文复制引用
罗玉宏,李莉..物流网络中节点带权的Steiner最小树的参数算法[J].计算机工程与科学,2018,40(1):58-65,8.基金项目
上海市教委科研创新重点项目(12ZS170) （12ZS170）
上海市高校“085工程”项目 （）
