周 晓

福建江夏学院工商管理学院，福州，350108

1 相关研究与问题提出

物流网络是由若干物流节点以及连接这些节点的运输线路构成的。一旦建设成形，网络基础设施和设备在较长的一段时期内不会发生改变，各线路和节点的最大物流处理能力会对所流经物流量的大小产生约束，进而影响到整个物流网络流量的分布。随着多品种、小批量的物流需求特性日益突出，如何有效降低物流成本成为社会和企业要解决的关键问题。在已有物流网络资源条件下，对于具有较大物流处理能力的跨区域网络，可以通过规模经济效应有效提高网络资源利用率，从而达到降低成本的目的。此时，物流总成本是物流量的凹函数，但是，对于区域内部的物流网络，与跨区域网络相比，由于网络能力约束比较苛刻，物流量分布比较分散，规模经济效应难以实现，单位物流成本往往随着物流量的增加而增加，物流总成本往往表现为物流量的凸函数形式。物流成本是影响物流网络流量分配的决定因素，因此，综合考虑物流网络的混合凹凸成本属性和网络能力约束，对物流网络流量进行分配优化研究，具有现实意义。

在现有的相关研究中，物流网络的流量分配问题往往是综合在物流设施选址问题中进行研究的，针对该问题已出现了大量的研究成果[1-7]。多数学者是从算法优化的角度寻求设施选址问题的最佳求解方法，比如，以无容量约束的设施选址问题为研究对象，Watanabe采用人工蜂群算法[1]，akir提出了模糊c-均值(FCM)算法[2]，Heidari提出了改进的粒子群优化算法[3]分别对该问题进行求解。Armas考虑了客户需求和服务成本的不确定性，提出了一种启发式算法对随机无容量约束的设施选址问题进行研究[4]。针对无容量限制和有容量限制的二级设施选址问题，Litvinchev和Fernandes分别提出了拉格朗日启发式算法[5]和遗传算法[6]的求解方法。Qin结合库存决策问题来分析多商品物流网络设计问题，重点分析了物流节点的库存费用，并给出了节点的容量约束[7]，但是没有考虑线路的容量约束。这些研究多以成本最小化作为问题的优化目标，但是往往忽略了物流的规模效应以及容量约束对成本的影响。

本文根据不同的物流成本特性将物流网络分成两级，在考虑线路和节点容量限制的基础上，对整体物流网络的流量分配优化问题进行建模，并给出一种双层遗传算法进行模型求解。最后，通过算例验证该算法的有效性。

2 问题描述与数学模型

将物流网络简化为简单二级网络结构，第一级网络实现供应节点至中间节点的区域之间的货物流动。考虑规模经济效应，第一级网络物流成本是物流流量的凹函数。第二级网络实现货物由中间节点至各需求节点的区域内的分配。第二级网络由于规模操作性较前级网络大大降低，加上该级网络资源的能力约束，物流成本表现为物流流量的凸函数。针对上述二级物流网络结构，进行物流流量的分配优化研究，确定通过各中间节点的物流流量，供应节点至中间节点，中间节点至需求节点之间各路径的物流流量，目标是实现整体网络物流成本的最小化。

问题的假设条件设定如下：

(1)由于不平衡供需问题可以通过增加虚拟供应/需求节点将问题转化为平衡问题，因此，为简化问题，假设供应总量与需求总量相等；

(2)不考虑中间节点发生的物流成本；

(3)网络中所有货物都必须经过中间节点，无法直接由供应节点至需求节点；

(4)中间节点之间无物流流量分配；

(6)物流节点满足流量守恒条件。

问题的数学模型构建如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中，式(1)表示将第一级网络和第二级网络的物流成本综合考虑，以整体网络的物流总成本作为问题的目标函数，实现其最小化。式(2)和式(3)分别是供应和需求约束。式(4)和式(5)是中间节点的物流处理能力约束。式(6)是流量守恒约束。式(7)是路径容量约束。式(8)是网络物流流量的非负整数约束。

3 模型求解

具有凹费用特性和容量约束的物流网络流量分配优化问题是最小凹费用问题，属于NP-难问题[9]。以此问题为子问题的具有非线性凹凸费用的二级物流网络流量分配优化问题也属于NP-难问题，常规方法求解困难。问题的关键在于如何确定中间节点的物流流量分配，在此基础上便可以确定各级网络的物流流量分配。结合问题特性，设计出双层遗传算法对模型进行求解。内层优化算法应用于第一级和第二级网络的物流流量独立分配优化；外层优化算法通过确定中间节点流量分配，结合内层优化算法，实现整体物流网络的流量分配优化。

3.1 外层优化算法

3.1.1 染色体编码

3.1.2 群体初始化

用内层优化算法分别对两级网络的物流流量分配问题进行求解。其中，初始中间节点流量M′=M。进而分别得到各级网络的最优解X1和X2以及相应的M′(X1),M′(X2)。

