本站原创
摘要：建立物流配送中心选址问题的0—1混合整数规划模型，并结合目标排序法和改进的PSRS设计求解0—1规划的并行算法。改进PSRS可将各个目标的验证任务进行均衡划分，并提交给各个处理器并行进行可行性验证，算法理论上具有接近处理器个数p的加速比。
关键词：配送中心选址；0—1整数规划；并行算法；PSRS
：A
0—1 Integer Programming Model and Parallel Algorithm for Location of Logistics Distribution Centers
SHEN Ping1，2，CHEN Yan1，LI Jie2，YANG Xuejun3
（1.School of Computer， Electronics and Information， Guangxi
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 he been partitioned and submited to p processors， which verify solutions in parallel. The proposed method he excellent speed up in p.
Key words：location of logistics distribution centers；0—1 integer programming；parallel algorithm；PSRS
1引言
在物流网络中，配送中心是供需双方的连接纽带，是整个物流系统的核心。如何有效的进行配送中心的选址是物流网络系统规划的核心问题，往往决定物流配送网络系统的结构、形状和配送模式，进而对物流系统的运作效率乃至物流行业经济效益的提高有重大影响。
针对配送中心选址的研究，国内外的学者主要围绕配送中心选址模型的建立和求解两方面展开研究，在理论和实践上都取得了较大的成果。目前物流中心选址模型大致可分为连续性模型和离散性模型两类。连续性模型对备选地点没有特别限制，但是有可能得出没有实际意义的选址结果，其代表性的方法是重心法；离散性模型则是在有限的备选地点中选择最佳的地点，获得的选址结果较符合实际情况，其代表性的方法有整数或混合整数规划法、运输规划法、Cluster 法、KuehnHamburger模型、Elson模型等[1—3]。由于离散型方法在理论和应用上的显著优势，是目前物流配送中心选址问题的主要研究方向。而0—1规划是整数规划中的一种特殊的形式，这种规划决策变量仅取值0或者1。0—1规划非常适合描述和解决配送中心选址问题。
随着应用问题的规模和精度要求越来越高，在单一处理器上进行大规模和超大规模的0—1规划问题求解所需计算时间越来越长，因此寻求缩短计算时间以提升计算效益成为当务之急。分布式并行计算技术的产生与发展，为进一步提高LP求解速度带来了契机[4，5]。
本文首先采用0—1规划模型对物流配送中心选址问题进行描述，并基于改进的PSRS（正则采样排序算法）[5，6]给出了一种求解物流配送中心的0—1规划模型的并行算法。仿真结果表明，算法能有效求解中大规模物流配送中心选址问题，且具有较好的加速比和可扩展性。
2配送中心选址问题的0—1规划模型
设m表示需求点的数量；（xi，yi）表示第i个需求点的坐标（i=1，2，…，m）；Si表示第i个需求点的需求量；n表示物流中心的数量；（xj，yj）表示第j个物流中心的坐标；uj表示第j个物流中心的流量限制；rj表示第j个物流中心的容量限制；Lij表示第i个物流中心到第j个需求点的距离；Sij表示由产品运输了L距离时的剩余量；θ表示产品在运输过程中，物流中心向需求点配送的产品单位距离内的衰减率；fij表示由第j个物流中心向第i个需求点配送农产品所需的运费；ω表示单位农产品的价值。同时定义以下符号：
计算技术与自动化2012年9月
第31卷第3期沈萍等：物流配送中心选址问题的0—1规划并行算法
xij=1 supply i from j0otherwise
Lij=（xj—xi）2+（yj—yi）2
由于产品以恒定速率衰减，因此：
Sij（0）（1—θ）Lij=Sij（Lij），Sij（Lij）=Si由上式显然有：Sij（0）=Si/（1—θ）Lij
由于产品在运输过程中的衰减，若要满足第i个需求点的需求，就必须要从第Si个物流中心补运TD个单位产品，其中：TD=Si/（1—θ）Lij
因而对应运费为：fij=LijSi/（1—θ）Lij
当产品由第j个物流中心送至第i个需求点时，价值为：ω[Si（1—θ）Lij—Si]=ωSi[1/（1—θ）Lij—1]
则物流中心总费用为：
z=∑nj=1∑mi=1[LijSi/（1—θ）Lij+ωSi[1/（1—θ）Lij—1]]xij
从而得到物流配送中心问题的数学模型为：
min z=∑nj=1∑mi=1[Si/（1—θ）Lij+（Lij+ωSi）]xij
s.t.∑mi=1Sixij≤rj∑mi=1Sixij/T≤u=1，2，…n
为方便讨论本文将以上模型表示为以下一般形式：
max z=f（X）
s.t.hi（X）=0，i=1，2，…，mgj（X）≥0，j=1，2，…lxk∈{0，1}，k=1，2，…n
30—1规划模型的并行求解
1）首先求出所有的解（包括可行解和非可行解）对应的目标函数值Z向量。
2）然后将Z向量进行按大到小排序。
3）最后按顺序对每个解的可行性进行检查。若极大化则从大到小检查，若极小化则从小到大检查。检查中发现的第一个可行解就是最优解。
该方法其本质依然是穷举法，当问题规模较大时，依然会遇到计算量极大的问题：如果变量为N个，则需求2N个目标函数值，然后还要进行排序，这是工作量很大的问题，再一个就是，如果排序结果是把最优解排在最后一个，那还得进行2N次检验。所以通过并行计算加快其求解速度十分有必要。
由于目标排序法中需要用有序的Z值序列来控制整个约束条件的检查，检测设Z的有序序列为（z1，z2，z3，…zγ）其中γ=2n且z1≥z2≥z3，…≥zγ。如果并行环境下有p个处理器，那么我们希望经过排序以后的Z''为：
c1，cp+1，c2p+1，…c（γ/p—1）p+1P1，
c2，cp+2，c2p+2，…c（γ/p—1）p+2P2，
cp，c2p，c，…，cγPP
图1排序后的新序列
上述情况中，检测设目标函数值个数r刚好可以被处理器个数p整除，若不能整除，可以按照上述序列依次分配给各个处理器，并不要求各个处理器上的个数严格相同。
第二步：采用改进的PSRS算法对各个处理器上的函数值进行"排序"，得到图1所示的序列；
第三步：各处理器按函数值Zi从大到小检查所对应的决策变量xi是否满足约束条件，若不满足，则i++，转到第四步；若满足约束条件则把Zi和Xi发给其他的处理器，并停止计算；
第四步：若处理器pj接收到其他处理器发送来的数据时，则将数据和当前的检查的数据进行对比：如果当前检查的函数值比发送来的函数值小，则停止本进程，并发消息通知p0，本进程已经结束；转到第五步；
第五步：对于处理器p0，若接收到了所有的结束的通知，则找出了最优值和最优值所对应的最优解。
4数值实验
数值实验中本文在我国的20个大中城市中，选择出10个以下的城市做为配送中心。要求如下：
1）我国的20个备选的大中城市是：北京、上海、广州、南京、武汉、成都、重庆、沈阳、深圳、杭州、长沙、南宁、福州、南昌、昆明、长春、石家庄、香港、澳门、台北。
2）在20个城市中选出10个以下（含10）城市做为配送中心。
3）市场需求指数之和超过3。
4）城市交通便利指数和超过30。
5）可开发市场潜力指数和大于
实验平台：集群环境由2台PC机搭建，2台PC机各拥有2.99GHz和3.00GHz的处理器和512MB和1GB内存。编程环境为VC++6.0下调用MPI接口。表1给出了算法串并行执行结果比较。并行环境下运行时间为
比较项目
串行
并行
运行前内存使用
293MB
293MB
593MB
454MB
300MB
161MB
120MB
执行时间
300MB
281MB
5结论
本文给出了物流配送中心选址问题的0—1整数规划模型，并结合改进PSRS以及目标排序法设计了一个物流配送中心选址问题的的并行求解算法。算法通过改进PSRS将问题求解中的主要工作进行均衡的任务划分，理论上可以得到接近p的加速比。数值实验结果有效验证了本文所提算法的有效性。
参考文献
Byrka J，Aaprdal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing，2010，39（ 6） ： 2212—2231.
Fellowsa M R，Fernau H. Facility location problems： a parameterized view[J].Discrete Applied Mathematics，2011，159（11）： 1118—1130.
[3]孙会军，高自友.供应链分销系统双层优化模型[J].管理科学学报，2003，6（ 3）： 66—70.
[4]陈国良. 并行算法的设计与分析（修订版）[M]. 高等教育出版社， 200
[6]H. Shi and J.Schaeffer. Parallel Sorting by Regular Sampling[J]. Journal of Parallel and Distributed Computing，14（4）， 1992.
关键词：配送中心选址；0—1整数规划；并行算法；PSRS
：A
0—1 Integer Programming Model and Parallel Algorithm for Location of Logistics Distribution Centers
SHEN Ping1，2，CHEN Yan1，LI Jie2，YANG Xuejun3
（1.School of Computer， Electronics and Information， Guangxi
源于：毕业设计论文www.udooo.com
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 he been partitioned and submited to p processors， which verify solutions in parallel. The proposed method he excellent speed up in p.
Key words：location of logistics distribution centers；0—1 integer programming；parallel algorithm；PSRS
1引言
在物流网络中，配送中心是供需双方的连接纽带，是整个物流系统的核心。如何有效的进行配送中心的选址是物流网络系统规划的核心问题，往往决定物流配送网络系统的结构、形状和配送模式，进而对物流系统的运作效率乃至物流行业经济效益的提高有重大影响。
针对配送中心选址的研究，国内外的学者主要围绕配送中心选址模型的建立和求解两方面展开研究，在理论和实践上都取得了较大的成果。目前物流中心选址模型大致可分为连续性模型和离散性模型两类。连续性模型对备选地点没有特别限制，但是有可能得出没有实际意义的选址结果，其代表性的方法是重心法；离散性模型则是在有限的备选地点中选择最佳的地点，获得的选址结果较符合实际情况，其代表性的方法有整数或混合整数规划法、运输规划法、Cluster 法、KuehnHamburger模型、Elson模型等[1—3]。由于离散型方法在理论和应用上的显著优势，是目前物流配送中心选址问题的主要研究方向。而0—1规划是整数规划中的一种特殊的形式，这种规划决策变量仅取值0或者1。0—1规划非常适合描述和解决配送中心选址问题。
随着应用问题的规模和精度要求越来越高，在单一处理器上进行大规模和超大规模的0—1规划问题求解所需计算时间越来越长，因此寻求缩短计算时间以提升计算效益成为当务之急。分布式并行计算技术的产生与发展，为进一步提高LP求解速度带来了契机[4，5]。
本文首先采用0—1规划模型对物流配送中心选址问题进行描述，并基于改进的PSRS（正则采样排序算法）[5，6]给出了一种求解物流配送中心的0—1规划模型的并行算法。仿真结果表明，算法能有效求解中大规模物流配送中心选址问题，且具有较好的加速比和可扩展性。
2配送中心选址问题的0—1规划模型
设m表示需求点的数量；（xi，yi）表示第i个需求点的坐标（i=1，2，…，m）；Si表示第i个需求点的需求量；n表示物流中心的数量；（xj，yj）表示第j个物流中心的坐标；uj表示第j个物流中心的流量限制；rj表示第j个物流中心的容量限制；Lij表示第i个物流中心到第j个需求点的距离；Sij表示由产品运输了L距离时的剩余量；θ表示产品在运输过程中，物流中心向需求点配送的产品单位距离内的衰减率；fij表示由第j个物流中心向第i个需求点配送农产品所需的运费；ω表示单位农产品的价值。同时定义以下符号：
计算技术与自动化2012年9月
第31卷第3期沈萍等：物流配送中心选址问题的0—1规划并行算法
xij=1 supply i from j0otherwise
Lij=（xj—xi）2+（yj—yi）2
由于产品以恒定速率衰减，因此：
Sij（0）（1—θ）Lij=Sij（Lij），Sij（Lij）=Si由上式显然有：Sij（0）=Si/（1—θ）Lij
由于产品在运输过程中的衰减，若要满足第i个需求点的需求，就必须要从第Si个物流中心补运TD个单位产品，其中：TD=Si/（1—θ）Lij
因而对应运费为：fij=LijSi/（1—θ）Lij
当产品由第j个物流中心送至第i个需求点时，价值为：ω[Si（1—θ）Lij—Si]=ωSi[1/（1—θ）Lij—1]
则物流中心总费用为：
z=∑nj=1∑mi=1[LijSi/（1—θ）Lij+ωSi[1/（1—θ）Lij—1]]xij
从而得到物流配送中心问题的数学模型为：
min z=∑nj=1∑mi=1[Si/（1—θ）Lij+（Lij+ωSi）]xij
s.t.∑mi=1Sixij≤rj∑mi=1Sixij/T≤u=1，2，…n
为方便讨论本文将以上模型表示为以下一般形式：
max z=f（X）
s.t.hi（X）=0，i=1，2，…，mgj（X）≥0，j=1，2，…lxk∈{0，1}，k=1，2，…n
30—1规划模型的并行求解
3.1
摘自：毕业论文范文www.udooo.com
目标排序法 目标排序法是求解0—1整数规划问题的有效方法。大致的思路为：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，反之则升序。然后按这个顺序逐个检验对应的解的可行性，当碰到第一个可行解时即得到最优解。该方法通过快速提高约束门槛可以大规模的减少检查的数量。具体步骤如下：1）首先求出所有的解（包括可行解和非可行解）对应的目标函数值Z向量。
2）然后将Z向量进行按大到小排序。
3）最后按顺序对每个解的可行性进行检查。若极大化则从大到小检查，若极小化则从小到大检查。检查中发现的第一个可行解就是最优解。
该方法其本质依然是穷举法，当问题规模较大时，依然会遇到计算量极大的问题：如果变量为N个，则需求2N个目标函数值，然后还要进行排序，这是工作量很大的问题，再一个就是，如果排序结果是把最优解排在最后一个，那还得进行2N次检验。所以通过并行计算加快其求解速度十分有必要。
3.2改进的PSRS算法
PSRS是一种基于均匀划分原理的负载均衡的并行排序算法[5，6]。待排序元素为n个，系统有处理器p个，系统先将n个元素均匀地分割成p段，每段指派一个处理器，然后各个处理器并行进行局部排序。然后从各个处理器中抽取p—1个样本，再对样本元素排序，然后从有序的样本元素中抽取划分元素共p—1个将样本均分为p段，有理由相信这些样本元素的划分元素也近似的将原来的序列均分为p段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集合在一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序序列了。由于目标排序法中需要用有序的Z值序列来控制整个约束条件的检查，检测设Z的有序序列为（z1，z2，z3，…zγ）其中γ=2n且z1≥z2≥z3，…≥zγ。如果并行环境下有p个处理器，那么我们希望经过排序以后的Z''为：
c1，cp+1，c2p+1，…c（γ/p—1）p+1P1，
c2，cp+2，c2p+2，…c（γ/p—1）p+2P2，
cp，c2p，c，…，cγPP
图1排序后的新序列
上述情况中，检测设目标函数值个数r刚好可以被处理器个数p整除，若不能整除，可以按照上述序列依次分配给各个处理器，并不要求各个处理器上的个数严格相同。
3.3求解0—1规划的并行算法
第一步：计算函数值任务分发。把求解函数值的任务分给各个处理器来做。各个处理器平均要计算r/p个函数值（γ=2n）；第二步：采用改进的PSRS算法对各个处理器上的函数值进行"排序"，得到图1所示的序列；
第三步：各处理器按函数值Zi从大到小检查所对应的决策变量xi是否满足约束条件，若不满足，则i++，转到第四步；若满足约束条件则把Zi和Xi发给其他的处理器，并停止计算；
第四步：若处理器pj接收到其他处理器发送来的数据时，则将数据和当前的检查的数据进行对比：如果当前检查的函数值比发送来的函数值小，则停止本进程，并发消息通知p0，本进程已经结束；转到第五步；
第五步：对于处理器p0，若接收到了所有的结束的通知，则找出了最优值和最优值所对应的最优解。
4数值实验
数值实验中本文在我国的20个大中城市中，选择出10个以下的城市做为配送中心。要求如下：
1）我国的20个备选的大中城市是：北京、上海、广州、南京、武汉、成都、重庆、沈阳、深圳、杭州、长沙、南宁、福州、南昌、昆明、长春、石家庄、香港、澳门、台北。
2）在20个城市中选出10个以下（含10）城市做为配送中心。
3）市场需求指数之和超过3。
4）城市交通便利指数和超过30。
5）可开发市场潜力指数和大于
3.5。
6）总的建设利益Z=∑2011000q—c+10*t+100f最大。实验平台：集群环境由2台PC机搭建，2台PC机各拥有2.99GHz和3.00GHz的处理器和512MB和1GB内存。编程环境为VC++6.0下调用MPI接口。表1给出了算法串并行执行结果比较。并行环境下运行时间为
1.284秒，比串行程序的2.203秒快0.919秒。加速比为716。
表1执行结果比较比较项目
串行
并行
运行前内存使用
293MB
293MB
1.02GB
运行时内存使用593MB
454MB
1.14GB
程序净使用内存300MB
161MB
120MB
执行时间
源于：论文格式www.udooo.com
2.203秒
1.284秒
总内存300MB
281MB
5结论
本文给出了物流配送中心选址问题的0—1整数规划模型，并结合改进PSRS以及目标排序法设计了一个物流配送中心选址问题的的并行求解算法。算法通过改进PSRS将问题求解中的主要工作进行均衡的任务划分，理论上可以得到接近p的加速比。数值实验结果有效验证了本文所提算法的有效性。
参考文献
Byrka J，Aaprdal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing，2010，39（ 6） ： 2212—2231.
Fellowsa M R，Fernau H. Facility location problems： a parameterized view[J].Discrete Applied Mathematics，2011，159（11）： 1118—1130.
[3]孙会军，高自友.供应链分销系统双层优化模型[J].管理科学学报，2003，6（ 3）： 66—70.
[4]陈国良. 并行算法的设计与分析（修订版）[M]. 高等教育出版社， 200
2.11
[5]杨林峰，李捷，陈燕. 基于改进PSRS的并行0—1规划算法. 计算机工程与设计. 2008.9， 29（17）： 4491—4493.[6]H. Shi and J.Schaeffer. Parallel Sorting by Regular Sampling[J]. Journal of Parallel and Distributed Computing，14（4）， 1992.