6 Article 160 1 10 20170224
6 Article 160 1 10 20170224
6 Article 160 1 10 20170224
doi: 10.4114/intartif.vol20iss60pp20-23
INTELIGENCIA ARTIFICIAL
http://journal.iberamia.org/
1 Introduction
Maritime container terminals are complex infrastructures located in seaports that have become backbone
elements within global supply chains. They are aimed at facing challenges derived from the huge volume
of freights moved around the world. In general terms, it can be claimed that their main function relates
to the transfer of the incoming freights packaged into containers between the different transport means
brought together, usually container vessels, trains, and trucks.
Terminal managers recognize the need to redesign the ways logistic operations are today being carried
out to address the challenges brought about by the international shipping industry. The main reason is
found on the impact the performance of maritime container terminals has on the trade competitiveness
of the countries. In this environment, two general approaches are persistently considered. The former
is intended to promote investments in new infrastructures and technologies which increase the capacity
to handle ever-increasing freight volumes. However, this approach has obvious drawbacks in terms of
environmental impact or financial sustainability, among others. Furthermore, the latter is based on the
improvement of the operations carried by the terminals, but the heterogeneity, interdependence, and
complexity of the processes constitute a major challenge for stakeholders.
The temporary and profitability needs of the processes found at maritime container terminals give
rise to optimization problems classified as N P-hard in terms of the Computational Complexity Theory.
This means that efficient optimization approaches have to be applied in order to cope with them. In this
regard, the approximate optimization techniques, such as heuristic and meta-heuristics, have proven to
be a comprehensive tool to solve intractable optimization problems due to the fact that they exhibit a
suitable balance between quality of the solutions reported and affordable computational requirements.
This thesis pursues to analyse outstanding optimization problems derived from the transshipment and
storage operations carried out in a maritime container terminal. These are the Quay Crane Scheduling
ISSN: 1988-3064(on-line)
IBERAMIA
c and the authors
Inteligencia Artificial 60(2017) 21
Problem, Pre-Marshalling Problem, Blocks Relocation Problem, and Stacking Problem, as well as some
of their most relevant variants. In this regard, terminal managers demand high-efficient optimization
approaches to solve these optimization problems with the aim of maintaining or even gaining market
share. With these goals in mind, several intelligent heuristics have been designed, implemented, and
validated during this thesis. The experimental results obtained reveal that the proposed techniques
are appropriated to be applied in practice, in an isolated fashion or embedded into general integration
schemes. In most of cases, these reduce significantly the computational times required by the best
approaches previously presented in the literature and improves the quality of the solutions obtained.
placed above other container with earlier retrieval time. That is, the initial non-located containers have
to be skipped in the target bay layout by means of relocation movements.
The Lowest Priority First Heuristic is an optimization approach proposed in [3] to solve the PMP.
The underlying idea of this heuristic is that if the containers with the latest retrieval times are placed
at the bottom of the stacks, then they will not have to be relocated in the future because they do not
avoid the retrieval of other containers with earlier retrieval times. In fact, according to the definition of
the PMP, each container has to be placed at the bottom of the bay or above other container with later
retrieval time in any target bay layout. For this purpose, the proposed heuristic iteratively places each
container either at the bottom of a stack or above other containers with later retrieval times. Finally,
an improvement process based on stack filling is applied to reduce the number of non-located containers.
The stack filling reasoning is based upon trying to take advantage of the empty slots in the destination
stack, filling them with non-located containers in the most adequate sorted sequence.
The computational results of the comparative analysis carried out with respect to previous approxi-
mate approaches from the scientific literature and an exact approach demonstrate the high performance
of the heuristic algorithm developed in this thesis. Moreover, its robustness has been statistically demon-
strated since it is able to solve scenarios with varying difficulties and sizes.
Moreover, the Blocks Relocation Problem, in short BRP, is an optimization problem that can be
described as follows. Given a set of homogeneous containers placed in a two-dimensional bay, the goal of
the BRP is to find the shortest sequence of movements aimed at retrieving all the containers one after
the other according to their increasing retrieval times. Without loss of generality, it is assumed that
the retrieval order is defined by following the retrieval times. This way, the container with the earliest
retrieval time must be retrieved before that with the second earliest retrieval time; the container with
the second earliest retrieval time must be retrieved before that container with the third earliest retrieval
time; and so forth, until all the containers are retrieved.
In this thesis, an optimization approach for solving the BRP is proposed in [4]. The cited paper has
a twofold contribution. On one hand, it presents an optimization model for the BRP that overcomes
several shortcomings of a model termed BRP-II found in the literature. In contrast to the proposed
optimization model, BRP-II reports infeasible solutions and does not guarantee the optimality of the
achieved solutions in some cases. The reasons are found in that (i) several containers currently placed
above the next to retrieve cannot be relocated to the same destination stack and (ii) the containers placed
below the next to retrieve can be relocated. Consequently, the reported solutions cannot be implemented
in practice. On the other hand, [4] presents a Branch and Bound algorithm aimed at solving the BRP
to optimality by means of short computational times. This algorithm includes an intelligent strategy
to explore the most promising nodes in the underlying tree. Thus, the performance of the Branch and
Bound algorithm can be easily adapted to report high-quality solutions at the expense of sacrificing the
optimality guarantee.
The computational experiments carried out in [4] reveal that the proposed optimization model can be
only applied in small-size scenarios due to its high computational burden. However, the exact algorithmic
approach based upon the framework of the Branch and Bound reports all the optimal solutions for the
problem instances found in the related literature by means of short computational times. This high
performance encourages its integration in potential intelligent systems, where the decision maker controls
its inputs to obtain appropriate sequences of movements aimed at retrieving the containers.
Finally, the Stacking Problem, in short SP, is an optimization problem in which the flow of homo-
geneous containers in a bay is optimized during a well-defined planning horizon [6]. That is, it seeks
to determine the slot in which each incoming container must be stored during its release time and the
movements to carry out for its removal during its retrieval time. The objective of the SP is to minimize
the number of movements required to store and retrieve all the containers by means of a stacking crane.
A high efficient heuristic algorithm is proposed in [2] for solving the SP. The rationale behind this
heuristic algorithm is to exploit those time periods in which there are no containers being moved in the
bay with the aim of minimizing the number of non-located containers.
The computational results indicate that the heuristic proposed in [2] is more competitive than those
approaches already presented in the literature and used as benchmark. In fact, the results indicate there
is statistical significance related to the heuristic and previous approaches. Also, the proposed heuristic
reports solutions with better objective function values on average than those obtained by means of the
Inteligencia Artificial 60(2017) 23
remaining approaches. The reason of the improvements obtained in the computational experiments arises
from reducing the number of non-located containers in the two-dimensional bay. In this regard, every time
the number of non-located containers is reduced in the bay, more stacks in which non-located containers
are built. Consequently, the probability of requiring new container relocations in the future is minimized.
3 Conclusions
In spite of the efforts made in the development of exact approaches in maritime logistics, no efficient tech-
niques have been reported in most of cases. Alternatively, heuristic techniques have stand as the promising
candidates because they report (near)optimal solutions within short computational times. Specifically,
several intelligent heuristic and meta-heuristic techniques are successfully proposed in this thesis to solve
the Quay Crane Scheduling Problem, Pre-Marshalling Problem, Blocks Relocation Problem, and Stack-
ing Problem, as well as some of their most relevant variants. In general terms, it can be claimed that the
proposed techniques have demonstrated to be more competitive than state-of-art approaches, reporting
solutions with higher quality in shorter computational times in all the cases under study. In addition, the
techniques are versatile enough to easily adapt to new variants of the optimization problems for which
they have been devised. This means that these techniques are suitable for being implemented in practice.
Acknowledgements
This work has been partially funded by the Spanish Ministry of Economy and Competitiveness (projects
TIN2012-32608 and TIN2015-70226-R) and with FEDER funds. Christopher Expósito-Izquierdo would
like to thank Belén Melián-Batista and J. Marcos Moreno-Vega for their efforts as supervisors of the
Ph.D. thesis summarized in this paper.
References
[1] C. Expósito-Izquierdo, J.L. González-Velarde, B. Melián-Batista, and J.M. Moreno-Vega. Hybrid
estimation of distribution algorithm for the quay crane scheduling problem. Applied Soft Computing,
13(10):4063 – 4076, 2013.
[2] C. Expósito-Izquierdo, E. Lalla-Ruiz, J. de Armas, B. Melián-Batista, and J.M. Moreno-Vega. A
heuristic algorithm based on an improvement strategy to exploit idle time periods for the stacking
problem. Computers & Industrial Engineering, 87:410 – 424, 2015.
[3] C. Expósito-Izquierdo, B. Melián-Batista, and J.M. Moreno-Vega. Pre-marshalling problem: Heuristic
solution method and instances generator. Expert Systems with Applications, 39(9):8337 – 8349, 2012.
[4] C. Expósito-Izquierdo, B. Melián-Batista, and J.M. Moreno-Vega. An exact approach for the blocks
relocation problem. Expert Systems with Applications, 42(17–18):6408 – 6422, 2015.
[5] K.H. Kim and Y.M. Park. A crane scheduling method for port container terminals. European Journal
of operational research, 156(3):752–768, 2004.
[6] R.J. Rei and J.P. Pedroso. Heuristic search for the stacking problem. International Transactions in
Operational Research, 19(3):379–395, 2012.
[7] M. Sammarra, J.F. Cordeau, G. Laporte, and M.F. Monaco. A tabu search heuristic for the quay
crane scheduling problem. Journal of Scheduling, 10(4-5):327–336, 2007.
[8] R. Stahlbock and S. Voβ. Operations research at container terminals: a literature update. OR
Spectrum, 30:1–52, 2008.