Ant Colony Optimization for Solving the Container Stacking Problem: Case of Le Havre (France) Seaport Terminal

Ant Colony Optimization for Solving the Container Stacking Problem: Case of Le Havre (France) Seaport Terminal

Jalel Euchi (LOGIQ Laboratory, Sfax University, Sfax, Tunisia), Riadh Moussi (Kairouan University, Kairouan, Tunisia), Fatma Ndiaye (University of Le Havre, Le Havre, France) and Adnan Yassine (University of Le Havre, Le Havre, France)
Copyright: © 2016 |Pages: 21
DOI: 10.4018/IJAL.2016070104


In this paper, the authors study the Container Stacking Problem (CSP) which is one of the most important problems in marine terminal. An optimization model is developed in order to determine the optimal storage strategy for various container-handling schedules. The objective of the model is to minimize the distance between vessel berthing location and the storage positions of containers. The CSP is solved by an efficient ant colony algorithm based on MAX-MIN ant system variant. The performance of the algorithm proposed is verified by a comparison with ILOG CPLEX for small-sized instances. In addition, numerical results for real-sized instances proved the efficiency of the algorithm.
Article Preview

1. Introduction

The idea to deliver goods in boxes or “containers” was originally developed by Malcolm Mclean in the 1950 which represents the first apparition of the principle of containerization. The development of containerization in the North Atlantic in 1965 and its gradual spread to the container has subsequently become a standardized box whose standards were set in 1974 by the ISO (International Standards Organization). The apparition of this principle was followed by the emergence of multimodal transport which consists of distributing goods via multiple types of transportation: ship, road, rail, etc.., and by the computerization and automation which allows the acceleration of the movement of goods and reducing costs traditionally associated.

Over the last four decades, the use of containers for international maritime transport has dramatically increased. An efficient container-handling at seaport terminal is very important for reducing transportation costs and maintaining shipping schedules.

Recently, given the competition among ports, the improvement of customer service became a serious problem for seaport terminal. One of the performance measures of customer service is the berthing time or throughout time. This time is based on the time for loading and unloading containers. In order to reduce the loading time, it is necessary to select the best storage locations for containers. This operation is a very important decision problem in a container terminal which is known by CSP. According to Kap et al. (2000) “the CSP consists in determining optimal positions or exact locations of containers from the empty slots in order to make efficient loading onto a ship, truck or train”.

In this paper, we propose a new and original mathematical model for the CSP problem which is based on: port restrictions and practical problem (e.g. case study section). The originality of the proposed model is gained by the presentation of several physical and logical constraints of port: First, in our work, we choose the best stack in the terminal to store a container unlike to other works that they choose the best block and the best side in it. Second, for each stack, containers are stored in the decreasing order of their departure time. This constraint is very important for avoiding the unproductive movements which are very expensive. At third, containers are stored by respecting the constraint of size compatibility. The implementation phase consists in solving the proposed mathematical model. We know that the CSP is an NP-hard problem. Generally, two different strategies can be investigated to resolve this type of problems: the exact algorithms and the meta-heuristics methods.

To the best of our knowledge, no exact solutions are proposed to solve these variant of problems. Several metaheuristics procedures are proposed to solve the CSP problems, either metaheuristics optimization via memory as the Tabu search (Erhan and Peter (2006), etc. or the evolutionary algorithms metaheuristics as the Genetic algorithm (Peter and Erhan (2001)), Hybrid Genetic algorithm and Simulated Annealing (Moussi et al. (2012)).

For the reason of the complexity of CSP, we propose an ant colony algorithm based on MAX-MIN ant system variant. To our knowledge ant algorithm was not previously applied to resolve CSP or any similar problem in seaport terminal.

ACO algorithms have been inspired by colonies of real ants, which deposit a chemical substance (called pheromone) on the ground. This substance influences the choices they make: the larger amount of pheromone is on a particular path; the larger probability is that an ant selects the path. Artificial ants in ACO algorithms behave in similar way see Marco (1992).

Complete Article List

Search this Journal:
Open Access Articles
Volume 9: 2 Issues (2019): Forthcoming, Available for Pre-Order
Volume 8: 2 Issues (2018)
Volume 7: 2 Issues (2017)
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing