Software Architecture-To analyze cargo loading optimization algorithm

March 24, 2010

To analyze cargo loading optimization algorithm

By: Shahzad Sarwar
To: Development Team + Management
Date: 24th March 2010

1. Objective:To analyze and plan software development for Cargo Loading optimization module in Flight Cargo of PCMS, Pegasus Cargo Management System.

1. To Study industry available software for Cargo Load optimization and planning.
2. To study the available algorithm for Cargo Loading optimization in Flight Cargo module of PCMS, Pegasus Cargo Management System.
3. To analyze requirement specification for Cargo Load optimization and planning.

2. Load Planner Software Comparative Analysis:
There is a very long list of available commercial software that performs cargo load optimization and planning with full visualization via graphical representation.
Following is brief list of some of the best in industry.

2.1. 3D Load Packer (3DLP)
3D Load Packer (3DLP) is the unique space optimizer designed to help to plan quickly and easily the best compact arrangement of a number of different size 3D rectangular objects (hereafter called “Boxes”) within one or more rectangular enclosures (hereafter “Containers”). 3DLP is based on the truly three-dimensional, most dense and quick original packing algorithms.
An overall load weight limit and truck axle weight limits may be taken into account as additional constraints or actual optimization factors. Full control on the allowed box overhang is also available.
The program has a facility for specifying the associated cost for each box / container item in order to calculate totals and affect upon optimization as additional priority factors. Optimizer goal and other main settings are adjustable.

2.2. Cube-IQ
The Cube-IQ Load Planning system is built around the best Loading Engine on the market and will give optimal volume/weight utilization. (Needed – sidebars and quotes from the industry)
Cube-IQ optimizes the loading of items in one or more containers, optionally of different sizes.
The system can help to cube-out loads on PC, and also in the actual loading through its clear, 3-D diagram based loading instructions.
Cube-IQ has a state-of-the-art load optimization engine. Cube-IQ’s database allows to pre-define containers and boxes, and to store and retrieve any number of complete loading cases. The system has full data import and export facilities and can both read and write Excel, XML and other formats.

2.3. AutoLoad Pro
AutoLoad Pro integrated 3D graphic technology, visual effects and excellent computing speed help to work out how to load varied shape of goods into varied sizes of containers efficiently with considering delivery safety of goods, utilization of space, move convenience and etc. AutoLoad Pro can work out theminimum containers, trucks and cartons quickly to complete a loading plan and reduce transportation cost as well.

2.4. CubeMaster™
CubeMaster™ is a versatile, cost-effective software solution to optimize the cargo load on your trucks, air & sea containers and pallets quickly and efficiently. It reduces shipping and transport costs through intelligent loading and optimal space utilization. CubeMaster™ supports in planning order picking, loading and capacity requirements. The system delivers clear instructions regarding the work preparation in seconds.

2.5. Load
Load saves money by optimizing container cargo – includes interactive 3D view
Load saves money by optimizing container cargo:
•includes interactive 3D view
•automatic optimizer
•packing lists are conveniently entered into Load!
•calculates maximum number of items per container
•Optimized packing lists and 3D views can be printed.

2.6. Packer3d Online Service
The Packer3d Online Service calculates optimal plans for loading different types of boxes, cylinders, and pallets into containers, trucks, and railroad freight cars.

2.7. packVol
packVol is an Optimization Software for Load Planning, designed to plan the best space utilization inside containers and trucks, to help to reduce transportation costs. It is an innovative software for MS Windows™, which has some unique features not found in other container loading software products. It is truly tri dimensional; the program allows to manage efficiently complex load planning problems.

2.8. PalletStacking
PalletStacking allow users to find the best arrangement of boxes on loading pallets to warehousing or transportation. This software reduce the costs of palletizing boxes and calculate the most optimal dimensions of boxes. PalletStaking Solution calculate the best arrangement of products in a box, calculate box dimensions and show 3D graphics of the solution. It could be exported to Microsoft Excel to generate reports.

2.9. LoadPlanner
LoadPlanner is the first system that offers comprehensive load planning and optimization solution. The heart of LoadPlanner is its sophisticated 3D loading algorithm, the result of many years of intensive research and cooperation with leading logistics providers. But what makes us different is that LoadPlanner is an advanced rule-based system. It has unique capabilities to:
• Classify business objects (items, orders, containers, etc.) into flexible system of categories.
• Formulate high-level business rules and constraints, and apply them to selected categories.
• Use business rules and constraints in the process of load planning and optimization.
• Solve multi-tier load planning problems (packaging – palletizing – container / trailer loading).
• Produce results in form of easy-to-analyse interactive 3D graphics.

