Real-time scheduling for twin RMGs in an automated container yard

This paper proposes heuristic-based and local-search-based real-time scheduling methods for twin rail-mounted gantry (RMG) cranes working in a block at an automated container terminal. The methods reschedule the cranes in real time for a given fixed-length look-ahead horizon whenever an RMG finishes a job. One difficulty with this problem is that sometimes additional rehandling of containers needs to be carried out in order to complete a requested job, especially when other containers are stacked on top of the target container. These rehandlings are the main cause of the delay of the crane operations, leading to extended waiting of automated guided vehicles (AGVs) or external trucks that co-work with the cranes. By treating the rehandling operations as independent jobs in our solution methods, we can greatly facilitate the cooperation between the two RMGs. Through this cooperation, the workload of the two RMGs can be better balanced and interference can be more easily avoided, thereby maximizing crane utilization. Simulation experiments show that the waiting times of AGVs and external trucks are significantly reduced due to the increased utilization through cooperation.     

How to park freight trains on rail–rail transshipment yards: the train location problem

In modern rail–rail transshipment yards huge gantry cranes spanning all railway tracks allow for an efficient transshipment of containers between different freight trains. This way, multiple trains loaded with cargo for varying destinations can be consolidated to a reduced number of homogeneous trains, which is an essential requirement of hub-and-spoke railway systems. An important problem during the daily operations of such a transshipment yard is the train location problem, which assigns each train of a given pulse to a railway track (vertical position) and decides on each train’s parking position on the track (horizontal position), so that the distances of container movements are minimized and the overall workload is equally shared among cranes. For this problem a mathematical model is presented; different heuristic solution procedures are described and tested in a comprehensive computational study. The results show that our procedures allow for a remarkable reduction of train processing time compared with typical real-world train location policies.     

Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry

This paper presents an ant colony optimisation (ACO)-based solution approach for a real-world two-crane routing problem, where a number of different load carriers must be moved within a given cycle time by two gantry cranes in a continuous production process for roof tiles. The cranes have to transport the roof-tile batches and to return the load carriers and intermediate pads for subsequent batches. A feasible solution has to observe workflow-, space-, collision-, and machine-cycle constraints. The objective is to find a feasible schedule that minimises the working time for both cranes. The authors compare different solution approaches in terms of learning – and visibility strategies based on ACO in extensive numerical studies. A visibility concept is used to both partition and balance workload between the cranes.     

Mathematical models and solution methods for optimal container terminal yard layouts

In this paper, we introduce an integer linear program for planning the layout of container yards. We concentrate on a special layout class of container yards which we call yard layout with transfer lanes. For those layouts typically rubber tired gantry cranes are used for stacking operations and trucks for horizontal transports. We show that the optimization model can be formulated as a special type of a resource constrained shortest path problem for which the LP relaxation always has at least one integer optimal solution. This model is restricted to a rectangular storage yard which allows a linear formulation. For an arbitrary shaped container yard we adopt the model and develop a variable neighborhood descent (VND) heuristic for solving non-rectangular instances. Concerning the rectangular case, we show that the VND heuristic achieves optimal solutions for 38% of the realistic test instances.     

Gantry crane scheduling in intermodal rail-road container terminals

Modern rail-road container terminals serve as important consolidation nodes in intermodal transportation networks where containers are transferred between freight trains and trucks. Among the most important decision problems in these yards is the crane scheduling problem, which decides on the sequences of container moves executed by each of the parallel gantry cranes. This paper treats a rich crane scheduling problem, which considers plenty relevant constraints and is directly applicable in Chinese intermodal terminals. For solving this problem, we propose a fix-and-optimise procedure, which is easy to implement and shown to successfully solve even large-sized instances with 100 container moves in reasonable time.     

Simulation-based optimization for discharge/loading operations at a maritime container terminal

The discharge/loading process of a single container ship by multiple quay cranes and shuttle vehicles moving back and forth from the quay to the yard and vice versa is focused in this paper. The core problem of this major operational issue reduces to finding the optimal assignment and optimal sequencing (schedule) of bays (jobs) processed by a fixed number of available cranes (machines). Under the classical assumption that machines have no release time and that their processing occurs with continuity, at a constant rate, in literature it has been tackled as a deterministic machine scheduling problem and formulated by integer programming as the quay crane scheduling problem (QCSP). Here, instead, the QCSP is viewed as a decisional step within an uncertain and dynamic logistic process where the quay cranes are the resources to be managed at the best, i.e., by minimizing the time spent waiting for each other due to conflicts, as well as the time wasted for blocking and starvation phenomena due to congestion occurring along the path from the quay area and to the stacking yard and vice versa. We present a simulation-based optimization (SO) model for this wider modeling problem with the objective of finding the schedule which optimizes a classical objective function. The search process for the optimal schedule is accomplished by a simulated annealing (SA) algorithm, while performance estimation of the overall container discharge/loading process is provided by the simulation framework as a whole. Numerical experiments on a real instance are presented for tuning purposes of the SA procedure implemented within the simulator.     

