罗玉宏，李 莉

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

1 引言

物流网络通常是指物流企业经营活动中所涉及的物流运输网络、物流信息网络和物流客户网络[1]。在我国，物流成本占GDP的20%，远远落后于发达国家10%的比重，调查显示，运输配送成本占物流总成本的60%左右，因此优化物流运输网络能有效地降低物流成本。对物流运输网络优化的核心是确定合适的物流节点位置、规模和数量，选择合适的连接线路及运输方式，使物流网络在满足服务要求的基础上总的运输成本最低。对物流运输网络的优化一直是国内外学者研究的热点，在物流业比较发达的欧美国家和日本，研究人员利用数学规划法、系统仿真法和启发式方法等技术工具对企业物流的组织管理模式、运营机制、设施选址、配送路径选择、物流成本优化等问题提供支持[2]。

1.1 问题描述

1.2 研究现状

对这类问题的研究，主要集中在物流配送中心选址与路径的优化。配送路径优化问题分为点点间运输、多点间运输、单回路运输及多回路运输等类型，并且结合各种现实条件，如最短时限运输问题、带时间窗的路径优化问题、带车容量限制的路径优化问题等进行研究[3]。由于运输路径优化是NP-hard问题，国内外对该问题的研究方法主要有：利用博弈论中的夏普里值方法解决物流网络中的转载运输问题；利用基于模型的推理方法和启发式搜索方法解决仓库设施的定位问题，以及物流网络结构设计中的聚集或分散决策；采用基于多目标规划设计物流网络的优化框架；借助排队论和非线性理论研究城市物流中心的选址和规模问题等[4,5]。

本文采用的研究方法是将物流网络模型抽象成平面图，将问题求解转化为构造一棵节点带权的Steiner最小树问题。这类问题的求解同样是NP-hard问题，采用的方法主要有精确解法、近似解法和参数解法[6,7]，代表性算法如下：

精确算法主要有支撑树穷举法、拓朴枚举法等[8 - 11]，Melzak[9]提出的欧氏Steiner最小树ESMT(Euclidean Steiner Minimum Tree)算法(简称K-ESMT)是当前求解Steiner最小树程序的核心思想，它将基于原点集的Steiner树的所有可能的拓扑结构进行分解，在分解为若干满Steiner树后，分别计算其总长，然后设法求出由这些满Steiner树的并集所构成的Steiner最小树，算法的运行时间达到O(nm) (m表示终端节点的个数，n表示网络的规模)。Shore等人[11]提出分支界定的方法，判断将一条边是否放入最优的Steiner树进行分支，然后再在各分支中分别考虑其最小连通性，时间复杂度为O(24n)。精确算法的时间复杂度高，当网络规模增大时，影响实际的应用。

因此，人们对Steiner树问题的研究主要集中在多项式时间可解的近似算法[11 - 17]。近似算法是在最差情况下找到的近似解与最优解的比值作为算法的近似度，以此作为衡量算法好坏的重要指标[13]。Kou等人[13]最早给出问题的近似算法，利用启发式算法获得一个近似比接近2的极小Steiner树，时间复杂度为O(nlogn)。Thomposon[15]利用最小生成树近似求解Steiner树 ，通过添加一个Steiner点来连接三个邻近的点，并通过删除边来避免环的出现，算法的时间复杂度为O(n4)。Robins[17]提出近似度接近最好的近似算法(简称Z-ESMT)，与传统方法不同，该算法尽可能少地压缩边，迭代地修改终端节点生成树，近似率接近1.55，时间复杂度为O(nm)。

参数理论是近年来发展起来的解决该难题的一项有效技术。参数理论的研究最初来源于观察到很多计算问题都与一个取值范围很小的重要参数相关，利用参数的性质可以在一定程度上加速计算[18]。Dreyfus和Wagner[19]基于分解技术提出的动态规划算法是求解Steiner树的经典算法，时间复杂度为O(3kn+2kn2)，其中k表示要覆盖的节点个数。Mölle等人[20]采用动态规划对问题进行求解(算法简称M-ESMT)，具有较好的时间复杂度O((2+ε)k·p(n))，其中0<ε<1，该算法的问题在于，当ε趋近于0时，p(n)的指数上升很快。例如，当ε=0.5时，时间复杂度为O(2.5kn14.2)，当ε=0.1时，时间复杂度为O(2.1kn57.6)，使得算法实际不可行。

