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

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

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

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

基于矩阵式遗传算法的进出口集装箱堆场箱位分配策略

为提高集装箱码头堆场系统的运作效率,本文针对集装箱码头进出口堆场的空间分配问题,建立了在“作业面”作业模式下以集卡水平运输距离最短为目标,考虑各箱位作业量均衡的集装箱箱位分配模型,对计划时段内的进出口箱箱位分配进行全局优化．采用矩阵式的实数编码方式的遗传算法对模型进行了求解,使用最优解保存策略保证了最终的优化结果．最后通过仿真算例,验证了本文所建立的箱位分配模型对优化堆场空间资源分配,提高进出口箱流转速度的适用性．     

Alternative algorithms for the optimization of a simulation model of a multimodal container terminal

Multimodal container terminals (MMCTs) are very complex and consequently require synchronization and balancing of container transfers at each node. The problem being investigated is the minimization of ship delays at the port by considering handling and travelling time of containers from the time the ship arrives at port until all the containers from that ship leave the port. When dealing with export containers, the problem would be that of the handling and travelling time of the containers from when they first arrive at the port until the ship carrying the containers departs from the port. Owing to the dynamic nature of the environment, a large number of timely decisions have been reviewed in accordance with the changing conditions of the MMCTs. The model has been run and tested with a small-size problem using CPLEX. A more realistic model is extremely difficult to solve and is in fact proven to be computationally intractable (NP-hard). Metaheuristics have been developed to deal with the intractability so that near-optimal solutions could be obtained in reasonable time.     

An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

This paper presents the case study of an Italian carrier, Grendi Trasporti Marittimi, which provides freight transportation services by trucks and containers. Its trucks deliver container loads from a port to import customers and collect container loads from export customers to the same port. In this case study, all import customers in a route must be serviced before all export customers, each customer can be visited more than once and containers are never unloaded or reloaded from the truck chassis along any route. We model the problem using an Integer Linear Programming formulation and propose an Adaptive Guidance metaheuristic. Our extensive computational experiments show that the adaptive guidance algorithm is capable of determining good-quality solutions in many instances of practical or potential interest for the carrier within 10?min of computing time, whereas the mathematical formulation often fails to provide the first feasible solution within 3?h of computing time.     

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.      

Decision support system for container terminal planning

In this paper we describe a decision support system for capacity planning of container terminals. Typical elements of a container terminal are a quay, cranes,a stack yard and trucks for transport of containers between the quay and the stack yard and vice versa. For each of these elements we can devise models to describe the performance. The decision support system combined a heuristic analysis of these models to a global model to study the interaction between the elements of a container terminal.     

A mathematical model of inter-terminal transportation

We present a novel integer programming model for analyzing inter-terminal transportation (ITT) in new and expanding sea ports. ITT is the movement of containers between terminals (sea, rail or otherwise) within a port. ITT represents a significant source of delay for containers being transshipped, which costs ports money and affects a port’s reputation. Our model assists ports in analyzing the impact of new infrastructure, the placement of terminals, and ITT vehicle investments. We provide analysis of ITT at two ports, the port of Hamburg, Germany and the Maasvlakte 1 & 2 area of the port of Rotterdam, The Netherlands, in which we solve a vehicle flow combined with a multi-commodity container flow on a congestion based time–space graph to optimality. We introduce a two-step solution procedure that computes a relaxation of the overall ITT problem in order to find solutions faster. Our graph contains special structures to model the long term loading and unloading of vehicles, and our model is general enough to model a number of important real-world aspects of ITT, such as traffic congestion, penalized late container delivery, multiple ITT transportation modes, and port infrastructure modifications. We show that our model can scale to real-world sizes and provide ports with important information for their long term decision making.     

Increasing the operational efficiency of container terminals in Australia