Optimizing the yard layout in container terminals

The main activities of container terminals are to load outbound containers on to vessels, discharge inbound containers from vessels, and store those containers in the yard before loading (or after discharging) them. This study proposes a method for determining an optimal layout of container yards taking into consideration the storage space requirements and throughput capacities of yard cranes and transporters. Two types of yard layout are under consideration: a layout where blocks are laid out parallel to the quay and transfer points are located beside a bay per block, and a layout whose blocks are laid out perpendicular to the quay and transfer points are located at both ends of each block. Various cost factors are used for optimizing the yard layout, which include the construction cost of the ground space, the fixed overhead cost of yard cranes, and the operating costs of yard cranes and transporters. Sensitivity analysis is performed to investigate the effect of various design parameters on the optimal layout of the yard. The two types of yard layout are compared with each other, and the results of this study are compared against those for real-world yard layouts from the perspective of throughput capacity and storage space capacity.     

电动汽车集约型换电设施的设计研究

为解决电动汽车换电站施工周期长、换电效率低、存在安全隐患等问题,提出了一种集约型换电设施的设计思路及方案。通过对集装箱合理改造,并集成电池缓存、自动取放、充电控制、安全防护等系统,从而构成一种具备电池取放自动化、均衡充电及自动保护功能的集约型换电设施。详述了该集约型换电设施各系统的功能及设计方案,实践证明该换电设施可提高土地利用率、降低换电站建设成本,并可提高换电效率及服务质量,达到预期效果,同时具有较高的市场潜力。     

Robust cyclic berth planning of container vessels

We consider a container terminal operator who faces the problem of constructing a cyclic berth plan. Such a plan defines the arrival and departure times of each cyclically calling vessel on a terminal, taking into account the expected number of containers to be handled and the necessary quay and crane capacity to do so. Conventional berth planning methods ignore the fact that, in practice, container terminal operator and shipping line agree upon an arrival window rather than an arrival time: if a vessel arrives within that window then a certain vessel productivity and hence departure time is guaranteed. The contributions of this paper are twofold. We not only minimize the peak loading of quay cranes in a port, but also explicitly take into account the arrival window agreements between the terminal operator and shipping lines. We present a robust optimization model for cyclic berth planning. Computational results on a real-world scenario for a container terminal in Antwerp show that the robust planning model can reach a substantial reduction in the crane capacity that is necessary to meet the window arrival agreements, as compared to a deterministic planning approach.     

Multiple yard cranes scheduling for loading operations in a container terminal

The efficiency of yard crane scheduling is critical in increasing the throughput of a maritime terminal. This article studies the problem of scheduling multiple yard cranes in loading operations. The movements of yard cranes among container blocks and the sequencing of yard cranes within each block are studied at the same time. Potential interferences between yard cranes are considered. A mixed integer programming model is developed to formulate the problem. A genetic algorithm and a tabu search algorithm are proposed to obtain near-optimal solutions. Experimental tests are conducted to evaluate the performance of the two algorithms based on various data settings.     

Design and development of an intelligent context-aware decision support system for real-time monitoring of container terminal operations

This paper describes a case study of the research and development of an intelligent context-aware decision support system (ICADSS) prototype for real-time monitoring of container terminal operations in Hong Kong. We present the system design and development of the prototype system, and discuss the experiences and lessons learned. To the best of our knowledge, this study is the first identifiable application of an intelligent context-aware decision support system for the real-time monitoring of container terminal operations reported in the academic literature. The intelligent context-aware decision support system employs ZigBee-based ubiquitous sensor network (USN) technology. In this study, an ICADSS prototype was built and implemented in a real world setting. The results of the system prototype evaluation are satisfactory and support the contention that it is more effective in supporting the real-time tracking and tracing of container trucks, quay cranes, and rubber-tired gantry cranes in a container terminal. The results also validate the practical viability of the proposed system architecture. Given the contextual details of the study, we present the lessons learned from developing and operating the system in a container terminal and provide suggestions for further research. We hope that the proposed system architecture and developed prototype system can help both practitioners and academics in the further use and research of intelligent context-aware decision support systems.     

基于蚁群算法的军用车辆器材装箱配载问题

目的对军用车辆器材装箱配载问题进行合理优化,以提高集装箱的空间利用率。方法阐述了军用车辆器材装箱配载问题的重要性,并对装箱配载问题进行理论分析,应用蚁群算法建立数学模型和实现流程,通过实例分析验证该算法的合理性。结果利用蚁群算法模拟与优化装箱配载问题使集装箱利用率达到了88.96%,并确定出了最优的装箱配载方案。结论蚁群算法能够对军用车辆器材装箱配载问题进行合理优化。     

