An Integrated Quay Crane Assignment and Scheduling Problem

As maritime container transport is developing rapidly, the need arises for efficient operations at container terminals. One of the most important determinants of container handling efficiency is the productivity of quay cranes, which are responsible for unloading and loading operations for container vessels. For this reason, the Quay Crane Assignment Problem (QCAP) and the Quay Crane Scheduling Problem (QCSP) have received increasing attention in the literature and the present paper deals with the integration of these interrelated problems. A formulation is developed for the Quay Crane Assignment and Scheduling Problem (QCASP), which accounts for crane positioning conditions and a Genetic Algorithm (GA) is developed to solve the QCASP. Both the model formulation and the solution methodology are presented in detail and computational analysis is conducted in order to evaluate the performance of the proposed GA. The results obtained from the GA are compared with the results from an exact technique, thus providing complete information about the performance of the heuristic in terms of solution quality.     

基于船时效率的岸桥配置优化

在集装箱码头系统中,对船舶进行有效的岸桥配置有助于缓解岸边资源紧张的现状,提高码头的运营效率。针对连续泊位下动态到港船舶的泊位分配和岸桥配置的集成优化问题,对船舶的岸桥配置进行基于船时效率的动态调整,以最小化包括船舶延迟靠泊成本、偏离偏好泊位成本、延迟离港成本和岸桥重新配置成本在内的总成本为目标建立模型,并根据基于船时效率的岸桥配置的调整规则设计了启发式算法,结合遗传算法（GA）对问题进行求解。最终通过算例分析,验证了提出的模型和算法在解决实际港口中泊位分配和岸桥配置问题上的有效性,并通过与未考虑岸桥配置进一步调整的传统GA计算的结果进行比较,证实了提出算法的优化效果。     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Hybrid rolling-horizon optimization for berth allocation and quay crane assignment with unscheduled vessels

Port operations usually suffer from uncertainties, such as vessels’ arrival time and handling time and unscheduled vessels. To address this, this study presents a dynamic berth allocation and crane assignment specific problem (BACASP) when unscheduled vessels arrive at the port, which is branded the berth allocation and quay crane assignment specific problem with unscheduled vessels (UBACASP). A rolling-horizon based method is proposed to decompose the UBACASP into a multi-stage static decision BACASP, wherein a rescheduling margin-based hybrid rolling-horizon optimization method is developed by incorporating the event-driven and periodical rolling-horizon strategies as the urgency of dynamic events is evaluated. In each rolling horizon, a mixed integer linear programming model (MILP) is presented for the BACASP to minimize the total port stay time of vessels and the penalties of delays associated with the spatial and temporal constraints, such as the length of continuous berth, number of quay cranes (QCs) and non-crossing of QCs. A discretization strategy is designed to divide the continuous berth into discrete segments, and convert the BACASP to a discrete combinatorial optimization problem, which is efficiently solved by the proposed adaptive large neighborhood search algorithm (ALNS). Case studies with different problem characteristics are conducted to prove the effectiveness of the solution methods proposed in this study. Moreover, the performances of the ALNS and the existing methods for solving the BACASP are compared, and the advantages and disadvantages of different rolling strategies under different degrees of uncertainties are deeply analyzed.     

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.     

A fast heuristic for quay crane scheduling with interference constraints

This paper considers the problem of scheduling quay cranes which are used at sea port container terminals to load and unload containers. This problem is studied intensively in a recent stream of research but still lacks a correct treatment of crane interference constraints. We present a revised optimization model for the scheduling of quay cranes and propose a heuristic solution procedure. At its core a Branch-and-Bound algorithm is applied for searching a subset of above average quality schedules. The heuristic takes advantage from efficient criteria for branching and bounding the search with respect to the impact of crane interference. Although the used techniques are quite standard, the new heuristic produces much better solutions in considerably shorter run times than all algorithms known from the literature.     

潮汐影响下泊位和岸桥双目标联合调度仿真

