The master bay plan problem: a solution method based on its connection to the three-dimensional bin packing problem

This paper addresses the problem of determining stowage plansfor containers in a ship, referred to as the Master Bay PlanProblem (MBPP). MBPP is NP-complete. We present a heuristic method for solvingMBPP based on its relation with the three-dimensional bin packingproblem (3D-BPP), where items are containers and bins are differentportions of the ship. Our aim is to find stowage plans, takinginto account structural and operational constraints relatedto both the containers and the ship, that minimize the timerequired for loading all containers on board. A validation of the proposed approach with some test casesis given. The results of real instances of the problem involvingmore than 1400 containers show the effectiveness of the proposedapproach for large scale applications.     

An interactive system for the loading of cargo aircraft

The paper describes an interactice, computer based procedure for solving the variant of the vehicle loading problem encountered when loading containers and pallets into an aircraft. The procedure is heuristic and practical oriented; it is presently being implemented by Scandinavian Airlines.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

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

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

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.     

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

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

The multiple container loading cost minimization problem

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.     

A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning

Cost effectiveness is central to the air freight forwarders. In this work, we study how an air freight forwarder should plan its cargo loading in order to minimize the total freight cost given a limited number of rented containers. To solve the problem efficiently for practical implementation, we propose a new large-scale neighborhood search heuristic. The proposed large-scale neighborhood relaxes the subset-disjoint restriction made in the existing literature; the relaxation risks a possibility of infeasible exchanges while at the same time it avoids the potentially large amount of checking effort required to enforce the subset-disjoint restriction. An efficient procedure is then used to search for improvement in the neighborhood. We have also proposed a subproblem to address the difficulties caused by the fixed charges. The compromised large-scale neighborhood (CLSN) search heuristic has shown stably superior performance when compared with the traditional large-scale neighborhood search and the mixed integer programming model.     

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

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

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.     

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

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

A heuristic for sea-freight container selection,cargo allocation and cargo orientation

A model is proposed to generate solutions for container selection, for the allocation of cargo to containers, and for cargo orientation within a container. The model is in the form of a mixed integer program with the objective of minimizing the total shipping cost. The practical requirements of loading priority and weight distribution along the main dimension of the container are incorporated into the model. A heuristic solution strategy is proposed and used to control the computation time by pre-setting the search increments. Three case examples are presented. The first and third examples show that the proposed model can produce a better solution than the manual schedulers. The second example is taken from the literature and is compared with the solution generated by the proposed model, demonstrating that the practical considerations incorporated into the model do not necessarily lead to increased shipping costs.     

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.     

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.     

Allocation of empty containers between multi-ports

Owing to imbalances in international trade activities, shipping companies accumulate a large number of unnecessary empty containers in the import-dominant ports, whilst request a large number of empty containers in export-dominant ports. The logistics challenge to shipping companies is to better manage and control their containers, which consist of company-owned containers and leased containers. The multi-port empty container allocation problem is concerned with the allocation of empty containers from supply ports to demand ports. In this paper, optimal pairs of critical policies, (U, D) for one port, which are importing empty containers up to U when the number of empty containers in the port is less than U, or exporting empty containers down to D when the number of empty containers is larger than D, doing nothing otherwise, are adapted to multi-port case so that decision-makers can make decisions about allocating the right amounts of empty containers to the right ports at the right time. This allocation problem has been formulated and the heuristic methods are designed according to that the average cost using (u, d) policy at one port is convex in u and d. Furthermore, the examples show that, using the heuristic algorithm, the result in the inland line case is quite close to the lower bound, even the distance is not so close in the global line case.     

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.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

Transportation problem with nonlinear side constraints a branch and bound approach

In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

Local search for a multi-drop multi-container loading problem

We consider a complex variant of the Container Loading Problem arising from a real-world industrial application. It includes several features such as multiple containers, box rotation, and bearable weight, which are of importance in many practical situations. In addition, it also considers the situation in which boxes have to be delivered to different destinations (multi-drop). Our solution technique is based on local search metaheuristics. Local search works on the space of sequences of boxes to be loaded, while the actual load is obtained by invoking, at each iteration, a specialized procedure called loader. The loader inserts the boxes in the container using a deterministic heuristic which produces a load that is feasible according to the constraints. We test our solver on real-world instances provided by our industrial partner, showing a clear improvement on the previous heuristic solution. In addition, we compare our solver on benchmarks from the literature on the basic container loading problems. The outcome is that the results are in some cases in-line with the best ones in the literature and for other cases they also improve upon the best known ones. All instances and solutions are made available on the web for future comparisons.