Development and simulation analysis of real-time yard crane control systems for seaport container transshipment terminals

As more and more container terminals open up all over the world, terminal operators are discovering that they must increase quay crane work rates to remain competitive. In this paper, we develop a real-time yard crane control system and show that a terminal’s long-run average quay crane rate depends on the portion of this system that dispatches yard cranes in the storage area in real time. Several real-time yard crane dispatching systems are evaluated by a fully-integrated, discrete event simulation model of a pure transshipment terminal that is designed to reproduce the multi-objective, stochastic, real-time environment at an RTGC-based, multiple-berth facility. Results indicate that yard cranes should prioritize the retrieval of containers from the stacks, rather than the storage of containers into stacks. Also, the yard crane dispatching system should not only consider the trucks already waiting for service in the yard, but also the trucks that are heading towards the yard. The experiments provide the first direct connection in the literature between real-time yard crane control systems and long-run performance at a seaport container terminal. We also make a qualitative comparison between rule-based and look-ahead yard crane dispatching schemes, and discuss deadlocking issues in detail.     

Optimal stack layout in a sea container terminal with automated lifting vehicles

Container terminal performance is largely determined by its design decisions, which include the number and type of quay cranes, stack cranes, transport vehicles, vehicle travel path and stack layout. We investigate the orientation of the stack layout (parallel or perpendicular to the quayside) on the throughput time performance of the terminals. Previous studies in this area typically use deterministic optimisation, and a few studies use probabilistic travel times and simulation to analyse the effect of stack layout on terminal throughput times. In this research, we capture the stochasticity with an integrated queuing network modelling approach to analyse the performance of container terminals with parallel stack layout using automated lifting vehicles. Using this analytical model, we investigate 1008 parallel stack layout configurations on throughput times and determine the optimal stack layout configuration. We find that, assuming an identical width of the internal transport area, container terminals with parallel stack layout perform better (from 4–12% in terms of container throughput times) than terminals with a perpendicular stack layout.     

求解集装箱装载问题的混合蚁群模拟退火算法

目的 针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法 首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降为二维装箱问题,有效降低集装箱的装载规模;其次,蚁群算法通过融入信息素选择更新策略,并利用自适应信息素挥发系数来提升算法整体的收敛速度,同时结合模拟退火算法对每代优秀路径集进行局部搜索,避免算法因收敛过快而陷入局部最优;最后,将蚁群模拟退火算法与二维装载点启发式算法相结合,优化每座塔的装载顺序和放置姿态,寻找最优的装载方案。结果 实验证明,在250组算例中,采用混合算法后,集装箱的平均空间利用率为90.92%,优于其他3种对比算法。结论 设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Quantifying the impact of inland transport times on container fleet sizing in liner shipping services with uncertainties

Container fleet sizing is a key issue in liner shipping industry. Although container shipping is an intermodal transport system, inland container movements are often beyond the control of shipping lines. It is vital to understand how the inland transport times and their variability affect the container fleet sizing. This paper first formulates the container fleet sizing problem in liner services with uncertain customer demands and stochastic inland transport times. Simulation-based optimisation approaches are then employed to solve the problem. Two typical shipping services, one cyclic route in trans-Pacific lane and the other more complicated route in Europe–Asia lane, are used as case studies. A quantitative relationship between the optimal container fleet size and the inland transport time is established. The impact of uncertainties in inland times on the fleet sizing is also investigated. The results provide shipping companies useful insights into making strategic decisions.     

集装箱码头岸吊作业调度建模及调度策略研究

岸吊作业调度对集装箱码头整体运营效率具有重要影响.综合考虑岸吊实际作业中的特有约束,包括预定义顺序约束、依赖于作业次序的设备调整时间、岸吊干涉约束,建立岸吊作业调度问题的混合整数规划模型.针对混合装卸模式,使用启发式算法生成预定义作业顺序,在此基础上采用基于连续贝作业策略的启发式算法对问题进行求解.数据实验结果显示基于SPT规则和连续贝作业的启发式算法能有效利用混合装卸带来的时间节省,减少设备调整时间,对实际岸吊作业调度具有指导意义.     

A scheduling method for Berth and Quay cranes

This paper discusses a method for scheduling Berth and Quay cranes, which are critical resources in port container terminals. An integer programming model is formulated by considering various practical constraints. A two-phase solution procedure is suggested for solving the mathematical model. The first phase determines the Berthing position and time of each vessel as well as the number of cranes assigned to each vessel at each time segment. The subgradient optimization technique is applied to obtain a near-optimal solution of the first phase. In the second phase, a detailed schedule for each Quay crane is constructed based on the solution found from the first phase. The dynamic programming technique is applied to solve the problem of the second phase. A numerical experiment was conducted to test the performance of the suggested algorithms. RID="*" ID="*" This research has been supported in part by Brain Korea 21 Program (1999–2002). Correspondence to: Y.-M. Park