针对集装箱船舶大型化导致的港口航道现有水深无法满足大型船舶安全吃水深度,需要借助潮水上涨进出航道的现状,研究了潮汐影响下连续型泊位和动态岸桥联合调度问题。建立了以最小化船舶周转时间和岸桥在船舶间移动次数的双目标混合整数规划模型。基于问题特点,设计了Epsilon约束精确算法和带精英策略的快速非支配排序遗传算法(NSGA-Ⅱ)分别求解小规模和大规模算例的Pareto最优解集,所得结果验证了模型和算法的正确性与有效性。通过潮汐周期灵敏度分析评估了潮汐周期长度对岸桥工作效率和港口服务质量的影响。仿真结果表明,建立的优化模型能够帮助港口企业有效降低潮汐对生产作业的影响,同时提供一组高效的Pareto最优泊位岸桥调度方案提高工作效率和经济效益。     

Modeling berth allocation and quay crane assignment considering QC driver cost and operating efficiency

Due to high labour costs and difference of QC driver’s handling efficiency existing between day and night, factors concerning QC drivers can significantly impact the schedule of berth allocation and quay crane assignment. This paper tackles the berth allocation and quay crane assignment problem considering QC driver cost, difference of the operating efficiency and performance-related pay between day and night. How QC driver-related factors affect the schedules is analyzed, and the objective composition including QC driver cost is given. A mixed integer programming model with model acceleration algorithms is developed for the proposed problem, and a meta-heuristic framework including a three-stage algorithm is proposed for solving the problem. Numerical experiments are conducted to validate the effectiveness of the proposed model and performance of the meta-heuristic approach, leading to a multitude of managerial insights.     

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.     

桥吊可动态分配的连续泊位分配问题算法

研究在允许桥吊动态分配的情况下集装箱码头的连续泊位动态分配问题,并建立以船舶在港时间最小为目标的动态泊位分配模型;然后基于兄弟-儿子方法对船舶的位置进行调整以规划桥吊使桥吊不交叉。在相同算例下,比现有方法得到的船舶在港时间更少,从而验证了模型及算法的有效性。     

干扰约束下考虑分组作业面的岸桥AGV联合调度

为解决自动化码头海侧多阶段设备作业的协调问题,加快集装箱在码头内部的周转过程。考虑干扰约束下分组作业面的的岸桥自动导引小车（AGV）联合调度问题。以岸桥、AGV完工时间和AGV等待时间加权总和最小为目标,考虑岸桥实际操作中的干扰约束与AGV堵塞等待等情况,建立岸桥与AGV联合调度优化模型。提出岸桥动态调度与AGV分组作业面调度模式,设计不同规模的算例,并采用遗传算法（GA）进行求解,将计算结果与传统调度模式进行对比。结果表明,该算法能有效提高岸桥与AGV作业效率,降低AGV的等待时间与堵塞次数,为码头实际作业提供依据。     

基于时间窗的双小车岸桥与AGV协调调度研究

针对自动化集装箱码头（automated container terminals,ACT）的自动导引车 ( automatic guided vehicle,AGVs) 与自动化双小车岸桥（double-trolley quay cranes,QCs）协调调度优化问题,以上海洋山港四期工程的实际布局和装卸工艺为基础,考虑装卸同时进行条件下以最小化任务总完工时间为目标,建立带有时间窗约束的双小车岸桥和AGV的协调调度模型,并采用遗传算法对实际算例进行求解。通过灵敏度分析,验证了该模型及算法的有效性,并对遗传算法参数设置的有效性进行检验。结果分析表明,该调度方法有助于提高自动化集装箱码头的作业效率,减少集装箱船的在港时间,提高码头竞争力。     

单船岸桥分配与调度集成优化模型

针对集装箱码头泊位确定条件下的单船岸桥(QC)分配和调度问题,建立了线性规划模型.模型以船舶在泊作业时间最短为目标,考虑多岸桥作业过程中的干扰等待时间与岸桥间的作业量均衡,并设计了嵌入解空间切割策略的改进蚁群优化(IACO)算法进行模型求解.实验结果表明:与可用岸桥全部投放使用的方法相比,所提模型与算法求得结果平均能够节省31.86%的岸桥资源;IACO算法与Lingo求得的结果相比,船舶在泊作业时间的平均偏差仅为5.23%,但CPU处理时间平均降低了78.7%,表明了所提模型与算法的可行性和有效性.