A heuristic for the quay crane scheduling problem based on contiguous bay crane operations

Quay cranes (QC) are key resources at container terminals, and the efficiency of QC operations is vital for terminal productivity. The Quay Crane Scheduling Problem (QCSP) is to schedule the work activities for a set of cranes assigned to a single berthed vessel with the objective of minimizing the completion time of all container handling tasks. The problem is complicated by special characteristics of QC operations. Considering QC moving time and interference constraints, the concept of contiguous bay operations is proposed and a heuristic is developed to generate QC schedules with this feature. The heuristic is efficient and effective: it has polynomial computational complexity, and it produces schedules with a completion time objective bounded above by a small increment over the optimal completion time. Importantly, the heuristic guarantees that no quay cranes are idle due to interference. Numerical experiments demonstrate that the optimality gap is small for practical instances.     

A tabu search heuristic for the quay crane scheduling problem

This paper proposes a tabu search heuristic for the Quay Crane Scheduling Problem (QCSP), the problem of scheduling a fixed number of quay cranes in order to load and unload containers into and from a ship. The optimality criterion considered is the minimum completion time. Precedence and non-simultaneity constraints between tasks are taken into account. The former originate from the different kind of operations that each crane has to perform; the latter are needed in order to avoid interferences between the cranes. The QCSP is decomposed into a routing problem and a scheduling problem. The routing problem is solved by a tabu search heuristic, while a local search technique is used to generate the solution of the scheduling problem. This is done by minimizing the longest path length in a disjunctive graph. The effectiveness of our algorithm is assessed by comparing it to a branch-and-cut algorithm and to a Greedy Randomized Adaptive Search Procedure (GRASP).     

A modified genetic algorithm for quay crane scheduling operations

The demand for the maritime transportation has significantly increased over the past 20 years due to the rapid pace of globalization. Terminal managers confront the challenge in establishing the appropriate quay crane schedule to achieve the earliest departure time of ship and provide efficient service. In general, quay crane schedule problems include two main issues (1) the allocation of quay cranes to handle the discharging and loading operations, and (2) the service sequence of ship bays in a vessel of each quay crane. Traditionally, the terminal planners determine the quay crane schedule based on their experience and own judgment. In addition, the interference among cranes and the increased in ship size further magnify its difficulty dramatically. Accordingly, this paper proposed a modified genetic algorithm to deal with the problem. To test the optimization reliability of the proposed algorithm, a set of well known benchmarking problem is solved, and the results obtained are being compared with other well known existing algorithms. The comparison demonstrates that the proposed algorithm performs as good as many existing algorithms and obtains better solutions than the best known ones in certain instances. In addition, the computational time(s) required are significantly much lesser, allowing it to be more applicable in practical situation.     

Modeling and solving rich quay crane scheduling problems

The quay crane scheduling problem is a core task of managing maritime container terminals. In this planning problem, discharge and load operations of containers of a ship are scheduled on a set of deployed quay cranes. In this paper, we provide a rich model for quay crane scheduling that covers important issues of practical relevance like crane-individual service rates, ready times and due dates for cranes, safety requirements, and precedence relations among container groups. Focus is put on the incorporation of so-called unidirectional schedules into the model, by which cranes move along the same direction, either from bow to stern or from stern to bow, when serving the vessel. For solving the problem, we employ a branch-and-bound scheme that is known to be the best available solution method for a class of less rich quay crane scheduling problems. This scheme is extended by revising and extending the contained lower bounds and branching criteria. Moreover, a novel Timed Petri Net approach is developed and incorporated into the scheme for determining the starting times of the discharge and load operations in a schedule. Numerical experiments are carried out on both, sets of benchmark instances taken from the literature and real instances from the port of Gioia Tauro, Italy. The experiments confirm that the new method provides high quality solutions within short runtimes. It delivers new best solutions for some of the benchmark problems from the literature. It also shows capable of coping with rich real world problem instances where it outperforms the planning approach applied by practitioners.     

Dynamic rolling strategy for multi-vessel quay crane scheduling

This paper focuses on the container loading and unloading problem with dynamic ship arrival times. Using a determined berth plan, in combination with the reality of a container terminal production scheduling environment, this paper proposes a scheduling method for quay cranes that can be used for multiple vessels in a container terminal, based on a dynamic rolling-horizon strategy. The goal of this method is to minimize the operation time of all ships at port and obtain operation equilibrium of quay cranes by establishing a mathematical model and using a genetic algorithm to solve the model. Numerical simulations are applied to calculate the optimal loading and unloading order and the completion time of container tasks on a ship. By comparing this result with the traditional method of quay crane loading and unloading, the paper verifies that the quay crane scheduling method for multiple vessels based on a dynamic rolling-horizon strategy can provide a positive contribution to improve the efficiency of container terminal quay crane loading and unloading and reduce resource wastage.     

A unified approach for the evaluation of quay crane scheduling models and algorithms

Scheduling of quay cranes at container terminals is a field of growing interest in research and practice. In the literature, we find diverse models for quay crane scheduling that consider the service of container vessels at different levels of detail. Currently, however, there exists no basis to compare the quality of planning that is achieved from these models. There is also no platform available that allows comparing different solution procedures and investigating conditions where they perform well or poorly. This paper presents a unified approach for evaluating the performance of different model classes and solution procedures. The approach is demonstrated by investigating the suitability of three models within a comprehensive computational study.     

A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach

This paper presents a new approach to analyze the integrated quay crane assignment and scheduling problem (QCASP). The problem determines the assignment of quay cranes to vessels and the sequence of tasks to be processed by each quay crane simultaneously, and accounts for important considerations such as safety margins between quay cranes (QCs), ordering conditions and vessel priority. Furthermore, QCs can travel from one vessel to another vessel whenever tasks are complete. The integrated problem is difficult to solve with exact methods due to its complexity. Therefore, a genetic algorithm (GA) is proposed to solve the integrated QCASP. Computational results validate the performance of the proposed GA.     

Hybrid evolutionary computation methods for quay crane scheduling problems

Quay crane scheduling is one of the most important operations in seaport terminals. The effectiveness of this operation can directly influence the overall performance as well as the competitive advantages of the terminal. This paper develops a new priority-based schedule construction procedure to generate quay crane schedules. From this procedure, two new hybrid evolutionary computation methods based on genetic algorithm (GA) and genetic programming (GP) are developed. The key difference between the two methods is their representations which decide how priorities of tasks are determined. While GA employs a permutation representation to decide the priorities of tasks, GP represents its individuals as a priority function which is used to calculate the priorities of tasks. A local search heuristic is also proposed to improve the quality of solutions obtained by GA and GP. The proposed hybrid evolutionary computation methods are tested on a large set of benchmark instances and the computational results show that they are competitive and efficient as compared to the existing methods. Many new best known solutions for the benchmark instances are discovered by using these methods. In addition, the proposed methods also show their flexibility when applied to generate robust solutions for quay crane scheduling problems under uncertainty. The results show that the obtained robust solutions are better than those obtained from the deterministic inputs.     

Quay crane and yard truck dual-cycle scheduling with mixed storage strategy

In order to enhance the efficiency of port operations, the scheduling problem of the quay cranes and yard trucks is crucial. Conventional port operation mode lacks optimization research on efficiency of port handling operation, yard truck scheduling, and container storage location. To make quay crane operations and horizontal transportation more efficient, this study uses a dual-cycle strategy to focus on a quay crane and yard truck scheduling problem in conjunction with a mixed storage strategy. A dispatching plan for yard trucks is considered, as well as the storage location of inbound containers. Based on the above factors, a mixed-integer programming model is formulated to minimize vessels’ berth time for completing all tasks. The proposed model is solved using a particle swarm optimization-based algorithm. Validation of the proposed model and algorithm is conducted through numerical experiments. Additionally, some managerial implications which may be potentially useful for port operators are obtained.     

