Ryan KAMMARTI
LACS, Ecole Nationale des Ingénieurs de Tunis
Tunis – Belvédère. Tunisie

Imen AYACHI
LACS, Ecole Nationale des Ingénieurs de Tunis
Tunis – Belvédère. Tunisie
LAGIS, Ecole Centrale de Lille
Villeneuve d’Ascq, France

Mekki KSOURI
LACS, Ecole Nationale des Ingénieurs de Tunis
Tunis – Belvédère. Tunisie

Pierre BORNE
LAGIS, Ecole Centrale de Lille
Villeneuve d’Ascq, France

Abstract: This paper deals with the resolution of combinatorial optimization problems, particularly those concerning the maritime transport scheduling. We are interested in the management platforms in a river port and more specifically in container organisation operations with a view to minimizing the number of container rehandlings. Subsequently, we meet customers’ delivery deadlines and we reduce ship stoppage time. In this paper, we propose a genetic algorithm to solve this problem and we present some experiments and results.

Keywords: Bin-paking, Genetic algorithm, transport scheduling, heuristic, optimization, container.

Ryan Kammarti was born in Tunis, Tunisia in 1978. He received his M.E. and Master degree in Automatics and Industrial Computing from the National Institute of Applied Sciences and Technology (INSAT) in 2003 and his Ph.D. degree in automatics and industrial computing from the Central School of Lille and the National School of Engineers of Tunis in 2006.He currently occupies an assistant teacher position with the University of Tunis EL Manar, Tunis, Tunisia. He is also a team head in the ACS research laboratory in the National School of Engineers of Tunis (ENIT).

Imen Ayachi was born in Tunisia in 1980; she received her M.E and Master degree in Automatics and Industrial Computing from the National Institute of Applied Science and Technology (INSAT) in 2006. Currently, she is a doctoral student (in Electrical Engineering and automatics and industrial computing) at the National School of Engineers of Tunis (ENIT – TUNISIA) and the Central School of Lille (EC LILLE – FRANCE). Presently she is a contractual assistant at the High School of Commerce (TUNISIA).

Mekki Ksouri was born in Jendouba, Tunisia in 1948. He received his M.A. degree in physics in the FST in Tunis in 1973, the M.E. degree from the High School of Electricity in Paris in 1973, degree, the D.Sc. degree, and the Ph.D. degree from the University of Paris VI, Paris, France, in 1975 and 1977 respectively. He is Professor at the National School of Engineers of Tunis (ENIT). He was principal of the National Institute of Applied Sciences and Technology (INSAT) from 1999 to 2005, principal and founder of the High School of Statistics and Information Analysis from 2001 to 2005 and the High Institute of Technologic Studies from 1996 to 1999 and principal of The High Normal School of Technological Education from 1978 to 1990. Pr. Ksouri is the author or coauthor of many journal articles, book chapters, and communications in international conferences. He is also the author of 6 books.

Pierre Borne received the Master degree of Physics in 1967, the Masters of Electronics, of Mechanics and of Applied Mathematics in 1968. The same year he obtained the engineering Diploma from the Industrial Institute in north “IDN”. He obtained the PhD in Automatic Control from the University of Lille in 1970 and the DSc of the same University in 1976. He became Doctor Honoris Causa of the Moscow Institute of Electronics and Mathematics (Russia) in 1999, the University of Waterloo (Canada) in 2006 and of the Polytechnic University of Bucharest (Romania). He is author or co-author of about 200 Journal articles and book chapters, and of 38 plenary lectures and of more than 250 communications in international conferences. He has been the supervisor of 71 PhD thesis and he is author of 20 books. He is Fellow of IEEE, member of the Fellows Committee of IEEE and has been President of the IEEE/SMC society in 2000 and 2001. He is presently Professor at the central school of Lille.

>>Full text
CITE THIS PAPER AS:
Ryan KAMMARTI, Imen AYACHI, Mekki KSOURI, Pierre BORNE, Evolutionary Approach for the Containers Bin-Packing Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (4), pp. 315-324, 2009.

1. Introduction

Containerization is the use of containers for goods transport, especially in the maritime domain. This process that began in the 1960s and generalized in 1980s is a container logistics chain, which was put in place around the world. In fact, major ports have been adapted to this new transport mode by creating dedicated terminals for loading and unloading container ships, storage of containers and their transfer to trains or trucks.

The processes of loading and unloading containers are among the most important tasks that have to be considered in a container terminal. Indeed, the determination of an effective container organization reduces material handling costs (i.e., the costs associated with loading, unloading and transporting cargo) and minimizes the time of loading and unloading the containers.

This work addresses one of the management issues docks in a port and more specifically the organization of the container at the port. At each port of destination, some containers are unloaded from ship and loaded in the port to be delivered to their customers. Our aim is to determine a valid containers arrangement in the port, in order to meet customers’ delivery deadlines, reduce the loading/unloading time of these containers as well as the number of rehandlings and accordingly to minimize the ship idle time.

When studying such optimization problems, it is necessary to take into consideration two main aspects, the on-time delivery of containers to customers and the re-handling operations. A re-handling is a container movement made in order to permit access to another, or to improve the overall stowage arrangement, and is considered a product of poor planning [Wilson and col., 2001]

The problem studied in this work is classified as a three dimensional bin packing problem where containers are items and storage spaces in the port are bins used. It falls into the category of NP hard problems.

To find solutions for the bin packing problem, researches used some heuristics like the ant colony, tabu search and the genetic algorithms.

In this paper, we have proposed an efficient genetic algorithm which consists on selecting two chromosomes (parent) from an initially constructed population using a roulette wheel technique. Then, the two parents are combined using a one point crossover operator. Finally, a mutation operator is performed.

Some experimental results are presented in addition to a study of the influence of the containers and chromosomes numbers, on this model.

The rest of this paper is organized as follows: In section 2, a literature review on the bin packing problem and some of its variants, especially the container stowage planning problem, is presented. Next in section 3, the mathematical formulation of the problem is given and the proposed GA is described. Then, some experiments and results are presented and discussed, in section 4. Finally, section 5 covers our conclusion.

6. Summary and Conclusions

In this work, we have presented an evolutionary approach to solve the problem of containers organization at the port Problem. Our objective is to respect customers’ delivery deadlines and to reduce the number of container rehandles.

We proposed a brief literature review on the bin packing problem and some of its variants, especially the container stowage planning problem. Then, we described the mathematical formulation of the problem. After that, we presented our optimization approach which is an evolutionary algorithm based on genetic operators. We also detailed the use genetic algorithm for solutions improving. The experimental results were later presented by showing the influence of the number of containers in a chromosome and the influence of the number of chromosomes per population on the convergence and the simulation time.