预倒出口箱区的多场桥调度优化

在集装箱出口箱区堆场的实际作业中,常将待提箱提前翻倒至一空闲箱区,使其装船前以船舶配载图的倒序堆垛,以提高装船效率。为提高初始出口箱区的预翻作业效率,针对该箱区的多场桥调度优化问题进行研究。以实施预翻作业的某一出口箱区为研究对象,在船舶配载图已知的前提下,考虑作业场桥间保持安全距离且不可跨越的条件,兼顾满足经验翻箱规则等现实约束,侧重作业过程中实时翻箱,构建了以场桥作业总行走时间最小为优化目标的线性规划模型,并设计了分支定价算法。在算例实验中,通过与非实时预翻箱方案、FCFS方案以及下界进行对比,验证了模型及算法的有效性,可为集装箱码头出口箱堆场的场桥调度提供参考。     

Storage space allocation models for inbound containers in an automatic container terminal

This paper studies the problem of improving the operations efficiency for retrieving inbound containers in a modern automatic container terminal. In the terminal, when an external truck arrives to collect a container stored in a specific container block, it waits at one end of the block where an automatic stack crane will retrieve the container and deliver it to the truck. With the aim of reducing the expected external truck waiting time which is determined by how the containers are stored in a block, we propose two correlated approaches for the operations efficiency improvement, (1) by designing an optimized block space allocation to store the inbound containers after they are discharged from vessels, and (2) by conducting overnight re-marshaling processes to re-organize the block space allocation after some containers are retrieved. For the block space allocation problem, we consider three optimization models under different strategies of storing containers, namely, a non-segregation model, a single-period segregation model, and a multiple-period segregation model. Optimal solution methods are proposed for all three models. For the re-marshaling problem with a given time limit, we find that the problem is NP-hard and develop a heuristic algorithm to solve the problem. We then use simulation to validate our models and solution approaches. Simulation results reveal important managerial insights such as the advantage of the multiple-period segregation over the myopic single-period segregation, the possibility of overflow of the segregation model, and the benefit of re-marshaling.     

Yard crane scheduling in port container terminals

Yard cranes are the most popular container handling equipment for loading containers onto or unloading containers from trucks in container yards of land scarce port container terminals. However, such equipment is bulky, and very often generates bottlenecks in the container flow in a terminal because of their slow operations. Hence, it is essential to develop good yard crane work schedules to ensure a high terminal throughput. This paper studies the problem of scheduling a yard crane to perform a given set of loading/unloading jobs with different ready times. The objective is to minimize the sum of job waiting times. A branch and bound algorithm is proposed to solve the scheduling problem optimally. Efficient and effective algorithms are proposed to find lower bounds and upper bounds. The performance of the proposed branch and bound algorithm is evaluated by a set of test problems generated based on real life data. The results show that the algorithm can find the optimal sequence for most problems of realistic sizes.     

Stowage planning in maritime container transportation

We consider a stowage-planning problem of arranging containers on a container ship in the maritime transportation system. Since containers are accessible only from the top of the stack, temporary unloading and reloading of containers, called shifting, is unavoidable if a container required to be unloaded at the current port is stacked under containers to be unloaded at later ports on the route of the ship. The objective of the stowage planning problem is to minimize the time required for shifting and crane movements on a tour of a container ship while maintaining the stability of the ship. For the problem, we develop a heuristic solution method in which the problem is divided into two subproblems, one for assigning container groups into the holds and one for determining a loading pattern of containers assigned to each hold. The former subproblem is solved by a greedy heuristic based on the transportation simplex method, while the latter is solved by a tree search method. These two subproblems are solved iteratively using information obtained from solutions of each other. To see the performance of the suggested algorithm, computational tests are performed on problem instances generated based on information obtained from an ocean container liner. Results show that the suggested algorithm works better than existing algorithms.     

Modeling and solution of the joint quay crane and truck scheduling problem

This paper addresses the joint quay crane and truck scheduling problem at a container terminal, considering the coordination of the two types of equipment to reduce their idle time between performing two successive tasks. For the unidirectional flow problem with only inbound containers, in which trucks go back to quayside without carrying outbound containers, a mixed-integer linear programming model is formulated to minimize the makespan. Several valid inequalities and a property of the optimal solutions for the problem are derived, and two lower bounds are obtained. An improved Particle Swarm Optimization (PSO) algorithm is then developed to solve this problem, in which a new velocity updating strategy is incorporated to improve the solution quality. For small sized problems, we have compared the solutions of the proposed PSO with the optimal solutions obtained by solving the model using the CPLEX software. The solutions of the proposed PSO for large sized problems are compared to the two lower bounds because CPLEX could not solve the problem optimally in reasonable time. For the more general situation considering both inbound and outbound containers, trucks may go back to quayside with outbound containers. The model is extended to handle this problem with bidirectional flow. Experiment shows that the improved PSO proposed in this paper is efficient to solve the joint quay crane and truck scheduling problem.     

