多配送中心选址问题的数学模型及算法.doc

李婷婷，等:多配送中心选址问题的数学模型及算法doi:10.3969/j.issn.1005-152X.2011.08.028技术与方法多配送中心选址问题的数学模型及算法李婷婷1,黄晓东1,李珍萍2(1.北京物资学院研究生部，北京101149；2.北京物资学院信息学院,北京101149)摘要在综合考虑存储费用、运输费用、固定建设成本的前提下，建立了使总费用最低的配送中心选址问题的数学模型，分别给出了精确算法和近似算法，并通过具体的案例进行了求解及分析。关键词多配送中心；选址；存储费用；固定建设成本中图分类号F224;F252.14文献标识码A文章编号1005-152X（2011）08-0085-04MathematicalModelandAlgorithmforMultipleDistributionCenterLocationProblemLITing-ting1,HUANGXiao-dong1,LIZhen-ping2(1.Post-graduateDepartment,BeijingWuziUniversity,Beijing101149;2.SchoolofInformaiton,BeijingWuziUniversity,Beijing101149,China)Abstract:Incomprehensiveconsiderationofthecostsofstorage,transportationandconstruction,thepaperestablishesamathematicalmodelaimedattheminimumtotalcostforamultipledistributioncenterlocationproblem,presentstheexactalgorithmandapproximationalgorithmrespectivelyandobtainssolutiontothemodelusingspecificcaseanalysis.Keywords:mutipledistributioncenter;location;storagecost;fixedconstructioncos基本上都只考虑固定建设费用和运输费用，不考虑存储费用。1引言从物流发展的趋势来看，配送中心不仅执行一般的物流在实际的选址过程中，存储费用是影响配送中心运行效益的一一个重要因素。存储费用是物资在库存过程中发生的费用，般与存储数量和存储时间成正比关系，存储费用包括仓库保管费用、存货损坏费用等。仓库保管费用是指仓库的保险费、税金等，存货损坏费用是指存货的陈旧贬值及过时削价损失等。由于不同仓库存储条件不同，因而存储费率会有所不同。本文将在综合考虑固定费用、运输费用、存储费用等的基础上，建立多配送中心选址问题的数学模型，并给出相应的求解方法，最后通过一个具体案例进行求解分析。职能，而且越来越多地要执行指挥调度、处理信息等职能，是整个物流网络的关键所在，受到各方面的广泛重视，因此物流配送中心的合理选择是企业发展的战略决策问题。一个成功的配送中心选址方案，可以缩短配送距离，加快配送速度，降低配送成本，提高服务质量，还可以促进生产和消费的有机协调与配送，使整个物流系统处于平衡发展的状态。配送中心选址决策就是要确定配送中心的数量、位置及每个配送中心服务的客户群体。配送中心的选择要遵循经济性原则，即要找到成本最低的地方，所以通常我们建立的配送中心选址模型的目标函数文献中基本上都是总费用最低。为了建模方便以及简化计算，通常会做出若干假设，从而简化总费用的计算，如现有文献中2多配送中心选址问题的数学模型多配送中心选址问题可以描述为：某个地区内有若干个需求点，已知各个需求点的需求量，现欲在若干个备选地址中选择一部分，建立配送中心，以满足这些需求点的需求，并使收稿日期2011-06-28基金项目北京市自然科学基金项目（1092011）；北京市属市管高等学校人才强教计划项目(PHR201006217)；北京市教育委员会科研基地建设项目（WYJD200902）作者简介李婷婷（1988-），河南人，硕士研究生，研究方向：物流工程；黄晓东（1986-），河南人，硕士研究生，研究方向：物流工程；李珍萍，山东人，博士，教授，硕士生导师，主要研究方向：组合优化、物流工程。（1966-）-85-技术与方法物流技术2011年第30卷第8期（总第239期）-86-李婷婷，等:多配送中心选址问题的数学模型及算法技术与方法的结果。3.2近似解法虽然多配送中心选址问题可以表示成线性规划模型，但由于模型中含有0、1变量，因此，属于整数线性规划模型。对于规模较大的问题，直接求解整数线性规划模型需要的时间太长，甚至无法求解。为了求解大规模问题，我们给出一种近似算法，该算法的基本思想是：首先将需求点按照地理位置划分成多个区域，再在每个区域中选择一个总费用最小的备选地建立配送中心。下面我们将结合本节案例说明近似算法的步骤：第一步：将需求点划分成3个区域。配送中心的选址决策型，因此可以利用Lingo软件编程直接求解线性规划模型，得到精确最优解。本例中通过求解，得到3个配送中心分别应该建在淮安市、宝应县和高淳县，最小的总费用为1680882元。图1中一个配送中心及其所服务的需求点用相同的形状表示。从地理位置来看高邮市处于中心的位置，理应是配送中心，但是其固定建设费用过高，是宝应县的2倍多，所以不在高邮市建立配送中心。镇江市和泰州市被分配到较远的怀安县的配送区域内，一方面是因为宝应县的单位存储费用比怀安市要高，另一方面本文的例子中给定的都是公路距离，并不是直线距离，因为江苏省处于长江下游，多水域，所以公路运输路线可能不是直线的。同时分配给怀安市的配送任务较少，是因为怀安市的固定建设费用较宝应县和高淳县高。总之这个分配结果是综合考虑固定建设费用、运输费用和存储费用受到很多因素影响，如供应商和需求点的分布、交通设施、政府政策、地域发展情况（劳动力成本、土地价格等）。首先根据影响选址的一些宏观因素进行配送区域的划分，使具有相似性的需求点聚在同一区域，这样有利于配送的管理和运营。采用文献1中的方法，即用SPSS软件将20个城市分为3个区域，从划分的结果可以看出，区域1中包含的配送中心备选地有灌云县和宿迁县，区域2中包含的配送中心备选地有淮安市、宝应县和高邮市，区域3中包含的配送中心备选地有南通县、高淳县和溧水县。表5、6和7分别显示了各个区域内节点之间的单位运输费用。第二步：计算各区域内的最佳配送中心。根据表2、表3、表5、表6和表7的数据，利用EXCEL分别求出8个备选点作为配送中心时对应的总费用，结果如表8所示。从表8的计算-87-技术与方法物流技术2011年第30卷第8期（总第239期）因此有可能把配送中心选在固定建设成本较高的备选地，如本例中区域3的配送中心建在南通市，其固定建设成本是该区域最高的，从而导致总成本较高。4总结本文在综合考虑存储费用、运输费用、固定建设成本的前提下，建立了使总费用最低的配送中心选址问题的数学模型，分别用精确算法和近似算法进行了求解，通过具体的案例进行了分析。由于研究配送中心选址时考虑存储费用的文献不是很多，所以本文的研究结果具有一定的理论意义。由于本文对研究的问题做了一定的假设，比如配送中心不限制容量，从配送中心到需求点是一次运输完成等，而这些假设与实际情况可能有一定的偏离，因此下一步我们将进一步修改这些假设，以便得到更加符合实际的结论。参考文献结果可以看出，三个区域的配送中心分别应该建在宿迁市、高邮市和南通市，总费用为2517092.2元。根据表5-表8，画出近似算法求得的配送中心分布图，如图2所示。和图1一样，一个配送中心所服务的需求点用相同的形状表示。从两种方法得到的结果可以看出，精确算法得到的方案的总费用1680882元比近似算法得到的方案的最小总费用2517092.2元少很多，这是由于近似算法在进行区域划分的时候，并没有考虑配送中心备选地的建设成本及单位存储费，-88-1胡贤满,张燕,李珍萍.带车辆路线安排的多配送中心选址问题的求解J.