龙源期刊网 http://www.qikan.com.cn

物流配送中心选址问题的0—1规划并行算法

作者：沈萍 陈燕 李捷 杨雪君

来源：《计算技术与自动化》2012年第03期

摘要：建立物流配送中心选址问题的0—1混合整数规划模型，并结合目标排序法和改进的PSRS设计求解0—1规划的并行算法。改进PSRS可将各个目标的验证任务进行均衡划分，并提交给各个处理器并行进行可行性验证，算法理论上具有接近处理器个数p的加速比。

关键词：配送中心选址；0—1整数规划；并行算法； 中图分类号：TP301.6 文献标识码：A

0—

Distribution Centers

，

，

，

，

（1.School of Computer， Electronics and Information， Guangxi University， Nanning530004， Guangxi， China；

2. Department of Computer， Electronics and Information Engineering， Guangxi Polytechnic， Nanning530226， Guangxi， China；

3.Guangxi Electronic Products Supervising And Testing Institude，Nanning530031，China） Abstract：According to the theory of 0—1 programming， this paper presents the model for the problem of logistics distribution centers location. And a new parallel algorithm for the proposed model is given based on objective values sorting and improved PSRS. The tasks of verify solutions have been partitioned and submited to p processors， which verify solutions in parallel. The proposed method have excellent speed up in p.

龙源期刊网 http://www.qikan.com.cn

Key words：location of logistics distribution centers；0—1 integer programming；parallel algorithm；PSRS 1引言

在物流网络中，配送中心是供需双方的连接纽带，是整个物流系统的核心。如何有效的进行配送中心的选址是物流网络系统规划的核心问题，往往决定物流配送网络系统的结构、形状和配送模式，进而对物流系统的运作效率乃至物流行业经济效益的提高有重大影响。 针对配送中心选址的研究，国内外的学者主要围绕配送中心选址模型的建立和求解两方面展开研究，在理论和实践上都取得了较大的成果。目前物流中心选址模型大致可分为连续性模型和离散性模型两类。连续性模型对备选地点没有特别限制，但是有可能得出没有实际意义的选址结果，其代表性的方法是重心法；离散性模型则是在有限的备选地点中选择最佳的地点，获得的选址结果较符合实际情况，其代表性的方法有整数或混合整数规划法、运输规划法、Cluster 法、

模型、Elson模型等

—

。由于离散型方法在理论和应

。而0—1规划是整

用上的显著优势，是目前物流配送中心选址问题的主要研究方向决配送中心选址问题。

随着应用问题的规模和精度要求越来越高，在单一处理器上进行大规模和超大规模的0—1规划问题求解所需计算时间越来越长，因此寻求缩短计算时间以提升计算效益成为当务之急。分布式并行计算技术的产生与发展，为进一步提高LP求解速度带来了契机

。

本文首先采用0—1规划模型对物流配送中心选址问题进行描述，并基于改进的PSRS（正则采样排序算法）性。

2配送中心选址问题的0—1规划模型 m）；

设m表示需求点的数量；（

，

）表示第i个需求点的坐标（i=1，2，…，

，

）表示第j个物

表示第j个物流中心的容量限制；

表示由产品运输了L距离时的

，

给出了一种求解物流配送中心的0—1规划模型的并行算法。仿

真结果表明，算法能有效求解中大规模物流配送中心选址问题，且具有较好的加速比和可扩展

，

数规划中的一种特殊的形式，这种规划决策变量仅取值0或者1。0—1规划非常适合描述和解

表示第i个需求点的需求量；n表示物流中心的数量；（

表示第j个物流中心的流量限制；

表示第i个物流中心到第j个需求点的距离；

流中心的坐标；

剩余量；θ表示产品在运输过程中，物流中心向需求点配送的产品单位距离内的衰减率；

表示由第j个物流中心向第i个需求点配送农产品所需的运费；ω表示单位农产品的

价值。同时定义以下符号：

龙源期刊网 http://www.qikan.com.cn

计算技术与自动化2012年9月

第31卷第3期沈萍等：物流配送中心选址问题的0—1规划并行算法

（

—

）

（

—

）

由于产品以恒定速率衰减，因此： （

（0）（1—θ））

（0）

（1—θ）

个物流

（

），

由上式显然有：

由于产品在运输过程中的衰减，若要满足第i个需求点的需求，就必须要从第中心补运

个单位产品，其中：

（1—θ）（1—θ）

（1—θ）

因而对应运费为：

当产品由第j个物流中心送至第i个需求点时，价值为：

—

则物流中心总费用为：

—

（1—θ）

（1—θ）

—

（1—θ）

从而得到物流配送中心问题的数学模型为： （

为方便讨论本文将以上模型表示为以下一般形式： k=1，2，…n

（X）

（X）=0，i=1，2，…，

（X）≥0，j=1，2，…

∈

，

，

）

，2，

（1—θ）