基于贪婪禁忌搜索算法的垂岸式堆场出口箱装船翻箱研究

基于垂岸式自动化集装箱码头不同装船周期出口集装箱堆场多贝位混合堆存、场桥大车在贝位间频繁移动取箱装船特点,考虑装船发箱时场桥移动等操作时间及翻箱取箱次数对出口箱装船效率和连续性影响,建立多贝位出口箱装船堆场翻箱模型,提出两阶段贪婪禁忌搜索算法,将翻箱规则嵌入算法中,有效限制算法时间和解空间增长速度。通过算例,将提出的翻箱规则与现有常见翻箱规则进行对比,验证模型及算法的有效性与实用性。结果表明,提出的模型和算法可以在合理的求解时间内输出较优的翻箱方案,减少装船时场桥发箱作业时间,提高装船作业效率。     

考虑翻箱的场桥调度和提箱集卡数量的集成优化

在集装箱码头的进口箱堆场中,码头预约机制、待提箱的实时位置和场桥作业调度方案是制约堆场作业效率和堵塞情况的关键。为缓解进口箱堆场的拥塞情况并提高作业效率,在固定的预约时段内,考虑实时压箱量最少的翻箱规则,兼顾场桥间不可跨越和保持安全间距等现实约束,以场桥最长完工时间最小为目标,构建数学优化模型,设计了嵌入修复算子的改进遗传算法用于求解;通过算例实验验证了算法的有效性和方案的优越性,可为堆场实际作业提供决策参考。     

Optimal berth allocation and time-invariant quay crane assignment in container terminals

Due to the dramatic increase in the world’s container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.     

Heuristics with a new block strategy for the single and multiple containers loading problems

A heuristic algorithm using new block strategy for the heterogeneous single and multiple containers loading problem (CLP) is proposed in this paper. In order to solve the single CLP, this algorithm fills unused spaces with the homogeneous load-blocks of identically oriented boxes and splits residual space into three child-spaces starting with an empty container. An initial container pattern is first built applying this approach recursively until all boxes are stowed or no unused spaces are left. And then, alternative container patterns are generated after replacing the load-blocks of the pattern-determining spaces in the initial container pattern with the alternative-blocks previously stored. Finally, an improvement procedure compares these alternatives with the initial container pattern to identify an improved container pattern. An algorithm for the multiple CLP uses the single CLP algorithm to generate an initial solution and uses improvement procedures to improve the initial solution. Numerical experiments with 715 test cases for the single CLP and 47 test cases for the multiple the CLP revealed the excellent performance of this algorithm.     

The time-dependent capacitated profitable tour problem with time windows and precedence constraints

We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances.     

Scheduling crossover cranes at container terminals during seaside peak times

This paper deals with crane scheduling in a block of a container terminal equipped with two crossover cranes. We concentrate on the situation when all requests in this block refer to the seaside. This seaside peak time occurs when a container ship is berthed and has to be served as quickly as possible because berthing time is a major cost driver for both, the shipping company and the port operator. In this case, the two cranes highly interfere. We formulate this problem as a MIP, prove its \(\mathcal {NP}\)-hardness and introduce a lower bound. Further, we provide several heuristic solution procedures based on priority rules. A comparison of all procedures concludes this paper and gives insights on how to solve this problem in practice.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

A local branching-based algorithm for the quay crane scheduling problem under unidirectional schedules

The quay crane scheduling problem (QCSP) is at the basis of a major logistic process in maritime container terminals: the process of discharging/loading containers from/on berthed vessels. Several groups of containers, laying in one or more stowage portions of a containership, have to be assigned to multiple cranes and discharge/loading operations have to be optimally sequenced, under some complicating constraints imposed by the practical working rules of quay cranes. The QCSP has been the object of a great deal of research work since the last decade and it is focused in this paper, with the aim of consolidating a promising solution approach based upon the combination of specialized branch & bound (B&B) and heuristic algorithms. A cost-effective solution technique that incorporates the local branching method within a refined B&B algorithm is proposed and its effectiveness is assessed by numerical comparisons against the latest algorithm available in literature.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

集装箱码头堆场翻箱与外集卡提箱顺序同步优化方法

针对集装箱码头提箱作业过程中,由于外集卡的提箱顺序与目标箱在堆场的堆存位置不匹配导致大量翻箱这一难题,以码头的作业成本和外集卡的延误成本之和最小为目标,建立堆场翻箱与外集卡提箱顺序同步优化模型,优化外集卡的提箱顺序、龙门吊的任务分配以及翻箱方案。设计基于动态规划的启发式算法求解模型,并利用算例对模型与算法的有效性进行了验证。结果表明:与目前码头普遍采用的提箱方式相比,通过调整外集卡提箱顺序并同时优化翻箱方案以及龙门吊的任务分配可以降低堆场翻箱率,减少龙门吊的移动成本,从而节省提箱作业的总成本。     