This paper discusses the major factors influencing the transfer efficiency of rail container terminals, as measured by the throughput time of containers. An analytically based simulation model is designed to describe container progress in the system. Cyclic heuristic rules for equipment assignment are applied and a new heuristic rule is developed to dispatch trains to tracks. The simulation model combined with the heuristic rules is used to address a number of specific objectives of the study. Different performance measures are applied and the impact that the train-to-track despatching and the handling equipment assignment can have on the measures is established. Validation and testing of models make use of data from Acacia Ridge Terminal, Brisbane, Australia.     

Container stowage planning: a methodology for generating computerised solutions

The container stowage problem concerns the suitable placement of containers in a container-ship on a multi-port journey; it requires consideration of the consequences each placement has on decisions at subsequent ports. A methodology for the automatic generation of computerised solutions to the container stowage problem is shown; objective functions that provide a basis for evaluating solutions are given in addition to the underlying structures and relationships that embody this problem. The methodology progressively refines the placement of containers within the cargo-space of a container ship until each container is specifically allocated to a stowage location. The methodology embodies a two stage process to computerised planning, that of a generalised placement strategy and a specialised placement procedure. Heuristic rules are built into objective functions for each stage that enable the combinatorial tree to be explored in an intelligent way, resulting in good, if not optimal, solutions for the problem in a reasonable processing time.     

不确定箱量下内河集装箱班轮航线动态配载决策

内河集装箱班轮运输中海关抽检可导致外贸箱箱量不断发生变化,班轮航线配载需要动态决策。基于滚动调度策略,将当前港口的配载决策按随机事件划分为多个阶段,以最小化班轮堆栈占用数量和相邻阶段间配载计划偏差为目标,构建单港口单阶段的配载决策模型,进而滚动实现班轮航线动态配载决策。基于大邻域搜索思想设计一种包含整数规划、破坏器与修复器的精确启发式算法,实现港口多阶段滚动配载。基于真实场景的算例研究表明,在优化堆栈占用数量方面,模型与算法之间差异不大,但在考虑相邻阶段间配载计划偏差时,算法的求解结果要优于模型。因此,模型与算法可用来辅助实现不确定箱量下内河集装箱班轮航线动态配载决策,且算法表现更优,可实现配载计划对不确定箱量的鲁棒吸收。     

Shipping Container Logistics and Allocation

A major shipping company in Hong Kong is faced with several logistical and allocation problems. It needs to find a better way to allocate empty containers that are transported from the Middle East to ports in the Far East, subject to vessel schedules and capacities. It needs to know what to do when the supply of empty containers is less than the demand, and it needs to determine the mix of container types that the company should maintain in the long run. To deal with these challenges, a simulation model of the shipping company's operational activities was developed. Heuristic search was employed to identify the policies that yield the lowest operating cost in terms of leasing, storage, pick-up, drop-off and other charges. What makes the problem difficult is that the forecasts of future export movement as well as the demand for empty containers change continually and the company is faced with the possibility of lost sales if containers are not available when requested by customers. This study provided insights that resulted in substantial savings to the shipping company while increasing customers' satisfaction.     

Modelling of containerized air cargo forwarding problems under uncertainty

This paper examines air container renting and cargo loading problems experienced by freight forwarding companies. Containers have to be booked in advance, in order to obtain discounted rental rates from airlines; renting or returning containers on the day of shipping will incur a heavy penalty. We first propose a mixed-integer model for the certain problem, in which shipment information is known with certainty, when booking. We then present a two-stage recourse model to handle the uncertainty problem, in which accurate shipment information cannot be obtained when booking, and all cargoes have to be shipped without delay. The first-stage decision is made at the booking stage, to book specific numbers of different types of containers. The second-stage decision is made on the day of shipping, depending on the extent to which the uncertainty has been realized. The decisions include number of additional containers of different types that are required to be rented, or the number of containers to be returned, under the scenario that might occur on the day of shipping. We then extend the recourse model into a robust model for dealing with the situation in which cargoes are allowed to be shipped later. The robust model provides a quantitative method to measure the trade-off between risk and cost. A series of experiments demonstrate the effectiveness of the robust model in dealing with risk and uncertainty.     

Optimal Short Horizon Distribution Operations in Reusable Container Systems