初始群体生成方法如下：

Step1:M′←θ1M′(X1)+θ2M′(X2)。θ1,θ2是随机数，满足θ1+θ2=1;

Step2:用内层优化算法分别对两级网络的进行求解；

Step3:循环以上两步骤，直至个体数量满足要求为止。

3.1.3 选择机制和适应函数

由于(μ+λ)选择策略在搜索过程中不仅能够保留最佳个体，而且能够加速算法收敛[10]，所以采用该策略作为群体中个体之间的竞争机制，即在μ个父代个体以及由这μ个父代个体交叉产生的λ个子代个体中选择μ个适应性最佳个体。算法以目标函数值，即整体网络的物流总成本作为个体的适应函数。

3.1.4 交叉操作

λ1←(f11+f21)/(F1+F2)

λ2←(f12+f22)/(F1+F2)

3.1.5 变异操作

3.2 内层优化算法

3.2.1 染色体编码

由于问题的可行解表示满足各项约束条件的物流网络流量分布方式，所以用X={xijk|∀i,∀j,∀k}代表染色体，xijk代表染色体基因，表示节点i至节点j的第k条路径上的物流流量。对于第一级网络，i,j,k分别代表r,w,p；对于第二级网络i,j,k分别代表r,w,q。

3.2.2 群体初始化

为了加快算法的收敛速度，在包括最优解的可行域内选择初始群体。通过对文献[11]中介绍的启发式方法增加路径约束，得到如下初始可行个体的求解方法：

step1:xijk,yijk←0；

step2:yijk←min(Ui,Vj,Cijk)+yijk；

step3:Pijk←argmin{f(yijk,Lijk)/yijk|yijk≠0}；

step4:xijk←yijk；

step5:Ui←Ui-yijk,Vj←Vj-yijk,Cijk←Cijk-yijk；

step6:循环step2-step5，直至所有物流量分配完毕。

为了实现群体的多样性，群体中大多数的个体通过对初始个体进行变换得到，其他少数剩余个体通过随机选择路径进行流量分配得到。变换操作的具体思路是任意选择若干条流量为0的路径，根据闭回路法找到包含每条路径的回路或者与其平行的路径，继而可以由回路中各路径流量或者平行路径流量以及各路径的容量限制确定所选择路径的流量大小，回路中其他路径或者平行路径的流量相应进行增减。显然，所得初始群体均为问题的可行解。

3.2.3 选择机制和适应函数

选择机制与外层优化算法相同，适应函数取子网络的物流成本函数。

3.2.4 交叉操作

依据参考文献[12]提出的交叉方法，内层优化算法的交叉方法设计如下：对于个体X1和X2，取X2中流量不为0，且X1中流量为0的所有路径的一半作为X1的变换路径，对其执行前面介绍的变换操作。变换路径的选择是根据下式进行的：

(9)

即，取αijk值小的路径优先进行变换。

3.2.5 变异操作

变异操作在一定变异概率下通过随机选择子代个体中流量为0的路径进行变换操作来实现。当变异的个体为子种群中的最佳个体时，同样采用(1+1)选择策略。

4 算例验证

表1 第一级物流网络的路径容量和长度

表2 第二级物流网络的路径容量和长度

通过一系列的测试确定算法参数取值如下：交叉概率为0.9，变异概率为0.1；内层优化算法μ=100，λ=200，迭代次数500；外层优化算法μ=50，λ=100，迭代次数100。对算法进行多次运行后得到的部分计算结果如表3所示。由表3可知，该算例的最优目标值为51 605单位费用，相应的物流网络流量最优分配方案如表4所示。

表3 部分计算结果

表4 物流网络流量的最优分配方案

5 结 论

规模经济效应是影响多品种、小批量需求特性下物流网络流量分配方式的重要因素。规模经济效应表现为单位物流成本随着物流量的增加而减少，物流总成本是物流量的凹函数。物流线路和节点的能力约束是影响物流网络流量分配的另一个重要因素。当网络能力约束比较苛刻，并且物流量分布比较分散时，规模经济效应难以实现，单位物流成本往往随着物流量的增加而增加，物流总成本是物流量的凸函数。本文以二级物流网络为研究对象，在详细分析各级物流子网络特征的基础上，建立了物流网络流量分配优化模型，该模型考虑了物流网络节点和线路的容量约束与运输的规模经济效应对成本的影响，将物流总成本定义为流量的混合非线性函数，并给出了一种双层遗传算法对模型进行求解。该算法由求解各级物流子网络的流量分配方案的内层算法和求解连结两级子网络的中间节点的流量分配方案的外层算法所构成，通过两层算法的不断迭代运行，最终得到优化结果。最后，用算例验证了模型和算法的有效性。