订单分批问题的数学模型及节约启发式算法 长江大学管理学院 　谭俊华 　李诗珍 　　摘 　要 : 构造了拣货作业中订单分批问题的数学模型 , 在一些模型假设的基础上 , 提出了解决该问题的节 约启发式算法 。算例分析表明 , 该算法的订单分批结果优于传统的先到先服务分批结果 , 为实现订单优化分批 拣货作业提供了新方法 。 关键词 : 拣货 ; 订单分批 ; 模型 ; 节约算法 Abstract: A mathematical model of order batching p roblem is established and a saving heuristics algorithm to solve Modeling and analyzing of a specific AS/RS shows that better results are the p roblem is given based on some assump tions obtained with the saving heuristics algorithm than with the traditional method of first come first service Keywords: order p icking; order batching; model; saving algorithm 　　订单分批是为了提高拣货作业的效率而将多 张订单合并成一批 , 进行批次拣取作业 , 其目的 在于缩短拣取时平均行走搬运的距离及时间 。若 再将每批次订单中的同一品项加总后进行拣取 , 然后把货品分类至每个不同的顾客 , 就形成了订 单的批量拣取 , 这样不仅缩短了拣取时平均行走 搬运的时间 , 也减少了储位重复寻找的时间 , 进 而提升了拣货的效率 。批量拣取根据分类方式的 不同可以分为拣取时分类和拣取后分类 2种 。 订单批量问题是指将订单按照适当的方式进 行分批并确定批量拣取路径以便目标函数达到最 优 [ 1 ] 。批量拣取的基础目标有 2种 : (1) 减少拣 (2) 减少拣货行走的距离进而 货行走的总时间 ; 提升产能和改善交货期 。本文以最小化行走距离 为目标构造了订单分批问题的数学模型 , 提出了 解决该问题的节约启发式算法 , 并给出一个用此 算法求解该问题的实例 。此算法可以有效求得订 单分批问题的近优解 , 能够广泛运用于大型配送 中心和流通仓库的拣货系统 , 以提高拣货作业的 效率 。 1　订单分批问题的数学模型 1 1　模型假设 (1) 仓库结构已知 ; (2) 每张订单上的品项数量不超过拣货车的 容量 ; —81— (3) 每批订单的拣取都能在 1 条拣货路线上 完成 ; (4) 任一拣货路径的起点和终点都在出入口 , 即拣货员推着拣货车从出入口出发 , 按设定的路 径策略从仓库中拣出货物 , 最后返回出入口 ; (5) 拣取时不存在缺货现象 ; (6) 订单数据输入后 , 计算机能按事先规定 的路径策略对需要拣取的品项进行路径排序 , 形 成顺序拣货单 。 1 2　数学模型 目标函数 m in∑ s∈S ds xs 约束条件 ∑n j =1 qj ajs ≤ C ajs xs = 1, ∑ xs ∈{ 0, 1} , ajs ∈{ 0, 1} j = 1, …, n s∈S 式中 　n———需要拣取的订单总数 ( 1) ( 2) ( 3) ( 4) C———拣货车的容量 qj ———第 j个订单中所有品项的数量 S ———所有可行订单批量集合 s———每个可行的订单批量 , 1　订单 j属于第 s批 0　订单 j不属于第 s批 s∈S ajs = 　j = 1, 2, …, n ds ———拣取第 s批订单中的所有品项的总行 走距离 1　第 s批被选中 0　第 s批没有被选中 xs = 《起重运输机械 》　2008 (3) © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

