对于集装箱离开时关于时间窗的集装箱翻箱问题
摘要
区块搬迁问题是一个典型组合优化问题。这些问题通常发生在日常使用区块堆叠系统的码头上。在区块堆叠的方法中,为了使用有限的存储区域的表面,区块被存储到其他物块的顶部。当在物块中有预决定的提货命令时,这种堆叠的方法无可避免的导致在目标物块上其他存储物块的重新移动调整,并且使这种无效的重新移动调整最小化是工业从业者主要关注的。集装箱码头是典型这种问题发生的场所,所以集装箱翻箱问题也涉及此类问题。在本研究中,我们考虑了集装箱离开码头的时间窗,时间窗通常被释放通过在进口集装箱码头的货车预约系统。我们假设了一个随机动态程序模型来计算所期望的一堆全部有离开时间窗的集装箱中需要翻箱的数量。这个模型在树形检索的基础上采用搜索基础的算法来解决,并且一种抽象启发式算法被期望来提升时间的表现。为了解决精确方法的计算的限制,我们发展了一种启发式算法叫做预期重组指数并且评估它的性能。
1.介绍
自从1950-60年左右引入第一批集装箱以来,集装箱处理技术和策略一直是衡量码头运营效率的关键因素。特别是近年来中国的集装箱运输量急剧增长已经对码头运营提出了严峻的挑战,因为用于处理这种流量的可用表面面积几乎没有变化。相对于一些使用轮式码头的码头来说,由于这个空间限制,集装箱码头运营采用块堆叠系统,使用如轮胎式龙门起重机(RTGC),轨道式龙门起重机(RMGC)或跨运车(SC)等搬运设备将集装箱彼此堆叠在一起。在Chu and Huang(2005)中提出的分析比较SC,RTGC和RMGC,表明处理能力从SC到RTGC到RMGC逐渐增加。此外,处理集装箱的优化策略已经被广泛研究以提高集装箱码头操作的效率。解决集装箱的综合调查优化战略能在Stahlbock and Vol3 (2008) 和 Steenlcen, Vol3, and Stahlboclc (2004)中找到.
在海运集装箱码头,进口集装箱从船上卸货并存放在堆场内,直到其所有者选择用派遣卡车提走它们。集装箱停留时间或者集装箱停留在堆场的持续时间,通常需要几小时到几天的时间,并且通常取决于每个码头免费存储的天数。例如,在奥克兰的港口(FOAL)进口集装箱每月平均停留时间约为2天在2013年。天数的范围从1.8天到2.6天不等(Port of Auckland eNews(2013))和停留时间的标准偏差在特定月份大约为1.7天(FOAL内部数据,2013的6月)。虽然进口集装箱的到货时间可根据船舶到达时间和船舶运行时间表预测。但是由于卡车到达时间的不可预测性,它们的离开时间有很大的变化。这是一种很典型的现象,搬运工发送一些关于卡车访问码头的预先信息在他们的卡车到达码头之前。卡车预约系统(TAS)就是包含有关卡车到达时间窗信息的一个系统。
1.1在集装箱码头的卡车预约系统
卡车预约系统TAS在集装箱码头的主要目的是为了缓解卡车到达高峰和低谷的不平衡并且与解决码头入口拥塞有关同时减少长期等待卡车对环境的影响。通过限制每个时间段的卡车到达次数,TAS可以减少高峰时段的卡车数量,因此提升了外部卡车的整体周转时间。 这项研究表明TAS也可以帮助提高提取集装箱时的翻箱效率。 香港国际码头(HIT)似乎是第一个在1997年左右实施预约系统的码头。目前在HIT中实施的预约系统是一个直接的配额系统,在系统中每30分钟的时间分配一次预约数量(Musty et al.(2005b))。 根据码头的情况每个时间段的有效数量是变化的。 例如在IVew新西兰,在2007年左右FOAL已经引进称为车辆预订系统的预约系统并为每个时段分配了一个小时。
TAS最乐观的情况是所有卡车在指定的时间段内到码头,但实际上由于几个原因很难实现这种乐观情况。对于难以实现这种情况的理由,每个港口可能有不同的原因。在一项调查针对加利福尼亚区域装卸工的调查中,加利福尼亚地区在2002年已通过法案促使海港口码头采取措施减少卡车排放和为了响应多个港口建立的卡车预约系统,Giuliano and 0#39;Brien(2007)确定了以下原因:高速公路拥堵,客户延误,海运码头延误等。一项研究由Morais and Lord(2006)完成的证实,预约系统在美国西海岸码头可能实施会有效减少西海岸码头的卡车空转/排队。然而他们指出,这些影响取决于这些造成拥挤因素。在HIT里大多数外部卡车从中国大陆带出口集装箱,司机不需要提供可靠的到达时间因为司机无法控制过境时间。因此,HIT仅需要卡车进入码头接货使用预约系统,并且仅限于上午8点至下午5点的码头高峰时间(Musty et al.(2005b))。 2013年,FOAL卡车的准时率约为55-60%,相较于之前的年份这是十分大的提升(Ports of Auckland eNews (2013))。经过多年的实施经验和持续提升对于准时卡车的激励,提升的水平可以控制。
在现有的关于TAS的文献中,只有一点解决了集装箱码头中的堆场处理问题。Huynh and Walton(2008)着眼于根据输入参数(如每个码区和每个时间窗的目标平均卡车运行时间和场地设备数量)为允许的卡车数量找到适当的上限。一个特设的启发式被用来解决他们的公式。Jones and Michael Walton(2002)研究了如何使用进口集装箱出发时间的信息来管理集装箱堆垛。他们提出了三种堆叠集装箱的方法:一是非知情策略,知情策略和随机策略,并开发了基于事件的仿真模型,捕捉各子系统之间的相互作用。他们假定港口必须有一些方法来收集关于出发时间的信息。例如,预期的停留时间。 Namboothiri and Erera(2008)从拖运公司的角度谈到了TAS,并研究了TAS如何影响管理提供集装箱提货和送货服务到港口的卡车队伍。 Zhao and Goodchild(2010)认为,在进口集装箱存放堆场里后,可以获得卡车的到达时间。他们对模拟程序进行了试验,以分析在有关卡车到达顺序的各种信息质量下的重新处理减少情况,并观察到可以通过对有关卡车到达的港口信息的小改进来获得重新处理的显着减少。 van Asperen,Borgman and Deldcer(2013)使用离散事件仿真模型来评估TAS对他们以前的研究(Borgman,van Asperen,&Dekker(2010))在线集装箱堆垛规则的影响。Zehendner and Feillet(2014)提出了一种混合整数规划模式来确定提供的关于总体工作量和可用处理能力的预约数量。 他们的模型旨在最大限度地减少终端的总体延迟,并且离散事件仿真验证了随机环境中通过优化模型获得的结果。
1.2集装箱翻箱问题
集装箱码头的堆场由多个堆垛组成,集装箱在被外部卡车提货或装载到船上之前暂时存放。本中文的堆垛是指由多个水平柱(或桩)和垂直层组成的二维库存空间。一旦集装箱堆叠在一起,它们只能从上面存取。如果目标集装箱顶部有集装箱,则应将上述集装箱重新安置到不同的柱子上,导致无效的移动。根据Caserta,Schwarze and Vol3(2011),已经确定了三种类型的堆垛后问题,即(i)重新编组问题,(ii)预先编组问题和(iii)搬迁问题。在文献中,最后一个问题被称为本文主要讨论的集装箱搬迁(重新搬迁,重新搬运)问题(CRP)或区块搬迁问题(BRP)。研究人员指出,在从码头取回集装箱时,集装箱再处理是大多数码头效率低下的主要原因。解决集装箱重新处理问题的大多数研究的目标都是尽量减少重新搬迁次数,或者重新搬迁时间。
CRP可以正式定义如下:给堆叠在一个给定堆垛布局中的集装箱提货订单,目标将理清堆垛中所有集装箱的重新搬迁次数最少。 这个问题的一般版本被称为块世界规划(BWP),其目标是建立任何可行的块堆叠配置。 BWP的复杂性已经由Gupta and Nau(1992)证明是NP-hard,并且最近由Caserta,Schwarze and Vol3(2012)证明了CRP的复杂性。
CRP首先由kim and Hong(2006)用动态规划(DP)模型制定。自从这项工作以来,如文献 Ku and Arthanari(2016)所述,文献中出现了几种CRP变体。通过假设检索过程中的集装箱重新到达过过程,CRP的静态和动态(Borjian,Manshadi,Barnhart and Jaillet(2013); Alcyuz and Lee(2014); Wan,Liu and Tsai(2009))版本也被研究了。另外,通过理清(或预先编组)的动作,研究了CRP的限制和不受限制的版本。解决这个问题的一个最新趋势是重点研究在不受限制的变体(Exposito-Izquierdo,Melian-Batista and Moreno-Vega(2014); Jin,Zhu,and Lim(2015) ; Petering and Hussein(2013); Zhu,Qin,Lim,and Zhang(2012))。我们还注意到,Unluyurt and Aydm(2012)研究了与Kim and Hong(2006)相同的问题,但是考虑到起重机行驶的距离将其扩展。
除了Kim and Hong(2006)提出的形式主义外,重新处理问题的模型受堆垛类型(导出或导入)的影响。 对于出口集装箱堆垛,Kim,Park and Ryu(2000)针对含重量组信息的出口集装箱推导了最佳堆垛策略。 Musty,Liu,Wan and Linn(2005a)开发了一种确定到货集装箱的存储位置的系统,以最小化由重新搬迁指数(RI)测量的重新搬迁次数。 kang,Ryu and Kim(2006)研究了出口集装箱的重新处理问题,并提出了一种模拟退火方法,以便为具有不确定重量信息的集装箱提供良好的堆垛策略。在此基础上,他们引入了用于权重分组的分类器来评估派生策略。 Yang and Kim(2006)讨论了存储需求单元,该存储需求单元可以一起存储并以任何顺序检索,以找到堆垛策略以最小化总数。
对于进口集装箱堆垛,Watanabe(1991)提出了可访问性指数作为重新处理事件的索引,将其同时应用于SC系统和转运起重机系统,以估计给定存储舱的预期重新搬迁次数。Castillo and Daganzo(1993)提出了两种存储进口集装箱的基本策略,第一种策略基于预期的每个集装箱移动,第二个集装箱根据到达时间分隔集装箱。Kim(1997)提出了分析评估来估计重新搬迁的次数,以检索海湾内的所有集装箱。 Saur and Martin(2011)根据集装箱停留时间的概率分布函数开发了一个数学模型,以便根据产生的重新搬迁数量来评估堆叠策略。
最近的论文仅考虑进口集装箱堆垛,并遵循集装箱到达的静态版本。然而,与其他研究不同的是,假设在同一时间窗口内预订的集装箱之间的集装箱离港随机性。我们称这个问题为时间窗口或CRPTW的CRP类别。在不使用预约系统的集装箱码头中,分配用于取货集装箱的卡车到达时间通常是不可预知的,但我们的模型假定TI1S可以提供卡车访问的时间窗口。在此设置下,不同时间窗口内集装箱之间的提取优先关系明确,但同一时间窗口内集装箱之间的优先关系不清楚。这个问题的目的是(i)找到减少拾取集装箱的重新处理的最优决策,给定通常由卡车预约和(ii)计算从堆垛中清除集装箱的最小预期重处理次数。
本文的其余部分组织如下:在下一节中,该问题被制定为随机动态规划(SDP)模型; 在第3节中,提出抽象启发式来改进树搜索的时间表现; 在第4节中,描述了一个称为期望重新搬迁索引(ERI)的启发式规则; 在第5节中,我们用本文讨论的方法报告了计算实验的结果; 在最后一节中,我们总结我们的发现并提出未来的研究方向。
2.随机模型的发展
为了关注我们模型的随机性,我们将模型限定为静态和受限版本,以下两个假设对于CRP的这种变体是通用的:(i)在检索过程中没有集装箱到达堆垛; (ii)只有当其中任何一个集装箱被取回时,集装箱才会被重新搬迁。
为了包含TAS的组成部分,我们还在模型中做出以下假设:(iii)堆垛中的每个集装箱都被预订到一个时间窗口,然后按小时升序将其映射到一个拾取序列; (iv)与堆垛集装箱相关联的卡车在其指定的时间窗内到达终端。
当一组集装箱被分配到相同的时间窗口时,它们都被映射到相同的序列,在这种情况下它们之间的优先关系是未知的。 我们假设在具有相同序列的集装箱之间有任何离开的机会相等。 这种随机场景不同于Kim and Hong(2006)中的模拟场景,其中一组集装箱可以以任意顺序进行检索。下面我们介绍SDP模型的符号。
N:初始堆垛中的集装箱总数
:为移除第k个集装箱而采取的行动
:k个集装箱被移除后的堆垛状态堆垛
:行动期间要移除的集装箱(k =0,...,N-1)。 这是一个随机变量
():给定状态的移除概率
(,):观察集装箱的状态转换函数从状态中移除
:由(,)转换的状态,即 = (,)
r(|):操作期间发生的重新处理次数给定状态
f():预计重新处理的最小总数,将剩余的集装箱从州移走。
该模型可以如公式(1)中那样被表述为递归函数是一个随机变量,因为当外部因素观察到之前,当前状态将被转换成的状态是不确定的,例如卡车到达。从Eq.式 (1)中,一般的递归函数如公式(2)。
先前的状态和在那里采取的动作独立于将来的随机变量,即和独立于,,hellip;,。 此外,给定状态下的最优动作与未来动作无关,即和独立于,,...,。 因此,我们可以转换的递归函数式(2)变成一般函数,如Eq.(3)。 其推导可由Zhang,Chen,Shi and Zheng(2010)的模型推导出来,这是Kim et al. (2000)对该模型的一个修正版本。
3决策树搜索
3.1 构建一个决策树
全文共20785字,剩余内容已隐藏,支付完成后下载完整资料
资料编号:[14901],资料为PDF文档或Word文档,PDF文档可免费转换为Word
以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
您可能感兴趣的文章
- 2.3港口吞吐量预测外文翻译资料
- 使用多标准移动通信分层遗传算法的阻抗 匹配网络的宽带优化外文翻译资料
- 移动RFID标签阅读与非重叠串联阅读器在输送带的应用外文翻译资料
- 利用数字图像进行的全场应变测量方法外文翻译资料
- 自然灾害中并发事件的多种应急资源的分配外文翻译资料
- 基于主机的卡仿真:开发,安全和生态系统影响分析外文翻译资料
- 实现基于Android智能手机的主机卡仿真模式作为替代ISO 14443A标准的Arduino NFC模块外文翻译资料
- 探索出行方式选择和出行链模式复杂性之间的关系外文翻译资料
- 信息系统研究、教育和实践的基本立场及其影响外文翻译资料
- 仓储和MH系统决策模型的设计优化与管理外文翻译资料