借助参数算法理论，本文提出了一种新的启发式算法P-NSMT(Parameterized algorithm for Minimum Node Weighted Steiner Tree)。实验表明，与其他同类型的算法相比，该算法具有更好的准确性和时间效率，特别适应于网络规模大、终端配送节点少的物流网络。

2 网络模型

在物流运输网络中，全部物流活动都在线路和节点上进行。线路指已经开辟的可以按规定进行物流运营的路线和航线，包括铁路线路、公路线路、水运线路、空运线路等。节点是物流网络中连接物流线路的结节之处，具有转运、存储、流通等特点。在线路上进行的活动主要是运输，产生运输费用，物流功能要素中的其他功能要素，如包装、装卸、保管、分货、配货、流通加工等都是在节点上完成的，产生节点费用[1]。

2.1 网络模型构建

为了便于构建网络模型，提出如下假设：

(1)每个城市看成一个节点，节点根据城市分类的等级，产生的节点费用各不同。因为建立配送中心的费用很高，为了便于研究，本文将建设成本平均分摊到若干年货物转运的单位成本中。

(2)任意两个节点都是连通的，如果两个节点有线路直达，则称这两个节点相邻，互为邻居，节点邻居的个数称为节点的度。如果两个节点不是邻居，则必须通过其它节点中转。

(3)设货物运输始发地为源节点，货物运输目的地为终端节点。为方便最小运输费用的研究，这里假定各节点都有足够的运输工具运送货物，并且都能在约束的时间内将货物运到。这些因素可以在选择运输工具或中转城市时作为约束条件引进，或设立配送中心解决。

(4)每个节点仅知道到相邻节点的货物运输费用，如果两个节点之间存在多种运输形式，采用价格较低的运输方式。

将上述问题转化为网络模型：一个无向图G=(V，E)。V是节点(顶点)集合，对应相应的源节点、中转节点和终端节点；E是链路(边)集合，对应相邻城市间的运输线路。e=[i,j](i,j∈V)是E中的任一条边，Eij表示从节点i向节点j运送单位货物所需要的费用。Vi表示节点i的节点费用。构建以始发地s为源节点，目的地Di为终端节点的生成树T，要求生成树T对应的总运输费用C(T,s)最小。

2.2 运输问题的转换

定义1基于源节点s的生成树T中节点i的运输费用为:

(1)

其中，Vs是源节点费用，Vi是中转或终端节点i的节点费用，Eij是单位货物从节点i运输到其邻节点j所产生的费用。

定义2货物运输的总费用，即Steiner树T的总权值为:

(2)

其中，dj是运往终端节点的货物重量，m是终端节点的数量。i=s..j是从源节点s到终端节点dj在生成树T中经过的路径节点编号，Ci(T,s)按照公式(1)计算，表示单位重量货物在从节点i到路径的下一个节点j所产生的运输费用。

因此，上述运输问题转换为求节点带权的Steiner最小树问题(Node Weighted Steiner Tree Problem)，这类问题属于NP-hard问题[21]。

3 参数算法

3.1 参数问题转换

在参数算法中，用参数理论来求解NP-hard问题，本节首先要将该问题转化为参数化问题。因此，首先将上述问题转换为参数算法中连接的顶点覆盖问题，然后提出启发式算法P-NSMT。

连接的顶点覆盖问题[22]：

输入: 一个给定的无向连通图G(V，E)以及一个正整数k，k≥|m+1|。

问题: 图G是否存在一个大小为k的顶点覆盖G′⊂G，G′是包含m+1个指定节点的连通树，并且树的总权值最小。

3.2 Steiner树的相关性质

为了获得参数k的值，需要用到文献[23]中Steiner树的相关性质。因此，首先需要将模型中节点带权的Steiner树转换为Steiner树。转换方式如下：

(1)节点费用包括两大部分：中转货物的费用和到达目的节点收货、存货等费用。其中到达目的节点收货、存货等费用与运输路径的选择关联度较小，只与到达目的节点的货物重量有关，因此这方面的费用本文暂不讨论。

(2)中转货物的费用与运输网络的优化有较大关系。模型中节点带权的Steiner树，边的权值是单位货物的运输费用，以节点间距离的形式呈现，与模型假设(1)节点中转单位货物的费用是统一的。因此，只要将中转单位货物的节点费用直接分摊到边的权值中去，就可以将节点带权的Steiner树转换为Steiner树，不会改变网络的连接结构。然后，直接使用已有的Steiner树的性质[23]：