模型的目标函数是订单分批后 , 使各批订单拣 取路线总和最小。约束条件 ( 2) 表示每批订单包 含的品项数不超过拣货车的容量 , 约束条件 ( 3) 和 (4) 表示每个订单只能被分配到一个批量中。 2　订单分批问题的节约启发式算法 当模型订单数量大于等于 3时 , 属于 NP完全 问题 [ 1 ] , 其求解较复杂 [ 2 ] 。节约启发式算法的基 本思想是车辆路径问题中的节约算法在订单分批 中的应用 。节约算法就是将订单 i和订单 j合并成 在一条路线上进行拣取的新订单 , 使合并后的行 走距离 (行走时间 ) 比分别拣取订单 i和订单 j具 有最大的节约量 S ij = di + dj - dij。在订单分批问题 中 , 订单相当于车辆路径问题中的城市 , 订单合 并后产生的行走距离 (行走时间 ) 节约量相当于 城市合并配送后节约的里程数 。两者本质的不同 在于合并的订单中 , 存在具有共同存储位置的品 项 。对这些品项的拣取 , 只需访问一次就能同时 满足多张订单的要求 。另外 , 由于车辆容量的限 制 , 并不是每张订单都能与其他订单合并成一批 进行拣取 。 2 1　初始批量的形成 (1) 输入一个时间段内所有需要拣取的订单 数据 , 包括拣货车的容量 ; (2) 将所有的订单两两组对 , 计算其品项数 之和 qij = qi + qj j≠ i) , 如果 qij ≤C, 则 计 算 其 行 走 距 离 节 约 量 S ij = S ji; ( i = 1, …, n; j = 1, …, n; 到找不到符合组成条件的订单为止 。当前批 O s 即 为找到的优化批量 。 ②max {S ik , S jp } = Sw p , 则计算 O s 与 Ow 品 项数之和 qsw = qs + qw , 若 qsw ≤C, 则将订单 Ow 加 入到当前批 O s 中形成新的当前批 O s = O s + Ow = { O k , O p , Ow }。否则对余下的组合重复 ( 2) , 直 到找不到符合组成条件的订单为止 。当前批 O s 即 为找到的优化批量 。 (3) 将当前批量 O s 中的订单从待分批的订单 集合中移走 , 转至 2 1中步骤 (4) 。 (4) 如果所有的组合都已经检查完成 , 但仍 有订单没有分配到适当的批中 , 则将这些订单单 独成批 。 3　算例分析 仓库结构为长方形 , 出入口位于仓库的一角 第 1个巷道的中心处 , 共有 7 个拣货巷道 , 货架 为低层固定货架 , 每排货架上沿巷道方向有 15列 存储位置 , 图 l为仓库货架二维平面图 。已知货架 长 15个单位 , 巷道中心距离为 4个单位 , 拣货车 的容量为 8。现有 7个需要拣取的订单 , 包括 5种 不同的品项 。订单订购的品项数分别为 : 订单 1 为 4品项 ; 订单 2为 6品项 ; 订单 3为 4品项 ; 订 单 4为 2品项 ; 订单 5 为 3 品项 ; 订单 6 为 5 品 项 ; 订单 7为 1品项 。订单品项在仓库中的分布如 图 1所示 。 (3) 将节量按由大到小非增序排列 ; (4) 选择节约量最大的组合 Skp = maxS ji合并 成一批 (如果有 2组数字相同 , 则任选 1组 ) ; 由 订单 O k 和 O p 组成 1 个新的订单 , 即 O s = { O k , O p } 形成初始批量 。 2 2　批量优化 (1) 分别以订单 k 和订单 p为基准订单 , 检 图 1　仓库结构及订单品项分布 i≠p, j 3 1　节约启发式分批 查 S ik和 S jp j = 1, …, n; ≠k) , 将节约量按由大到小非增序排列 。 ( i = 1, …, n; (2) 选择节约量最大的组合 , 存在 2种情况 : ①max {S ik , S jp } = Svk , 则计算 O s 与 O v 品项 数之和 qsv = qs + qv , 若 qsv ≤C, 则将订单 O v 加入 到当前 批 O s 中形 成新 的 当 前 批 O s = O s + O v = { O k , O p , O v }。否则对余下的组合重复 ( 2 ) , 直 　《起重运输机械 》　2008 (3) 由已知条件可知 : 7 张订单订购总品项数为 25, 拣货车容量为 8, 所以要拣取所有的品项至少 要分 4批才能实现 。由于分批的目的在于最小化 订单拣取的行走距离 , 所以在分批之前必须确定 相应的路径策略 。路径策略主要有穿越策略 (也 叫 S形策略 ) 、返回策略 、中点策略 、最大间隙策 —91— © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

1 1 1 1 务的原则分批结果为 (1) , ( 5, (7) 。下面依然采用 S 形启发式路径策略计算 6) , 不分批和 2 种分批情况下的行走总距离 , 即模型 中目标函数的值 。 ( 3, 4) , ( 2) , 节约启发式分批 : D = d357 + d46 + d1 + d2 = 108 + 108 + 108 + 108 = 432 先到先服务分批 : D = d1 + d2 + d34 + d56 + d7 = 108 + 108 + 108 + 138 + 10 = 472 不分批 : D = d1 + d2 + d3 + d4 + d5 + d6 + d7 = 108 + 108 + 106 + 78 + 98 + 108 + 10 = 616 从计算结果可以看出 : 节约启发式分批总行 走距离最短 , 不分批行走距离最长 , 先到先服务 介于两者之间 。订单中重复产品的数量越多 , 不 同订单产品分布的巷道重复数越多 , 节约算法中 行走距离的节约量也会越大 , 分批拣货的优越性 就会越明显 。 4　结束语 有效的订单分批方法可以带来拣货作业效率 的巨大提升 。通过对订单分批问题的分析 , 建立 了相应的数学模型 , 提出了解决该问题的节约启 发式算法 , 并与其他方法进行了比较分析 。结果 表明 , 此算法的订单分批结果优于传统的先到先 服务分批结果 , 为实现拣货作业中的订单优化分 批提供了新方法 。当然 , 影响订单分批结果的因 素很多 , 如产品在仓库中的分布情况 、路径策略 的运用等 。因此也可以在此基础上 , 综合考虑多 种因素 , 选择相应的订单合成标准 , 对订单分批 算法做相应的改进 。 参 　考 　文 　献 1　Noud Gademann, Steef Van De Velde O rder batching to m inim ize total travel time in a parallel - aisle ware house 2　缪兴锋 IIE Transactions, 2005 (37) : 63—75 秦明森物流运筹学方法 广州 : 华南理工大学 出版社 , 2007 3　Charles G Petersen II An evaluation of order p icking routing International Journal of Operations & Production policies M anagement, 1997, 17 (11) : 1098—1111 略及优化策略等 [ 3 ] 。本文采用最简单的穿越策略。 穿越策略就是一个拣货员从仓库的一端进入拣货通 道 , 而从该通道的另一端退出进入下一个包含拣取 位置的拣货通道。拣货员从出入口出发 , 在返回出 入口之前按这种方法遍历所有包含拣取位置的通道。 节约启发式算法对订单进行分批过程如下 : (1) 将所有的订单两两组对 , 如果 qij ≤C ( i j≠ i) , 则计算其行走 j = 1, …, 7; = 1, …, 7; 距离节约量 S ij = S ji , 如表 1所示 。 表 1　订单组合节约值表 订单 1 2 3 4 5 6 7 1 — × 78 64 68 × - 2 2 3 4 5 6 7 — — × 58 76 × 96 × 10 — 54 × 78 - 4 10 — 68 10 — - 10 — 注 : ×表示不符合组合条件 (2) 选择节约值最大的 3、5组合 , 形成初始 批量 。令 O s = { O3 , O5 } , 则 qs = q3 + q5 = 7 < C。 (3) 考虑与订单 3、5有关的节约值。按从大到 小非增序排列 {S31 , S34 , S51 , S56 , S54 , S57 , S37 }。 (4) 选择节约值最大的 S31计算 qs + q1 = 7 + 4 > C, 不满足组合条件 , 放弃 。 (5) 从余下的排序中选择节约值最大的 S34 , 计算 qs + q4 = 7 + 2 > C, 不满足组合条件 , 放弃 。 ( 6) 重复步骤 ( 5) , S57符合组合条件 , 将订 单 7加入到 s中 , 即 O s1 = { O3 , O5 , O7 }。由于 qs = 8, 拣货车容量已满 。后面的组合不必再检查 , 当前批 s即为第 1个优化批量 。 (7) 将订单 3、5、7从待分配订单中移走 , 转 至步骤 (1) , 得到第 2个优化分批 Os2 = {O4 , O6 }。 (8) 再将订单 4、6从待分配订单中移走 , 转 至步骤 (1) 。此时只剩下订单 1和 2, 而 1和 2又 不满足组合条件 , 所以订单 1和订单 2分别自成一 批 。至此分批完毕 , 结果为 (3, 5, 7) , ( 4, 6) , (1) , 3 2　比较分析 (2) 。 在拣货作业中 , 最简单的对订单进行分批的 经验方法就是遵循先到先服务原则 , 很显然 , 在 受到拣货车容量约束的条件下 , 算例按先到先服 作 　　者 : 谭俊华 地 　　址 : 湖北荆州长江大学 (东校区 ) 管理学院 邮 　　编 : 434023 —02— 《起重运输机械 》　2008 (3) © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net