英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
摘要：在Kiva系统的一个仓库中协调成百上千的机器人的任务呈现了许多具有挑战性的多媒介资源分配问题。资源包括库存、开放订单、小型货架单元和机器人本身。资源的类型可以根据它们是否可消费，是否可再循环或者是否可调度来分类。此外，全局优化问题可以被分解成更易于管理的子问题，其中一些问题映射到众所周知的计算问题的（困难）版本，也是动态和时间问题的联结。
介绍：Kiva系统的仓库自动化创新方法是使用数百个定制的移动机器人，搬运小型货架单元并向操作人员提供货物。操作人员站在沿着存储区域的周边的工作站，该存储区域填充有数千个存储架。机器人从存储区域取出特定的存货货架，并将它们送到指定站点，站点的操作人员通过识别货架单元上的适当货物的软件和激光指示器的引导，挑选货物并将其放入到要出库的运输纸箱中。Kiva系统有许多优点（Wurman，D#39;Andrea和Mountz 2008），其中最重要的是，kiva系统通过消除传统仓库所需的行走，使操作员的生产效率提高了2到3倍。
图1是Kiva机器人和货架。从机械角度来看，机器人相对简单。 它们具有一对侧面安装的驱动轮和能够将存货货架提升到离地大约两英寸距离的提升机构。机器人是双向的，并且具有安装在前面和后面用于障碍物检测的传感器。机器人的导航系统是航位推算法和用于寻找在系统安装期间放置在地板上的基准标记的相机的组合。虽然力学是直接的，但允许机器人以工业级别的可靠性进行操作的车载控制系统是相当复杂的。
图1 kiva机器人搬运的存货货架
有趣的是，机器人之于仓库，正如出租车之于城市。仓库的复杂性在服务器上运行的仓库控制软件中得到了真正的体现。
从计算机科学的角度来看，Kiva系统的移动履行系统代表了一个示例性多媒介应用程序。每个机器人（在Kiva术语中称为移动单元）和每个工作站都是一个独立的媒介，具有一定程度的自主权。还有几个媒介的作用是做出对整个系统总体生产行为至关重要的分配决定。这些媒介分布在多个刀片服务器和每个工作站的台式计算机上。
本文的目的不是解释Kiva系统配置的算法和优化方法。与此相反，本文用了足够的细节来描述问题的领域，鼓励其他研究者探究它。我们认为，这个问题领域包含了许多有趣的计算挑战，可以用各种专业的知识来处理。
Kiva系统中的资源：随着Kiva系统的生产线的增长，资源分配问题的复杂性也增加了。为了理解系统做出的分配决定的范围，有必要了解系统内的主要流程。同时，我们简化了以下的描述来展示一个典型系统的实现。实际系统支持这些主题的重大变化，而且包括这里未处理的子系统，例如库存盘点，机器人充电和垃圾移除。
图2显示了Kiva系统中的两个主要流程。左图显示了一个配置了Kiva系统的单品拣选配置的仓库。在这个配置中，Kiva系统负责运输库存货物，而不是运输箱子。库存周期（红色和紫色箭头）捕捉在仓库中装载产品的货架单元的生命周期。这些搁架单元，称为货架，在逻辑上是存储位置的集合，称为箱。这些箱在人工补货站点由操作人员填充，并且在拣选站点处由操作人员再次逐渐清空。 在这两个活动之间，它们可以存储在存储区域中，如在大型停车场中的汽车。 在货物拣选配置中，拣选人员填充装运纸箱并将它们放到出库输送机上来将成品箱运输到装运区域（蓝色箭头）。
图2 单品拣选（左）和订单拣选（右）
然而，Kiva系统也可以被设置成传送订单，如图2的右图所示。在这种情况下，我们设计了第二组货架，用于存放出库的装运纸箱。这些货架在订单周期中行进（如蓝色和绿色箭头所示）。空订单箱首先进入箱子感应台，由操作员构建空箱并将它们分级放置到订单货架。订单货架一次可以携带多达十几个订单，但是货架的实际容量在实际应用之间变化很大。然后订单货架移动到操作人员周围的拣选站点，在那里他们在操作者旁边停放。机器人小车将存货货架送到操作员的面前，操作员根据站点指令将所需产品从存货货架移动到订单货架上的相应纸箱。一旦订单货架上的所有订单已完成拣选，机器人小车抬起订单货架并将其送回存储区。在适当的时间，订单货架被送到出库站点，在那里拣选完成的箱被从货架上取下，放在货车上。注意，在循环周期中的任何两个站点之间，系统需要提供货架存储区域，直到到达前往下一站点的适当时间。
当配置存货货架时，我们将系统称为订单拣选的实现。注意，这样的系统仍然包括存货货架和库存周期。订单拣选系统使客户能够随机访问已完成订单，并且在到达货车交货期限之前具有更大的灵活性。一般来说，相对于单品拣选系统和用于成品包装的基于传送带的缓冲和分拣的解决方案，订单拣选系统更具经济性。
将系统视为具有不同属性的多种类型的稀缺资源的集合是具有启发性的想法：
库存：自然地，库存的物理单位是消耗资源。库存的数量遵循从补货到可置于货架的循环，分配给订单，被拣选到订单。典型的客户可以具有10,000至100,000个或更多个独特的产品类型。每个都可用尺寸、包装数量和速度（订购的频率）等参数来描述。在实践中，库存速度遵循80/20规则是非常常见的：20％的产品占了80％的订单量。
存货货架：货架是共享、按计划行动的资源。一个机器人一次只能运送一个货架，并且货架一次只能访问一个工作站，但货架可以安排按顺序访问多个工作站。货架可以是正方形或矩形，并且可以从货架的四个面中的一个或多个访问每个搁架上的箱子。典型的仓库可以拥有5,000个或更多个存储货架。
存储箱：货架上的箱是可回收的资源。箱子在补货站点被填充，在拣选站点被清减。一旦箱子被完全清空，就可再次用于装新货物。与传统的仓库系统不同，Kiva系统中的存储位置不必放置之前存储的相同货物。因为货架可以由1个到100个箱组成，所以Kiva系统中的存储箱的数量可以轻易地超过100,000个可寻址位置。
订单的货架空间：在单品拣选配置中，操作人员将箱子放在货架上，并用货架中的货物填充箱子。货架在尺寸上受到限制，并且每次只能容纳一定数量的箱。该货架空间是可再循环的，这意味着一旦工人将完成的订单送到输送机上，该货架空间便可用于另一订单。典型的单品拣选工作站一次可以分级4到20个订单。
订单：订单是另一种消耗资源。这样考虑它们可能是反直觉的，因为它们代表系统的输出。然而，核心分配问题就是如何从一组可用订单中选择一个订单以分配给站点。订单一旦分配，就会从可用订单池中移除。订单自身由订单项列表定义。每行代表对特定产品类型的特定数量单位的需求。订单中的行的数量在不同客户之间变化很大，但通常是指数分布模型。使用Kiva系统进行零售再存货的客户通常知道前一天的订单，因此在一天开始时可分配订单的可用池代表一整天的工作。另一方面，使用Kiva系统进行电子商务活动的客户每天都会收到订单——通常在下午达到高峰，并且必须在当天填写订单。在这种情况下，系统存在较小滚动窗口显示可用订单。
订单货架：当系统处于订单拣选配置中时，工作人员在导入工作台将空箱导入订单货架。然后这些货架前往拣选站点和出库站点。订单货架可以承载2~8个订单，典型的仓库将有250个这样的货架。重要的是，虽然订单货架本身是可调度资源，但它们也表示下游分配步骤的订单的集合。系统的性能很大程度上取决于哪些订单被一起放置在订单货架上。
停放位置：存货货架和较小的订单货架的大部分时间都处于停放，等待的状态，直到它们被需要，因此停放位置的有效分配也很关键。停放位置填满任何Kiva系统仓库的内部块，像一个规划良好的城市。一个仓库会有像货架一样多的停放位置，那么在所有的工人都回家的晚上（假设他们全部回家），每个货架都有一个地方停放。我们认为停放位置是可回收资源，因为一旦一个货架离开它停放的位置，这个位置就可用于停放任何其他货架。以相同的方式，箱也不需要在它们被清空之后用相同的货物填满，停放位置不为任何特定的货架保留。
机器人小车：机器人本身是可共享的、可调度的资源。一个机器人小车一次只能搬运一个货架，而且它们一次只能访问一个站点。机器人小车具有双重目的，可以同时搬运存货货架和订单货架。到目前为止，Kiva系统已经设置了几个解决方案，每个有500多个机器人，一个设置了有1000个机器人。
站点：一个kiva系统的周边常常排列着拣选站点和补货站点。 在订单拣选配置中，感应装置和出库站点混合在一起。站点是规划好的资源，但它们与其他站点的不同之处在于，它们能够物理地缓冲队列中的到达货架，以完成快速采集。操作人员根据货物的类型和所涉及的订单任务与货架相配合来完成任务，其时间短至四秒，长至两分钟。另外，保持所有操作人员繁忙且工作量平衡是非常重要的。大型Kiva系统可以有150个或更多的站点。
由于这些半自主媒介及其资源的紧密相互作用，我们将系统行为称为协调自主：媒介在其各自的任务上工作时主要自主地操作，但是因为它们对资源进行激烈竞争，系统在分配资源数量时提供了大量的的协调支持。
有趣的分配问题：在高级别中，优化系统需要双重目标功能：在使操作人员尽可能忙的同时，最小化所需设备，特别是货架和机器人小车。这些目标相当于在所有工作必须每天完成的约束下最小化运营费用（人）和资本费用（设备）。 这两个目标并不总是兼容的；例如，每个存货货架配有一个机器人的方案最可能保持工人始终繁忙，但这种方案具有无法接受的高成本。在实践中，我们假设保持所有的工人忙碌是一个约束，那么目标函数是最小化设备。
图3 机器人小车输送货物的步骤
必须减少设备成本时，我们运用的主要机制是用更少的机器人小车做更多的工作。机器人小车的任务涉及图3所示的五个步骤：
- 机器人小车从当前位置前往货架所在位置。
- 将货架从它现在的位置运送到站点的队伍中。
- 在站点排队等待，直至货架任务完成回到小车处。
- 操作人员从货架上拣选货物。
- 将货架送回存储区域。
改进步骤1、2、3或5中的任何一个或者全部步骤有助于减少维持操作人员工作率所需的设备。但是，一旦选择了机器人和货架，对于减少任务路径的长度就没多少可以做的。所有减少行驶距离的决定都是在选择机器人小车和货架之前做出的。
也许减少所需机器人的最大方法是提高从交付货物的每个货架上拣取说完货物数量。例如，如果我们将在一次传送中拣取货物的平均数量从1.0更改为2.0，那么只需要大约一半数量的机器人。
我们将每个货架拣取的行的数量这个一般概念称为堆积。它有几种类型，其中一些相比起其它的更容易改进。当两个或多个订单同时需要来自相同箱子、相同的工作站台的货物时，发生堆积。当货架的一面被机器人小车占据期间，货架同一面的多个箱子被同时访问时，便发生了面堆积。被拣选的货物可能是出自单个订单或者站点处的多个订单。与面堆积相比，站点堆积捕获所有在该次到达期间在该站点从货架上拣出的货物，即使拣选操作为了从另一面拣取货物要求货架旋转。任务堆积捕获在机器人小车完全与货架接合期间拣取的货物的数量。三个站点，每个站点都要拣取货物，机器人小车将货架送往这三个站点的行程将有1.0站点堆积，但整个行程中有3.0任务堆积。
从算法的角度看，使得Kiva系统如此吸引人的原因之一是虽然整体计算问题是一个难以处理的、动态的、具有不完整信息的随机的优化，但它可以分解成容易解决的子问题。解决全局优化问题的方法是否比分解问题的方法更好这件事仍待观察。接下来，我们强调了一些子问题，并讨论它们对上述的机器人任务的步骤的影响。
存货货架选择问题：也许最直接的优化机会发生在我们必须选择一个货架来将货物交付给站点时。通常，站点处有在多个工作线进行拣选的多个订单任务。因此，当选择下一个待交付的货架时，我们有从几个到可能数百个的拥有将在站点处满足一些工作线的货物的货架。货架已离站点的距离和它们能满足的工作线的数量来分类。在特定时刻，这个问题对应于多组多覆盖问题（Dobson 1982; Rajagopalan和Vazirani 1993）。然而实际上，该问题很少被讨论研究；一旦订单（或订单货架）在站点完成，另一订单（或订单货架）将占据其位置，从而带来更多工作线。与先前选择的存货货架的到达时间有关的新订单到达时间也将影响系统的效率。
最优货架选择的制定还应考虑选择已经安排去访问其他站点的货架的优点和缺点。当一个货架从一个站点跳到另一个站点——在kiva术语中成为站点跳跃——我们需要分步弥补在多个站点访问之中从步骤1和5的耗费。站点跳跃通常意味着货架到达站点的时间会更加地延长，这与它的优点相抵消。此外，确定访问站点的最佳顺序是旅行商问题的一个实例（下面讨论）。
货架存储位置分配：当一个货架的任务完成，不管它是一个存货货架或一个订单货架，我们需要决定在哪里存储它。在将货架存储在附近和减少步骤5之间有一个明显的矛盾，并且，将货架存储在靠近它下一次可能被使用的地方减少未来步骤2。同时，放置一个慢速的货架在拣选站点附近存在机会成本。一个慢速货架可能每2小时移动一次，然而一个快速货架肯呢个每15分钟移动一次。我们更倾向于使用最便利的存储位置存放更快速的货架，因为在两小时的期间内，我们可以为快速货架的八次移动节省时间，但我们将慢速货架存放在好的存储位置时，它只能移动一次。
订单分配问题：在上面的讨论中，我们假定在选择货架时在站点处存在订单。然而，哪个订单分配给哪个站点是关于系统中最关键的问题之一。首先，我们考虑单品拣选配置中的问题，其中出库的货箱在拣选站点构建并放置在要填充的桌子或架子上。在该配置中，操作员通常工作在4至12个订单之间。当订单完成，并且操作人员将其送到出库输送机上时，货架位置才可用于新订单。通常，有数百个新订单等待处理。当选择分配给站点的新订单时，我们可以检查完成它
全文共8556字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144854]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