A new continuous berth allocation and quay crane assignment model in container terminal

Over the past decades, Chinese ports throughput grew rapidly, and more and more concerns were shown on the operational efficiency and effectiveness. Many studies have been made for scheduling berth and quay cranes, which are the critical resources in container terminals. In this paper, a two-phase model for berth allocation and quay crane assignment is proposed. In the first phase, according to the relationships of time and space between vessels, a new continuous berth allocation model is established, in which not only the common restricts but the coverage area of quay crane are considered. Then in the quay crane assignment phase, a multi-objective programming model is proposed, in which the first objective is to minimize the range of maximum and minimum quay cranes used for resources saving, and the second one is to minimize the movements of quay cranes so as to improve the efficiency. A particle swarm optimization algorithm for BAP was developed. The results of numerical experiments show that the proposed approach can improve the essential operations in container terminal.     

Quay crane scheduling in automated container terminal for the trade-off between operation efficiency and energy consumption

At present, the automation of handling equipment has changed the operation mode in the automated container terminal. This paper investigates the automated quay crane scheduling problem (AQCSP) for the automated container terminal. The operation process of AQCSP is decomposed, and formulated it as a mixed integrated programming model. In the numerical experiments, the relation between operation efficiency and energy consumption has been quantitative analyzed by case study. Moreover, the sensitivity analysis of the ratios for all tasks in a vessel bay and the tasks in each stack are also presented. The findings of this study will provide a theoretical reference for the study on the trade-off operation efficiency and energy consumption on the operational level.     

带作业范围约束的岸桥调度模型及其算法设计

受电缆线坑位置与缆线长度的限制,岸桥作业只能在一定的横向移动范围之内。考虑到这一现实要求,结合岸桥作业禁止跨越与安全距离等特有约束,以最小化装卸作业的makespan为目标,构建了新的岸桥作业调度混合整数规划模型。针对问题的NP-hard特性,设计了一种混合模拟退火算法,运用启发式算法生成质量较高的初始解,结合遗传算法的变异运算生成邻域新解,增强了解的多样性,引入禁忌搜索算法的禁忌表操作,避免了循环搜索,提高了求解效率。大规模实验结果表明所建立的模型是有效的,算法的求解质量与效率明显优于标准模拟退火算法与禁忌搜索算法。当实验规模逐渐增大时,与LINGO软件相比,算法在求解效率方面的优势越来越明显。     

An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal

This paper addresses an effective approach to solve the issue of berth allocation and quay crane assignment in a multi-user container terminal. First of all, the studied coupling problem is formulated with the interactions between berth allocation and quay crane assignment considered. Then, an evolutionary algorithm with nested loops was developed to obtain optimal solutions. The algorithm is well structured, where two inner loops are used to solve sub-problems of berth allocation and quay crane assignment respectively; an outer loop is then utilized to find an approximate solution based on the results of the two inner loops. The results of numerical experiments show that the proposed approach can improve the essential operations in container terminals.     

时间窗下单船岸桥调度——基于数学规划和规则的启发式算法

在考虑任务属性中的任务优先顺序和不可同时执行要求,岸桥属性中的岸桥时间窗、转移时间、初始位置、安全距离和装卸速度等因素下,以单艘船舶的最短岸桥作业时间为目标函数,建立单艘船舶岸桥调度的混合整数线性模型P1。计算数据采集于宁波某集装箱港口,通过简化模型P2求解岸桥调度模型P1的下限边界值和排程数据,在此基础上,运用基于规则的启发式算法求解模型P1的岸桥调度时序表。计算结果表示本组合算法能较好地得到满意解,而且比较符合港口实际。     

Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information

