第２７卷第１２期 计算机应用研究 Ｖｏ１．２７ Ｎｏ．１２ ２０１０年１２月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｄｅｅ．２０ｌ０ 物流配送中心动态选址模型及算法研究 税文兵 ，叶怀珍 ，张诗波 （１．西南交通大学物流学院，成都６１００３１；２．西华大学交通与汽车工程学院，成都６１００３９） 摘要：针对传统物流配送中心动态选址模型没有充分考虑配送中心的可能状态和库存持有成本的问题，建立 了一种新的模型。首先，利用两步骤近似法构建了在有库存和运输双重能力约束下，每一个周期配送中心的库 存成本计算方法；然后，分别给出了配送中心在整个规划期内的打开、运营、关闭和再次打开的成本表达式；最 后，分别用遗传算法、克隆选择算法、粒子群算法求解所建立的模型，并从算法的寻优能力、稳定性、运算速度和 收敛性方面比较了三种算法的性能。算例测试结果表明，所建立的模型是有效的；从总体上看，遗传算法的适应 性要强于克隆选择算法和粒子群算法。 关键词：动态选址；库存成本；遗传算法；克隆选择算法；粒子群算法 中图分类号：Ｆ２５２；Ｏ２１ 文献标志码：Ａ 文章编号：１００１．３６９５（２ＯＬＯ）１２．４４７６—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１０．１２．０２２ Ｒｅｓｅａｒｃｈ ｏｎ ｄｙｎａｍｉｃ ｌｏｃａｔｉｏｎ ｍｏｄｅｌ ａｎｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｌｏｇｉｓｔｉｃｓ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｅｎｔｅｒｓ ＳＨＵＩ Ｗｅｎ—ｂｉｎｇ ，ＹＥ Ｈｕａｉ．ｚｈｅｎ ，ＺＨＡＮＧ Ｓｈｉ—ｂｏ （１．Ｓｃｈｏｏｌ ｏｆＬｏｇｉｓｔｉｃｓ，Ｓｏｕｔｈｗｅｓｔ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ ６１００３１，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎ＆ＡｕｔｏｍｏｔｉｅｖＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉｈｕａ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ ６１００３９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ａｌｌ ｐｏｓｓｉｂｌｅ ｓｔａｔｅｓ ａｎｄ ｔｈｅ ｉｎｖｅｎｔｏｒｙ ｈｏｌｄｉｎｇ ｃｏｓｔ ｎｏｔ ｃｏｍｐｌｅｔｅｌｙ ｃｏｎｓｉｄｅｒｅｄ ｉｎ ｇｅｎｅｒａｌ ｄｙ— ｎａｍｉｃ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｍｏｄｅｌ，ｔｈｉｓ ｐａｐｅｒ ｄｅｖｅｌｏｐｅｄ ａ ｎｅｗ ｍｏｄｅ１．Ｆｉｒｓｔｌｙ，ｏｂｔａｉｎｅｄ ｔｈｅ ｆｏｒｍｕｌａ ｏｆ ｉｎｖｅｎｔｏｒｙ ｃｏｓｔ ｉｎ ｐｅｒ ｐｅｒｉｏｄ ｗｉｔｈ ｓｔｏｒａｇｅ ａｎｄ ｔｒａｆｆｉｃ ｃａｐａｃｉｔｙ ｃｏｎｓｔｒａｉｎｔｓ ｔｈｒｏｕｇｈ ｔｗｏ ｓｔｅｐｓ ａｐｐｒｏｘｉｍａｔｅｌｙ ｍｅｔｈｏｄ．Ｔｈｅｎ，ｇａｖｅ ｔｈｅ ｆｏｒｍｕｌａｓ ｏｆ ｏｐｅｎｉｎｇ，０ｐ－ ｅｒａｔｉｏｎ，ｃｌｏｓｉｎｇ ａｎｄ ｒｅｏｐｅｎｉｎｇ ｃｏｓｔ ｉｎ ｐｌａｎｎｉｎｇ ｈｏｒｉｚｏｎ，ａｎｄ ｄｅｖｅｌｏｐｅｄ ａ ｎｅｗ ｄｙｎａｍｉｃ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｍｏｄｅ１．Ｆｉｎａｌｌｙ，ｓｏｌｖｅｄ ｔｈｅ ｍｏｄｅｌ ｂｙ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｃｌｏｎｅ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｅｓｐｅｃｔｉｖｅｌｙ，ａｎｄ ｃｏｍｐａｒｅｄ ｔｈｅ ｃａｐａｃｉ— ｔｉｅｓ ｏｆ ｆｉｎｄｉｎｇ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ，ｓｔａｂｉｌｉｔｙ，ｃｏｕｎｔｉｎｇ ｓｐｅｅｄ ａｎｄ ａｓｔｒｉｎｇｅｎｃｙ ｂｅｔｗｅｅｎ ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ．Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｏｄｅｌ ｉｓ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｔｈｅ ｍｏｓｔ ｓｕｉｔａｂｌｅ ｆｏｒ ｔｈｅ ｐｒｏｂｌｅｍ． Ｋｅｙ ｗｏｒｄｓ：ｄｙｎａｍｉｃ ｌｏｃａｔｉｏｎ；ｉｎｖｅｎｔｏｒｙ ｃｏｓｔ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｃｌｏｎｅ ｓｅｌｅｃｔｉｏｎ ｌａｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ） 设施动态选址问题的研究始于１９６８年，当时Ｂａｌｌｏｕ 以 ０引言 使规划期内利润最大为目标，采用静态优化与动态规划相结合 面对日益增加的竞争压力和快速变化的市场需求，企业的 的方法得到一个仓库最佳的打开和关闭时序。随后，Ｓｗｅｅｎｅｙ 驱动力已由生产转向通过分销和服务提供的附加值。因此，合 等人 发现Ｂａｌｌｏｕ的方法是次优的，并提出了一种改进的算 理地建立分销网络，加强对分销环节的管理，是在当前客户驱动 法。Ｓｃｏｔｔ【３ 首先研究了多个设施的动态选址问题，并假定设施 的竞争环境下，提高客户满意度，增强企业竞争力的重要途径。 一旦打开，在整个规划期内将保持不变。Ｅｒｌｅｎｋｏｔｔｅｒ＿４ 研究了 由于中间库存设施，如配送中心、仓库等的存在，不仅可使 设施有容量动态选址问题，并比较了不同的启发式算法的 企业具备快速响应市场变化的能力，而且还能通过规模化运 优劣。Ｈｉｎｏｊｏｓａ等人 研究了多商品、两梯级（工厂到仓库、仓 输、优化的库存控制给企业带来很大的成本节约。所以，中问 库到顾客）有容量的动态选址问题，采用基于拉格朗日松 库存设施的选址决策一直是分销网络设计中的一个重要战略 弛的启发式算法进行求解。Ｍｅｌａｃｈｒｉｎｏｕｄｉｓ等人 研究了多目 问题。一般来说，设施的选址决策都涉及到较大的资源投入， 标的单商品、两梯级（供应商到设施，设施到顾客）有容量 需要较长时问才能收回投资，所以不会很快地发生变化。但 的动态选址问题，用ＬＩＮＧＯ求解。Ｍｅｌｏ等人” 研究了考虑设 是，由于企业内部和外部的一些变化，如企业发展战略的改变、 施库存持有成本多产品、三梯级（供应商到工厂，工厂到配送 供应商和顾客位置的改变、相关法律的改变等，都可能使企业 中心，配送中心到仓库）有容量的动态选址问题，用 面临对已有的设施位置进行二次选址的决策。为了使现有设 ＣＰＬＥＸ求解。Ｈｉｎｏｊｏｓａ等人 采用基于拉格朗日松弛的启发 施的关闭和设施的再选址对整个分销活动的影响最小，需要对 式算法求解考虑库存成本的动态设施选址模型。 整个设施的使用状态有一个系统的考虑，即形成一个优化的动 上述文献都假定设施一旦打开后，将不允许再关闭；设施 态设施选址布局。 一旦关闭，将不允许再打开，而实际中正如前文所述，是存在设 收稿１３期：２０１０－０５－２６；修回１３期：２０１０—０６—２７ 基金项目：四川省教育厅科研基金资助项目（０９ＺＣ０１７） 作者简介：税文兵（１９８２一），男，四川ｆｔ．山人，博士研究生，主要研究方向为物流系统优化（ｓｗｂｚｚｑ＠１２６．ｃｏｍ）；叶怀珍（１９４３一），女，江苏常州人。 教授，博导，主要研究方向为物流工程、交通运输与管理；张诗波（１９８１一），男，四川乐山人，讲师，硕士，主要研究方向为交通仿真． 第１２期 税文兵，等：物流配送中心动态选址模型及算法研究 ・４４７７・ 施重复打开和关闭的需要的。Ｗｅｓｏｌｏｗｓｋｙ 首先研究了允许 设施重复打开和关闭的单个设施的动态选址问题，但没有考虑 已打开设施的运营成本和设施的关闭成本。Ｄｉａｓ和Ｋｏ等 人”叫研究了单产品、一个梯级力的这类问题。Ｃａｎｅｌ 等人 ｎ，１２］研究了多商品、两梯级有能力的这类问题，分别 如果配送中心 是打开的，取１，否则取０； 为在周期ｔ内，如 果零售商ｉ由配送中心 服务，取１，否则取０。 １．２库存和运输能力约束下的设施库存成本 配送中心采用连续检查（Ｑ，Ｒ）库存策略，即当配送中心库 存量低于再订购点 时，就向工厂订购Ｑ数量的商品；商品会 在发出订单后，Ｊ时间内到达配送中心。当配送中心向工厂发 出订单后，如果在提前期内没有需求，那么配送中心的库存将 达到最大值。考虑配送中心的库存能力约束，即有式（１） 成立： Ｑ｜‘＋Ｒ４≤ＣＩ ０１ 采用动态规划和遗传算法求解，但前者假定设施的初次打开成 本和再次打开成本是一样的（大多情况下是不相同的），后者 没有考虑设施的关闭成本。另外，这些研究都没有考虑设施库 存持有成本，因此，有可能造成分销网络总的物流成本并不是 最低的。 本文研究的二级分销网络设计中的动态设施选址问题，允 许设施在整个规划期内多次打开和关闭，并考虑了设施的库存 持有成本、运营成本、打开成本和关闭成本。与一般动态设施 选址研究对库存持有成本的考虑不同，本文将经典库存理论中 对库存成本的计算方法引入设施的动态选址模型中，从而实现 了战略层面的设施动态选址决策与战术层面的库存管理决策 的统一。由于目前还没有对这类问题求解算法的研究，本文将 分别采用标准遗传算法、克隆选择算法、离散的粒子群算法对 模型进行求解，进而比较三种算法在该问题上的适应性。 １模型的建立 １．１模型的假设及符号 模型的建立是基于如下假设：ａ）待选址的物流设施是由 工厂、配送中心、零售商组成的二级分销网络中的配送中心； ｂ）整个规划期分成若干个时间周期，在每一个时间周期零售 商的需求服从参数已知的正态分布；ｃ）在每一个周期，配送中 心存在两种能力约束，即库存能力约束和运输能力约束；ｄ）每 一个零售商在同一个周期只接受一个配送中心的服务，但在不 同的周期可以由不同的配送中心服务；ｅ）配送中心维持一定 的库存以满足零售商的需求，且采用连续检查（Ｑ， ）库存策 略，不允许缺货；ｆ）零售商只维持很少的库存量，忽略不计。 模型建立过程中所用到的符号如下： 为时间周期的集合，某一个时间周期用 表示；，为零售 商的集合，某一个零售商用ｉ表示；Ｊ为配送中心的集合，某一 个配送中心用 表示；ｄ 为在周期ｔ内，零售商ｉ的需求均值 （单位／ｄ）； 为在周期ｔ内，零售商ｉ的需求的标准差；Ｄ 为在 周期ｔ内，配送中心 相对于工厂的需求均值（单位／ｄ）； 为 在周期ｔ内，配送中心 相对于工厂的需求标准差； 为在周 期 内，产品的单位库存持有成本（ 单位）； 为在周期 内，配送中心 的一次订购成本（ 次）；Ｏ／表示配送中心商品 的可得率，反映了顾客的服务水平；Ｑ 为在周期 内，配送中心 的订购批量（单位）；Ｒ 为在周期ｔ内，配送中心 的再订购 点；ｓ 为在周期ｔ内，配送中心 的安全库存量（单位）； 为在 周期ｔ内，配送中心 订货的提前期（ｄ）；ｃ 为在周期ｔ内，配 送中心 的最大库存量（单位）；ｃ 为在周期ｔ内，从工厂到配 送中心． 的每次的最大运输量（单位／次）；。 为在周期ｔ内，从 工厂到配送中心 的单位运输成本（元／单位）；ｂ 为在周期ｔ 内，从配送中心 到零售商ｉ的单位运输成本（元／单位）； 为在周期ｆ内，配送中心 的初次打开成本（元）；船 为在周期 ｔ内，配送中心 的再次打开成本（元）；Ｆｃ 为在周期ｔ内，配送 中心． 的关闭成本（元）；肋 为在周期ｔ内，配送中心 的运营 成本（元）；Ａ为每个周期内的有效需求天数； 为在周期ｔ内， 在实际中，提前期内没有需求的情况出现的概率极低，因 此式（Ｉ）是非常保守的能力约束，在实际中一般不会由此来设 置配送中心的库存能力。为了更好地反映实际情况，引入参数 ｐ表示最大库存量超过库存能力的最大概率，则有式（２）成立： Ｐ｛Ｒ 一ＤＬ＋Ｑ ≥ｃ ｝≤Ｐ Ｐ｛ＤＬ≤Ｑｊ，＋Ｒ 一 ｝≤ｐ （２） 式中， 是提前期内配送中心的需求，服从均值为，Ｊ Ｄ 、方 差 ・ 的正态分布。因此，有 Ｐ｛ ＤＬ－ＬｊｔＤ￣≤ ｝≤ｐ √Ｌ ｖｌ￡ √Ｌｌｖ √Ｌ兰 Ｈｖ ≤ Ｑ Ｒｉｔ—Ｌ＃ｏｊ，一Ｚｐ√Ｌｉｔｖ｜ｔ≤ｃ６ｔ ｔ３ 另外，考虑从工厂到配送中心的运输能力是有限的，因此 配送中心的订购批量不能超过运输能力ｃ ，即有 ０≤ ≤ｃ （４） 式（３）和（４）构成了配送中心的双重能力约束。对于不考 虑缺货的连续检查（Ｑ，Ｒ）库存策略，一般采用Ａｘｓａｔｅｒ的两步 骤近似法来建立库存决策模型：首先是使用ＥＯＱ模型来确定 订购批量，其中的需求量用随机需求的均值来表示；其次是确 定再订购点 。 根据ＥＯＱ库存模型原理，在周期￡内，配送中心 的最佳 订购批量是通过求解下面的规划问题得到的： ＡＤ ｊ，．ｍｉｎ ＝Ｆ ．＋ ｓ．ｔ式（３）和（４） 不考虑能力约束时，得到的最佳订购批量为 Ｑ ＝２Ｆｊ＇ＡＤｊｔ 考虑能力约束时，令 Ｑｊ，ｌ＝Ｃｌ 一Ｒｉｔ＋ＬｉｔＤ Ｚｐ√Ｌ ｔｖ ，Ｑ ＝ＣｖＩｔ 最佳订购批量为 Ｑ ＝ｍｉｎ＼Ｑ ，Ｑ｜ｔＩ，ＱＩｔｖ＼ 连续检查（Ｑ， ）库存策略下，配送中心的再订购点和安全 库存分别为 Ｒ＝Ｌ｜ ＤｌＩ＋２ √ＬＪｔｖ ｔ５ ｓ ＝ｚ √Ｌ ｖ ｔ６ 由于每一个零售商在同一个周期只接受一个配送中心的 服务，有下式成立： ＝ ｄ ， ＝； 连续检查（Ｑ，Ｒ）库存策略下，在周期ｔ内，配送中 Ｌ，ｊ的最 小库存成本 为 ・４４７８・ 计算机应用研究 第２７卷 群体；ｅ）计算群体中个体位串解码后的适应值；ｆ）按照遗传策 ＝ ＋ 略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 其中： ｇ）判断迭代中止原则是否满足，不满足则返回步骤ｆ）。 ２．２克隆选择算法 克隆选择算法（ｃｌｏｎｅ ｓｅｌｅｃｔｉｏｎ Ｎｇｏｄｔｈｍ，ＣＳＡ）是基于生物 “１【 ＣＶ ｆ ］ Ｊ ｝ 免疫系统的克隆选择原理形成的一种概率性搜索算法。克隆 选择学说认为：当抗原侵入机体时，克隆选择机制能在机体内 选择出能识别和消灭相应抗原的免疫细胞，使之激活、分化和 增殖，分泌抗原匹配的抗体进行免疫应答，并最终清除抗原。 １．３考虑设施多种状态和库存成本的动态选址模型 综合上述的库存成本和配送中心在整个规划期内打开、运 借鉴克隆选择学说，将抗原与待求解问题的目标函数和各种约 营、关闭和再次打开成本¨ ］，构成考虑设施多种状态和库存 成本的动态选址模型： （ 手 ＋ 莘 （１一Ｘｔｉｔ））＋ 军Ｆ ＋ 手Ｆ （ 一 一－）＋ ａｒｉｎ 军 （１一 一 ） ＋ （Ａ军军（ａｊｒ＋６ ）ｄｉ ）＋ ＋ ㈩ ｓ．．ｔ．∑＝． １ ｉ∈，， Ｔ （８） ｙ ≤ ｉ∈，√∈，，ｔ∈Ｔ （９） ＝ｍ ｛ ， ，…， ，一｝ （１０） ＝ｍａｘ｛ ， ，…， ，一｝ （１１） Ｘ ∈ｔｏ，１＼ｊ∈ｊ，ｔ∈Ｔ （１２） ｙ ∈｛０，１｝ｉ∈Ｉ，ｊ∈，，ｔ∈Ｔ （１３） 式（７）是模型的目标函数，其中第一项是配送中心的初次 打开成本，第二项是配送中心的运营成本，第三项是配送中心 的关闭成本，第四项是配送中心的再次打开成本，第五项是从 工厂到配送中心和从配送中心到零售商的运输成本，第六项是 配送中心的库存持有成本。约束条件式（８）保证每一个零售 商只接受一个配送中心的服务。约束条件式（９）表示只有当 配送中心处于打开状态，才能为零售商提供服务。式（１０）和 （１ １）是计算初次打开成本和再打开成本的中间计算变量。约 束条件式（１２）和（１３）是标准的整数条件。 ２模型的算法 所建立的模型属于纯整数非线性规划模型，同时也是ＮＰ 困难问题。对于这类问题常用近似算法或智能优化算法求解。 目前，使用比较多的智能优化算法有遗传算法、克隆选择算法、 粒子群算法、蚁群算法、模拟退火算法等。这些算法的求解机 制各不相同，它们的性能在不同的问题上有不同的表现。而对 于本文中的这一类型的非线性规划模型，在文献中还没有相应 的算法比较研究。因此，下面将分别采用遗传算法、克隆选择 算法和粒子群算法对模型进行求解，以比较它们的适应性。 ２．１遗传算法 遗传算法（ｇｅｎｅｔｉｃ Ｎｇｏｎｔｈｍ，ＧＡ）起源于２０世纪６０年代末 ７０年代初对生物系统所进行的计算机模拟研究，是三种算法 中较为成熟和广泛使用的一种群体优化算法。标准遗传算法 的一般流程如下：ａ）选择编码策略，把参数集合转换为位串结 构空间Ｉｂ）定义适应度函数；ｃ）确定遗传策略，包括选择、交 叉、变异方法，确定交叉率、变异率等参数；ｄ）随机初始化生成 束条件相对应、抗体与待求解问题的候选解相对应、抗体和抗 原的亲和力与待求解问题的候选解满足待求解问题目标函数 的程度相对应，模仿克隆选择机理，构成克隆选择算法。 克隆选择算法流程 如下：ａ）随机生成抗体集舫，抗体 个数为Ｎ；ｂ）确定抗体集 ６的适应度向量，＿ｅ）从舢中选择ｎ 个适应度最高的个体组成一个新的集合Ａｂ ；ｄ）对肋 进行 克隆操作，生成新的抗体集ｃ；抗体的适应度值越大，克隆的个 体就越多；ｅ）对抗体集Ｃ进行亲和度成熟操作（变异操作），生 成成熟的抗体集Ｃ’，亲和度越高的个体，其变异率就越小，反 之亦然；ｆ）确定Ｃ 中每个抗体的适应度向量ｆ ；ｇ）根据，’，从 Ｃ 中选择ｎ个适应度最高的抗体，组成抗体集Ａｂ；ｈ）随机产 生ｄ个新抗体，替代 ６中ｄ个适应度最低的抗体。 ２．３粒子群算法 粒子群优化（ＰＳＯ）算法是由ＥｂｅＮａｒｔ等人 于１９９５年提 出的一种优化算法。ＰＳＯ算法将群体中的每个个体视为 搜索空间中一个没有质量和体积的粒子，这些粒子在搜索空间 中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的 飞行经验对自己的飞行速度进行动态调整，从而形成群体寻优 的正反馈机制。ＰＳＯ初始化为一群随机粒子Ｐ（随机解），然后 通过迭代找到最优解。在每一次迭代中，粒子Ｐ通过跟踪两 个极值来更新自己：第一个就是粒子本身所找到的最优解，这 个解叫做个体极值点Ｐ ；另一个是整个种群目前找到的最优 解，这个极值是全局极值点ｇ 。 。在找到这两个最优解时，粒 子根据如下的公式来更新自己的速度和新的位置： 口： ＝ｎ ：＋ｃｌ ｒＩ．（ｐｂ ｔ— ）＋ｃ２ｒ２（ｇｂｅｓｔ一 ：） ：“： ：＋ 其中：∞称做惯性权重；ｃ 、ｃ 为常数，称做学习因子（也叫加速 系数）Ｉｒ１、ｒ２是两个０—１问的随机数。上述更新公式主要用 于连续论域中搜索数值函数的最优值，对于离散问题，需要对 位置更新公式进行修正。Ｋｅｎｎｅｄｙ等人” 提出了一个离散的 ＰＳＯ算法。其中，粒子的速度更新公式不变，位置更新公式 如下： ｉｆ（ｒ＜ｓ（ ：“））ｔｈｅｎ ：”＝１；ｅｌｓｅ ：“＝Ｏ ｓ ＋１）： ３算例 某企业有一种新产品上市，预测产品的需求将经历较小、 变大、减小的变化，相关的成本也会发生变化。现在需要确定 企业最佳的配送中心动态选址布局，使总的物流成本最小。假 设有三个候选的配送中心位置，四个零售商，以及分别对应三 种需求的三个时间周期。各周期的参数参考文献［１７，１８］生 第１２期 税文兵，等：物流配送中心动态选址模型及算法研究 ・４４７９・ 成，如表１—４所示。假定配送中心在每个周期的运营成本是 初次打开成本的１／２ ”』，在每个周期末（不包括最后一个周 期）的关闭成本是运营成本的１／５，再次打开成本（从第三个周 期开始）是运营成本的１／２。每个周期的服务水平要求为 ９０％，库存能力被违背的最大概率为０．３％，每个周期的有效 为了比较三种智能算法的性能，分别对每一种算法进 行了１０次测试。设置评价的指标有：１Ｏ次测试中获得的最小 解、最大解、最小相对误差，平均解、方差，平均每次运算的时 间，以及每一种算法群体性能。最小相对误差越小，算法的精 确度越高；平均解和方差反映了算法的稳定性；平均每次运算 需求天数为３００ ｄ。 表１零售商在每个周期的需求参数 表２候选配送中心初次打开成本（元）和最大能力 注：ＦＡ为配送中心的初次打开成本（元）；ＩＣ为配送中心的存储能 力（单位）；ＶＣ为从工厂到配送中心的运输能力（单位／次）。 表３与配送中心相关的其他参数 配送中心 时间周期ＨＣ ＯＣ ＴＣ Ｌ 注：ＨＣ为库存持有成本（元／单位）；ＯＣ为订购成本（元／次）；ＴＣ 为从工厂到配送中心的运输成本（元／单位）；Ｌ为提前期（ｄ）。 表４从零售商到配送中心的运输成本（元／单位） 配送中心Ｔｌ ，．３ 配送中心 ｌ ，ｒ２ ，ｒＪｌ ４３５’ ３９２ ４１１ ，３一Ｊ１ ２４３ ２１９ ２３０ ，ｒ，２ ２３４ ２１１ ２２１ ｆ３一ｈ ２４３ ２１９ ２３０ ＩｒＪ３ ９０ ８１ ８５ ｌ３一Ｊ ２６４ ２３８ ２４９ ，２・Ｊｔ ２５０ ２２５ ２３６ ，４－Ｊｌ ３４２ ３０８ ３２３ ，２一如 １２８ １１５ １２１ ，４一Ｊ２ ３９６ ３５６ ３７４ ｌ ３ １２０ １０８ １１３ ，４－Ｊ３ ４６８ ４２１ ４４２ 算例有４５个０、１决策变量，１２个等式约束，３６个不等式 约束。三种算法均采用二进制编码。经过多次试算，确定三种 智能优化算法的参数设置如下： ａ）ＧＡ：染色体规模６０；交叉概率０．７；变异概率０．０１５；最 大迭代次数１００。 ｂ）ＣＳＡ：抗体规模６０；每次选出的抗体数３０；克隆系数 ０．９；变异系数４．０；增补系数０．２８；最大迭代次数１００。 ｃ）ＰＳＯ：粒子群规模６０；加速系数均为２；惯性权重初始为 １．３，结束为０．４；最大迭代次数１００。 时间越短，算法的速度越快；群体性能用群体平均适应度值随 代数的变化情况反映，说明了算法的收敛性。 三种算法的程序均用ＭＡＴＬＡＢ实现，运算实验在Ｃｅｌｅｒ— Ｏｉｌ＠４２０ １．６０ ＧＨｚ １ ＧＢ ＲＡＭ的ＰＣ上完成，运算结果统计数 据如表５所示。从表中可以看出，从算法的寻优能力（最小 解）、稳定性（方差）和运算速度（运算时间）来看，ＧＡ最好，其 次是ＰＳＯ，ＣＳＡ表现最差。 表５三种算法１Ｏ次运算结果对比 图１是在１０次测试中，三种算法对应的群体平均适应度 值随代数的变化情况。从图中可以看出，克隆选择算法能够经 过较少的迭代次数使群体收敛到较低的值，其收敛性要强于遗 传算法和粒子群算法。 ×１０ 翅 删 露 枯 迭代次数 图１ 三种算法群体的平均适应度值随迭代次数的变化过程 ４结束语 中间库存设施的选址决策是分销网络设计中的战略性决 策问题之一，它决定了整个分销网络的结构、成本和服务水平， 从而影响到企业的市场竞争力。本文研究了在动态变化的环 境下，二级分销网络中物流配送中心的动态选址问题，建立了 考虑配送中心库存持有成本的动态选址模型。模型考虑了设 施的运输和库存双重能力约束，允许设施打开、关闭、再打开三 种状态存在，以规划期内设施的打开成本、运营成本、关闭成本 和再打开成本、运输成本、库存持有成本之和最小为目标，对配 送中心的动态选址决策和服务范围进行决策。对所建立的 ＩＮＬＰ模型，分别采用遗传、克隆选择和粒子群算法求解，并从 算法的寻优能力、稳定性、运算速度和种群变化比较了三种算 法的适应性。算例表明，所建立的模型是有效的；遗传算法具 有最佳的寻优能力、稳定性和运算速度，只是生成种群的质量 稍差，但从总体上看，遗传算法是求解本文所建模型的三种算 法中最适合的智能优化算法。 参考文献： ［１］ＢＡＬＬＯＵ Ｒ Ｈ．Ｄｙｎａｍｉｃ ｗａｌ￣ｈｏｕｓｅ ｌｏｃａｔｉｏｎ ａｎａｌｙｓｉｓ［Ｊ］．ｄｏｕｒｅａｌ ｏｆ Ｍａｒｋｅｔｉｎｇ Ｒｅｓｅａｒｃｈ，１９６８，５（３）：２７１－２７６． （下转第４４９１页） 第１２期 向 宇，等：基于灰色关联理论ＡＧＲＥＥ方法的ＢＡ系统可靠性分配 表２各单元的重要度因子 设备名称 工作站 工作站２ ＮＴＵ１ ＴＵ２ ＤＤＣｌ ＤＤＣ２ ・４４９１・ 性分配计算的合理性，为完成系统可靠性设计提供帮助；计算 方法简单，易于实现。不足之处在于没有考虑实际工程中环境 及技术因素，可在进一步的研究中解决。 参考文献： ［１］黄大荣，黄丽芬．基于集对分析联系数故障树的ＢＡ系统可靠性 分析［Ｊ］．计算机应用研究，２０１０，２７（１）：１１１・１１３． 重要度 ０．６３４ ０．４９５ ０ ６４４ ０．６４６ ０．７３９ ０．７３０ ０．５５７ ０．５５４ ［２］李建军．发射装置可靠性指标分配方法研究及其应用［Ｊ］．舰船 科学技术，２００９，３１（５）：１０２—１０４． 传感器 执行阀 ［３］郝静如，米洁，立启光．机械可靠性工程［Ｍ］．北京：国防工业出版 社．２００８． ３）可靠度计算 ［４］邓聚龙．灰色系统理论［Ｍ］．武汉：华中科技大学出版社，１９８９： 设系统要求可靠度达到０．９５，各单元重要零件数依次为 ５０、５０、３０、３０、１８、１８、】２、７。计算系统的零件总数为２１５。由式 ５３—１３１． （３）易得到各单元复杂度因子。根据式（４）计算各部分的可靠 ［５］邓聚龙．灰色系统基本方法［Ｍ］．武汉：华中科技大学出版社， １９８７：１—５６． 度如下： ［６］姜悦岭．一种改进的ＡＧＲＥＥ可靠度分配算法［Ｊ］．锦州师范学 Ｒ１（￡）＝０．９８１３； ２（ ）：Ｏ．９７６０；Ｒ３（ ）：Ｏ．９８８９；Ｒ４（ｔ）＝０．９８９３ 院学报：自然科学版，２００１，２２（１）：１７—２１． Ｒ５（ｆ）＝０．９９４２；Ｒ６（ｔ）：０．９９４１；Ｒ７（ｔ）＝０．９９４９；Ｒ８（ｔ）＝０．９９６７ ［７］郑裕国，张康达．修正的ＡＧＲＥＥ法及其在空分设备可靠度分配 计算结果表明，该方法符合刚开始提出的设计准则，存在 中的应用［Ｊ］．机械设计，１９９６（５）：９＋１９＋４２—４３． 些微的误差也是因为所建立的ＡＧＲＥＥ方法没有考虑单元的 ［８］ＭＩＳＲＡ Ｋ Ｂ，ＷＥＢＥＲ Ｇ Ｇ．Ａ ｎｅｗ ｍｅｔｈｏｄ ｆｏｒ ｆｕｚｚｙ ｔｒｅｅ ａｎａｌｙｓｉｓ［Ｊ］． 环境因素及技术成熟程度，为了解决这个问题，可在实际操作 Ｍｉｃｒｏｅｌｅｃｔｒｏｎ ａｎｄ Ｒｅｌｉａｂｉｌｉｔｙ，１９８９，２９（２）：１９５ ２１６． 中根据现场情况对计：算结果作适当调整。 ［９］ＺＯＮＧ Ｘｉａｏ－ｙａｎｇ．Ａ ｆａｕｌｔ ｐｒｅｄｉｃｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｐｒｏｃｅｓｓ ｐｌｎａｔｓ ｕｓｉｎｇ ｆａｕｌｔ ｔｒｅｅ ａｎａｌｙｓｉｓ ｉｎ ｓｅｎｓｏｒ ｍａｌｆｕｎｃｔｉｏｎ［Ｃ］／／Ｐｒｏｅ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａ－ ４结束语 ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ．２００６：２４１５— ２４２０． 本文在深入分析可靠性ＡＧＲＥＥ分配方法的基础上，针对 ［１０］ＷＡＮＧ Ｓｈｅｎｇ—ｗｅｉ，ＸＩＥ Ｊｕｎ—ｌｏｎｇ．Ｉｔｅｇｒａｔｉｎｇ ｂｕｉｌｄｉｎｇ ｍａｎａｇｅｍｅｎｔ 现存方法的不足，引入灰色关联理论，运用灰色关联分析方法 ｓｙｓｔｅｍ ａｎｄ ｆａｃｉｌｉｔｉｅｓ ｍａｎａｇｅｍｅｎｔ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ［Ｊ］．Ａｕｔｏｍａｔｉｏｎ ｉｎ 求取各单元的重要性因子，建立ＢＡ系统可靠性框图，使用该 Ｃｏｎｓｔｒｕｃｔｉｏｎ，２００２，１ １（６）：７０７．７１５． 方法对ＢＡ系统进行可靠性分配。实例证明该方法能有效解 ［１１］赵花城，沈海尧，王玉洁．大坝安全监测自动化系统平均无故障 决工程实际中数据不足难以科学分配可靠性的问题，增加可靠 工作时间计算探讨［Ｊ］．大坝与安全，２００７（５）：３０—３４． （上接第４４７９页） ｓｅａｒｃｈ，２００７，３４（６）：１８００－１８２３． ［２］ＳＷＥＥＮＥＹ Ｄ Ｊ，ＴＡＴＨＡＭ Ｒ Ｌ．Ａｎ ｉｍｐｒｏｖｅｄ ｌｏｎｇ－ｉｕｎ ｍｏｄｅｌ ｆｏｒ ［１ １］ＣＡＮＥＬ Ｃ．Ｔｈｅ ｕｎｃａｐａｃｉｔａｔｅｄ ｍｕｌｔｉ—ｐｅｒｉｏｄ ｆａｃｉｌｉｔｉｅｓ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｍｕｌｔｉｐｌｅ ｗａｒｅｈｏｕｓｅ ｌｏｃａｔｉｏｎ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９７６，２２ ｗｉｔｈ ｐｒｏｆｉｔ ｍａｘｉｍｉｚａｔｉｏｎ［Ｊ］．ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｈｙｓｉｃａｌ （７）：７４８—７５８． Ｄｉｓｔｒｉｂｕｔｉｏｎ＆Ｌｏｇｉｓｔｉｃｓ Ｍａｎａｇｅｍｅｎｔ，１９９９，２９（６）：４０９－４３３． ［３］ＳＣＯＴＴ Ａ Ｊ．Ｄｙｎａｍｉｃ ｌｏｃａｔｉｏｎ—ｌａｌｏｃａｔｉｏｎ ｓｙｓｔｅｍｓ：ｓｏｍｅ ｂａｓｉｃ ｐｌａｎｎｉｎｇ ［１２］ＫＯ Ｈ Ｊ，ＫＯ Ｃ Ｓ，ＫＩＭ Ｔ．Ａ ｈｙｂｒｉｄ ｏｐｔｉｍｉｚａｔｉｏｎ／ｓｉｍｕｌａｔｉｏｎ ａｐｐｒｏａｃｈ ｓｔｒａｔｅｇｉｅｓ［Ｊ］．Ｅｎｖｉｒｏｎｍｅｎｔ ａｎｄ Ｐｌａｎｎｉｎｇ，１９７１，３（１）：７３－８２． ｏｆｒ ａ ｄｉｓｔｉｒｂｕｔｉｏｎ ｎｅｔｗｏｒｋ ｄｅｓｉｎｇ ｏｆ ３ＰＬＳ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｉｎｄｕｓ— ［４］ＥＲＬＥＮＫＯＴＴＥＲ Ｄ．Ａ ｃｏｍｐａｒａｔｉｖｅ ｓｔｕｄｙ ｏｆ ａｐｐｒｏａｃｈｅｓ ｔｏ ｄｙｎａｍｉｃ ｔｒｉａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，５０（４）：４４Ｏ一４４９． ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅ－ ［１３］ＡＸＳＡＴＥＲ Ｓ．Ｕｓｉｎｇ ｔｈｅ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ＥＯＱ ｆｏｒｍｕｌａ ｉｎ ｓｔｏｃｈａｓｔｉｃ ｉｎ— ｓｅａｒｃｈ，１９８１，６（２）：１３３－１４３． ｖｅｎｔｏｒｙ ｃｏｎｔｒｏｌ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９９６，４２（６）：８３０－ ［５］ＨＩＮＯＪＯＳＡ Ｙ，ＰＵＥＲＴＯ Ｊ，ＦＥＲＮＡＮＤＥＺ Ｆ Ｒ．Ａ ｍｕｌｔｉｐｅｒｉｏｄ ｔｗｏ— ８３４． ｅｃｈｅｌｏｎ ｍｕｈｉｃｏｍｍｏｄｉｔｙ ｃａｐａｅｉｔａｔｅｄ ｐｌａｎｔ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｕ— ［１４］Ｄｅ ＣＡＳＴＲＯ Ｌ Ｎ，ＺＵＢＥＮ ｖｏｎ Ｆ Ｊ．Ｔｈｅ ｃｌｏｎｅ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，２０００，１２３（２）：２７１— ｗｉｈｔ ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃ ｏｆ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ．２０００：３６—３７． ２９１． ［６］ＭＥＬＡＣＨＲＩＮＯＵＤＩＳ Ｅ，ＭＩＮ Ｈ．Ｔｈｅ ｄｙｎａｍｉｃ ｒｅｌｏｃａｔｉｏｎ ａｎｄ ｐｈａｓｅ— ［１５］ＥＢＥＲＨＡＲＴ Ｒ，ＫＥＮＮＥＤＹ Ｊ．Ａ ｎｅｗ ｏｐｔｉｍｉｚｅｒ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｕｔ ｏｆ ａ ｈｙｂｒｉｄ，ｔｗｏ－ｅｃｈｅｌｏｎ ｐｌａｎｔ／ｗａｒｅｈｏｕｓｉｎｇ ｆａｃｉｌｉｔｙ：ａ ｍｕｌｔｉｐｌｅ ｔｈｅｏｒｙ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ ＭｉｃｒｏＭａｃｈ— ｏｂｊｅｃｔｉｖｅ ａｐｐｒｏａｃｈ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅ— ｉｎｅ ａｎｄ Ｈｕｍａｎ Ｓｃｉｅｎｃｅ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ， １９９５：３９－４３． ｓｅａｒｃｈ，２０００，１２３（１）：１—１５． ［７］ＭＥＬＯ Ｍ Ｔ，ＮＩＣＫＥＬ Ｓ，Ｄａ ＧＡＭＡ Ｆ Ｓ．Ｄｙｎａｍｉｃ ｍｕｌｔｉ—ｃｏｍｍｏｄｉｔｙ ［１６］ＫＥＮＮＥＤＹ Ｊ，ＥＢＥＲＨＡＲＴ Ｒ．Ｐａｒｔｉｃｌｅ ｓｗａｒｌｎ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／ Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ（Ｐｅｒｔｈ ｃａｐａｃｉｔａｔｅｄ ｆａｃｉｌｉｔｙ ｌｃｏａｔｉｏｎ：ａ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌｉｎｇ ｆｒａｍｅｗｏｒｋ ｆｏｒ Ａｕｓｔｒａｌｉａ）．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ，１９９５：１９４２— ｓｔｒａｔｅｇｉｃ ｓｕｐｐｌｙ ｃｈａｉｎ ｐｌａｎｎｉｎｇ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅ— １９４６． ｓｅａｒｃｈ，２００５，３３（１）：１８１—２０８． ［１７］ＣＡＮＥＬ Ｃ，ＫＨＵＭＡＷＡＬＡ ＢＭ，ＬＡＷ Ｊ，ｅｔ ａ１．Ａｎａｌｇｏｉｒｔｈｍｆｏｒｔｈｅ ［８］ＨＩＮＯＪＯＳＡ Ｙ，ＫＡＬＣＳＩＣＳ Ｊ，ＮＩＣＫＥＬ Ｓ，ｅｔ ａ１．Ｄｙｎａｍｉｃ ｓｕｐｐｌｙ ｃａｐａｃｉｔａｔｅｄ，ｍｕｌｔｉ—ｃｏｍｍｏｄｉｔｙ ｍｕｌｔｉ—ｐｅｒｉｏｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｃｈａｉｎ ｄｅｓｉｇｎ ｗｉｔｈ ｉｎｖｅｎｔｏｒｙ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅ— ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，２００１，２８（５）：４１１— ｓｅａｒｃｈ，２００８，３５（２）：３７３－３９１． ４２７． ［９］ＷＥＳＯＬＯＷＳＫＹ Ｇ Ｏ．Ｄｙｎａｍｉｃ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ ［１８］ＭＩＲＡＮＤＡ Ｐ Ａ，ＧＡＲＲＩＤＯ Ｒ Ａ．Ｉｎｃｏｒｐｏｒａｔｉｎｇ ｉｎｖｅｎｔｏｒｙ ｃｏｎｔｒｏｌ ｄｅ— Ｓｃｉｅｎｃｅ，１９７３，１９（１１）：１２４１—１２４８． ｃｉｓｉｏｎｓ ｉｎｔｏ ａ ｓｔｒａｔｅｇｉｃ ｄｉｓｔｉｒｂｕｔｉｏｎ ｎｅｔｗｏｒｋ ｄｅｓｉｎｇ ｍｏｄｅｌ ｗｉｔｈ ｓｔｏｃｈａｓ— ［１０］ＤＩＡＳ Ｊ，ＣＡＰＴＩＶｅ Ｍ Ｅ，ＣＬＩＭＡＣＯ Ｊ．Ｅｆｉｆｃｉｅｎｔ ｐｒｉｍａｌ—ｄｕａｌ ｈｅｕｒｉｓｔｉｃ ｔｉｃ ｄｅｍａｎｄ［Ｊ］．Ｔｒａｍ；ｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｐａｒｔ Ｅ，２００４，４Ｏ（３）： ｏｆｒ ａ ｄｙｎａｍｉｃ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅ－ 】８３—２０７．