Real-Time Solution of Bi-Level Optimal Control Problems

Bi-level optimal control problems are presented as an extension to classical optimal control problems. Hereby, additional constraints for the primary problem are considered, which depend on the optimal solution of a secondary optimal control problem. A demanding problem is the numerical complexity, since at any point in time the solution of the optimal control problem as well as a complete solution of the secondary problem have to be determined. Hence we deal with two dependent variables in time. The numerical solution of the bi-level problem is illustrated by an application of a container crane. Jerk and energy optimal trajectories with free final time are calculated under the terminal condition that the crane system comes to be at rest at a predefined location. In enlargement additional constraints are investigated to ensure that the crane system can be brought to a rest position by a safety stop at a free but admissible location in minimal time from any state of the trajectory. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal location of dwell points in a single loop AGV system with time restrictions on vehicle availability

Since the workload of a manufacturing system changes over time, the material handling equipment used in the facility will be idle at certain time intervals to avoid system overload. In this context, a relevant control problem in operating an automated guided vehicle (AGV) system is where to locate idle vehicles. These locations, called dwell points, establish the response times for AVG requests. In this article, a dynamic programming algorithm to solve idle vehicle positioning problems in unidirectional single loop systems is developed to minimize the maximum response time considering restrictions on vehicle time available to travel and load/unload requests. This polynomial time algorithm finds optimal dwell points when all requests from a given pick-up station are handled by a single AGV. The proposed algorithm is used to study the change in maximum response time as a function of the number of vehicles in the system.     

基于角点处扭矢构造双三次Coons曲面的一种优化方法

本文针对矩形网格角点处的扭矢采用优化方法构造双三次Coons曲面,提出一种新的优化准则来确定角点处的扭矢.首先,通过变分原理,考虑曲面导矢的极小化问题转化的Euler-Lagrange偏微分方程,将该方程应用于每一个Coons块的角点上,引入一个新的极小化问题,其解是Euler-Lagrange偏微分方程的近似最优解.然后,建立一个具有块三对角系数矩阵的线性方程组来求解新的极小化问题.该系数矩阵可以表示为两个相同的形式特殊的矩阵的Kronnecker积,进而可以证明其非奇异性.最后,数值实验验证本文方法的稳定性和有效性.     

Modelling and Optimal Receding-horizon Control of Maritime Container Terminals

The main objective of this paper consists in modelling, optimizing, and controlling container transfer operations inside intermodal terminals. More specifically, maritime container terminals are here considered, involving three kinds of transportation modes, i.e., maritime, rail, and road transport. Generally speaking, an intermodal port terminal can be seen as a system of container flows with two interfaces, towards the hinterland and towards the sea, respectively. Moreover, inside a terminal, unloading operations of inbound containers, container storage, and loading operations of outbound containers are carried out. A simple model for maritime container terminals is proposed in this paper. In the model, a system of queues represents the standing of containers and their movements inside the terminal. The dynamic evolutions of these queues are described by discrete-time equations, where the state variables represent the queue lengths and the control variables take into account the utilization of terminal resources such as load/unload handling rates. On the basis of the proposed model, an optimization problem is defined that consists in minimizing the transfer delays of containers in the terminal. The problem is stated as an optimal control problem whose solution is sought by adopting a receding-horizon strategy.      

The fleet size and mix problem for capacitated arc routing

There have been several attempts to solve the capacitated arc routing problem with m vehicles starting their tours from a central node. The objective has been to minimize the total distance travelled. In the problem treated here we also have the fixed costs of the vehicles included in the objective function. A set of vehicle capacities with their respective costs are used. Thus the objective function becomes a combination of fixed and variable costs. The solution procedure consists of four phases. In the first phase, a Chinese or rural postman problem is solved depending on whether all or some of the arcs in the network demand service with the objective of minimizing the total distance travelled. It results in a tour called the giant tour. In the second phase, the giant tour is partitioned into single vehicle subtours feasible with respect to the constraints. A new network is constructed with the node set corresponding to the arcs of the giant tour and with the arc set consisting of the subtours of the giant tour. The arc costs include both the fixed and variable costs of the subtours. The third phase consists of solving the shortest path problem on this new network to result in the least cost set of subtours represented on the new network. In the last phase a postprocessor is applied to the solution to improve it. The procedure is repeated for different giant tours to improve the final solution. The problem is extended to the case where there can be upper bounds on the number of vehicles with given capacities using a branch and bound method. Extension to directed networks is given. Some computational results are reported.