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

计算机工程与科学

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

罗玉宏，李莉

(上海对外经贸大学统计与信息学院，上海 201620)

收稿日期:2016-01-07 修回日期:2016-10-07 出版日期:2018-01-25 发布日期:2018-01-25
基金资助:
上海市教委科研创新重点项目（12ZS170）；上海市高校“085工程”项目

A parameterized algorithm for minimum node

weighted Steiner tree in logistics networks

LUO Yu-hong，LI Li

(School of Statistics and Information,Shanghai University of International Business and Economics,Shanghai 201620,China)

Received:2016-01-07 Revised:2016-10-07 Online:2018-01-25 Published:2018-01-25

摘要/Abstract

摘要：

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

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

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 P-NSMT 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.

Key words: logistics network, node weighted Steiner tree, minimum spanning tree, parameterized algorithm

罗玉宏，李莉. 物流网络中节点带权的Steiner最小树的参数算法[J]. 计算机工程与科学.

LUO Yu-hong，LI Li.

A parameterized algorithm for minimum node

weighted Steiner tree in logistics networks

[J]. Computer Engineering & Science.