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.     

A Genetic Algorithm with a Compact Solution Encoding for the Container Ship Stowage Problem

The purpose of this study is to develop an efficient heuristic for solving the stowage problem. Containers on board a container ship are stacked one on top of the other in columns, and can only be unloaded from the top of the column. A key objective of stowage planning is to minimize the number of container movements. A genetic algorithm technique is used for solving the problem. A compact and efficient encoding of solutions is developed, which reduces significantly the search space. The efficiency of the suggested encoding is demonstrated through an extensive set of simulation runs and its flexibility is demonstrated by successful incorporation of ship stability constraints.     

Tabu Search for the planar three-index assignment problem

Tabu Search is a very effective method for approximately solving hard combinatorial problems. In the current work we implement Tabu Search for solving the Planar Three-Index Assignment Problem. The problem deals with finding the minimum cost assignment between elements of three distinct sets demanding that every pair of elements, each representing a different set, appears in the same solution exactly once. The solutions of the problems correspond to Latin squares. These structures form the basis of the move generation mechanism employed by the Tabu Search procedures. Standard Tabu Search ideas such as candidate move list, variable tabu list size, and frequency-based memory are tested. Computational results for a range of problems of varying dimensions are presented.     

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.     

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

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

A hybrid genetic algorithm for the container loading problem

This paper presents a hybrid genetic algorithm (GA) for the container loading problem with boxes of different sizes and a single container for loading. Generated stowage plans include several vertical layers each containing several boxes. Within the procedure, stowage plans are represented by complex data structures closely related to the problem. To generate offspring, specific genetic operators are used that are based on an integrated greedy heuristic. The process takes several practical constraints into account. Extensive test calculations including procedures from other authors vouch for the good performance of the GA, above all for problems with strongly heterogeneous boxes.     

A Constraint Programming model for fast optimal stowage of container vessel bays

Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for large container vessels within a few minutes. It decomposes the problem into a master planning phase that distributes the containers to bay sections and a slot planning phase that assigns containers of each bay section to slots. In this paper, we focus on the slot planning phase of this approach and present a Constraint Programming and Integer Programming model for stowing a set of containers in a single bay section. This so-called slot planning problem is NP-hard and often involves stowing several hundred containers. Using state-of-the-art constraint solvers and modeling techniques, however, we were able to solve 90% of 236 real instances from our industrial collaborator to optimality within 1 second. Thus, somewhat to our surprise, it is possible to solve most of these problems optimally within the time required for practical application.     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

Tabu Search for Frequency Assignment in Mobile Radio Networks

The main goal of the Frequency Assignment Problem in mobile radio networks consists of assigning a limited number of frequencies to each radio cell in a cellular network while minimizing electromagnetic interference due to the reuse of frequencies. This problem, known to be NP-hard, is of great importance in practice since better solutions will allow a telecommunications operator to manage larger cellular networks. This paper presents a new Tabu Search algorithm for this application. The algorithm is tested on realistic and large problem instances and compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.     

基于遗传算法与贪婪策略的多港口集装箱配载研究

在物流运输行业中,集装箱运输已经成为我国长江沿岸各大港口的主要运输业务。集装箱的处理流程,尤其是集装箱的配载过程直接影响着班轮的运输效率,配载方案的制定对班轮运输起着至关重要的作用。本文针对多港口集装箱船的配载情况,利用CPLEX对该线性规划问题进行求解,并设计遗传算法和贪婪算法对长江沿岸多港口集装箱船配载情形进行对比。通过仿真实验,在小规模时遗传算法与CPLEX求解的精确解相同,验证了遗传算法的有效性。并且在大规模运输情形下,遗传算法得出的结果明显优于贪婪策略,进一步说明了遗传算法是行之有效的。得出的解决方案降低了班轮公司的运输成本,提高了港口的工作效率,对我国长江沿岸港口集装箱配载计划的制定具有一定的指导作用。     

A decomposition heuristics for the container ship stowage problem

In this paper we face the problem of stowing a containership, referred to as the Master Bay Plan Problem (MBPP); this problem is difficult to solve due to its combinatorial nature and the constraints related to both the ship and the containers. We present a decomposition approach that allows us to assign a priori the bays of a containership to the set of containers to be loaded according to their final destination, such that different portions of the ship are independently considered for the stowage. Then, we find the optimal solution of each subset of bays by using a 0/1 Linear Programming model. Finally, we check the global ship stability of the overall stowage plan and look for its feasibility by using an exchange algorithm which is based on local search techniques. The validation of the proposed approach is performed with some real life test cases. This work has been developed within the research area: “The harbour as a logistic node” of the Italian Centre of Excellence on Integrated Logistics (CIELI) of the University of Genoa, Italy     

A Tabu search heuristic for the generalized assignment problem

This paper considers the generalized assignment problem (GAP). It is a well-known NP-hard combinatorial optimization problem that is interesting in itself and also appears as a subproblem in other problems of practical importance. A Tabu search heuristic for the GAP is proposed. The algorithm uses recent and medium-term memory to dynamically adjust the weight of the penalty incurred for violating feasibility. The most distinctive features of the proposed algorithm are its simplicity and its flexibility. These two characteristics result in an algorithm that, compared to other well-known heuristic procedures, provides good quality solutions in competitive computational times. Computational experiments have been performed in order to evaluate the behavior of the proposed algorithm.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

Optimization of a high-speed placement machine using tabu search algorithms

Combinatorial optimization represents a wide range of real-life manufacturing optimization problems. Due to the high computational complexity, and the usually high number of variables, the solution of these problems imposes considerable challenges. This paper presents a tabu search approach to a combinatorial optimization problem, in which the objective is to maximize the production throughput of a high-speed automated placement machine. Tabu search is a modern heuristic technique widely employed to cope with large search spaces, for which classical search methods would not provide satisfactory solutions in a reasonable amount of time. The developed TS strategies are tailored to address the different issues caused by the modular structure of the machine. This revised version was published online in June 2006 with corrections to the Cover Date.     

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container.We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.     

An architecture for solving sequencing and resource allocation problems using approximation methods

In the search for better optimisation techniques, new methods that mix artificial intelligence and operations research have emerged. Search heuristics are integrated with optimisation algorithms. Approximation methods, like Hill Climbing, Simulated Annealing, and Tabu Search, that have been used with success in combinatorial optimisation problems, are one of such research lines. This paper presents the key elements of approximation methods and combines them in a tool appropriate for solving sequencing and resource allocation problems. The system permits a clear division between problem specification and problem solving, allowing a declarative representation and therefore minimising developing costs. The key issues discussed in this work are a model for representing this class of problems in a standard form, a set of strategies for applying the approximation methodology, and an expert system that dynamically manipulates the strategies' parameters.     

A prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

Optimization of container process at seaport terminals

Seaport container terminals are an important part of the logistics systems in international trades. This paper investigates the relationship between quay cranes, yard machines and container storage locations in a multi-berth and multi-ship environment. The aims are to develop a model for improving the operation efficiency of the seaports and to develop an analytical tool for yard operation planning. Due to the fact that the container transfer times are sequence-dependent and with the large number of variables involved, the proposed model cannot be solved in a reasonable time interval for realistically sized problems. For this reason, List Scheduling and Tabu Search algorithms have been developed to solve this formidable and NP-hard scheduling problem. Numerical implementations have been analysed and promising results have been achieved.