1、基于双层规划的物流系统集成定位 2运输路线安排 2库存问题研究(哈尔滨 工业大学管理学院 , 哈尔滨 150001摘要 : 为优化物流系统 , 并能更好地描述管理部门的阶层关系和更全面地体现决策者的意愿 , 从物流系统集成的角度出发 , 基于客户所采用的多时期随机库存策略 , 使用双层规划法建立了供应链二级分销网络中的设施选址 、 车辆运输路线安排 、 库存控制的集成优化模型 ,中选出一系列设施的位置 , 并确定巡回运输路线 , ; 并给出了求解该模型的启发式算法 , 最后通过实例计算证明了上述模型 、关键词 : 双层规划 ; 设施选址 ; 车辆运输路线安排 ;中图分类号 : F274; C9
2、34 Study 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 expressdeci
3、sion 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 co
4、ntrol 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 o
5、f 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 的集成 . 通常对于大部分
6、 LRP 所作的研究都忽略了库存控制问题 14, 然而库存控制与设施选址和 车辆运输路线安排是密切相关的 5,6,Perl 和 Siris oponsilp 设计 的网络模型便认识到了设施选址 、 车辆运输 路线安排 、 库存控制之间所存在着的相互依赖性 7. 为了控制总物流成本 , 必须从系统的角度出发进行总 体分析 , 充 分 考 虑 定 位 2运 输 路 线 安 排 2库 存 控 制 问 题 的 集 成 (C ombined Location R outing and Inventory Problem , C LRIP .LRP 所包括的两个子 问题 LAP 和 VRP 都是 NP 2
7、hard 问题 , 因此 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. 选址决策 、 库存控制 、 车辆运输路线安排在物流系统结构中是属于不同层次的 , 选址属于战
8、略层 、 库收稿日期 :2006203216资助项目 :国家自然科学基金项目 (70501009作者简介 :崔广彬 (1972- , 男 , 博士研究生 , 研究方向 :集成物流系统优化 ,E 2mail :cgb717hit.edu. cn.存管理属于战术层 、 车辆运输调度属于运作层 . 为提高客户满意度 , 在优化分销物流网络时通常忽视了这 样一个问题 , 即上层的管理者虽然具有最终的决策权 , 但是客户也具相对自主的选择权 , 两者之间通常存 在着矛盾 . 客户通常选择能够满足自己需求的物流设施来为其提供服务 , 同时也要求运输服务费用 、 库存 费用最小 , 此时运输服务可采用巡回运
9、输路线的方式 ; 当客户 的巡回运输路线方案确定以后 , 为了能够找 出一个更好的选址方案 , 上层决策者可以对初始巡回运输路线上的设施选址方案进行调整 , 选择其它可选 的物流设施来取代原物流设施 , 并把它重新设置在巡回运输路线上 . 为了能够如实反映上述情况 , 可使用 双层规划法对 C LRIP 进行建模求解 , 上层规划为决策部门确定最佳的设施位置以使选址成本最小 ; 在满足 客户需求的基础上 , 下层规划的目标是确定客户的巡回运输路线 , 以及基于客户所采用的库存策略确定巡 回运输路线上客户的最佳订货量 , 从而保证客户的运输费用 、 库存费用最低 .2 CL RIP 的描述. 增
10、多 , 库存及由此引起的库存成本往往会增加 , , , 可以减少运输距 离 、 降低运输成本 ; , , 采用小批量 、 高频次的运输又 会降低 库存成本 , . 、 运输决策 、 以及库存决策三者之间是相互影响 的 , 因此 , , 在物流系统优化研究中充分考虑 C LRIP 问题 . C :为使整个系 统费用最小化 , 在给定的多个潜在 设施点中选出一系列 设施的位置 , , 同时也要基于客户所采用的库存 策略确定其最佳订货量 .本文对 C LRIP 问题进行研究所基于的物流网络是供应链二级分销网络 , 网络中有一个工厂节点 、 多个 配送中心节点 、 多个客户节点 , 工厂的位置已经确定
11、 , 需要在各地建立配送中心 , 从工厂到各个配送中心为 一级网络 , 各个配送中心为用户送货为二级网络 , 客户采用多时期随机存贮策略 , 最终需要确定配送中心 的位置 、 车辆为客户送货的巡回运输路线 、 以及巡回运输路线上客户的最佳订货量 、 订货点 , 网络结构如图 1所示 . 图 1 二级分销网络示意图2. 1 假设条件文中 C LRIP 问题是基于如下假设 :(1 客户需求为单一品种的商品 , 并且有多个潜在的配送中心 ; (2 每个客户仅能由同一 车辆为其提供服 务 ; (3 在为客户提供运输服务的每条巡回运输路线上只有一辆车 ; (4 每 条巡回运输路线上的客户的总需求不能超过
12、车辆的服务能力 . (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
13、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 内的客户随机需求概率密度函
14、数 ; 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 上 的第一个客户节点 (
15、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
16、 =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 ,
17、巡回运输路线 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 保证在一条巡回运 输路线上只能由一个配送中心提供服务 . 式 (
18、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 (1
19、0 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 最佳订货量和订货点的计算仅当客户在提前期内的需求量超过订货点 r