在无向连通图G中，有m个终端节点和1个源节点，令σ=max(Eij)/min(Eij)，Eij∈E。

推论1在连接的顶点覆盖问题中，节点带权的Steiner最小树T的节点数k≤m+1+l。

4 P-NSMT算法

4.1 算法描述

P-NSMT算法思想是首先尽可能只利用终端节点构造一棵连通的最小生成树，然后逐步向树中添加能减少生成树总权值的Steiner节点，最终生成一棵节点总数不超过参数k的Steiner最小树。算法包括三个阶段：

第一阶段，在图G中建立以源节点s为根节点，包含所有终端节点的初始生成树T。过程如下：

(1) 将所有节点设置成白色节点，源节点s设置为黑色节点；

(2) 将源节点s的所有邻居节点变成s的孩子节点(叶子节点)，并将这些孩子节点设置成黑色节点；

(3) 如果存在终端节点不包括在生成树T中，遍历树T的叶子节点，分别将这些节点的白色邻居节点变为其孩子节点(叶子节点)，并将这些白色邻居节点设置成黑色节点；

(4) 重复步聚(3)，直到所有的终端节点都包括在生成树T中(可能会存在一些未加入生成树的非终端节点)。

这个阶段也可以采用文献[24]提出的分布式算法，直接构造一棵包含所有终端节点的最小生成树，时间复杂度可以控制在O(nlogn)。

第二阶段，对生成树T进行预处理，构造一棵尽可能只包括终端节点的连通的最小生成树。过程如下：

(1)因为在最小覆盖G′中，叶子节点必须是终端节点。所以，先去掉所有不可能出现在最小覆盖G′中的节点，删除规则为：

① 在生成树中，叶子节点j不是终端节点，如果它没有别的邻居节点，不作为Steiner候选节点，直接删除它(如图1a所示)。

Figure 1 Rules of deleting non candidates for Steiner node图1 删除非Steiner候选节点的规则

② 在生成树中，叶子节点j不是终端节点，如果它的任一邻居节点u是它的兄弟，且父节点到j的运费大于到节点u的费用(Eij>Eiu)，节点j不是Steiner候选节点，直接删除它(如图1b所示)。

③ 对于不属于生成树中的非终端节点，如果它的度不满足性质1的要求，那么它不是Steiner节点，直接删除它。

(2)将生成树T剩下所有非终端节点的叶子节点剪枝后，作为备选的Steiner点存放在集合B中。

(3)利用启发式算法对生成树T进行优化，建立总费用趋向最小的生成树：

按轮对生成树T进行优化操作，每一轮优化过程都是从生成树根节点s开始。为方便计算，每个节点都有一个存储变量C，用来存放从源节点s运送货物到该节点所需要的费用之和。优化算法STO(T,s)：

① 首先按照公式(1)分别计算从根节点s运输货物到它任一孩子节点所需要的费用Cs(T,s)，并将其分别告知其孩子节点，孩子节点将其存放在各自的C中。

② 按照广度优先的次序依次遍历树T的每一个节点(按照当前生成树的顺序，不管本轮中树的结构是否发生变化)。设初始值f=1(用f=0表示有交换父节点操作发生，f=1表示没有交换父节点的操作发生)。如果一轮遍历结束后，f还是为1，则终止优化。

③ 当遍历经过节点i时，节点i的处理过程Handle(i)如下:

a.节点i的任一邻居节点j(j不在节点i的子树中)计算其运输货物到节点i的总费用C′=(C+Cj(T,s))(这里C是节点j的存储变量)并告知节点i;

b.节点i比较自身的C与C′的大小，如果存在C′

c.节点i分别计算它运输货物到它任一孩子节点所需要的费用Ci(T,s),然后将C+Ci(T,s)的值分别告知它的孩子节点，孩子节点将值存放在各自的C中；

d.遍历下一个节点。

④ 删除可能存在的非终端叶子节点，将其移入Steiner点的备选集B中。

显然，这时树T中仅包含源节点和终端节点，以及将终端节点连通必不可少的非终端节点(如果源节点和终端节点不能直接构成连通图)，生成树T的总费用接近最优，并且|T|≤k。