Manufacturers in many countries are facing increasing market pressures to use returnable containers. Few studies address the day-to-day operational problems of controlling production and distribution that are inherent in closed systems that reuse containers. In this paper we present a formulation of an optimal configuration of this type of system. In particular, we model the reusable bottle production and distribution activities of a large soft drink manufacturer located in Mexico City, Mexico. Two types of operational research models are combined to form the overall optimization system. A pair of linear programs (one aggregated, the other disaggregated) determines a master plan that is subsequently fined-tuned on a shift-by-shift basis using a difference equation simulation model. The simulation model mimics the heuristic ‘rules of thumb’ used by production planners for product distribution and container reuse planning. The results of our study indicate that this formulation provides a timely response in the field to key operational problems addressed by no previous approach. Included are better organizational control (through providing one-week production and distribution plans), feedback allowing modification of heuristic rules previously used in controlling the distribution of product and container reuse, and improvement in inventory behaviour such as avoiding shortages. These improvements have resulted in considerable market share gains since the models were implemented.     

大窑湾入境集装箱量及疫情集装箱量的模糊预测研究

作为国际海运和物流业的主要装载工具集装箱是入境统计以及检验检疫的主要对象.按特定规律统计的集装箱量时间序列既有一定的统计规律,又有较大的随机性.采用模糊时间序列方法,通过构造论域、模糊集以及提出多重计算规则,对2005年6月至2012年10月大窑湾入境集装箱量、疫情集装箱量,以及疫情与入境集装箱量比值时间序列进行了模糊分析与预测.预测值与实际值的比较说明了算法的有效性.预测值与实际值的平均绝对误差、平均绝对百分误差从整体上揭示了时间序列自身的模糊性和模型的合理性.     

Optimization of container inspection strategy via a genetic algorithm

It is estimated that 90% of the world’s freight is moved as containerized cargo, with over 125 million TEUs (Twenty foot Equivalent Units) of container being shipped by 2010. To inspect this volume of cargo for explosives, drugs or other contraband is a daunting challenge. This paper presents an optimization technique for developing an inspection strategy that will provide a specified detection rate for containers containing contraband at a minimum cost. Nested genetic algorithms are employed to optimize the topology of an inspection strategy decision tree, the placement of sensors on the tree and the sensor thresholds which partition suspicious containers (containers believed to contain contraband) from innocuous containers (containers which are believed to be free of contraband). The results of this optimization technique are compared to previously published techniques.     

Conservative allocation models for outbound containers in container terminals

This paper examines location assignment for outbound containers in container terminals. It is an extension to the previous modeling work of Kim et al. (2000) and Zhang et al. (2010). The previous model was an “optimistic” handling way and gave a moderate punishment for placing a lighter container onto the top of a stack already loaded with heavier containers. Considering that the original model neglected the stack height and the state-changing magnitude information when interpreting the punishment parameter and hid too much information about the specific configurations for a given stack representation, we propose two new “conservative” allocation models in this paper. One considers the stack height and the state-changing magnitude information by reinterpreting the punishment parameter and the other further considers the specific configurations for a given stack representation. Solution qualities for the “optimistic” and the two “conservative” allocation models are compared on two performance indicators. The numerical experiments indicate that both the first and second “conservative” allocation models outperform the original model in terms of the two performance indicators. In addition, to overcome computational difficulties encountered by the dynamic programming algorithm for large-scale problems, an approximate dynamic programming algorithm is presented as well.     

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.     

Principles of Combinatorial Optimization Applied to Container-Ship Stowage Planning

In this paper, a methodology for generating automated solutions to the container stowage problem is shown. The methodology was derived by applying principles of combinatorial optimization and, in particular, the Tabu Search metaheuristic. The methodology progressively refines the placement of containers, using the Tabu search concept of neighbourhoods, within the cargo-space of a container ship until each container is specifically allocated to a stowage location. Heuristic rules are built into objective functions for each stage that enable the combinatorial tree to be explored in an intelligent way, resulting in good, if not optimal, solutions for the problem in a reasonable processing time.     

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.