The performance of a container terminal depends on many aspects of operations. This paper focuses on the optimal sequencing of a yard crane (or YC for short) for serving a fleet of vehicles for delivery and pickup jobs. The objective is to minimize the average vehicle waiting time. While heuristic algorithms could not guarantee an optimal solution, a conventional mathematical formulation such as mixed integer program would require too much computing time. We present two new algorithms to efficiently compute YC dispatching sequences that are provably optimal within the planning window. The first algorithm is based on the well-known A^∗ search along with an admissible heuristics. We also incorporate this heuristics into a second backtracking algorithm which uses a prioritized search order to accelerate the computation. Experimental results show that both new algorithms perform very well for realistic YC jobs. Specifically, both are able to find within seconds optimal solutions for heavy workload scenarios with over 2.4 × 10¹⁸ possible dispatching sequences. Moreover, even when the vehicle arrival times are not accurately forecasted, the new algorithms are still robust enough to produce optimal or near-optimal sequences, and they consistently outperform all the other algorithms evaluated.     

A queuing network model for the management of berth crane operations

This paper focuses on the optimal management of container discharge/loading at any given berthing point, within a real maritime terminal. Productivity maximization of expensive resources, as rail-mounted berth cranes, should be matched with the vessel requirement of minimizing waiting times with an adequate rate of service completion. To this practical problem, a queuing network model is proposed. Due to its complexity, discrete-event simulation appears as the most appropriate approach to model solution. To get a systematic representation of real constraints and policies of resource allocation and activity scheduling, an event graph (EG)-based methodology has been exploited in simulator design. Alternative policies issued by the operation manager can be inserted in a suitable panel-like view of the queuing network model and then compared by means of simulation, to evaluate the average measures for all berth cranes, such as throughput and completion time. Numerical experiments for simulator validation against real data are encouraging. Some decisions on both straddle carrier assignment to berth cranes and hold assignment and sequencing upon the same crane could be improved by the proposed manager-friendly simulation tool.     

A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90^°${90}^{°}$ in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature.     

Heuristics for solving continuous berth allocation problem considering periodic balancing utilization of cranes

This study investigates a berth allocation problem considering the periodic balancing utilization of quay cranes in container terminals. The proposed model considers that the quay cranes allocated to a work shift should be fully used and other real-world considerations, such as the continuous quay line, the penalties for early arrivals and departure delays. To solve the model, several heuristics are developed: the model for large problems is decomposed into sub-models that are solved by rolling-horizon heuristics; neighborhood search heuristics are used for optimizing a berthing order of vessels; parallel computing is used to improve the algorithmic performance. The method performs well when applied to real-world large-scale instances with promising computation time that is linearly related to the number of vessels.     

基于滚动规划的泊位和岸桥分配集成模型研究

泊位分配（BA）,岸桥配置（QCA）及岸桥调度（QCS）是三个基本的岸边决策问题。提出了一个基于混合整数线性规划的BA和QCA的集成模型,模型综合考虑了货轮优先权,理想泊位及处理时间三个方面的因素。在实际生产数据上的运行结果表明该模型具有决策支持的潜在能力。     

A case based heuristic for container stacking in seaport terminals

In this paper, we suggest a Case Based heuristic for the online container stacking management system in seaport terminals. The main objectives of the system are to determine the exact position of each import container in the storage area and to control container allocation and react to unexpected events and disturbances in an intelligent, self-organizing and real-time manner. First, we propose learning mechanisms and knowledge models for a better management of knowledge related to disturbances and container environment. This system takes into account different types of containers especially the storage of dangerous containers. For assessment of the suggested system, real data are collected from King Abdul Aziz Dammam seaport terminal (Saudi Arabia). The performance of the developed heuristic is assessed with different scenarios and compared to three other stacking strategies studied in the scientific literature. The obtained results are promising and show that the developed CBR (Case Based Reasoning) based heuristic can be efficient or similar problems, i.e. online container staking.