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

《物流配送中心选址问题的0—1规划并行算法　》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、ers　　　　SHENPing1，2，CHENYan1，LIJie2，YANGXuejun3　　（1.Schoolofputer，ElectronicsandInformation，GuangxiUniversity，Nanning530004，Guangxi，China；　　2.Departmentofputer，ElectronicsandInformationEngineering，GuangxiPolytechnic，Nanning530226，Guangxi，China；　　3.GuangxiElectronicPr

3、oductsSupervisingAndTestingInstitude，Nanning530031，China）　　Abstract：Accordingtothetheoryof0—1programming，thispaperpresentsthemodelfortheproblemoflogisticsdistributioncenterslocation.AndanefortheproposedmodelisgivenbasedonobjectivevaluessortingandimprovedPSRS.Thetasksofverifysol

4、utionshavebeenpartitionedandsubmitedtopprocessors，ethodhaveexcellentspeedupinp.　　　　Keyming；parallelalgorithm；PSRS　　　　1引言　　在物流X络中，配送中心是供需双方的连接纽带，是整个物流系统的核心。如何有效的进行配送中心的选址是物流X络系统规划的核心问题，往往决定物流配送X络系统的结构、形状和配送模式，进而对物流系统的运作效率乃至物流行业经济效益的提高有重大影响。　　针对配送中心选址的研究，国内外的学者主要围绕配送中心选址模型的建立

5、和求解两方面展开研究，在理论和实践上都取得了较大的成果。目前物流中心选址模型大致可分为连续性模型和离散性模型两类。连续性模型对备选地点没有特别限制，但是有可能得出没有实际意义的选址结果，其代表性的方法是重心法；离散性模型则是在有限的备选地点中选择最佳的地点，获得的选址结果较符合实际情况，其代表性的方法有整数或混合整数规划法、运输规划法、Cluster法、KuehnHamburger模型、Elson模型等[1—3]。由于离散型方法在理论和应用上的显著优势，是目前物流配送中心选址问题的主要研究方向[1]。而0—1规划是整数规划中的一种特殊的

6、形式，这种规划决策变量仅取值0或者1。0—1规划非常适合描述和解决配送中心选址问题。　　随着应用问题的规模和精度要求越来越高，在单一处理器上进行大规模和超大规模的0—1规划问题求解所需计算时间越来越长，因此寻求缩短计算时间以提升计算效益成为当务之急。分布式并行计算技术的产生与发展，为进一步提高LP求解速度带来了契机[4，5]。　　本文首先采用0—1规划模型对物流配送中心选址问题进行描述，并基于改进的PSRS（正则采样排序算法）[5，6]给出了一种求解物流配送中心的0—1规划模型的并行算法。仿真结果表明，算法能有效求解中大规模物流配送中

7、心选址问题，且具有较好的加速比和可扩展性。　　2配送中心选址问题的0—1规划模型　　设m表示需求点的数量；（xi，yi）表示第i个需求点的坐标（i=1，2，…，m）；Si表示第i个需求点的需求量；n表示物流中心的数量；（xj，yj）表示第j个物流中心的坐标；uj表示第j个物流中心的流量限制；rj表示第j个物流中心的容量限制；Lij表示第i个物流中心到第j个需求点的距离；Sij表示由产品运输了L距离时的剩余量；θ表示产品在运输过程中，物流中心向需求点配送的产品单位距离内的衰减率；fij表示由第j个物流中心向第i个需

8、求点配送农产品所需的运费；ω表示单位农产品的价值。同时定义以下符号：　　计算技术与自动化2012年9月