二级分销系统控制参数的一个启发式算法

D0I:10.13374/i.issn1001-053x.1992.02.020 北京科技大学学报 第14第2期 Vo1.14No,2 1992年3月 Journal of University of Science and Technology Beijingy March 1992 级分销系统控制 参数的一个启发式算法 高俊山· 摘要：给出确定随机需求环境下一类二级分销系统运行控制参数的一个启发式(Hc口一 ristic)算法。所讨论的系统由1个中心仓库和N个分仓库构成。稳定的随机需求在分仓 库上发生，分仓库向中心仓库定货，而向外部货源的定货则由中心仓库来完成。中心仓库 和分仓库都采用(T,S)策略控制。在满足给定的服务水平前提下，系统以最低期望总库 存费为目标。 关键词：库存论，多级库存系统，Heuristic?算法 A Heuristic Methode to Determine Control Parameters for A Two-Echelon Inventory System Cao Junshan' ABSTRACT:The paper presents a Heuristic method which can be used to deter- mine the control parameters for a two-echelon inventory system,The system under consideration consists of one central warehouse and N local ones,Steady stochestic demands occur at local warehouses which order from the central war- ehouse and it is the central warehouse's responsibility to order from outside supplier.Both the central and local warehouses are controlled under (T,S) policy.The system seeks the minimum expected total inventory cost under the constraint of satisfying a specified service level, KEY WONDS:inventory control,multi-echelon inventory system,Heuristic method 1991-08-27收稿 ·管理工程系(Dcpt,of Management Engineering) 244

第 第 期 ， 年 月 北 京 科 技 大 学 学 报 仁 牡。 五 二级分销系统控制 参数的一个启发式算法 高 俊 山 ’ 摘 要 给出确定随机需求环境下‘ 类二级分销系统运行控制参数的一 个启发 式 卜 算法 。 所讨论的系统由 个中心仓库和 个分仓库构成 。 稳定的陇 机 需求在分 仓 库上发生 ， 分仓库向中心仓库定货 ， 而 向外部货源的定货则 由中心仓库来完成 。 中心 仓 库 和分仓库都采用 ， 策略控制 。 在满足给定的服务水平前提下 ， 系统以最低期望 总 库 存 费为 目标 。 关键词 库存论 ， 多级库存系统 ， 算法 一 翔 一 了 五 ’ 。 ， 。 。 ， 一 ， 一 一 收稿 管理 工程系 功 DOI ：10．13374／j ．issn1001－053x．1992．02．020

