A hybrid methodology to solve the container loading problem with weight distribution and cutting problems

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

27/09/2011

RESUMO

Transport of goods has represented an important role in economic development throughout the history and ship containerization brought great advantages. Its invention in mid-1950s brought down the cost of transport and reduced time for loading and unloading cargo. Consequently, it increased efficiency of port working and reduced handling cargo to hours instead of weeks, as before. However, the good use of containerization involves new and specialized logistic process, a number of technologies and automated systems to handle a great number of containers and even greater volume of cargo. To answer these requirements, computation appears as important tool. The described scenary has been treated in academic literature as the Container Loading Problem (CLP), with some variants. It is necessary consider practical requirements, for example the stability of cargo or weight distribution. The last one is of vital importance since the position of the centre of gravity of cargo affects the stability during its transport. When desconsidered, it could result in damage to cargo or vehicle. During our research, we were specially interested in this requirement. But, in order compare the found solutions with other ones, we proposed a methodology to measures the weight distribution. So, to the described problem, specifically the Knapsack Loading Problem (3D-KLP), this work presents a methodology that not only maximizes the packed cargo volume but also optimizes the weight distribution, its great contribution. Mainly if we consider that the cargo to be packed is composed by items with different densities, which turns the problem more difficult. The present methodology is composed by two phases with distinct goals. The first phase is concerned with maximize the weight distribution combining a search algorithm, the backtracking, with heuristics that solve integer linear programming models. The second phase executes a Genetic Algorithm to maximize the weight distribution of previously packed cargo. We also present a justification for why genetic algorithm was used in our methodology. An additional application was made to solve cutting problems. This class of problems occurs in various industrial process, when it is necessary to cut different types of material as glass, wood or parper, with a minimum of waste. We use a well-known benchmark test to compare our results with other approaches. This work also presents a case study of our implementation using some real data in a factory of stoves and refrigerators in Brazil. It shown promising results in reduced time. Keywords: Container Loading Problem, Knapsack Loading Problem, Weight Distribution, Integer Programming, Backtracking, Genetic Algorithms.

ASSUNTO(S)

programaÇÃo linear - dissertaÇÕes algorÍtmos genÉticos - dissertaÇÕes contÊineres - dissertaÇÕes sistemas de informacao

ACESSO AO ARTIGO

Documentos Relacionados