[摘要]:随着环保意识的增强，对废弃物品的回收处理越来越得到人们的关注，广义生产者的责任迫使生产厂商彻底解决新的管理问题。问题之一是关于逆向物流网络的设计。本文提出了用在网络中寻找某一点最小支撑树的方法来解决处理中心选址的问题，并给出一个算例。
[关键词] 产品回收网络枢纽点最小枢纽树
0引言
随着科学技术的进步，产品生命周期的缩短，产品更新换代速度加快，被人们淘汰和废弃的产品也越来越多，于此同时，人们越来越重视环境保护，尤其是废旧产品的回收处理。于是，很多企业不得不面对弃置或者回收品，许多新的管理问题也应运而生。其中的一个关键问题就是产品回收逆向物流系统的网络设计，包括回收中心，处理工厂等设施定位和各设施间的运输网络优化等问题。国内外学者对这方面的研究也只是近10年的事情。Barros et al.[1]根据荷兰建筑沙土的回收案例建立了数学规划模型，通过对该模型求解，解决了系统中的决策问题。Spengler[2]建立了德国钢铁工作业副产品再利用的MILP模型，该模型基于多层库房定位问题。Blance,Krikke[3]研究了一个专门回收废弃车辆公司的回收系统，提出了一个考虑了随机因素的逆向物流网络模型。马祖军，张殿业，代颖[4]提出了一种在传统生产分销物流网络基础上进行再制造物流网络优化涉及的混合整数线性规划模型，目的是使各种再制造物流设施的投资和运营成本以及设施间的运输成本之和最小。李海婴，蔡长术，翟运开[5]以汽车业为支点进行成因分析和逆向物流网络的结构及其设计综述。马祖军，张殿业，代颖[6]分析了逆向物流的系统功能，逆向物流类型与结构，讨论了逆向物流网络设计问题。张华歆[7]提出了四种比较典型的逆向物流结构，建立一种逆向物流网络设计的多目标线性模型。本文采用网络图论的方法，将产品回收网络中处理中心选址的问题转化为在有向网络图中寻找一个最优点为枢纽点的最小支撑树的问题，并给出算例进行求解。
为了方便讨论, 我们先介绍有关基本概念[13]。
通常我们把有向图D=(V, A)(V是D的顶点集, A是其弧的集合, 可分别记为V(D)和A(D))中点vi与弧ai的有限交替序列l：v0a1v1a2v2…vn-1anvn(其中ai=(vi , vi+1)或ai=(vi＋1 , vi))称为点v0与vn之间的半通道; 若半通道l中所有vi均不相同，且l中ai=(vi , vi+1)(i＝0,1,…,n-1)，则称l为一条从点v0到vn的路，记为l=l(v0, vn)或l=(v0, v1,…, vn); 分别称路l中始点v0和终点vn的相关弧a1=(v0, v1)和an－1=(vn－1, vn)为l的始端弧和终端弧。若路l中vn=v0 ，则称l为回路。设有向图D'=(V', A')满足V'⊆V, A'⊆A, 称D'为D的子有向图；若V'≠∅, 称以V'为顶点集且以A"={a│a=(u, v)∈A, 且u,v∈V'}为弧集的子有向图为D中由V'导出的子有向图，记为D[V']；此外我们称有向图D和定义在其弧集A上的一个非负实数w(a)(a∈A)为网络，记为N=(D, w)，或记为N=(V, A, w)，也可称N[V']=(D[V'], w)为N中由V'导出的子网络。
定义1[13]. 设T=(V, E)是有向图D=(V, A)中的子有向图，v0∈V，如果∀v∈V，T中有唯一一条由点v0到v的路，则称T是以v0为根的支撑出树，简称为支撑出树；若∀v∈V，T中有唯一一条由点v到v0的路，则称T是以v0为根的支撑入树, 简称为支撑入树。若有V=V1∪V2,V1∩V2={v0}，且∀v∈V1, T中有唯一一条从v到v0的路, 而∀u∈V2，T中有唯一一条从v0到u的路，则称T是D中发自V1以v0为枢纽点的支撑树，简称T为(V1,v0)枢纽树，又简称为枢纽树，记作T(V1,v0) .
定义2[13]. 设T*是网络N=(D, w)中的(V1,v0)枢纽树，若N中任一棵(V1,v0)枢纽树T都满足：w(T)≥w(T*)(其中w(T)=∑a∈A(T)w(a)，A(T)是T的弧集), 则称T*为N中最小(V1,v0)枢纽树, 简称为最小枢纽树; 当T*是支撑入(出)树时, 称T*是以v0为根的最小支撑入(出)树, 简称最小支撑入(出)树。
定义3[13]. 设D是有向图，称D中弧a=(u,v)分别为点v和u的入弧和出弧，又设p是D中一条由点v0到u0的路，称D中不在路p上但却是p上点v' (v'≠v0)的入弧a' 和点u' (u'≠u0)的出弧a" 分别为D在p上的入桩和出桩，并称v' 为入桩a' 的桩端，u' 为出桩a" 的桩头。
为了讨论的方便，我们再引入以下有关运算符号。设D1=(V1, A1)和D2=(V2, A2)均为有向图，D1+D2=D，D=(V, A)是指: V=V1∪V2，A=A1∪A2；若还有V1⊆V2，A1⊆A2，则D2－D1=D', D'=(V', A')是指：V'=V2，A'=A2＼A1={a│a∈A2且a∉A1}，D'也可记为D'=D2－A1. 在有向图D=(V, A)中, 若V1⊂V, V2⊂V, 可记={v│v∈V且v∉V1}, (V1, V2)={a│a=(u,v)∈A且u∈V1, v∈V2} .
1 产品回收网络处理中心选址问题
网络由线路和节点构成，在逆向物流网络中，作为重点的处理中心，其操作和经营费用也同样影响着网络的构建。可以对本文要描述的问题定义如下：一定类型的回收品从消费者那里弃置下来，在有限数量的回收点予以回收，这些回收品经过一定的处理，处理的目的是以最小的成本恢复产品的最大经济价值，同时满足技术，法律，环保的要求。
现在，在物理网络设计的模型中，需要确定回收设施，本文主要讨论网络中处理中心位置的选择。目的是要使运输发费用，以及建设处理中心的投入成本最小化，同时满足需求与供给限制。
设有K个回收点的回收产品，经处理中心再重新分配到到J个分销处进行再分销，现已有若干拆解中心候选地I个。问题是如何从I个己有的处理中心候选地中选择若干个处理中心，与具体某一回收项目中己确定的回收点、分销地点构成最便捷、经济的网络，使逆向物流费用达到最小值。从这个实际问题就引出了一个在网络图中选择一个最优点为枢纽点的最短支撑树问题。