为了更好地理解Handle(i)的处理过程，举例如下(图2)：节点i原来的父节点为v，从源节点到v的运输费是3(C=3)，计算从源节点到i的运输费用为C+Vv+Evi=11,令节点i中C=11。u和v分别是节点i在树中的邻居节点，如果从节点u运送货物到节点i，它的运输费用为C+Vu+Eui=15>11，所以u不是节点i更换父节点的对象。如果从节点j运送货物到节点i，它的运输费用为C+Vj+Eji=6<11，所以j可以成为节点i新的父节点。更改节点i的父节点v到j，更新节点i中的C=6。

Figure 2 Node i changes its father node v→j图2 节点i改变父节点v→j

第三阶段，向生成树T中逐步加入符合优化条件的Steiner点，减少生成树T的总费用。

(1)如果|T|

(2)依次从备选集B中取出一个节点v(v必须是树T中节点的邻居节点)。

(3)节点v在它的邻居节点中寻找属于生成树T中的节点u，使节点v连接到节点u后，节点v中的C值最小。

(4)对节点v在生成树中的任一邻居节点j(节点u除外)进行是否更改父节点判断，如果j选择v作为其父节点,则证明节点v的加入将减少生成树的总费用，那么：

① 将v连接到节点u,将|T|加1;

② 将j连接到节点v,更新j中的C值，对j子树Tj进行STO(Tj,j)优化操作；

③ 删除T中存在的非终端叶子节点，每删除1个，进行|T|减1的操作，并且更新生成树T的信息。

(5)如果备选集B中符合条件的任一节点加入后，生成树不再改变，终止算法。

4.2 算法性能分析

定理1P-NSMT算法的时间复杂度为O(nlogn+kδGδT+k2logk+k2δT)。

证明对P-NSMT算法的复杂度进行分析：

第一阶段构造初始的生成树T，最快可以达到O(nlogn)[24]；

第二阶段中第(1)、(2)步对生成树T进行剪枝操作的时间复杂度为O(nlogn)，第(3)步在优化初始的生成树T的过程中，Handle(i)的时间复杂度为O(δT)，δT是树的度。因此，STO(T,s)算法的时间复杂度为O(klogk+kδT)。

第三阶段生成树优化过程中，最多会对kδG个节点进行是否改变连接节点的判断，δG是图G的度，时间复杂度为O(kδGδT)，最多会对k-m个节点进行子树优化，处理时间为O(k2logk+k2δT)。这个阶段算法的时间复杂度为O(kδGδT+k2logk+k2δT)

因此，P-NSMT算法总的时间复杂度为O(nlogn+kδGδT+k2logk+k2δT)。

证毕。

□

由定理1可知，当k值相对n较小时，可以大大提高算法的性能。当k值增大时，算法的性能会慢慢下降，当k→n，算法的第二阶段对所有的节点组成的生成树进行优化操作，通过剪枝后直接生成Steiner最小树，不再进行第(3)阶段的操作。因此，有如下推论：

推论2当k→n时，算法的时间复杂度为O(nlogn+nδG)。

5 实验结果

5.1 模拟环境

比较P-NSMT算法与其它有代表性的构造Steiner最小树算法的性能，这些算法包括：精确解法K-ESMT、近似解法Z-ESMT和参数解法M-ESMT(ε=0.5)。为了便于比较，实验中事先将节点带权的Steiner树转换成Steiner树，再运算出相应的结果。

分别在不同的网络规模、不同数目的终端节点情况下，比较算法P-NSMT、K-ESMT、Z-ESMT和M-ESMT的准确性和效率，这两个指标的计算方法定义如下：

其中:alg∈A={Z-ESMT,K-ESMT,M-ESMT,P-NSMT},C(Talg,s) 表示用A中的算法生成以s为源节点的Steiner最小树的总费用，用公式(2)计算,C(Tbest,s)=min{C(Talg,s),alg∈A};Time(Talg) 表示用A中的算法生成以s为源节点的Steiner最小树的计算机运行时间,Time(Tbest)=min{Time(Talg),alg∈A}。

5.2 模拟结果

实验在不同的网络环境下分别模拟100次，取95%的置信区间，结果如下：

(1) 算法准确性NormalizedCost的比较。

