摘 要：本文根据物流选址-分配两级中转运输实际，首先提出了受多重能力约束的两级设施选址-分配问题模型和两种启发式算法，然后用两种算法对进口物资中转运输两级设施选址-分配问题进行了研究，并根据对比研究结果对局部贪婪算法进行了改进。本文所提出的模型和改进算法，能用来解决具有相同能力约束的两级设施选址-分配问题，或为之提供参考。

关键词：贪婪算法;物流;选址-分配

在物流实践中，有许多的进出口物资要经过两次甚至更多次的换装才能运抵目的地，因此，研究受多重能力约束的两级设施选址分配问题，不仅为解决大型企业进口原材料物流系统优化奠定基础，而且也为解决相应的两级设施选址-分配问题提供指导。

本文研究的受多重能力约束的两级设施选址-分配问题，在将节点和边同时都带最大和最小单批容量转化为边带最大和最小单批容量的基础上，考虑物流网络在边的最大单批容量和最小单批容量、物流中心吞吐能力和运输工具总运输能力等多重能力约束下，如何进行中转运输的物流中心选址和相关资源分配，使总的费用最小。即本文研究的受多重能力约束的两级设施选址分配问题，是考虑边的带最大和最小单批容量的受多重能力约束的两级设施选址-分配问题，模型假设网络系统满足一个条件，即物品只能用不同运输工具经过某两级物流中心节点进行中转运输。

一、局部贪婪算法的改进

基于Dijkstra最短路法的全贪婪算法并不是最优的。通常局部贪婪算法所求得解不及最短路法所求得的解[4]。通过对相关求解过程的分析发现，以上提出的局部贪婪算法，既未完全优先选用平均单位运费较高的节点上单位变动费用较低的物流通路作为运输路线，又未能将单位运费低的运输工具的安排在其最具优势的运输路线上。针对以上问题，本文提出的局部贪婪算法进行改进，主要的改进体现在物流通路选取中物流文点的优先次序方面，即用“平均离差较大的一级文点（中转文点或需求文点）的平均单位变动费用从高到低的文点顺序”代替“物流中心文点数多的一级物流中心文点的平均单位变动费用从高到低的文点顺序”。改进后的局部贪婪算法的简要步骤如下：

第一阶段，中转站选址

1.计算边能通行的运输工具的平均单位运费。

2.分级计算各物流中心文点和需求文点物流通路的平均单位变动费用。平均单位变动费用包括物流通路各边的平均单位运输、各中转文点的单位变动费用之和。

3.分级选取物流中心文点并初步选取其吞吐量。各级物流中心文点选取的方法、步骤及添加文点的要求同。分级计算物流中心文点和需求文点的物流通路平均单位变动费用的平均离差。如果需求文点的平均单位变动费用大于各级物流中心文点的平均单位变动费用离差，则已选取的全部物流中心文点的吞吐量为其全部吞吐能力。

第二阶段，资源和运输量分配

1.确定已选取的物流中心文点所连接的边能通行的运输工具，并计算其物流通路在不同的运输工具组合下的单位运费。

2.分配資源和运输量

分配资源和运输量的方法。在已选取的物流中心文点及已选用的吞吐量范围内，在供应文点的剩余供应量、物流中心文点的剩余吞吐能力和需求文点的剩余需求量均大于0的物流通路中，依平均离差较大的一级文点（中转文点或需求文点）的平均单位变动费用从高到低的文点顺序，依次选用单位运费低的物流通路作为运输路线，按整车（船）运输的原则，选取该运输路线中物流中心文点的剩余吞吐能力、供应文点的剩余供应量、需求文点的剩余需求量和相应运输工具的剩余运输能力中的最小值作为该运输路线中各运输工具在相应文点间的运输量。按此方法重复进行迭代，直到满足需求。此步骤同时确定了决策变量y^r_ij的取值（若则x^r_ij>0则y^r_ij=1;反之y^r_ij=0）。

如果已选取的物流中心文点所连接的边a_ij（a_ij=能通行的运输工具的总运输能力小于该文点所选取的吞吐能力，则将该文点剩余的吞吐能力转移至已选取的同级物流中心文点中平均单位运费最大的物流中心文点，重新进行第五步。

如果已选取的物流中心文点中平均单位运费最大的文点没有剩余吞吐能力，或者其剩余吞吐能力比拟转移的吞吐能力小，则返回第四步添加同级物流中心文点。新添加的同级物流中心文点的吞吐能力为拟转移的吞吐能力与已选取的物流中心文点中平均单位运费最大的文点的剩余吞吐能力的差值。

3.计算各运输工具在各条边上的运输量。

4.计算目标函数值。

二、结论

本文的研究，一方面，注重模型的针对性，相关算法的快捷，另一方面，注意模型与算法的普遍适用性，力求为设施选址与运输决策的综合研究与应用提供理论和应用上的铺垫。研究成果对相关企业进行物流系统设计或日常物流运营具有指导或参考价值。

参考文献

[1] 杨珺，杨超，马云峰.带有双重容量限制的FIP问题研究[J].中国公路学报，2004（4）：88-91.

[4] 邢文训，谢金星.现代优化计算方法[M].北京：清华大学出版社， 2003，2.

【作者简介】 王锐（1967—），女，大专，研究方向：企业经营管理。