文献综述-动态需求下跨集装箱码头集卡调度问题研究.doc

文献综述一跨码头集卡调度问题研究现状集装箱港口是集装箱运输中极其重要的枢纽。集装箱港口的运作效率直接决定了集装箱运输的成本。为了提高集装箱港口的管理和运作水平，国内外许多学者都在集装箱港口运作优化方面做了大量的工作。集卡调度是集装箱码头智能化调度的核心问题之一，集卡运输作为港口内唯一交通运输方式，其运作效率将直接影响堆场码放的效率，进而影响到港口整体作业的运作效率。因此，对于港内集卡运输方面的研究成为了近期研究的热点之一。国内外许多学者为解决此类问题做了很多尝试，也取得了许多可喜的研究成果。但是这些研究大多以当地集装箱港口的实际情况为依托，而国内外港口的实际情况却存在较大的差别，由各自实际情况建立的模型、设计的算法和得出的结论都有所区别。二国外研究现状集装箱码头的水平运输设备除了集卡之外还有跨运车与自动化码头所采用的AGV(自动导向车)，考虑到AGV的高昂的前期投资，一般只用于国外劳动力费用高的港口。国际上关于港口水平运输机械的研究多集中于自动化或半自动化港口中使用的AGV(自动导向车)。Gobal和Kasilingam (1992)1给出了一个基于AGVs空闲时间和集装箱码头其他装卸设备等待时间的AGVs数量估算仿真模型，求解在满足操作水平条件下的最小AGVs需求数量。Chen et al.(1997)2l研究了自动化集装箱港口中的AGVs调度问题。文章采用贪婪算法求出了AGVs调度的最优解同时给出了求解多台岸桥情况下的一种启发式算法。Kim k.H和Bae J.W(1999)3根据多船、多岸桥同时作业的情况建立了多目标规划模型。该文献进一步研究了装卸同时作业的情况，建立了整数规划模型(MVSL)，并证明了MVSL是Np-hard问题，设计了一种启发式算法对模型进行求解，使得即使问题规模很大也能有办法解决。ChinI Liu，Hossein Jula，Katarina Vukadinovic，Petros Ioannou(2004)4介绍AGV在不同结构集装箱堆场运输，应用多属性决策方法评价码头实施情况，计算每个码头使用AGV的最优数。Hans-Otto Gunther，Martin Grunow，Matthias Lehmann5主要研究自动化集装箱码头AGV小车的两种调度策略：online调度与Off-line调度算法，研究港口装卸操作并加以仿真。Bose等(2000)6研究多船同时操作，用遗传算法使岸桥的总耽搁时间最短讨论集卡调度优化问题。Krishnamurt等7对同时确定所有拖车路径的问题进行了研究。在这个问题的研究中，一个大问题被分解为若干个子问题进行研究。在得到子问题的解决方案后，再进行有机的组合形成一个总的解决方案。Maxwell和Muckstadt8构建了一种数学模型来解决拖车的规模确定问题，在这个模型中，把任务序列时窗化，把岸桥、堆场等固定设施抽象为节点，节点的流量即为任务输入集装箱与任务输出集装箱的差值。拖车空载行驶路径的长短直接影响到作业总时间，模型的目标是使拖车空载的行驶路径最短。Mantel and Landeweerd9提供了一种两层排队网络模型来确定自动化码头执行任务时需要的AGV数量。在第一层，所有AGV被看成等价的服务台，运输任务作为顾客；第二层AGV被视为顾客，而整个堆场被视为服务时间一定的服务台。通过在不同AGV数量下计算模型的等待时间，可以确定合理的AGV数。三国内研究现状我国的港口多属于非自动化港口，出于劳动力费用和操控灵活性等方面的考虑，国内港口多采用人力控制的拖车作为水平运输工具。因此国内的研究则偏向于集卡作为水平运输机械的港口。王超，陈磊等10针对集卡调度问题，充分考虑了现在科技发展全面应用GPS定位系统的前提，给出了一个智能化集卡实时调度方案。计明军,靳志宏11对同时装卸集装箱作业的情况进行研究，考虑了集装箱卡车的运输时间和岸桥的作业时间，建立基于时间最少的优化模型。利用进化计算的特点，设计求解此优化模型的进化算法，进行了数值仿真试验，在合理时间内获得了最优数值结果。此模型和方法为码头集卡线路优化问题提供了决策支持。尚晶，陶德馨12提出了在数字化技术环境下的集装箱码头集卡实时调度规则，并建立了这两种调度模式的动态仿真模型。经过仿真实验分析，比较这两种度模式对码头生产能力的影响，结果表明提出的调度策略是合理可行的，具有较强的可操作性。李浩渊，汪定伟13分析了动态集卡配置对集装箱码头装卸作业的影响，构建了一个集装箱码头整体作业系统的仿真模型。运用仿真模型与优化算法相结合的基于仿真的优化方法(SBO)对集装箱码头动态集卡配置问题进行了求解，并将基于MPI消息传递标准的并行集群计算方法引入该求解过程，很好的解决了基于仿真的优化方法中存在的计算代价过大的问题。计明军，刘丰硕等14在待装集装箱船舶与待卸集装箱船舶同时作业情况下，研究集卡的运输路径，建立集卡行驶路径最短的优化模型，并对优化模型进行数值试验，在合理时间内获得了最优结果。在此基础上以岸桥等待时间最短估算作业需要配备的最佳集卡数量。严政，陶德馨15从探索集装箱堆场机械设备调度的规则入手，提出了基于动态优化组合的港区内集装箱集卡(简称集卡)的调度规则。应用作业调度信息系统和无线局域网络实现集卡作业状态的实时监控和动态优化的调度功能，并用离散事件动态仿真的方法进行了模拟，验证了该方法的有效性。陈方鼎16研究了采用“大作业面”工艺时集装箱码头集卡的调度问题。根据实际情况将集卡调度同岸桥作业相结合，建立了协调岸桥的集卡调度模型。采用了现代优化算法中的群体智能算法，并结合蚁群算法与粒子群算法，形成混合群体智能算法进行求解。通过一个模拟现实集装箱码头同时服务多艘船舶的案例，得到优于“作业线”装卸工艺的结果，这些结果表明所提出的模型与算法对解决集装箱码头集卡调度问题具有一定的现实意义。近年来，计算机建模和仿真技术越来越多地应用于集装箱码头的规划和管理中。计算机仿真作为一种测试与验证平台，仅能对给定的设计结果进行评价，无法提供进一步的辅助决策功能。四当前研究存在的问题1. 国外文献的研究对象主要为AGV。目前大多数文献对港内拖车调度问题的研究都集中在自动导引车(AGV)上，AGV的行驶路线相对固定，能够及时反馈位置信息以及能准确执行调度指令，这使得一些调度策略能完整执行。而目前国内港口基本没有使用AGV，主要采用人工集卡，在这种情况下，由于人工因素的制约，一些调度策略就不能被很好执行。2. 建立的模型与实际仍有差距。在现有的研究文献中，对于港口运输问题，为了简化问题或多或少做了一些假设，诸如岸桥等待时间为零、岸桥装卸操作时间为常数、集卡在泊位到堆场之间的行驶时间是固定的、忽略交通网络堵塞因素等等。但是，在实际中，这些因素对问题结果的影响并不小，所以普遍存在的问题使得现有的研究结果很难投入到实际应用中去。3. 缺乏对全场调度的研究。目前对拖车运输研究所建立的模型，大多是针对一个岸桥作业的情形。虽然有国外少数文献考虑了多岸桥组合模型的求解，但考虑的因素做了很大的简化假设，同时由于国外港口与我国港口的特征差别，所建立的模型和提出的算法结果在我国港口的实际应用效果较差。全场调度问题由于其规模大，很难找到一个高效的算法得到问题的最优解17。五 结论集装箱拖车运输是集装箱码头作业系统中的重要环节，衔接前沿岸桥和后方龙门吊的工作。当前理论界和实践界较少考虑整个港口系统内的全局集卡调度问题。大多数研究集中在某码头内部，没有考虑港口跨码头情况以及其他子系统的相互影响，因此，只能做到局部优化，而不能达到港口内部物流资源的优化整合。本文对同时港口码头集卡作业的情况进行研究，考虑了集卡调度过程中涉及的司机经验等级、有效工时、调运成本等因素，建立了跨码头集卡调度的决策模型。经过模型求解及算例分析，决策结果表明建立的决策模型鲁棒性良好，具有较强的求解效率。此模型和方法为港口跨码头集卡调度问题提供了决策支持。六参考文献1Gobal SL. and Kasilingam RG. A simulation model for estimating vehicle requirements in automated guided vehicle systemsComputer Industry Engineering，1991,21：623-627.2Chen Y.，Leong Y.T.，Ng J.W.C. et al. Dispatching automated guided vehicles in a mega container terminal, paper presented at INFORMS Montreal 1998, Canada.3 Kim K.H. and J.W. Bae, A dispatching method for automated guided vehicles to minimize delays of containership operations. International Journal of Management Science 1999, 5(1), pp. 125.4Chin-ILiu，Hossein Jula，Katarina Vukadinovic，Petros loannouAutomated guided vehicle system for two container yard layouts.Transportation Research Part, 2004-02：3493685Hans-Otto Gunther，Martin Grunow，Matthias LehmannAGV Dispatching Strategies at Automated Seaport Container TerminalsInternational Symposium on OR and Its Application,2005：48-646Bose J.，Refiners T.，Steenken Det alVehicle dispatching at seaport container terminals using evolutionary algorithmsProceedings of the 33m Hawaii International Conference on Systems Sciences,2000.7Krishnamurti, R., and Laporte, G., “Double-horizon based heuristic for the dynamic pickup and delivery problem with time windows, Transportation Research B 2000, 38: 635-6558Maxwell, W. L. and Muckstadt, J. A., Design of automatic guided vehicle systems, IIE Transaction, 1982, 14(2), 114-1249Mentel R. J. and H. R.A. Landeweerd, Design and operation control of an AGV system, International Journal of Production Economics, Vol. 41 (1995), pp. 257-25610王超,陈磊等. 集装箱码头集卡智能化实时调度方案J.中国港口,2008-10：51-52.11计明军,靳志宏.集装箱码头集卡与岸桥协调调度优化R.大连：大连海事大学,2007：1-6.12尚晶,陶德馨.集装箱码头集卡调度策略的仿真研究N.武汉理工大学学报,2006-10.