分两种情况，第一种情况，当节点规模固定、终端节点数不同时，比较算法的NormalizedCost值。图3a显示了网络规模为1 000个节点，终端节点数m分别为(10，40，70,100)的仿真结果。从图中可以看出，采用精确解法的K-ESMT算法，求解出来的Steiner最小树的总运费是最少的。P-NSMT算法的结果接近于最小的精确算法K-ESMT的结果，差距不超过2%，不同的终端节点数目对算法的准确性影响不大，并且随着终端节点数的增大，差距更加缩小。其它两种算法的结果差距也基本上能控制在10%以内。

第二种情况，当终端节点数比例相同、网络规模不同时，比较算法的准确性。图3b显示了终端节点比例为10%，网络规模分别为(100，400，700，1 000)的仿真结果。从图中可以看出，当终端节点比例固定为10%时，采用精确解法的K-ESMT算法的准确性最高。其他三种算法随着网络规模的增加，算法的准确性都得到了提高。P-NSMT算法优于Z-ESMT算法和M-ESMT算法，与K-ESMT算法最大差距为5%,最小差距为1%。

Figure 3 Normalized Cost of the Steiner trees constructed by different algorithms图3 各算法准确性Normalized Cost的比较

(2) 算法运行效率NormalizedTime的比较。

比较各算法建立Steiner最小树的运行时间，实验平台的主要配置为Windows 7操作系统，Intel® CoreTMi3 CPU M380@2.53 GHz,内存2 GB，使用C++编写算法并使用GCC4.8.5进行编译。

实验同样分两种情况。第一种情况，当节点规模固定、终端节点数不同时，比较算法的运行时间。图4a 显示了网络规模为1 000个节点，终端节点数m分别为(10，40，70，100)，算法的NormalizedTime的值。结果显示，P-NSMT算法的时间性能是最好的，特别是在终端节点数为10的时候，K-ESMT算法和M-ESMT算法运行时间分别达到了P-NSMT算法的9 351倍和8 025倍，近似算法Z-ESMT运行时间是P-NSMT算法的3 068倍。当终端节点数增多时，四者的差距迅速缩小。当终端节点数达到100时，时间的差距缩小到300以内。可见，P-NSMT算法在终端节点数很小时，更能体现出算法的时间性能优势。

第二种情况，当终端节点比例相同、网络规模不同时，比较算法的运行时间。图4b显示了当终端节点比例占10%，网络规模分别为(100，400，700，1 000)，各算法的NormalizedTime的值。可以看出，时间性能的差距不大，当网络规模为100时，四个算法的差距不超过40倍；随着网络规模的增大，运行时间的差距慢慢增大，当网络规模达到1 000时，差距扩大到300倍左右。

从两种情况都可以看出，P-NSMT算法的时间性能是最好的，其次是Z-ESMT算法，时间性能最差的是K-ESMT算法和M-ESMT算法。虽然M-ESMT算法理论上的时间复杂度比Z-ESMT算法和K-ESMT要好，但实际操作中，并没有反映出来。P-NSMT算法无论是在理论时间复杂度还是实际的运行时间上，都体现了性能上的优势，特别是当终端节点数目远小于网络规模时，更加能体现出算法的时间性能优势。

Figure 4 Normalized Time of the Steiner trees constructed by different algorithms图4 各算法运行效率Normalized Time的比较

6 结束语

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

下一步的研究工作将运用参数算法解决多源点和多终端节点的物流网络优化问题。综合考虑最短时限运输问题、带时间窗的路径优化问题、带车容量限制的路径优化问题等，使算法的更趋向于实际应用。

[1] Alan H, Remko V H. Logistics management and strategy:Competing through the supply chain[M].4th Edition.Upper Saddle River:Prentice Hall,2011.

[2] Xiang Tao.Research status and future trends of logistics network[J].Science & Technology Economy Market,2008(1):41-42.(in Chinese)

[3] Li Zhen-ping,Zhou Wen-feng.Modeling and solving of logistics distribution center location and path optimization problem [M].Beijing:China Machine Press,2014.(in Chinese)

[4] Ju Song-dong,Xu Jie,Bian Wen-liang,et.al.Putting forward and research on MF network theory[J].Journal of Beijing Jiaotong University(Social Sciences Edition),2009,8(2):16-20.(in Chinese)

[5] Gong Gu, Hu Xiao-ting,Wei Kai-xia,et al.Optimized performance research of the vehicle routing problem in industry logistics[J].Computer Engineering & Science,2011,33(5):106-111.(in Chinese)

