英语原文共 18 页
国际生产杂志研究
出版细节，包括作者和订阅信息：http://www.tandfonline.com/loi/tprs
基于聚类的自动化仓库拣货顺序算法
Byung-In Kim a , Sunderesh S Heragu b, Robert J Graves b amp; Art St Onge c
孟菲斯工业与系统工程大学，美国孟菲斯TN 38152
决策科学与工程系统系，特洛伊伦斯勒理工学院，12180美国
圣昂杰公司，美国宾夕法尼亚州约克17402
在线发布：2010年8月6日
基于聚类的自动化仓库拣货顺序算法
BYUNG-IN KIMy, SUNDERESH S. HERAGUz*,
ROBERT J. GRAVESz and ART ST. ONGE}
本文讨论了一个自动化仓库中的拣货顺序问题，该仓库中拣货机的行程部分是固定的，布局长度明显长于宽度，并且拣货机在给定时间只能拿取一个项目。问题是寻找一个给定垂直路径的最优序列，因此它是一类特殊的旅行商问题。针对这一问题，提出了一种简单的基于排序的启发式算法和一种高效的基于聚类的算法。为了更有效地利用龙门机器人，考虑了一种灵活的跌落缓冲分配，并针对新的工作条件对所提出的算法进行了改进，实验结果表明了该算法的有效性。
- 介绍
仓储功能包括接收、存储和订单完成。将产品分配到存储位置、订单分批或排序、将拣配任务分配给订单拣配者以及拣配顺序（路线）是仓库问题中的重要计划和操作决策。（Rouwenhorst等人. 2000, Van den Berg 1999）。仓库功能是批发分销商和客户驱动公司的核心业务。(Daniels 等人. 1998)。调查显示，拣货的消耗量超过仓库中50%的活动（Tompkins等人1996）。因此，订单拣配是仓库操作中最大的一项支出也就不足为奇了。（Heragu 1997）
本文讨论了基于实际工业问题的自动化仓库中的拣货顺序问题。仓库由16个拣货区组成。仓库可储存40多万件产品，一般每天可提取10万件产品。拣货区按顺序排列，它们之间有一个共同的传送带，因此每个订单托盘依次经过拣货区1至拣货区16。一个拣货区有一个门式拣货机器人，包含85个跌落缓冲器，其中放置由门式拣货机器人拣来的产品并等待其订单托盘。拾取区域的长度显明比宽度长，龙门机器人在给定的时间内只能拿取一件物品。由于龙门机器人在拾取产品后必须将产品放置在最近的跌落缓冲器上，因此可以假定拾取位置和跌落缓冲器之间的路径是固定的。因此，拣货顺序问题就是在给定的垂直路径下找到一个最优序列，使之成为一种特殊的旅行商问题（TSP）。目的是尽量缩短龙门机器人的行走时间。针对这一问题，提出了一种简单的基于排序的启发式算法和一种高效的基于聚类的算法，实验结果表明，该方法是有效的。为了更有效地使用龙门机器人，考虑了一种灵活的缓冲分配方法，并针对新的运行条件对所提出的算法进行了改进。
本文的组织结构如下。在简要回顾第2节中的文献后，第3节中介绍了实际的工业仓储问题（我们提出的订单选择排序算法适用于此）。一种简单的基于排序的启发式算法，一种高效的基于聚类的算法，第4节介绍了它们对不同操作条件的修改。实验结果和结论见第5节和第6节。
- 文献综述
本节简要介绍了仓库规划和控制。Ratliff和Rosenthal（1983）开发了一种基于图的算法，用于优化解决矩形仓库中的订单挑选问题，矩形仓库中存储区域之间存在平行通道，并且采摘机只能在通道的末端改变存储区域。他们假定选择器一次只为一个订单选择项目，并且一个订单中的项目数在选择器的能力范围内。Roodbergen和De Koster（2001）扩展了Ratliff和Rosenthal（1983）的工作。他们考虑平行通道仓库中的订单拣货问题，在这种情况下，订单拣货员可以在过道的两端和中间跨越过道。他们开发了一种动态规划算法来解决这个问题。Van den Berg和Gademann（1999）开发了一个运输问题（TP）模型，该模型适用于具有专用存储和单台装载机的自动化存储和检索系统（AS/RS）中的块排序。他们证明了tp问题的最优解是使机器运行时间最小化的最优序列。Han等，（1987）考虑一个AS/RS，其中
设备执行两个命令周期。他们提供了提高设备吞吐量和双命令周期时间下限的方法。Hwang等人。（1988）目前基于聚类的启发式算法，用于单通道AS/RS中的订单分批拣货。为了使订单拣货装置的总行程最小，将多个订单组合成一批并在一次行程中拣货。根据属性向量定义相似系数，Hwang和Lee（1988）提出了一种启发式方法，该方法对给定的一组订单进行批处理，从而使存储/检索设备的总行程时间最小化。Liu（1999）应用聚类技术解决了具有重力流货架的配送中心的库存位置和订单选择问题。产品项和客户基于它们的相似性加以群集，使用提议的度量标准来度量。他将聚类问题定义为一个整数规划模型，并提出了一种原始对偶算法来求解。Daniels等人（1998）考虑仓库问题，其中货物存储在多个位置，并且可以动态选择零件的拣配位置，他们提出了一个同时确定位置分配和拣配顺序的模型。他们指出，所建立的模型是NP完全的，并提出了几种启发式求解方法和实验结果。订单拣选问题以前被建模为切比雪夫旅行销售员问题（TTSP），并开发了各种TTSP算法。其中包括Bozer等人（1990），Heragu等人（1994年）和Goetschalckx（1983年），Ashyeri 和 Gelders (1985) 将仓库设计方法分为分析方法、模拟方法和启发式方法之后，回顾现有的仓库设计方法文献。van den berg（1999）和Rouwenhorst等人（2000）仓库规划与控制调查文献。规划包括存储位置分配问题，仓储系统的控制包括路由、排序、调度、停留点选择和订单批处理。Goetschalckx和Wei（1994）提出了1985年至1992年订单挑选系统的参考书目。
- 拣货顺序问题
在本节中，我们将详细介绍我们所提出的订单选择排序算法应用于的实际工业仓储问题。仓库接收来自美国和海外多家工厂的化妆品，它的功能主要是双重的。第一种是从工厂接收数千种不同数量的产品，并将其储存在仓库中。第二种是接收客户订单，直接从仓库中储存的产品中填写。这两种活动都是每天进行的。本文的重点是订单排序问题，介绍了基于智能代理的拣配算法（资源分配），补货操作介绍于其他出版物（见Kim等人2002、2003a、2003b）。仓库是全自动的，有16个拣货区。拣货区按顺序排列，它们之间有一个共同的传送带，因此每个订单托盘依次经过拣货区1至拣货区16。每个拾取区域都有一个机架拾取机器人和19个拾取手提袋（见图1）。每个皮卡手提袋有48个隔间，每个隔间在给定时间内只存储一种产品类型，并且具有容量30种产品。虽然一个典型的产品只包含在一个拣货区中，但一些流行的产品可能会分布在多个拣货区中，并分布在拣货区中。拣货区还包含85个跌落缓冲器，其中放置由龙门机器人拣起的产品并等待其订单托盘，每个放置缓冲区在给定时间只能容纳一个产品。当每个订单托盘在系统中运行时，传送机速度以恒定的间隔进行索引，允许跌落缓冲器将其内容物存放在任何指定的订单托盘上。龙门机器人不仅必须在其区域内选择当前订单的项目，也必须在订单托盘进入其区域之前将它们放置在缓冲区中。如果指定接收项目的托盘通过缓冲区后，该项目被存放在放置缓冲区中，则会发生拾取错误。每个订单托盘将包含一个客户的订单，并且可以容纳多个行项目。每个订单的行项目是一个产品的单个单位。
为了有效地使用龙门机器人，80个托盘逻辑上形成一个“火车”（图2）。80个托盘中的第一个托盘被称为“机车”，其余79个托盘构成机车牵引的列车。订单序列中的每个订单行项目都包含要挑选的产品以及产品所在的隔间的信息。当一列定购列车的机车到达一个指定的点（称为触发点）时，将扫描列车中的所有80个定购托盘，以查看必须从该区域提取哪些项目（如果有的话）。一个区域的触发点是一个下游点，距离该区域的起点有三个区域长度。图2中突出显示的小矩形与必须拾取的项相对应。然后，由龙门机器人为订单创建一个工作队列，并进行批量填充。机器人一次只能处理一个项目。因此，在机器人选择一个项目之后，它必须在选择另一个项目之前将该项目放置在放置缓冲区中。为工作队列找到一个最优或接近最优的拣货序列是订单拣货序列问题，而正是这个问题本文试图解决。最佳顺序是要求机架移动时间最少的顺序。
龙门机器人 拣取单元 区划
传送带 跌落缓冲器
图1.机架拾取区布局。
一般来说，拣货顺序问题可以被建模为旅行销售员问题（见Heragu，1997）。在这一工业应用中，龙门机器人在拾取产品后将其放置在最近的跌落缓冲器上，即垂直于其下方的跌落缓冲器上，使机器人排序问题成为一种特殊类型的旅行推销员问题（见图3）。
使用人工选择位置P0，它将是问题的虚拟起始和结束位置（参见图4），可以将问题建模为旅行推销员问题（TSP）。人工位置和其他位置之间的行驶时间设置为零。因为龙门机器人有两个独立的电机，允许在水平和垂直方向同时移动，从一个点移动到另一个点所需的时间取决于两个点之间水平和垂直移动时间的最大值。再一次，因为龙门机器人在挑选产品后必须将产品放在跌落缓冲器上，从拾取位置到另一个拾取位置的移动时间包括从拾取位置到放置缓冲区的移动时间加上从放置缓冲区到下一个拾取位置的移动时间。因此，可以按照一个数学模型（参见Heragu 1997）来表述订单选择序列问题。
放大视图 触发点
火车头 订单序列=80个订单托盘
图2.顺序列车和触发点。
位置 跌落缓冲器
图3.订单拣货顺序问题
虚拟起止位置
图4.人工货位的拣货顺序问题
该模型假定有n个拾取位置，人工拾取位置索引为0。决策变量wij取二进制值0或1，这取决于在订单拣配序列中，拣配位置j之后是否立即访问拣配位置i。目标函数最小化了龙门机器人完成订单的总行程时间，前两个约束确保只有一个到达和一个离开拾取位置，第三组约束在最优解中不包含任何子项，第四组方程与任意两个拾取位置之间的移动时间有关。
n n
Min sum; sum; dijwij
i=0 j=0，ine;j
n
sum; wij=1 对于每个j
i=0，ine;j
n
sum;wij=1 对于每个i
j=0，jne;i
ui-uj （n 1）wij≦n 1≦ine;j≦n
从位置i到最近跌落缓冲器的移动时间 从跌落缓冲器到位置j的移动时间,1≦ine;j≦n
dij=
0 0≦ine;j≦n,i或j=0
wij=0或1 对于每个i,j,ine;j
ui是任意实数 对于每个i
为了近实时地解决这一问题，本文在下一节中提出了一种简单的基于排序的启发式算法和一种高效的基于聚类的算法。
- 排序问题的算法
4.1基于X坐标的启发式
假设机架机器人必须将项目放置在离所选项目位置最近的放置缓冲区中，根据其X坐标（即简单的从左到右或从右到左排序启发法）对所选位置进行排序，在许多情况下给出了一个最佳的解决方案，因为拾取区域的长度明显长于宽度（见图5）。具体来说，当拾取位置足够稀疏，使得机架机器人在任意两个可能位置（一个是前一个位置的放置缓冲区，另一个是下一个位置）之间的水平移动时间始终长于垂直移动时间时，基于X坐标的排序方法生成一个最优解（图6）。由于龙门机器人有两个独立的电机，一个允许水平方向移动，另一个允许垂直方向移动，因此两个位置之间的移动时间取决于水平和垂直移动时间的较长时间。
B.-I.Kim等人
图5.基于X坐标的启发式。
最小水平移动时间
*pi:选择位置
*（hi，vi）：水平和垂直移动时间
将pi的缓冲区放到位置i 1
图6.当一个由X坐标为基础的排序保证的最佳解决方案。
资料编号：[4577]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
