技术与方法 物流技术２００９年第２８卷第ｌ期（总第１９６期） 基于双层规划的供应链分销中心选址模型与算法研究 吴国强’，陈义华’，王旭 ，朱玉琴’ （１．重庆大学数理学院，重庆４０００４４；２．重庆大学机械学院，重庆４０００４４） 【摘要】在以往的选址模型的基础上，建立了反应客户需求的分销中心选址双层规划模型，该模型在引入产品厂家到分销中 心的运输成本费用以及客户对产品的时间限制的基础一ｋ，考虑具有非满载车辆路线选择问题，来确定使总费用最小化的分销中 心的数量，以及分销中心与用户的供需关系。 【关键词】供应链；选址模型；分销中心；用户需求；双层规划 【中图分类号】Ｆ２２４．０；Ｆ２９９．２４ 【文献标识码】Ａ ［３Ｅ￣］１００５—１５２Ｘ（２００９）０１—００６０—０３ Ｒｅｓｅａｒｃｈ ｏｎ ＳＣ Ｄｉｓｔｒｉｂｕｔｉｏｎ Ｃｅｎｔｅｒ Ｌｏｃａｔｉｏｎ Ｍｏｄｅｌ＆Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｂｉ－ｌｅｖｅｌ Ｐｒｏｇｒａｍｍｉｎｇ ｗｕ Ｇｕｏ－ｑｉａｎｇ ＣＨＥＮ Ｙｉ—ｈｕａ ．ＷＡＮＧ Ｘｕ ，ＺＨＵ Ｙｕ—ｑｉｎｇ （１．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ＆Ｓｃｉｅｎｃｅ；２．Ｓｃｈｏｏｌ ｏｆ Ｍａｃｈｉｎｅｒｙ．Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ ４０００４４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｐａｓｔ ｌｃｏａｔｉｏｎ ｍｏｄｅｌ，ｔｈｅ ｐａｐｅｒ ｅｓｔａｂｌｉｓｈｅｓ ａ ｈｉ－ｌｅｖｅｌ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ ｏｆ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｅｎｔｅｒ ｌｏｃａｔｉｏｎ，ｗｈｉｃｈ ｒｅｆｌｅｃｔｓ ｃｕｓｔｏｍｅｒ ｄｅｍａｎｄｓ．Ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｔｈｅ ｔｒａｆｉｆｃ ｃｏｓｔｓ ｏｆ ｍａｎｕｆａｃｔｕｒｅｒｓ ａｎｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｅｎｔｅｒ ａｓ ｗｅｌｌ ａｓ ｔｈｅ ｔｉｍｅ ｃｏｎｓｔｒａｉｎｔｓ ｏｆ ｃｕｓｔｏｍｅｒｓ，ｔｈｅ ｍｏｄｅｌ ｉｓ ｕｓｅｄ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｑｕａｎｔｉｔｙ ｏｆ ｄｉｓｔｉｒｂｕｔｉｏｎ ｃｅｎｔｅｒ ｉｎ ｔｈｅ ｃｏｎｄｉｔｉｏｎ ｏｆ ｍｉｌｉｍｉｚｅｄ ｔｏｔａｌ ｃｏｓｔｓ ａｎｄ ｔｈｅ ｓｕｐｐｌｙ／ｄｅｍａｎｄ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｅｎｔｅｒ ａｎｄ ｃｕｓｔｏｍｅｒ． Ｋｅｙｗｏｒｄｓ：ｓｕｐｐｌｙ ｃｈａｉｎ；ｌｃｏａｔｉｏｎ ｍｏｄｅｌ；ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｅｎｔｅｒ；，ｃｕｓｔｏｍｅｒ ｄｅｍａｎｄ；ｂｉ—ｌｅｖｅｌ ｐｒｏｇｒａｍｍｉｎｇ １ 引言 轿车，满足各个分销商的需求量有限，非满载的配送任务如果 是单点配送，将会浪费很大的一部分成本，因此本文采用巡回 分销中心的选址研究开展了相当长的时间，已形成一些 线路配送，即若干个需求量较小的分销商在一条配送线路。文 常规的选址模型，特别近几年电子商务的发展，为物流中的信 献【６—８腱立了在充分考虑物流规划部门与客户双方利益的基 息流、商流和资金流的电子化打下了强有力的基础，然而作为 础上，将设施选址和运输路线安排结合起来同时考虑，找出最 电子商务中最特殊的一个环节——物流配送，以及笔者研究 佳的供应点位置，同时还要求供应点到各个分销商的运输成 的分销中心配送问题是电子商务有待更进一步研究的重点， 本最小，这些模型在得出最优路线的同时，也合理计算了每个 因而如何正确确定选择分销中心的地理位置以及如何考虑配 客户的运输费用。但他们没有考虑在客户选择的条件下由多 送路线，以期来优化和完善物流配送系统，已成为电子商务企 个分销中心共同配货，同时每个分销中心的配货量取决于客 业成功的关键。 户的选择行为，体现了客户的利益。本文是在此研究基础上， 在以往的文献中，分销中心的选址模型成为当前研究的 考虑了分销中心从厂家进货的运输成本费用，在路线选择最 热点。文献【１］给出了九个基本的选址模型，其建立的目的就是 优的同时，又兼顾客户的时间要求，最大限度地兼顾到分销中 运输费用和固定选址投资费用最小。文献【２】考虑了产品运输 心和客户双方利益。 成本和分销中心运营可变成本的基础上，建立了一个有关多 个分销中心的选址模型，文献【３】考虑了非线性运输费用的选 ２物流分销中心的选址模型的建立 址问题，并用分枝定界法进行求解，但常见的选址模型都假定 从分销中心出发的车辆每次到分销商的配送是放射线状的 ， 对于上层规划可以描述为决策部门在允许的条件下，考 即从设施点出发的运输车辆每次访问一个客户需求点后就返 虑最佳配送路线配送和尽量满足客户时间需求的条件下，确 回到设施点，但实际的配送过程中，特别是大宗货物，比如小 定最佳的分销中心的地点，使得总成本最小，而下层规划引进 【收稿日￣］２００８—０９—２３ 【基金项目】国家科技支撑计划课题（２００６ＢＡＨ０２Ａ０９—３）；重庆市科技项目计划课题（ＣＳＴＣ，２００６ＡＢ２０２５） ［作者简介】吴国强，男．重庆大学数理学院研究生，研究方向：物流工程与供应链管理；陈义华，男，重庆大学数理学院教授，研究方向：物流工 程与供应链管理、城市交通规划、智能决策理论。 一６０— 吴国强，等：基于双层规划的供应链分销中心选址模型与算法研究 技术与方法 了份额模型｛９１，刻画了客户需求量在不同的分销中心之间的分 到达时间；ｃ．，ｃ：分别表示提前到达时间和推迟到达时间单位时 配模式，它的目标是满足客户的费用最少。以此达到分销中心 间给以的惩罚值，是两个常数，它们由客户对货物保管费用和 和客户的共同得益。 需求程度来确定；Ｒ是分销中心的最多建设数；Ｎ是一个大于零 上层规划模型的建立： 的常数；Ｇ是分销商的集合。 定义变量如下： 上层目标函数是从分销中心的进货以及在考虑最佳路线 碡 如果第ｋ个运输工具从分销中心ｉ出发由ｊ点经过１点 配送和尽量满足客户时间需求的前提下，寻找最优的分销中 否则 心的选建方案，以及分销中心的最少数量来满足客户的需求， 如果第ｋ个运输工具从分销中心ｉ到客户Ｊ点配货 否则 以达到花费的总费用最小。对于这个选址模型本文在利用 ｆ１分销中心ｉ对分销商ｊ服务 Ｃｌａｒｋｅ—Ｗｒｉｇｈｔ的节约启发式算法的基础上构造了连接点对时 ０否则 对线路上的点的最大允许提前时间或最大允许延迟时间的检 ｆ１在ｉ地建立分销中心 查约束，以及等待惩罚和延迟惩罚的处理方法… 。 ｌ０否则 对于下层目标函数描述了多个分销中心存在的条件下， 由此本文建立如下模型： 客户需求量在不同的分销中心的分配模式，使客户的利益达 ｍｉｎｆ＝∑ Ｚｉ＋∑∑∑∑ｃ 到最大。本文引进了在交通上常用的份额模型，来解决各个分 销商如何选择分销中心的配送量，以满足分销商自身的利益。 ＋∑∑ ＋∑％ 本文首先引进一个吸引测度指标Ｍ ，它表示Ｍ。越大，分 ￣ｃ，ＺＺ ＺＹ￣ｍａｘ［ＥＴｊ一 ，０］ 销中心ｉ对分销商的吸引力强度越大；反之，则越小。这个指标 与分销中心所在地的经济发展水平、交通状况、文化水平以及 －＋＇Ｃ２∑∑∑．）， ｍａｘ［ 一￡ ，０］ 服务水平密切相关。除此之外还有一个因素也是分销商必然 要考虑的问题，就是从各个分销中心进货的费用问题。综上所 ．ｔＺ∑ ＜－ｑｋ ∈ 述，客户在做出决策之前，要同时考虑两方面的因素，即试图 达到吸引力最大和试图花最小的费用的结合，在这两种因素 ∑ ＝ ＶｉｅＧ，ｌｅＨ，七∈Ｖ 交叉的作用下，会达到一个吸引力和费用之间的平衡，来确定 客户在各个分销中心的需求量的分配情况．以此为基础本文 ∑ ＝ ＶｉｅＧ，ｊｅｌｌ，ｋｅＶ 建立了以下模型，来刻画分销商需求量的分配情况。 ∑ ＝ ＶｉｅＧ，ｊｅｌｌ 下层规划模型： ｍｉｎ ｆ＝∑∑． （ ） ＝ｌ￣／ｋｅＶ，ｊｅ Ｈ，ｌｅＳ ＋ １∑∑（ Ｉｎ 一 ）一∑∑Ｍ， ≤ Ｖｉ∈Ｇ，Ｊ、ｌｅＨ，ｋ∈Ｖ ｉｅＧ｝∈Ｈ ｔＥＧ Ｈ ｌ ＞’ ≤Ｎ Ｖｉ∈Ｇ ∑ ＝Ｗ，Ｖｉｅ Ｇ （１一Ｐ ） ＝０ Ｖｉ∈Ｇ，．『∈日 Ｘ Ｍｚｉ Ｖｉ∈Ｇ，Ｊ∈Ｈ ∑ ≤Ｘｉ－＜ｚ Ｙ，Ｖｉｅ Ｇ， ∈Ⅳ ．． ０ ｆ∈Ｇ，ｆ∈Ｈ ｛ＥＨ ， ，Ｚ ∈｛ｏ’１） 其中 （・）为需求函数的反函数， “ ；其中ｕ。 是分销商ｊ从分销中心ｉ进货的最小费用；Ｍ＞０，是一个常数； Ｇ｛ｉｌｉ＝ｌ，……，Ｒｌ指～系列可行性分销中心的潜在设施；Ｈ｛ｊｌ ｗ 是分销商的总需求量；ｒ是函数的校正参数，ｒ＞０；对于下层规 ｊ＝Ｒ＋ｌ，……，Ｒ＋Ｎ｝指一系列需要服务的客户；ＳｌｌＧ｝Ｕｌｒｔ｝｝指所有 划，由于ｘｌｎｘ函数是严格的下凸函数，所以整个表达式是一个 的分销中心和客户总和；Ｖ｛ｖ ｌｋ＝ｌ，…，Ｋ｝指Ｋ个运输工具可以到 严格的凸规划问题，且约束条件是线性的，故有唯一的极小值 达设施的路线；ｃ。是产品厂家到分销中心ｉ单位产品的运输费 点。对于该模型的求解，本文利用改进的Ｆｒａｎｋ—Ｗｏｌｆｅ算法进行 用 是分销中心一次从厂家的进货量；ｃⅡ表示为从点ｊ运送到 求解，本文也可以利用交通上常用的两阶算法ｆｌｏｌ，这要看模型 点ｉ的运输成本费用；它的含义可以是距离、费用、时间等；Ｄ ．是 的复杂程度而进行具体选择。 表示分销中心ｉ对分销商 提供单位产品的费用成本函数；Ｆ． 是第ｉ个分销中心选中后的基建投资费用和日常管理费用，它 ３模型的求解 与当地的经济发展程度、消费水平、土地价格有关；ｓ 是由分销 中心ｉ给分销商ｊ送货到达的时间； 是分销中心ｉ的最大集货 一般来说双层规划问题的求解都是非常复杂的，原因之一 量；ＥＴｊ，ＬＴｉ分别是分销商ｊ要求货物最早到达时间和货物最迟 就是它是一个ＮＰ—ｈａｒｄ问题，不存在多项式的求解算法。文献 一６１— 技术与方法 【７】中运用基于灵敏度分析方法的启发式算法ＳＡＢ（ｓｅｎｓｉｔｉｖｉｔｙ ａｎａｌｙｓｉｓ ｂａｓｅｄ ａｌｏｇｏｒｉｔｈｍ）解决了双层规划的选址模型，考虑了 物流技术２００９年第２８卷第１期（总第１９６期） 表２各分销商与分销中心的距离及它们之间的距离 ０ ｏ ｌ ２ ３ ｏ ４０ ６０ ７５ ｌ ４０ ０ ６５ ４０ ２ ６０ ６５ ０ ７５ ３ ７５ ４０ ７５ ０ ４ ９０ ｌ００ １００ ｌ００ ５ ２００ ５０ ｌ００ ５０ ６ １００ ７５ ７５ ９０ ７ ｌ６０ ｌｌ０ ７５ ９０ ８ ８０ ｌ００ ７５ １ ５０ 存在离散变量的条件下的解决方案，基于此，笔者建立本文所 述的模型的反函数： Ｍｚｉ—Ｙｏ（其中Ｙｆｆ是松弛变量） 将上述关系代入上层目标函数中，可以用Ｃｌａｒｋｅ—Ｗｒｉｇｈｔ ４ ５ ６ ７ ８ ９０ ２００ ｌ００ １６０ ８０ ｌ００ ５０ ７５ Ｉ】０ ｌ００ ｌ００ １００ ７５ ７５ ７５ ｌ００ ５０ ９０ ９０ ｌ ５０ ０ ｌ００ ７５ ７５ １００ １００ ０ ７０ ９０ ７５ ７５ ７０ ０ ７０ ｌ００ ７５ ９０ ７０ ０ ｌ００ １００ ７５ １ ００ １００ ０ 节约启发式算法对上层规划所描述的具有时间限制的分销中 心选址模型进行求解，对于上层规划求出的最优解，再一次求 下层问题就可以得到客户需求量在各个分销中心的分配，重复 上面的思路，可以得到一组新的选址方案，如此重复计算，最后 有望收敛于双层规划模型的最优解。 表３点对间的连接费用的节约值 （Ｉ，Ｊ） （５，７） （５，６） （３，５） （５，８） （４，５） （１，５） （６．７） 《Ｉ，ｊ） ２７０ ２３Ｏ ２２５ ２０５ ｌ９０ １９０ １９０ 具体计算步骤如下： Ｓｔｅｐ１：设定一个初始解ｚ ，令迭代次数ｋ＝ｏ； Ｓｔｅｐ２：对于给定的 ，求解下层规划问题，得到Ｘｑ； （ｉ，Ｊ） ｓ（ｉ，ｊ】 （ｉ，Ｊ） （４，７） ｌ７５ （２，６） （２，５） １６０ （３．６） （２，７） Ｉ４５ （６．８） （３，７） １４５ （１，３） （７．８） １４０ ｆ４，８） （４，６） ｌ１５ （１，６） （１，７）ｉ ９０ （２，８） ｓ（１。ｊ） （ｉ．Ｊ） ８５ （３．４） ８５ （２，３） ８０ （２，４） ７５ （１．２） ７０ （１，４） ６５ （１，８） ６５ （３，８） Ｓｔｅｐ３：Ｉ￣ｘ ＝ＭＺ 一 ，将 代入求出ＹＵ ，然后将关系 式Ｘｉｊ＝Ｍｚｉ—Ｙｏ 代入上层目标函数，求解上层问题得到一组 新的选址方案 ； Ｉ，ｊ） ６５ ６０ ５Ｏ ３ ５ ３０ ２０ ５ 本文在充分考虑路线安排的配送分配和尽量满足客户时 间需求的前题条件下，结合物流规划部门与客户双方利益，构 的条件下物流配送原则，具有很高的实用价值。但是本文只是 考虑单个工厂供应的情况，而在实际的情况下一个分销中心应 该有多个工厂共同配送，在此基础上又必须考虑工厂配送的路 比较符合当前在电子商务 ｓｔｅｐ４：如果ｌＦ“Ｉ＿， ｌ ￡，停止计算，否则，令ｋ＝ｋ＋ｌ，转第 造了一个综合的分销中心选址模型，２步，其中￡为迭代精度。 ４实例分析 本文对以上模型进行参数设定 ｃ ｃ 与当前的销售情况有 线选择，同时在现实条件下，分销中心还存在竞争的情况，因此 模型在这方面还应改进，才能更适应当前的实际需要。 【参考文献】 【１］Ａ ＫＥＮ Ｓ Ｃ Ｈ．Ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｍｏｄｅｌｓ ｆｏｒ ｄｉｓｔｉｒｂｕｔｉｏｎ ｐｌａｎｎｉｎｇ［Ｊ］．Ｅｕｒｏ－ ｐｅａｎ Ｊｏｕｒｎａｌ ｏｆＯｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，１９８５，２２（２）：２６３－２７９． 关，淡季和旺季各不相同，Ｍ。是分销中心ｉ的吸引力，与ｉ分销中 心所在城市的经济发展水平、道路发达程度、文化水平有关。 运输成本由运输距离决定，各点之间的距离见表２。通过对以 上双层规划模型的求解，确定了在８个分销商供货的情况下， 由３个分销中心配送的情况。以下以第１个分销中心的车辆 安排情况及路线选择做具体的研究，其中０代表第一个分销 中心，见表１。 ［２］张培林，魏巧云，物流分销中心选址模型及其启发式算法【Ｊ】．交通运输 工程学报，２００３，３（２）：６５—６８． ［３】ＨＯＬＭＢＥＲ Ｇ Ｋ．Ｅｘａｃｔ ｓｏｌｕｔｉｏｎ ｍｅｔｈｏｄｓ ｏｒｆ ｉｎｃａｐａｃｉｔａｔｅｄ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｃｏｌｌｖｅｘ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｃｏｓｔｓ ｆＪ】；Ｅｕｒｏｐｅａｎ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ， １９９９，１ ｌ４（１）：１２７－１４０． 表１分销中心在各个分销商的分配情况及时间要求 分销商Ｉ １】２ ｌ ３ Ｉ Ｉ ５ Ｉ ６ ７ ２ ５ ８ ３ ［４］ＯＷＥＮ Ｓ Ｈ．ＤＡＳＫ Ｎ Ｍ ｓ．Ｓｔｒａｔｅｇｉｃ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ：ａ ｒｅｖｉｅｗ［Ｊ］．Ｅｕｒｏｐｅａｎ 需求量Ｉ ２ Ｉ １ １ ４５ Ｉ ３ ｌ ｔ．５ １ ４ ｏｆＯｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，１９９８，１ １ １（３）：４２３－４４７． ［５】ＡＮＤＲＥＡＳＫＬＯＳＥ．Ｕｓｉｎｇｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓｉｎｐｒｏｂｌｅｍｓ ｏｆｃｏｍｂｉｎｅｄ１ｏ— ｃａｔｉｏｎ ａｎｄ ｒｏｕｔｉｎｇ［Ａ】．Ｏｐｅｒａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｐｒｏｃｅｅｄｉｎｇｓ［Ｃ］．Ｎｅｗ Ｙｏｒｋ： Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ，１９９６． 时间限制ｌ【ｌＪ ４】Ｊ ，６】ｌ 【ｌ Ｊ２】ｌ ，１ Ｉ ３ ５】Ｊ【２， 【５，８】 【ｌ ５，４】 初始时，当车辆从分销中心出发，开往任务ｊ时，若ＥＴ ≤ ｔ ，≤ＬＴ，，取Ｓｔｊ＝ｔｌＩ，若ｔ。 ＜ＥｒＩ’ｊ，取Ｓｕ＝Ｅ％。计算各个点对间的连接 ［６］孙会君，高自友．供应链分销系统双层优化模型【Ｊ】．管理科学学报， ２００３，（６），６６－７０． 的费用的节约值：ｓ（ ，Ｊ）＝ ｏ＋Ｃｏ，一 ＝ ＋ｄｏ，一 ，通过 上式计算，按从大到小的顺序进行排序，得到表３。 利用以上的数据，本文利用Ｃ—Ｗ节约启发式算法来进行 ［７】沈立新，陈燕，孙兆刚．基于双层规划的虚拟物流企业联盟伙伴选择 模型及求解算法ｆＪ】．科学技术与工程，２００５，（５）：２４４—２４８． ［８］ＹＡＮＧ Ｈ，ＹＡＧＡＲ Ｓ．Ｔｒａｆｌｌｃ ａｓｓｉｇｎｍｅｎｔ ａｎｄ ｓｉｇｎａｌ ｃｏｎｔｒｏｌ ｉｎ ｓａｔｕｒａｔｅｄ 求解，构造线路，得到最终的路线安排如下： ０－－４ ８－４ ５－４ ７－４ ０．０－４ ６ ４ ０ ０－－）３＿÷１－÷２＿÷０ ｍａｄ ｎｅｔｗｏｒｋ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ，１９９５，２９（Ａ）：１２５－１３９． 【９］ＳＨＥＦＦＩ．Ｙ ｕｂａｎ ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｎｅｔｗｏｒｋ：ｅｑｕｉｌｉｂｒｉｕｍ ｎａａｌｙｓｉｓ ｗｉｔｈ Ｍａｔｈ— 由上可见，分销中心１对８个分销商进行供货的情况，同 样的条件下，本文可以对另外两个进行路线安排，以达到效率 最高。 ｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍ ｉｎｇ Ｍｅｔｈｏｄｓ【Ｍ】．Ｎｅｗ Ｊｅｒｓｅｙ：Ｐｒｅｎｔｉｃｅ—Ｈａｌｌ，１９８５． ［１０】黄海军．城市交通网络平衡分析——理论与实践［Ｍ】．北京：人民交 通出版社，１９９３． ５结语 ０２—— 【１１］李军，郭耀煌．物流配送【ＭＪ＿ｊＥ京：中国物资出版社，２００１． 【ｌ２】张潜．物流配送路径优化调度建模与实务【Ｍ】．北京：中国物资出版 社．２００５． ——