[6] Zheng Ying,Wang Jian-xin,Chen Jian-er.Survey of Steiner tree problem[J].Computer Science,2011,38(10):16-22.(in Chinese)

[7] Tobias P,Siavash V D.The Steiner tree challenge:An updated study[EB/OL].[2014-08-24].http://dimacs11.cs.princeton.edu/downloads.html.

[8] Markus L, Zvana L, Martin L, et al. New real-world instances for the Steiner tree problem in graphs[R].Vienna:Department of Statistics and Operations Research, University of Vienna,2014.

[9] Melazk Z A.On the problem of Steiner[J].Canadian Mathematical Bulletin,1961,4(1):143-148.

[10] Huang T, Young E F Y. Obsteiner:An exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2013,32(6):882-893.

[11] Shore M L,Foulds L R,Gibbons P B.An algorithm for the Steiner problem in graphs[J].Networks,1982,12(3):323-333.

[12] Uchoa E, Werneck R F.Fast local search for the Steiner problem in graphs[J].ACM Journal of Experimental Algorithms,2012,17(2):2.2:1-2.2:22.

[13] Kou L,Markowsky G,Berman L.A fast algorithm for Steiner trees[J].Acta Information,1981,15(2):141-145.

[14] Hougardy S,Silvanus J,Vygen J.Dijkstra meets steiner:A fast exact goal-oriented Steiner tree algorithm[EB/OL].[2015-09-08].https://arxiv.org/abs/1406.0492.

[15] Thomposon E A. The method of minimum evolution[J].Annals of Human Genetics,1973,36(3):333-340.

[16] Pajor T,Uchoa E,Werneck R F.A robust and scalable algorithm for the Steiner problem in graphs[EB/OL].[2014-12-10].http://arxiv.org/pdf/1412.2787v2.pdf.

[17] Robins G,Zelikovsky A.Improved Steiner tree approximation in graphs[C]∥Proc of Symposium on Discrete Algorithms,2000:770-779.

[18] Chen J.Parameterized computation and complexity:A new approach dealing with NP-hardness[J].Journal of Computer Science and Technology,2005,20(1):18-37.

[19] Dreyfus S E,Wagner R.The Steiner problem in graphs[J].Networks,1971,1(3):195-207.

[20] Mǒlle D,Richter S,Rossmanith P A.Faster algorithm for the Steiner tree problem[C]∥Proc of the 23rd Symposium on Theoretical Aspects of Computer Science,2006:561-570.

[21] Li Zhen-jian, Zhu Hong.An approximation algorithm of minimum spanning tree with edges and vertices weight[J].Computer Applications and Software,2008,25(1):12-13.(in Chinese)

[22] Chen Jian-e, Kanj I, Jia Wei-jia.Vertex cover:Further observations and further improvements[C]∥Proc of the 25th International Worshop on Graph-Theoretic Concepts in Computer Science, 1999:313-324.

[23] Liang Zhao-jian.The distributing of terminals and the prop-

erty of Steiner vertices on the Steiner tree problem[D].Changsha:National University of Defense Technology,2004.(in Chinese)

[24] Gallager R, Humblet P A, Spira P M.A distributed algorithm for minimum weight spanning trees[J].ACM Transactions on Programming Languages and Systems,1983,5(1):66-77.

附中文参考文献:

[2] 向涛.物流网络研究现状及未来趋势[J].科技经济市场，2008(1):41-42.

[3] 李珍萍,周文峰.物流配送中心选址与路径优化问题—建模与求解[M].北京:机械工业出版社,2014.

[4] 鞠颂东,徐杰,卞文良,等.物流网络理论的提出与探究[J].北京交通大学学报(社会科学版),2009,8(2):16-20.

[5] 巩固,胡晓婷,卫开夏,等.物流配送车辆路径问题的优化研究[J].计算机工程与科学，2011,33(5):106-111.

[6] 郑莹,王建新,陈建二.Steiner Tree 问题的研究进展[J].计算机科学,2011,38(10):16-22.

[21] 李镇坚,朱洪.一种点边带权最小生成树的近似算法[J],计算机应用与软件,2008,25(1):12-13.

[23] 梁兆健.Steiner树问题中正则点分布Steiner点性质[D].长沙：国防科学技术大学,2004.