摘要：作为挖掘现代企业利润源泉的突破口，配送在物流活动中占有举足轻重的地位。多网点配送中心选址是后续物流活动开展的首要条件，对于该问题的研究具有现实意义。由于微粒群算法的普适性、鲁棒性、全局搜索性等特点，在求解复杂问题中能够较好地体现其优越性。结合运筹学中的运输规划的思想，对复杂的数学模型进行了简化，并针对问题的特点构造了求解编码机制。根据文献资料，将其中的仿真数据进行了整合，使得数据具有一定的现实意义，并用微粒群算法进行求解，得到了较好的效果。
关键词：配送中心；多网点选址；微粒群算法；普适性；鲁棒性
中图分类号：TP301.6 文献标识码：A
文章编号：1002-3100(2007)11-0066-05
Abstract: As the breakthrough of excavating the source of profit of modern enterprises, distribution is crucial in the logistics activities. Multiple point location is the primary condition of conducting follow-up involving logistics activities. To conduct the study is meaningful because in the real world such problem exists. Since particle swarm optimization algorithm has such characteristics as universality, robustness, global search, it signifies its advantage absolutely in solving complicate problems. Thanks to the ideology of the transportation programming in the operational research, the complicate mathematic model gets simplified, and a coding mechanism, which corresponded with the problem, is formed as a mean to the problem. According to the literature and reference, the simulated data gets integrated, which enables the data to be realistic and credible. The particle swarm optimization algorithm is adopted to searching the optimum solution, and the conclusionis proved to be effective.
Key words: distribution center; multiple point location; particle swarm optimization algorithm; universality; robustness
配送中心是在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动[1]。在整个配送活动中，运输占据很重要的地位。物流配送中心选址研究有很多方法，但仍需要得到科学的模型化、数量化方法的支持。这些方法大致可以分为定性和定量两大类。定性的方法主要是层次分析法和模糊综合评价相结合对各个方案进行指标评价，找出最优地址；定量的方法主要包括重心法、运输规划法、Cluster法、CFLP法、Baumol-Wolfe法、混合0-1整数规划法、双层规划法、遗传算法等[2]。
微粒群算法（Particle Swarm Optimization）又称为粒子群算法，是由美国心理学博士James Kennedy和电子工程学博士Russell Eberhart于1995年共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，将优化问题的解看成空间中不断飞行的，没有质量，没有体积的一个个微粒。目前已广泛应用于函数优化、神经网络训练、数据挖掘、模糊系统控制以及其他的应用领域[3]。与其他智能算法相比，微粒群算法编码受限制少，容易实现，搜索范围大，应用更灵活，受到很多研究者的青睐。
1选址问题描述及其数学模型
作为挖掘企业“第三利润源泉”——物流的突破口，配送中心正逐渐显现其重要性。市场需求的多样性，如今的产品需求向多品种中小批量的方向发展，定制已替代了大量制造，大批供应的传统模式。同样地，由于产品品种的多样性，产品结构的复杂性，传统的送货模式已无法高效，及时地满足客户的要求。此时，配送中心应运而生，它以便利，灵活，准时，低成本的优势受到企业的青睐，并以规模经济缩减成本。配送中心的出现无疑为如今的企业带来了新的希望。
配送中心的地址选择在物流活动中占举足轻重的地位，有广泛的实际应用背景。配送中心的选址决策不仅直接关系到其未来的运营费用及服务水平，还关系到整个社会物流的合理化，因而配送中心选址问题是配送中心建设项目中至关重要的问题。由于配送中心选址属于长期规划项目，一旦确定了地点，很难变更，因此在选址决策前需要考虑众多影响因素。如果将配送中心规划在同一区域的各个地点，不同布局方案可能使整个物流系统的运作成本产生很大的差异[4]，这就对选址决策提出了更高的要求。
文献[5]将选址问题分为一元网点和多元网点问题，一元网点问题通过解析方法可以近似得到合理的选址方案。而多元网点问题由于不仅要考虑选择几个地点及其组合方案，还要考虑如何协调供应商与客户之间的关系，以保证能及时得到供应，并准时送达客户，这就要求模型基于供求双方用多个约束条件来保证货物流通的合理性，最终造成问题本身的规模巨大。
配送中心的选址问题描述如下：有m个供货点和l个客户需求点，现已经根据定性方法大体确定了n个地点作为备选地点，并且知道货物运输费率，建造配送中心的费用以及配送中心以后运营费率。要求从已确定的n个备选地点中选择P个地点建造配送中心，使得费用支出最少。根据文献[6]所给出的选址模型，费用函数由运输费用，运营费用以及建造费用构成，从供应点供货能力，满足需求，容量要求，个数要求几个方面考虑，将文献给出的模型稍做变化，模型描述如（1）。
式（2）的第一部分是微粒对当前自身运动状态的信任，搜索范围的大小取决于惯性权重ω。第二部分是“认知”部分，微粒考虑了自身的经验，体现了通过自我“认知”，实现增强学习的过程。第三部分是“社会”部分，微粒通过群体之间的交互，实现信息共享，有能力达到新的搜索空间。算法流程描述如下：（1）在可行域内，随机初始化微粒和速度；（2）评价每个微粒的适应值；（3）标记本代各微粒为pbest，并从中挑出适应值最好的标记为gbest；（4）在可行域内，按式（2）和（3）更新微粒；（5）评价每个新微粒的适应值；（6）通过优胜劣汰更新pbest和gbest；（7）如满足终止要求，停止；否则，转（4）。
2.2运输规划。1947年G.B.Danzig在研究美国空军资源的优化配置时提出了线性规划及其通用解法—单纯形法[7]。从此以后，电子计算机求解线性规划获得成功，著作的出版标志着运筹学这门学科基本形成。运输规划在运筹学中属于线性规划的一个分支，主要研究在供需双方供货能力，需求及运输费率已知的条件下，如何安排货物的调运，使总运输费用最小化。其中，包含产销平衡，不平衡的情况，有广泛的应用背景。运输规划与一般线性规划不同之处在于，经转换，可以通过表上作业法这一简便而有效的方法解决，因其构造简单，求解方便，能保证在有限的迭代步骤中得到最优解，应用十分广泛。
3基于问题的预处理
3.1模型转型。根据具体问题，将数学模型转化成可以求解的计算机模型，这是求解优化问题首要考虑的问题。对于用优化算法求解来说，通过模型转换，可以使问题的描述更有针对性。原本求解规模大，数学模型复杂的问题经过转换，往往可以减小求解规模，简化模型，程序设计人员能够更好地发挥主观能动性，将算法求解实现。
3.2编码。现在由于制造业中，加工装配式生产较为普遍，而大批大量生产和供应的计划经济时代已销声匿迹了。因此，各个厂家从成本和效率方面考虑，从量上来说适可而止，仅满足需求即可，而时间上，我们在运用MRP做计划时，可以从历史数据上估出供应商的功效，以提前期作为约束供应商的发货时间。因此，从数量上来说，现实的供应量和需求量大致相当更为合理，并且供应量、需求量与库存量的相差也不会太大，这就造成了编码的困难。
编码就是将问题的解用一种码来表示，从而将问题的状态空间与算法的码空间相对应[8]。因为微粒要在一个区域内运动，其运动范围一大，就会超越区域；而运动范围一小，其变化量就小，如此一来，解的可行性得不到保证，且微粒的变化小会造成搜索能力的下降。
所用的数据中，供应点的总供货量与需求点的总需求量相等，而配送中心的库存量总和要超过供货量及需求量一点，这正是体现了供应链管理的思想。现在的加工装配式生产，一个部件对应多个其他部件或零件，要保证按时供应，按需生产，这就要求供应商能够在必要的时间，供应必要数量的货物。供应商的存货量不能过大，超过一定的阈值，供应商无法保证所有货物都能销出去。另一方面，囤积的货物过多，就会增加管理费用和货损造成的费用，很不经济。因此，这套数据具有一定的现实意义。
笔者在C-Free的开发环境下，采用C语言编写了微粒群算法的程序，在2.00GHz的CPU，256MB内存的计算机上运行。参数设置如下：
由于上述计算是纯理论计算，计算的结果可能存在理想性、非理性的问题。因此，理论的计算结果往往要结合实际情况进行进一步分析，在得到实践的检验后，理论数据才能应用到实践活动中去。问题要求建设4个配送中心，但从流通量来看第3个配送中心的流通量只有一个单位，说明4个配送中心的业务量其实只靠3个配送中心就能完成大部分工作量。由于配送中心能够盈利，靠的是规模经济，如果没有大量的货物流通，显然，这个配送中心如果建设运营，很可能会面临亏本的威胁。因此，在这个位置可以考虑建一个辅助型的配送中心，这个配送中心以维护为主，兼具辅助其他配送中心的职能。由于配送中心有许多保证其正常运营的高成本的设备和设施（包括车辆、输送机、堆垛机、拣选设备、AGV等），在其生命周期内不可避免要对其进行维护和更新。设备和设施是企业用以生产产品和提供服务的物质基础，对设备和设施的维护和管理工作的好坏将直接影响企业竞争能力和经济效益[9]。这第3个配送中心的位置可以建设用来经营其他配送中心硬件的维护和管理的工作，同时，它又拥有配送中心的部分职能可以分担一部分配送业务或者在其他配送中心发生紧急情况的时候给予支援。
基于上述参数设置，用微粒群算法，总共迭代200次，以达到最优解迭代次数和用时这两个指标进行考察，结论请参考表3。当种群n=10时，平均达到最优解迭代次数36.8，平均用时0.0825s；当种群n=30时，平均达到最优解迭代次数15.4，平均用时0.1981s。选取种群为10，模拟次数为4，定迭代次数为35次的运算结果，用Excel工具绘出趋势图，请参考图1。从表3的数据和趋势图可以看到采用微粒群算法求解上述问题具有种群少，迭代次数少，用时短等优点。但其中也不乏缺陷，如：达到最优解的迭代次数有好有坏，参差不齐等。
5结束语
物流配送中心选址问题是一混合整数规划，当备选地点增加，就会造成配送中心地点选择的范围增大，地点的选择范围又制约着呈整数变化的货物调运变量，整个问题的规模就会大幅增加，造成求解的困难。本文通过对模型进行变换，缩小了求解规模，采用了特别的编码机制，保障了解的可行性，运用微粒群算法，在有效的时间内取得了良好的结果。从建模，分析到运算整个过程来看，可以得到这样的结论：微粒群算法能在混合整数规划的求解中发挥效用；微粒群算法在求解配送中心选址问题中，可采用小规模种群，经过有限步的迭代，得到相当好的结果，具有速度上的优势。
参考文献：
[1] 孙宏岭. 高效率配送中心的设计与经营[M]. 北京：中国物资出版社，2002:1.
[2] 魏兴光. 物流配送中心选址方法综述[J]. 物流与交通，2005(9):48-49.
[3] 高尚，杨静宇. 群体智能算法及其应用[M]. 北京：中国水利水电出版社，2006:7.
[4] 王燕，蒋笑梅. 配送中心全程规划[M]. 北京：机械工业出版社，2003:83,103.
[5] 李长江. 物流中心设计与运作[M]. 北京：中国物资出版社，2002:13-22,34-35.
[6] 罗荣桂，彭伟华. 物流配送中心选址优化模型与算法实现[J]. 台声·新视角，2005(10):47-48.
[7] 胡运权. 运筹学教程[M]. 2版. 北京：清华大学出版社，2003:2.
[8] 王凌. 车间调度及其遗传算法[M]. 北京：清华大学出版社，2003:36.
[9] 陈荣秋，马士华. 生产与运作管理[M]. 北京：高等教育出版社，1999:353.
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
相关热词搜索： 微粒 选址 算法 配送中心 研究下一篇：运筹帷幄之中,,决胜千里之外