由于系统内各库点之间的联系与影响，多级库存系统的分析一般都比较复杂，若再考虑 随机因素的作用，则更是如此。但各种类型的多级库存系统的优化控制却是管理实际中经常 碰到的问题。因此，多级库存系统的建模、分析及优化一直是库存控制理论研究的重要内容 之一1-)。本文将根据文献〔5们对一类二级分销系统的运行状态同系统及环境参教之间关系 的分析结果，.建立一个确定该类系统运行控制参数的启发式(Heuristic)算法。 1系统概述 讨论的系统由一个中心仓库和N个分仓库构成，其主要特征如下（参见图1）： (1)外部需求在分仓库发生，分仓库向中心仓库定货，而由中心仓库向外部货源定货。 在发货无耽搁条件下，中心仓库和分仓库的收货延滞时间分别为常数1。和I1,12,…,1x。 (2)不同分仓库上发生的需求相互独立。同一分仓库不同时段发生的需求构成独立同分 布(i.d)随机变量序列。分仓库在一个时段发生的需求记为D。 (3)中心仓库和分仓库都用(T,S)策略控制，即每隔T个时段定货一次，使得定货后 的名义库存量（实有库存量+待收货量一欠付货量）达到目标值S。中心仓库和各分仓库根 据各自的控制参数(T。,S,),(T1,S1),(T2,S2),…,(Tw,Sw)独立控制，并且各分 仓库之间无调剂活动。 (4)系统由如下定义的需求满足率P作为服务水平的度量指标。在满足给定的需求满足 率前提下，系统以期望总库存费（存货费+定货费）最低为控制目标。 p= ∑rp4 (1) i= E(B,) 1-T…E(B,) p:= 者8<1 (2) 其他 式中： p,一一第仓库的需求满足率 B,一第仓库收货时刻的欠付货量 External supplier o Central.warehouse (T0,S0) 12 Local Locai Local warehouse 1 warehouse 2 warehouse N (T1,S) (T2,S2) (TNSN Demands D Demands D2 Demands DN 图1系统示意图 Fig.1 Chart of the system 245

由于 系统内各库点之 间的联 系与影响 ， 多级库存 系统的分析一般都比较复杂 ， 若再考虑 随机 因素的作用 ， 则更是如此 。 但各种 类型的多 级库存 系统 的优化控制却是管理实际 中经常 碰到的向题 。 因此 ， 多级库存系统的建模 、 分析及优化 一直是库存控制理论研究 的重要内容 之 一 〔 ‘ 一 ‘ ’ 。 本文将根据文献〔 〕对一类二 级分 销系统的运行状态 同系统及环境参教之间关 系 的分析结果 ， 建立一个确定该 类 系统 运行控制 参数的 启发式 “ 算法 。 系 统 概 述 讨论的 系统 由一个中心仓库和 个分仓库构成 ， 其主要特 征如下 参见 图 外部需求 在分仓库发生 ， 分仓库向中心仓库定货 ， 而 由中心仓库向外部货源定货 。 在发 货无耽搁条件下 ， 中心仓库和分仓库的收货延滞时间分别为常数 。 和 ， ， ， 二 。 不 同分仓库上发生的需求相互独立 。 同一分仓库不 同时段发生 的需求 构 成独 立 同分 布 · 随机 变量序 列 。 分仓库 在一个时段 发 生的需求记 为刀 ‘ 。 中心仓库和分仓库都用 ， 策略控制 ， 即每隔 个时段定货一次 ， 使得定 货 后 的名义库存 量 实有库存量 待收货量 一 欠 付货量 达到 目标值 。 中心仓 库和各分仓 库根 据各 自的控制参数 。 ， 。 ， ， ， ， ， … ， ， 二 独 立控 制 ， 并且各分 仓库之 间无调 剂活 动 。 系统 由如 下定义 的需求满足率尸作 为服务水平的度量 指 标 。 在满 足 给定的需求满足 率前提下 ， 系统 以期望总库存 费 存货 费 定货费 最低 为控制 目标 。 ‘ 习 ‘ 夕 ‘ 一 篇 ， ‘ 。 ， ， ， 二 石死币甄万万火 工 其他 ﹄ 七 式 中 ‘ － 第‘仓库的需求满 足 率 ‘ － 第‘仓库收 货时 刻的 欠付货量 〔 ， ， 兮 〔 ，及 场 ， 剐 日 。 刀 日 万 图 系统 示 意图 三 · 乒

E(D,) E(D,) (3) 2需求滿足率 由(1)式和(2)式易见，计算系统需求满足率的关键是求得各分仓库的期望欠付货 量E(B:)。分仓库发出定货后，取决于当时中心仓库的实有库存量。有2种可能的情况：中 心仓库立即发货或耽搁一段时间（中心仓库存货小于定货量而需向外货源定货）。若记1，' 和，”分别为第分仓库两种情况下的收货延滞时间，则有 E(B,)=pXL=1,}E(B,lL,=1,')+p,{L,=1,"}E(B,lL,=1") =q,…E(B,lL,=1,')+(1-9).E(BlL,=1,") (4) 根据文献〔5的分析，9，取决于中心仓库的定货目标S。,各分仓库的需求D,(分布)及 定货间隔Ti,(i=1,2,…,N),而E(B,lL,=1)则取决于该分仓库的需求D,(分布)，定 货目标S,和定货间隔以及从中心仓库到该分仓库的收货延滞时间t: 9:=f(S。,T1,…,Tw,D1,…,Dw) (5) E(B,L,=1)=f(D,S,T,1) (6) 显然，1！=1，而：则还受T。,T,和1.的影响。 如果各分仓库上需求均为正态分布或Pois$on分布随机变量序列，那么以上2式可写成 显式形式。例如对于正态分布需求： ,=2(s。-5m) G:(n) (7) BBL,==rp,(S） +,a-s)(1-(6g2A）) .(8) 式中： ,=E(D,), g:=V(D,) 中(·)一标准正态分布密度函数 巾(·)一标准正态分布函数 G,(n),H,(n)一n,T0,T1,,Tw;h1,…,4x和01…，0x的函数， 详见文献C5)中(31)-(40) m,=T, (9) t一运行周期，定义为相继二次所有仓库同时发出定货之间的时间 246

， ‘ 甲万一一一 一一 一 习 ‘ 需求满足率 由 式和 式 易见 ， 计算系统需求满足率 的关键是求得各分仓库的期望欠付货 量 ‘ 。 分仓库发 出定货后 ， 取决于当时 中心仓库的实有库存量 。 有 种可能的情况 中 心仓库立即发 货或耽搁一段时间 中心仓库存货小千定货量而需 向外货源定 货 。 若 记 和 ‘ 护 分别为第‘分仓库两种情况下的收货延滞时 间 ， 则有 ， ， 毛 。 ‘ 卜 ‘ 二 ‘ 尹 王 ‘ ‘ 一 ， ‘ “ 二 叮， ， ， ，， 一 ， 一 ， ， ， 根据文献〔 〕的分析 ， ，取决于中心仓库的定货 目标 。 ， 各分仓库的需求 ， 分布 及 定 货间隔 ， ， ， … ， ， 而 ， ， 二 则取决于该分仓库的需求刀 ‘ 分布 ， 定 货 目标 ‘ 和定货 间隔以及从中心仓库到该分仓库的收货延滞时 间 叮 二 。 ， ， … ， ， ， ， … ， 二 ， · ， 二 ， ，， ， ， 显 然 ， 打 ‘ ， 而 滚吐还 受 。 ， 。 和 。 的影响 。 如果 各分仓库上需求 均为正态分 布或 ， 。 分 布随机 变量序 列 ， 那 么 以上 式可 写 成 显式形式 。 例如对于 正态分 布需求 始奇买 ， 。 一 ‘ 声‘ 一 ‘ ” 口 ‘ ‘ 。 二 ， ‘ 价， ， ， 一 ， 产‘ ‘ 『， ‘ 产 ‘ 一 ，一 中 共韶杂 上 式 中 产‘ 二 ‘ ， 予 。 ， ， 功 · －标堆正态分 布密度函数 巾 · －标谁正态分 布 函数 “ ， ‘ － ， 。 ， ， … ， 详 见文献〔 〕 中 一 产 ， 一 ， 拼二 和叮 、 … ， 口 的函数 ， 了二 宁 一 ’ 二 － 运行周期 ， 定义 为相继二 次 所有仓库同时发出定货之 间的时 间

3参数优化模型 对子考虑随机因素的多级库存问题，同时求解定货间隔（或定货量）和定货目标（或保 险库存量)两类参数若不是不可能的，也是极为复杂的。通常采取的作法是对它们分别求解 一先将系统中各随机变量代以其期望值，将问题按确定型模型分析，求出定货间隔，然后 再引入随机因素的影响，求出定货目标。这种作法为大多数研究者所采用。关于确定性需求 条件下多级库存系统最佳定货间隔的求法，已有许多工作(07)。因此，这里将主要考虑已 知定货间隔T。,T:,…,Tw条件下，如何确定定货目标S。,S1,…,Sw。 由于定货间隔T。,T1,…,T已定，因此不必再考虑定货费的影响。记C,为单位货物 存放于第仓库(i=0,1,2…N)单位时段所发生的货物持有费，则以下非线性规划问题的 解给出单位时问系统期望货物持有费最低的定货目标S·=(S,S,S2,…,S): 〔)minE「1之z∑c(T,-k)W,(S,nT,+) (10) T-1=0-0 s.t.∑rn:(S。,S)=p (11) 0≤P,≤1，i=1,2,…,N 式中W,(S,t)为第仓库在定货目标为S,条件下时刻的实有存货量。根据文献〔5)中的分 析，它受多方面因素的影响。W,(S,t)与各因素间的复杂关系使得〔D1的求解将极为困 难。下面从另一角度来分析这一问题。设想从式(11)所规定的可行域中一点S出发，向另 一可行点S移动，记 y=S-So (12) 则由图2可以看出，这一移动引起第仓库的平均实有存货条变化为： 1-Ty.+(-） 2 (1-7,)y (13) T (1-n)T Di (1-7×Tyt 1y* D: 2: 22 (+1)T:+1 图2S变动对实有存货的影响 Fig.?Effect of S change on the store 247

参数优化模型 对于考虑随机 因素的多级库存问题 ， 同时求解定货间隔 或定货量 和定货 目标 或保 险库存 量 两 类参数若不是不可能的 ， 也是极为 复杂的 。 通常采取 的作法是对它们分别求解 －先将系统 中各 随机 变量代 以其期望值 ， 将向题按 确定型模型分析 ， 求出定货间隔 ， 然后 再引人随机 因素的影响 ， 求出定货 目标 。 这种作法为大多数研究者所采用 。 关于确定性需求 条件下多级库存 系统 最佳定 货间隔的求 法 ， 已 有许多工作 〔 ’ ’ 。 因此 ， 这里将主要考 虑 已 知定 货间隔 。 ， ， ， … ， 、 条件 下 ， 如何确定定货 目标 。 ， ， ， … ， 、 由于 定货间隔 。 ， ， … ， 二 已定 ， 因此不 必再考虑 定货费的影响 。 记 为单位货物 存 放于 第 仓 库 ￡ 。 ， ， ” 单位时段 所发生 的货物持 有费 ， 则 以下非线性规划 问 题 的 解给出单位 时 间系统期望 货物持有费最低的 定货 目标 ’ 忿 ， 甲 ， 曹 ， 一 ， 贾 ， ‘ 〔刀 〕 角 ‘令，三 ‘ · ‘ 一 秃 一 邵 ‘ 、 ， 称 壳 功乙气 ， 乙 ‘ · 尸 ‘ 。 ， ‘ 二 刀 簇刀， ， 二 ， ， … ， 式 中牙 。 ， ， 为第’仓库在定货 目标 为 条件下时刻 的 实有存 货量 。 根据文献 〔 〕 中 的 分 析 ， 它 受 多方 面 因素的影响 。 牙 ‘ ， 与各 因素间的 复杂 关 系使得 〔 〕 的求 解 将 极 为 困 难 。 下面从 另 一角度来分析 这一向题 。 设想 从式 所规定的可行域 中一 点 。 出 发 ， 向 另 一可行点 移 动 ， 记 一 。 则 由图 可 以 看 出 ， 这 一 移动 引起第 仓库的平均 实有存货量 变化 为 一 ，‘ ‘ ， ‘ 音 ， ‘ 一 份 生 一 勺 ‘ ‘ 了 一 、 、 、 …兰 、 、 、 · 功 ， 、 擎尖… ”二 叮厂 一 不几 ， 、 亡二砂万 ‘ “ 厂二二一 一 一 门「了万奄二二二叁吸 了二一 一 一 门「一 厂一 一 － － 厂 一 － －「 一 哭霉介淞、 … 图 变动对实有存 货的影 响 玉 了 五

式中刀：为第仓库实有存货量为0时间比例。上述移动可节省货物持有费： N -∑c4(1-7)y:=-∑c(1-)S,+Zc(1-0)S: (14) 1=0 t-0 1=0 显然，规划〔P1)的最优解对应于一个节省货物持有费最多的这样一个移动，换句话说，〔P1) 等价于： 〔P2〕min∑c,(1-7:).S, (15) 71 s.tt"p,(S。,S)=p (16) 1 0≤p,(S。,S≤1，i=1,2,,N (17) 4启发式(Heuristic)算法 上面的〔P2)本身并未使问题简化多少。事实上，它只是将目标函数(10)中的所有复杂因 素都转移到一个系数？，中去了。重要的是，新模型中的这个系数的实际意义一第仓库无实 有存货的时间比例。不难理解，这个系数与该仓的欠货比1一P,应该大致相同（对于确定 型需求，二者相等)。若以1一p:代替”：，则问题就会大大地简化。此外，实际中一般不会 取各个分仓库服务水平相差悬殊的控制方案，这样可进一步令p1=p2=…=Pw=P,从而 CP2〕简化为： 〔P3)min∑c:S: (18) 4-0 s.t.p:(S。,S,)=pi=1,2,…,N (19) 注意〔P3)约束条件(19)的特点。每个S,只通过一个方程与S,相关联。因此，如果对给 定的S。,(19)式中的每个方程可解出唯一的S,则cP3)将变成一个关于S的单变量优化问 题。这个要求在大多数情况下都可满足，从p:(S。,S,)的构成可知，在以下两个条件下(19) 式有唯一解： (1)9:是S.的单值函数； (2)对于给定的c,G(S)=E(B:L,=)=c有唯一解。 从(7)式和(8)式易见，正态需求楷况下这两个条件是满足的。一般情况，第一个条件总 能满足，而第二个条件则要求需求分布函数满足（参见文献〔4）中关于9，和E(B,|L:=)的一 般表达式)： dF(x)≠dF(x-c),c≠0 例：继续考虑文献〔4)中的举例。设单时段各分仓库的需求皆为正态分布，且41=20， 01“2,42=10,02=1,代人(7)式和(8)式得： 248

