基于双层规划的物流系统集成定位-运输路线安排-库存问题研究

基于双层规划的物流系统集成定位 2运输路线安排 2库存问题研究(哈尔滨工业大学管理学院 , 哈尔滨 150001摘要 : 为优化物流系统 , 并能更好地描述管理部门的阶层关系和更全面地体现决策者的意愿 , 从物流系统集成的角度出发 , 基于客户所采用的多时期随机库存策略 , 使用双层规划法建立了供应链二级分销网络中的设施选址 、 车辆运输路线安排 、 库存控制的集成优化模型 ,中选出一系列设施的位置 , 并确定巡回运输路线 , ; 并给出了求解该模型的启发式算法 , 最后通过实例计算证明了上述模型 、关键词 : 双层规划 ; 设施选址 ; 车辆运输路线安排 ;中图分类号 : F274; C934Study on the C and Inventory Problem in based on Bi 2level ProgrammingCUI G uang 2bin , LI Y i 2jun(School of management , Harbin Institute of T echnology , Harbin 150001,China Abstract : In order to optimize logistics system , describe the hierarchy of management section better , and expressdecision makers will com pletely , from the point of integration , a bi 2level programming method is proposed to establishthe m odel of the combined location routing and inventory problem (C LRIP for the tw o 2echelon distribution netw ork inthe supply chain based on customers multi 2period inventory control policy with stochastic demands. C LRIP is used toallocate depots from several potential locations , to schedule vehicle routing , and determine customers orderquantities. A new heuristics alg orithm is presented to s olve the m odel. Finally , an exam ple is given to illustrate theefficiency of the above m odels and methods.K ey w ords : bi 2level programming ; depot location ; vehicle routing ; inventory control1 引言定位 2车辆运输路线安排 (Location 2routing Problem , LRP 是集成物流系统优化研究中的一个重要问题 , LRP 是定位 2分配问题 (Location Allocation Problem , LAP 和车辆运输路线安排问题 (Vehicle R outing Problem , VRP 的集成 . 通常对于大部分 LRP 所作的研究都忽略了库存控制问题 14, 然而库存控制与设施选址和 车辆运输路线安排是密切相关的 5,6,Perl 和 Siris oponsilp 设计的网络模型便认识到了设施选址 、 车辆运输 路线安排 、 库存控制之间所存在着的相互依赖性 7. 为了控制总物流成本 , 必须从系统的角度出发进行总 体分析 , 充 分 考 虑 定 位 2运 输 路 线 安 排 2库 存 控 制 问 题 的 集 成 (C ombined Location R outing and Inventory Problem , C LRIP .LRP 所包括的两个子问题 LAP 和 VRP 都是 NP 2hard 问题 , 因此 LRP 是 NP 2hard 问题 8, 而 C LRIP 是比 LRP 更为复杂的问题 , 也是 NP 2hard 问题 9. 精确求解 C LRIP 很困难 , 通常采用启发式算法 , 如 :Liu和 Lee 提供了一个求解 C LIRP 的两阶段启发式算法 9. S. C. Liu 和 C. C. Lin 把 C LRIP 问题分成两个子问题 :1 设 施定位 2分配问题 ;2 运输路线安排和库存控制问题 , 并利用禁忌搜索结合模拟退火混合算法进行了求 解 10. 选址决策 、 库存控制 、 车辆运输路线安排在物流系统结构中是属于不同层次的 , 选址属于战略层 、 库收稿日期 :2006203216资助项目 :国家自然科学基金项目 (70501009 作者简介 :崔广彬 (1972- , 男 , 博士研究生 , 研究方向 :集成物流系统优化 ,E 2mail :. cn. 存管理属于战术层 、 车辆运输调度属于运作层 . 为提高客户满意度 , 在优化分销物流网络时通常忽视了这 样一个问题 , 即上层的管理者虽然具有最终的决策权 , 但是客户也具相对自主的选择权 , 两者之间通常存 在着矛盾 . 客户通常选择能够满足自己需求的物流设施来为其提供服务 , 同时也要求运输服务费用 、 库存 费用最小 , 此时运输服务可采用巡回运输路线的方式 ; 当客户的巡回运输路线方案确定以后 , 为了能够找 出一个更好的选址方案 , 上层决策者可以对初始巡回运输路线上的设施选址方案进行调整 , 选择其它可选 的物流设施来取代原物流设施 , 并把它重新设置在巡回运输路线上 . 为了能够如实反映上述情况 , 可使用 双层规划法对 C LRIP 进行建模求解 , 上层规划为决策部门确定最佳的设施位置以使选址成本最小 ; 在满足 客户需求的基础上 , 下层规划的目标是确定客户的巡回运输路线 , 以及基于客户所采用的库存策略确定巡 回运输路线上客户的最佳订货量 , 从而保证客户的运输费用 、 库存费用最低 .2 CL RIP 的描述. 增多 , 库存及由此引起的库存成本往往会增加 , , , 可以减少运输距 离 、 降低运输成本 ; , , 采用小批量 、 高频次的运输又 会降低库存成本 , . 、 运输决策 、 以及库存决策三者之间是相互影响 的 , 因此 , , 在物流系统优化研究中充分考虑 C LRIP 问题 . C :为使整个系统费用最小化 , 在给定的多个潜在设施点中选出一系列 设施的位置 , , 同时也要基于客户所采用的库存 策略确定其最佳订货量 .本文对 C LRIP 问题进行研究所基于的物流网络是供应链二级分销网络 , 网络中有一个工厂节点 、 多个 配送中心节点 、 多个客户节点 , 工厂的位置已经确定 , 需要在各地建立配送中心 , 从工厂到各个配送中心为 一级网络 , 各个配送中心为用户送货为二级网络 , 客户采用多时期随机存贮策略 , 最终需要确定配送中心 的位置 、 车辆为客户送货的巡回运输路线 、 以及巡回运输路线上客户的最佳订货量 、 订货点 , 网络结构如图 1所示 . 图 1 二级分销网络示意图2. 1 假设条件文中 C LRIP 问题是基于如下假设 :(1 客户需求为单一品种的商品 , 并且有多个潜在的配送中心 ; (2 每个客户仅能由同一车辆为其提供服 务 ; (3 在为客户提供运输服务的每条巡回运输路线上只有一辆车 ; (4 每 条巡回运输路线上的客户的总需求不能超过车辆的服务能力 . (5 每辆车 在完成每次运输任务后返回到出发点 . (6 运输车辆为同一车型 . 2. 2 模型中参数的含义I :所有客户节点集合 ; J :所有配送中心节点集合 ; K :所有运输车辆集合 ; p :表示工厂 ; b :车辆的运载能力 ; MaxSup :车辆的最大服务能力 ;f j :建立配送中心 j 的固定费用 ; W pj :由工厂 p 至配送中心 j 的每单位运量的运费 ; C V :车辆每次的派遣费用 ; C D :每次的订购费用 ; C p :存贮费用 ; C S :缺货费用 ; C M :车辆在巡回运输路线上每单位运距的运费 ; i :表示客户节点 (i I ; j :表示配送中心节点 (j J ; k :表示运输车辆 (k K ; g , h :表示整个网络中的客 户节点或者配送中心节点 , g (I J , h (I J ; d kgh 表示在巡回运输路线 k 中由节点 g 至节点 h 间的 距离 , k K , g (I J , h (I J ; Dis k :表示巡回运输路线 k 的总运距 . Q k :表示巡回运输路线 k 中所 有客户节点的订货批量 ; D k :表示巡回运输路线 k 中所有客户节点的总需求量 ; r k :表示巡回运输路线 k 中所有客户节点的订货点 ; f L (x :订货提前期 L 内的客户随机需求概率密度函数 ; k :表示巡回路线 k 中 所有客户节点在订货提前期内的平均需求 ; :S (r k 表示巡回运输路线中所有客户节点的期望缺货数量 ;D jk :巡回运输路线 k 上的所有客户对配送中心 j 的需求量 ; V k :表示巡回运输路线 k 上所有节点的集合 ; j 3:表示已被设置在巡回运输路线 k 上的配送中心节点 (j 3 V k ; (i s , i s +1 :表示巡回运输路线 k 上05系统工程理论与实践 2007年 6月 的所有客户节点中一对相互邻接节点对 (i s , i s +1 V k ; i 1:表示选中 j 3为配送中心的巡回运输路线 k 上 的第一个客户节点 (i 1 V k ; i f 表示选中 j 3为配送中心的巡回运输路线 k 上的最后一个客户节点 (i f V k; Dis jk =d kji s +d kji s +1+d ki 1i f -d kj 3i1-d kj 3i f -d ki s i s +1, Dis jk 表示巡回运输路线 k 上的配送中心经交换 ,即节点 j (j J 取代节点 j 3后巡回运输路线 k 上总的运输距离的变化量 , 配送中心的交换操作过程如图 2所示 .图 2 2. 3 决策变量X kgh =1, 如果运输车辆 k h k K , g h , g , h (I J ; 否则 , X kgh =0. Y ij =1, i j 提供服务 , i I , j J ; 否则 , Y ij =0. y j =1, , j J ; 否则 , y j =0.Z jk =1, 如果配送中心 j 在巡回运输路线 k 上 , j J , k K ; 否则 , Z jk =0.2. 4 模型的建立模型中每条巡回运输路线上的客户在各个时期的需求是随机的 , 当库存量降低到订货点时立即提出 订货 , D k Q k 为运输车辆 k 在其巡回运输路线上的平均送货次数 . 巡回运输路线 k 上的存贮费为 :C P (Q k 2+r k -k , 巡回运输路线 k 上的缺货费为 :C S S (r k D k Q k , 巡回运输路线 k 上的订货费为 :C D D kQ k. 上层规划模型 :min j J k KC M Dis jk Z jk +j Jf j y j+j JW pj k KD kj(1 s. t.j JZ jk=1, k K(2 y j Z jk , j J , k K (3 y j 0,1, j J (4 Z jk 0,1, j J , k K(5 式 (1 上层规划目标函数是从决策者的角度出发使总的配送中心选址费用、 一级物流网络中的运输费用 、 以及巡回运输路线上的配送中心经交换后所产生的运输费用的增加量最小 . 式 (2 保证在一条巡回运 输路线上只能由一个配送中心提供服务 . 式 (3 保证只有已被选中的配送中心才能为巡回运输路线上的客 户提供服务 . 式 (4 保证决策变量满足取整数约束 .下层规划模型 :min k K g (I J h (I J C M d kgh X kgh Q k+k KC V D k Q k +C P Q k2+r k -k+C D D k Q k +C S S (r k D k Q k (6 s. t. Q k b , k K(7 D k Max sup , k K(8 k KD kj M y j , j J(915第 6期 基于双层规划的物流系统集成定位 2运输路线安排 2库存问题研究 k K h (I J X kih =1, i I (10 g (I J X khg -g (I J X kgh =0, k K , h (I J (11 i Ij JX kij 1, k K (12 h (I J X kih +h (I J X kjh -Y ij 1, i I , j J , k K (13X kgh =0,1, k K , g (I J , h (I J (14 Z j =0,1, j J (15 Y ij =0,1, i I , j J (16 式 (6 下层规划目标函数的目标是满足客户需求的同时 , . 式 (7 保 . (8求不应超过运输车辆的服务能力 . 式 (9 , M 为任意大的数 . 式 (10 , 即将货物运至某一点的 车辆 , 必须在同一点离开 . 式 (11 . 式 (13 保 . 式 (14 -式 (16 保证决策变量为整数 .3 算法分析3. 1 最佳订货量和订货点的计算仅当客户在提前期内的需求量超过订货点 rk 时才发生供应短缺 , 用 x 表示提前期内的随机需求量 , 则提前期内的期望缺货数量为 :S (r k = r k (x -r k f L (x d x (17 将 (6 式对 Qk 求偏导数 , 并令其为 0有 :Q 2k -Q 2k-Q 2k-(Q 2k+2 =0 所以Q 3k = D (C C C Dis C S (r C P(18将 (6 式对 r k 求偏导数 , 并令其为 0有 :C S D kQ kd S (r k d r k+C P =0可以求得 : r k f L (x d x =C QC S D k(19 由式 (18 和式 (19 可知 , 为求 Qk 需知道 r k , 为求 r k 需知道 Q k , 故采用如下的迭代算法 , 步骤如下 :1 作为初始解在式 (18 中令 S (r k =0, 求出 Q 1k ;2 将 Q 1k 的值代入式 (19 , 求出 r 1k ;3 将 r 1k 的值代入式 (17 , 计算 S (r 1k 4 再将 S (r 1k 值代入式 (18 , 求得 Q 2k ;5 重复 (2 -(4 步 , 直到 Q i k 和 r i k 的值基本上不再有较大的变化为止 .3. 2 下层规划的求解算法为了能够将在同一条巡回运输路线上、 由同一个配送中心提供服务的客户聚为一类 , 并满足每条巡回 运输路线上客户的运输费用、 库存费用最少 , 客户初始巡回运输路线的求解方法如下 :第一步 :1 设 k =1, r =1, MaxSup =车辆服务能力 ;2 把所有客户节点放入集合 F ;3 将所有配送中心 25系统工程理论与实践 2007年 6月 节点放入集合 E .第二步 :1 从集合 F 中随机选取一个客户节点 ;2 把该客户节点放入集合 V k 中 ;3 从集合 F 中删除 该客户节点 .第三步 :从集合 F 中选择具有最小边际费 CS 的客户节点 i , 作为下一个候选客户节点 ; CS =S (V k +i -S (V k , S (V k 或 S (V k +i 可由下式计算 :(C V +C M Dis k D Q k +C P Q k2+r k -k+C D D Q k +C S S (r k D Q k , 其中 Q k 、 r k 可由 3. 1中的方法求得 .第四步 :如果集合 V k 中的客户节点和候选客户节点 i 的总需求不大于车辆服务能力 , 那么 :1 把候选 客户节点 i 放入集合 V k 中 ;2 从集合 F 中删除节点 i ;3 转向第五步 . 否则 =k +1;2 把候选客户 节点 i 放入集合 V k 中 ;3 从集合 F 中删除候选客户节点 ;4 第五步 :如果集合 F 为空集 , 那么转向第六步 ; , 第六步 :计算 V t (1 t k t =qti =1id i qti =1di, Y t = qti =1yi d i qti =1di(20(X t , Y t 为 V t 的重心坐标 , q t 为 V t 中的客户节点总数 , d i 为 V t 中客户节点 i 的需求量 , (x i , y i 为客户节点 i 的坐标 (1 i q t .第七步 :1 从配送中心集合 E 中选择一个距集合 V r 的重心坐标最近的配送中心节点 ;2 把该配送中 心节点放入集合 V r ;3 从配送中心集合 E 中删除该配送中心节点 ;4 设 r =r +1.第八步 :如果 r k , 那么转向第九步 ; 否则 , 转向第七步 .第九步 :将最终所求得的客户的初始巡回运输路线记为 V t (1 t k , 并计算出每条巡回运输路线上 的运输成本与库存成本 SC t (1 t k . 3. 3 上层规划的求解由下层规划的求解过程可知 , 其模型中的约束条件都能被满足 . 对于约束 (9 :k KD kj M y j , j J ,已知 y j , 如果 y j =0, 则 D kj =0, 可以将此约束去除 ; 如果 y j =1, 那么 D kj M , M 为任意大数 , 此约束自 然满足 . 设 u kj 为松弛变量 , 令 D kj =My j -u kj , j J , k K . 当 y j =0时 , 可以直接得出 D kj 和 u kj 的值 , 当 y j =1时 , 根据下层规划求解算法求出 D 3kj 后 , 利用公式 D 3kj =My j -u 3kj , 可以计算出松弛变量 u 3kj 的 值 , 这样可以得到如下的关系式 :D kj =My j -3kj , j J , k K(21 第一步 :根据已得到的初始巡回运输路线方案 V t (1 t k , 求出 u 3kj (j J , k K , 再将公式 (21 代入上层规划的目标函数中 .第二步 :对于初始巡回运输路线方案 V t (1 t k , j 3t 表示被选中的配送中心节点 , j 3t V t (1 t k , 计算费用 C L :C L =j3t (J V t (F j 3t y j 3t+M W pj 3t y j 3t -W pj 3t u 3kj 3t 第三步 :对初始巡回运输路线上的配送中心进行交换操作 , 选择配送中心节点 j (j J 与巡回运输路线 V t (1 t k 上的配送中心节点 j 3t (j 3t V t 进行交换操作 , 并计算由交换操作所引起的每条巡回运输 路线长度的最小增加量 min j J , j j3tDis jt :min j J , j j3tDis jt =(d tji s +d tji s +1+d ti 1i f -d tj 3t i 1-d tj 3t i f -d ti s i s +1 , i 1, i s , i s +1,i f , j 3t V t , j J .35第 6期 基于双层规划的物流系统集成定位 2运输路线安排 2库存问题研究54 系统工程理论与实践 2007 年 6 月 3. 4 RIP 双层规划模型的求解算法 CL 影响的 . 通过求解下层规划可以得到满足客户需求的初始巡回运输路线 ,将其代入上层规划 ,决策者可以 对初始选址方案进行重新调整 . 双层规划模型能够更好地描述管理部门的阶层关系并能更全面地体现决 策者的意愿 . 故有如下算法 : 第一步 : 基于上层规划 ,利用 3. 2 中的方法 ,求出初始巡回运输路线方案 V t ( 1 t k . 的配送中心保持不变 . 4 实例应用 Cl ( j , t = ( min CM Disjt + ( Fj t3 j t3 + M pj t3 j t3 - W pj t3 kj t3 , i 1 , is , is + 1 , if , j t V t , j J ,1 t y W y u j J , j j t k CM = 1 , CD = 15 , CS = 2 , CP = 1 , b = 150 , MaxSup = 1000 ,配送中心的其它参数见表 1 ,客户的其它参见表 2. 3 3 第四步 : 根据 min 3 jt ,令 j t = j ( j t V t , j J ,1 t k ,求解如下问题 : Dis j J , j j t k CLRIP 问题包括三个子问题 : 设施选址决策 、 车辆运输路线安排 、 库存控制 ,且三个子问题之间是相互 第二步 : 基于下层规划 ,利用 3. 3 中的方法求出 CL , CL ( j , t ( 1 t k . 3 3 第三步 : 如果 CL ( j , t CL ( 1 t k , 则选择配送中心 j 取代 j t ( j t V t ; 否则原巡回运输路线上 第四步 : 输出 V t 、 t 、t ( 1 t k . Q r 假定在供应链二级分销网络系统中有 1 个工厂 p ,3 个配送中心 ,10 个客户 , 如下条件已知 : CV = 20 , 表1 配送中心参数 配送中心 j1 j2 j3 空间位置坐标 (50 ,148 (34 ,82 (185 ,198 固定成本 250 430 150 工厂 p 与配送中心间的运费 2 3 2 3 t =1 表2 客户参数 客户 i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 空间位置坐标 (142 ,85 (163 ,175 (87 ,96 (63 ,57 (204 ,217 (130 ,165 (180 ,210 (93 ,114 (170 ,163 (78 ,103 年需求量 385 430 540 324 238 296 340 286 392 310 3 提前期内客户需求的平均分布 U0 ,5 U0 ,4 U0 ,8 U0 ,9 U0 ,6 U0 ,7 U0 ,6 U0 ,5 U0 ,8 U0 ,7 3 第一步 : 根据上述已知条件 , 由下层规划通过计算可得到如下初始解方案 : V 1 = i 3 , i10 , j2 , SC1 = 93116922 ; V 2 = i1 , i 8 , i6 , j1 , SC2 = 232718 ; V 3 = i2 , i 7 , j3 , SC3 = 68910039 ; V 4 = i 5 , i9 , i 4 , j3 , SC4 = 302817. 第二步 : 取 M = 1000 , 根据下层规划可得到 D11 = 1000 y1 - 1000 , D12 = 1000 y2 - 150 , D13 = 1000 y3 - 1000 , D21 = 1000 y1 - 33 , D22 = 1000 y2 - 1000 , D23 = 1000 y3 - 1000 , D31 = 1000 y1 - 1000 , D32 = 1000 y2 - 1000 , D33 = 1000 y3 - 230 , D41 = 1000 y1 - 1000 , D42 = 1000 y2 - 1000 , D43 = 1000 y3 - 46 ; 将初始解代入上层规划可得 到 CL = 8762 ; 方案 V 1 : CL ( j1 , 1 = 7495. 2477 , 方案 V 2 : CL ( j3 , 2 = 850317557 , 方案 V 3 : CL ( j1 , 3 = 第6期 基于双层规划的物流系统集成定位2运输路线安排2库存问题研究 55 89771381 ,方案 V 4 : CL ( j1 ,4 = 880913514. 与初始解方案相对应的整个系统的总费用 C = CL + SC1 + SC2 + 91026 , S ( r3 = 010474 , SC= 68910039 ; V 4 = i5 , i9 , i4 , j3 , Q4 = 150 , r4 = 2111918 , S ( r4 = 010711 , SC = 3 4 302817. 与新方案对应的费用 CL 7482 ,在新方案下系统的总费用 C CL SC+ SC + SC + SC= = = + 1 2 3 4 1448112 C . 5 结论 被取代 . 第四步 : 可得到如下新方案 : V 1 = i3 , i10 , j1 , Q1 = 150 , r1 = 1316765 , S ( r1 = 010584 , SC= 100618 ; V 2 1 路线上客户的最佳订货量 、 订货点 . 参考文献 : 1 Perl J , Daskin MS. A warehouse location2routing problem J . Transportation Research Quarterly , 1985 , 19B (5 :381 - 396. 2 Srivastava R. Alternate solution procedures for the location2routing problem J . Omega , 1993 , 21 (4 :497 - 506. Operational Research , 1999 , 116 (1 :87 - 99. Operation Research , 2002 , 29 (10 :1393 - 1415. 19A (5 : 383 - 398. 6 directions J . European Journal of Operational Research , 1998 , 108 (1 : 1 - 15. Distribution and Material Management , 1988 , 18 (6 :18 - 26. Advanced Manufacturing Technology , 2005 , 26 (4 :372 - 381. 8 Lenstra J K, Rinnooy Kan A H G. Complexity of vehicle routing and scheduling problems , 1981 , 11 (2 :221 - 227. consideration J . The International Journal of Advanced Manufacturing Technology ,2003 , 22 (11 - 12 : 941 - 950. 基于供应链二级分销网络 ,本文使用双层规划法建立了设施选址问题 、 车辆运输路线安排问题 、 库存 控制问题的集成优化模型 ,上层规划考虑了选址决策 ,下层规划考虑了车辆运输路线安排以及库存控制问 题 ,该