3. Algorithms for loading optimization Problem:
Cargo loading optimization is well known computer science problem and has many well known algorithms to solve this problem.
Following is brief description about some of the best algorithms to solve this problem.
3.1. Algorithms for the Container Loading Problem
By Guntram Scheithauer , Operations Research Proceedings 1991,

This paper covers the three-dimensional problem of optimal packing of a container with rectangular pieces. It proposes an approximation algorithm based on the “forward state strategy” of dynamic programming. A suitable description of packings is developed for the implementation of the approximation algorithm, and some computational experience is reported. The effective employment of capacity gets a more and more increasing importance in many problems of production and transportation planning. The reasons in transportation are e.g. the enlarging trade and growing transportation costs.


3.2. A Less Flexibility First Based Algorithm
Yuen-Ting Wu
Yu-Liang Wu
Department of Computer Science and Engineering, the Chinese University of Hong Kong, Hong Kong

This paper presents a Less Flexibility First (LFF) based algorithm for solving container loading problems in which boxes of given sizes are to be packed into a single container. The objective is to maximize volume utilization. LFF, firstly introduced in [An effective quasi-human heuristic for solving the rectangle packing problem, European Journal of Operations Research 141 (2002) 341], is an effective deterministic heuristic applied to 2D packing problems and generated up to 99% packing densities. Its usage is now extended to the container loading problem. Objects are packed according to their flexibilities. Less flexible objects are packed to less flexible positions of the container. Pseudo-packing procedures enable improvements on volume utilization. Encouraging packing results with up to 93% volume utilization are obtained in experiments running on benchmark cases from other authors.


3.3. A Maximal-Space Algorithm for the Container Loading Problem
F. Parreño, R. Alvarez-Valdes, J. M. Tamarit, J. F. Oliveira
Department of Mathematics, University of Castilla-La Mancha, Albacete, Spain
Department of Statistics and Operations Research, University of Valencia, Burjassot, Spain
Department of Statistics and Operations Research, University of Valencia, Burjassot, Spain
Faculty of Engineering, University of Porto, Porto, Portugal, and INESC Porto, Instituto de Engenharia de Sistemas e Computadores de Porto, Porto, Portugal
In this paper, a greedy randomized adaptive search procedure (GRASP) for the container loading problem is presented. This approach is based on a constructive block heuristic that builds upon the concept of maximal space, a nondisjoint representation of the free space in a container.
This new algorithm is extensively tested over the complete set of Bischoff and Ratcliff problems [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23 377–390], ranging from weakly heterogeneous to strongly heterogeneous cargo, and outperforms all the known nonparallel approaches that, partially or completely, have used this set of test problems. When comparing against parallel algorithms, it is better on average but not for every class of problem. In terms of efficiency, this approach runs in much less computing time than that required by parallel methods. Thorough computational experiments concerning the evaluation of the impact of algorithm design choices and internal parameters on the overall efficiency of this new approach are also presented.

Click to access tr03-07.pdf

3.4. Improved Optimization Algorithm for the Container Loading Problem
Xiamen, China
May 19-May 21
ISBN: 978-0-7695-3570-8
Container loading problem is a kind of space resources optimization problem which consists of various constraints. The solution can be extended to aircraft, cargo loading for ships, even the memory allocation for computer, and other applications. This paper proposes a new algorithm for loading a variety of different goods into a single container with multi-batches. With the concept of “plane” and “block”, the algorithm uses “depth priority” strategy to locate for the suitable space. The algorithm also allows goods to rotate in any possible directions, while under the guarantee of efficient space usage, it improves the placement stability. With the priorities of each goods assigned by the algorithm, we should could allocate more goods at the same location. The optimal algorithm is supposed to withdraw when the last batch packing is unsuitable. Experimental results show that the algorithm is effective to solve such problems.


3.5. A Genetic Algorithm for Solving the Container Loading Problem
FernUniversität Hagen, Kleine Straße 22, D-58084 Hagen, BRD
The paper presents a genetic algorithm (GA) for the container loading problem. The main
ideas of the approach are first to generate a set of disjunctive box towers and second to arrange the box towers on the floor of the container according to a given optimization criterion. The loading problem may include different practical constraints. The performance of the GA is demonstrated by a numerical test comparing the GA and several other procedures for the container loading problem.

