外文翻译--从距离最小化和堆栈重排角度解决路线集装箱堆积问题方法【中英文文献译文】
外文翻译-从距离最小化和堆栈重排角度解决路线集装箱堆积问题方法【中英文文献译文】,中英文文献译文,外文,翻译,距离,最小化,以及,堆栈,重排,角度,解决,路线,线路,集装箱,堆积,问题,方法,法子,中英文,文献,译文
毕业设计外文资料翻译学 院: 机械工程学院 专 业: 机械制造设计及其自动化 姓 名: 王延光 学 号: 110501222 外(用外文写)文出处:Computers & Operations Research 52 (2014) 6883 附 件: 1.外文资料翻译译文;2.外文原文。 指导教师评语:基本掌握了检索并阅读外文文献的方法,所选外文内容与毕业设计题目基本相关,格式基本符合要求。 签名: 秦志英 2015 年 4 月 15日附件1:外文资料翻译译文从距离最小化和堆栈重排角度解决路线集装箱堆积问题方法关键词:组合优化 天车调度 堆垛机问题 集装箱堆放 混合整数规划摘要我们考虑一个优化问题的排序操作起重机来用于内部运动在海上集装箱港口。关于塔式起重机(SCP)的问题一些文章也研究了这个问题的一些特性。然而,大多数文献的范围(包括SCP)局限于最小化的路线或距离起重机和由此产生的刺激成本。在实践中,通常堆放的货物集装箱或堆积在多个单独的列或者栈在港口。所以,起重机等需要经常重新安排或调整集装箱堆栈,以选择任何必需的容器。如果大量重新堆垛,起重机花费相当大的精力集装箱堆栈重排操作。最小化的问题对起重机总的精力/时间的努力,必须占两个堆栈重组成本和刺激(路线距离)的成本。合并问题不同于标准路线距离最小化的情况下堆栈重排活动被认为是。我们正式定义合并问题,识别它特征,因此设计出合适的模型。我们制定一些替代MIP 方法来解决这个问题。我们MIP配方的性能进行比较和分析他们是否适合各种可能的情况。1介绍 起重机的分配和调度容器移动表示“状态”操作已经被充分研究过的国际米兰- 模态货运集装箱运输在货物集装箱码头,经常被应用于优化模型提高整体性能和效率方面转在时间和吞吐量。具体来说,塔式起重机问题(SCP)地址的问题/成本最小化时间发生时,车辆的单位负荷能力指定部署到皮卡和交付之间的容器位置 主要货物终端处理大量的集装箱空间限制经常强迫,堆放或容器堆在栈上列或堆。叠加发生在存储码(存储容器,通常长时间)或在码头泊位区(起重机负载船舶或卸载容器)。另外,堆积最终导致无成本,只要集装箱堆栈随后重新获取堆在另一个容器。然而,起重机调度和SCP的讨论现有的文献忽视叠加歌剧的影响操作效率和时间表 堆栈重排的努力水平是不同的,活动执行的起重机而身体运动,沿通路终端移动容器。总成本发生在集装箱装卸操作的总和(垂直)堆栈重排成本和(水平)移动成本。我们处理的顺序顺序容器,所以以减少关注整体的处理成本统一-成本最小化。底层问题也可以扩展到更一般的情况下(如印度河- 审判仓库)和栈对象的其他例子需要有效地重新安排叉车。我们不解决一边像时间窗限制约束。 内部运动的集装箱货物终端涉及到各种各样的需要执行的操作。我们使用图1说明这个问题。这个图显示集装箱堆放位置(16)货物码头。图显示了最初的堆栈安排和所需的最终安排在这六个地点的容器。一个起重机分配来执行所有的水平和垂直重排任务是必需的。考虑集装箱1,它被放置在一堆容器2、17和19在位置6。1需要搬到一个新的容器在终端位置5。起重机部署活动必须做到以下几点:图1:草图显示需要重排的典型SpRP数据实例的容器。 1.存取机必须从其当前位置移动到皮卡6集装箱1点。我们称之为空载水平运动的努力(NLHM)。NLHM涉及顺序相依的成本水平运动,因为它依赖于直接的优先级顺序容器由起重机。 2.起重机现在必须重新排列堆栈位置1移除容器19;17;2、堆积和堆积以上所需的容器1。我们称之为垂直这一努力堆栈重排的努力(VSR)。VSR还依赖于顺序容器由起重机。但这是完全与NLHM不同,在这个意义上,VSR任何容器j取决于处理的所有容器的累积效应在这个特定的容器。 3.起重机携带容器1到目的地位置5。我们叫这是满载水平运动(FLHM)。FLHM 涉及到一个水平运动的固定成本。 4.起重机必须放弃容器1在堆栈的顶部目标位置5。我们忽视的成本和努力做的事情这个活动。最后栈1在5的位置不是一个问题当前讨论的目的。 容器搬迁的总成本的总和,积累后果依赖成本(NLHM),累计- 序列相关的成本(VSR)和所有给定的固定成本容器(FLHM)。我们表示最小化的问题总和所有容器的容器堆积优先路由问题(SpRP)。货物终端每日处理集装箱100件(见31日33)和采用集装箱堆栈大约8 - 10米高(见32),可以实现使用节省大量成本,起重机操作时间表,占VSR结合NLHM。SpRP是我们研究的动机,其中,我们研究扩展SCP,直到现在,也包括不小VSR成本。 NLHM为模板通过转换问题(见30日39) ,到一个非对称旅行商问题如下:我们模拟容器访问节点图,任何一对节点之间花费一段不对称弧Eij,这段弧在容器对应位置之间。水平运动是通过直接模仿完整的图,n+1个节点表示,位置在N里,0和n个容器。边缘E 包括所有定向边缘需要连接任何一对i;j的节点从。任何有效边界ij消耗就是 E ij的距离。在哈密顿循环N解释一个可行的操作顺序来处理所有容器。NLHM成本降到最低,我们寻找哈密顿路径最小化成本的所有边缘遍历。对于一个给定的SpRP实例X,我们定义了图G 作为其水平图。在SCP文学里NLHM的建模是一个标准(见30日39)。 从图1讨论VSR成本,考虑集装箱7。它需要从其皮卡位置3交货地点5。我们忽视重量20集装箱我们的讨论。但是容器8在堆叠3里高于容器7 。同时,集装箱9应该是进入位置3。考虑到起重机已经处理容器9一些时间处理7,但是容器8尚未处理。现在,如果容器获取7, 存在容器8和9以上集装箱7。这两个集装箱需要暂时从堆栈中删除3之前获取集装箱7。集装箱7的堆栈后,这些容器必须放置在3的位置原始订单。因此,额外的堆叠两个容器的成本发生在抓取集装箱7从3。 相反,考虑到起重机处理容器8, 然后7最后9。在这种情况下,当7是被拿来8和9上面出现7。所以VSR成本7是零(忽视集装箱的重量20)。因此,序列容器为8和9决定了VSR处理成本集装箱7。应用这个到其他位置时,放置或删除一些容器j影响VSR其他容器的成本以后的时间。1.1问题定义 考虑n无关的相同的容器(不感动的优先购买权)在一个已知的时间范围。这些n容器堆积在列或堆栈。可能会有更多的容器栈中(除了n容器需要移动)。这些额外的容器的重量栈处理。任何容器,是包含与n个被处理的容器之一,最初的皮卡位置i和最终的目的地D位置i是已知的。i的物理距离位置,i是用C和D。一对容器i;j,距离从交货地点DiPj来标示Eij皮卡位置。在集装箱堆栈i之上最初数量的容器i被指示为Hi。然而,i上面的实际数量的容器变化时更多的容器可能从i上面掉落。 一个起重机可将n容器。起重机停在一个特殊的位置0(仓库)的开始吗时间范围,必须回到这个仓库位置0的结束的时间范围。这个起重机是唯一的资源的能力SpRP所需执行的所有操作。任何行动参与NLHM FLHM或VSR缴费,转化为一个成比例的成本。我们定义这些成本如下:1. 成本发生的起重机的水平距离旅行单位是h(无论NLHM或FLHM)。如果起重机i在位置D放置容器。然后移动到皮卡Pj容器的位置。为此,它距离Eij NLHM 努力和成本导致h Eij。然后,起重机将携带容器j从位置Pj到Dj,穿越的距离 Cj。这导致耗费h Eij。2. 起重机被移除并且从堆栈被一个容器(而重新安排集装箱)替换的总花费就是v。考虑到容器j包含hj 在堆栈上面。如果就被获取,VSR的花费h Eij必须会发生。这VSR成本是独立于实际位置Pj和任何容器下面的堆栈。因子h,v是固定的端口/终端和假设,并且作为SpRP初始参数。然后,涉及到的任何SpRP数据实例有以下参数:1. P(n1)向量的位置确定,作为初始来源或皮卡位置n容器。2. D(n1)向量的位置确定,作为交付目的地(或下降位置)n容器。3. H(n1)向量的初始堆栈高度的容器堆积,在皮卡堆栈点P我上面容器(定义i在原来的容器)容器。实际的数量的容器上面堆放我以后可能会改变,只要其他容器被移动。4. C(n1)矢量传感器之间的水平距离,点Pi和交付点Di任何容器i。5. E(n1)向量之间的水平距离Di的的容器和小点Pj 容器, i为所有对容器;j为原始容器。E 不需要对称的。我们定义术语E0j的向量水平之间的距离,位置0和jth容器的传感器位置Pj 。同样的,我们定义术语Ei0作为向量之间的水平距离,交货地点D i容器和位置0。最后,对于为了方便讨论,我们定义设置N=(1,2 ,)作为无序集所有n容器处理。1.2假设虽然研究SpRP,我们做以下简化假设:1. 时间方面:我们忽视任何时间窗限制或集装箱装卸操作的最后期限。我们将使用一个,在几个MIP配方方面的时间。我们假设时间花费在执行一个特定活动是数值等于成本或投资于这样做活动。例如,如果VSR处理致力于容器i是vhi ,那么我们断言,vhi 单位需要的时间,起重机从堆栈获取容器i。所以,最小化总时间为任何SpRP需要完成的所有活动,实例导致总成本的最小化。2. 暂存区:存在一些小临时暂存区,附近的小容器可能被放置的地方,在堆栈重排。考虑到起重机的任务是与抓取容器i从一些位置。但是容器j 堆叠超过i。所以,起重机将首先取出并将j 放入暂存区域。然后旁边的起重机将i挑选。此后,它将取代堆栈j的位置。最后,它会选i,开始朝着D。暂存区仅在堆栈重组活动中,必须使用并尽快空出。3. 筹备重排容器:没有起重机可以做任何预期或制备容器或重排堆栈。另外,对于一个给定的操作容器,不能预处理买下资方或中断。例如,参照图1, 假设首先一个起重机将处理容器9, 处理容器7和8 紧随其后。然后我们假设起重机将首先交付容器9之上的堆栈位置3容器7 和8。这对容器9完成所需的操作。此后,吊车将开始操作容器7。抓取集装箱7,吊车将容器9 20 和8暂时放在暂存区域,然后获取集装箱7,然后取代容器9、20和3和8 ,最后离开集装箱7。具体来说,起重机不中断容器9促进以后的交付来自检索3的集装箱7。4. 最后在交货地点产生的烟囱高度:假设容器i被交付给它的下降位置D。期间这个交付操作后,烟囱高度的容器在Di,高于或低于i的成本没有影响。最后i在D栈序列SpRP并不重要。终端运营商和工人可能需要知道这一点,未来的操作规范,但它不会影响成本/时间/精力SpRP。图7:内的变异比较混合配方所需的时间(以秒为单位)达到最优解图8:确定整体最佳MIP瓦里安 不可行性或subtour这样的路线,预期在只有少数情况下才出现。执行两种途径诱导之间的互连由两组变量。所以路线可行性限制,最好的执行通过补救或治疗干预只有变量诱导出一个毫无意义的路线(违反传递性)。这个动作削减使治疗干预的基本配方紧凑,容易解决。任何额外的约束或变量(如Wijk或Yk)是多余的、有害的。因此,定理1和2的应用导致了一个新交叉之间的约束路由和叠加还导致了一个MIP制定执行出最好的选项的探索。4结论和未来工作 在本文中,我们介绍了SpRP新的贡献,文献(我们所知,SpRP之前没有的文献研究)。我们提出了几个传统MIP模型,作为解决SpRP配方的一部分,计算分析时,我们还显示一些能力具体配方不同配置的能力。一个重要贡献是逻辑基础(定理1和2)从不同的MIP方法结合的关键概念。这使用约束的相互适应发展强大MIP配方。我们演示了这些方法的优越性,这些在许多可能的配方/宽的方法能解决数据实例具有不同配置的问题。 尽管这些方法是引人注目的和有效的,在这工作也有一些数学基础,但加强我们开发的配方的方法仍难以解决,尺寸问题就是实例。此外,一些额外的实际问题和约束,如在海上遇到港口还需要解决。集装箱港口可能有特定的时间限制,某些容器也必须达到一个离开船,火车或卡车。我们还需要考虑动态/在线实例。在未来的研究,我们相信,最好的方法来解决大SpRP数据(额外的约束)是通过开发实例,高效的启发式方法。后记 作者期望得到有见地的评论,因为曾经匿名评论者的评论已经充分帮助改善了此文。参考文献(略)附件2:外文原文(复印件) 8
收藏