式 中刀 ‘ 为第 仓 库实有存货量为。时 间比 例 。 上述 移动可节省货物持 有费 一 乙 。 · 一 ， ‘ · 夕 ‘ 二 一 乙 ‘ · 一 刃 ‘ · ‘ ‘ · 一 刃‘ · 丁 显然 ， 规划〔 〕的最优解对应于 一个节省货物持有费最多的这样一个移动 ，换句话说 ， 〔尸幻 等价于 万 〔 〕 ‘ 一 一 勺 一 ‘ 咨二 乙 ， 一 ， ， ‘ 二 落 ， 。 ， ‘ ， ， ， … ， 启发式 算法 上面的 〔 〕本身并未使问题简化多少 。 事实上 ， 它只是将 目标函数 中的所有复杂 因 素都转移到一个 系数叩 ， 中去 了 。 重要的 是 ， 新模型 中的 这个 系数的 实际意 义－ 第 ‘ 仓库无 实 有存货的时 间比 例 。 不难理解 ， 这个 系数 与 该仓 的欠 货比 一 尸 。 应该大致相 同 对 于 确 定 型需求 ， 二者相等 。 若 以 一 ，代替， ‘ ， 则问题就会大大地简化 。 此外 ， 实际 中一般不会 取各个分仓库服务水平相差悬殊的控制方案 ， 这样可 进 一步 令 工 ” 一 二 二 ， 从 而 〔 〕简化为 〔 〕 乙 ‘ 子 之 。 。 ‘ 。 ， 。 ， ， 一 ， 注意 〔 〕 约束条件 的特点 。 每个 ‘ 只通过一个 方程 与 。 相 关联 。 因 此 ， 如果 对 给 定的 。 ， 式 中的每个 方程可解 出唯一的 ‘ ， 则 〔尸 〕将变 成一个关于 。 的单变 量优 化问 题 。 这个要求在大 多数情况下都可满 足 ， 从 ， 。 ， ‘ 的构成可知 ， 在以下两个条件下 式 有 唯一解 ‘是 。 的 单值 函数 对于 给定的 ， ‘ ， ‘ · 有唯一解 。 从 式和 式 易见 ， 正态需求 情况 下 这两 个条件是满足的 。 一般情况 ， 第一 个条件 总 能满足 ， 而第二 个条件则要求需求分 布 函数满 足 参见文献 〔 〕 中关于 ‘ 和 ‘ ‘ 二 的 一 般表 达式 二 笋 二 一 ， 笋 例 继续考虑 文献〔 〕 中的举例 。 设单时段 各分 仓库 的需求 皆 为正态分布 ， 且 声， ， 二 ， 户 ， ， ， 代人 式和 式 得