Container loading problems may be grouped in different ways. A basic distinction exists between cases in which a given set of goods has to be loaded completely and cases which allow some goods to be left behind. Whilst the former type of problem involves more than one container, the latter is often restricted to a single container (cf. the distinction made by DYCKHOFF, 1990). Another important distinction concerns the goods to be loaded. BORTFELDT (1994) considers the loading of rectangular goods, i.e. boxes, and defines a cargo comprising only identical boxes as ‘homogeneous’. He also refers to a given set of boxes with many different types of boxes as ‘strongly heterogeneous’
and one with only a few different types of boxes as ‘weakly heterogeneous’. The subject of this paper is the loading of a strongly heterogeneous set of boxes into a single container. The literature references given below are focused on this type of problem and also on genetic approaches.


Click to access gehringbortfeldt_container.pdf

3.6. A Heuristic Algorithm with Heterogeneous Boxes
Zhoujing Wang Li, K.W. Xiaoping Zhang Xiamen Univ., Fujian

The container loading problem (CLP) is notoriously known to be NP-hard, an intrinsically difficult problem that is too complex to be solved in polynomial time on a system of serial computers. Heuristic algorithms are often the only viable option to tackle this type of combinatorial optimization problems. This article puts forward a heuristic algorithm based on a tertiary tree model to handle the CLP with heterogeneous rectangular boxes. A dynamic spatial decomposition method is employed to partition the unfilled container space after a group of homogeneous boxes is loaded into the container. This decomposition approach, together with an optimal-fitting sequencing rule and an inner-left-corner-occupying placement rule, permits a holistic filling strategy to pack a container. A comparative study with existing algorithms and an illustrative example demonstrate the efficiency of this heuristic algorithm.


3.7. A parallel tabu search algorithm for the container loading problem
A. Bortfeldt , H. Gehring and D. Mack
FernUniversität, Fachbereich Wirtschaftswissenschaft, Postfach 940, 58084, Hagen, Germany

This paper presents a parallel tabu search algorithm for the container loading problem with a single container to be loaded. The emphasis is on the case of a weakly heterogeneous load. The distributed-parallel approach is based on the concept of multi-search threads according to Toulouse et al. [Issues in designing parallel and distributed search algorithms for discrete optimization problems, Publication CRT-96-36, Centre de recherche sur les transports, Universitéde Montréal, Canada, 1996] i.e., several search paths are investigated concurrently. The parallel searches are carried out by differently configured instances of a tabu search algorithm, which cooperate by the exchange of (best) solutions at the end of defined search phases. The parallel search processes are executed on a corresponding number of LAN workstations. The efficiency of the parallel tabu search algorithm is demonstrated by an extensive comparative test including well-known reference problems and loading procedures from other authors.

4. Requirement specification for Load Plan PCMS:

a. To develop an efficient algorithm which can generate loading plan for goods in an aircraft or container.

b. Input Data for Algorithm:
1. Job cards data with number of pieces of goods to be filled in a aircraft/container with dimension(volume)
2. Dimension of aircraft’s area to be filled or dimension of container to be filled.

c. Out put data for algorithm:

1. To provide list of jobs card that would be filled in the aircraft or container.
2. To provide the exact location of goods to be placed in aircraft or container.

d. There would be an option to offload a particular job from container or aircraft.
Algorithm will automatically provide re-scheduled information after this change.

e. There would be an option to load a particular job to aircraft or container as priority. Algorithm will automatically provide re-scheduled information after this change.

f. A email alert will be generated to all the clients, shipper, consignee, agent, operation person and prepared by persons.

g. There would be 3-D graphical representation for load planning showing details
of exact items loaded in aircraft or container.

5. Future Guide lines:• To contact the corresponding algorithm providers for possibility of getting code of implementation of algorithms.
• After getting feedback from algorithm providers, best suited can be selected.
• A implementations are found in c language, so there is a need to transform that logic in C#, then modify the algorithm as per our need. This need code exploration in C.
• To do R & D related to 3-D graphical representation of objects in .Net specifically WPF.
• Third party graphical libraries like ceometric can be explored to get help in 3-D virtualization of objects.

6. References:

Algo for container Loading problem:

Click to access tr03-07.pdf

Click to access gehringbortfeldt_container.pdf