Mathematical models and heuristic solutions for container positioning problems in port terminals

This PhD thesis is concerned with the container positioning problem (CPP) which consists in determining optimal sequences of positions and moves for containers in a single storage block of a terminal yard. The purpose of the thesis is to apply Operations Research (OR) methods for optimizing the CPP by constructing mathematical programming formulations of the problem and developing an efficient heuristic algorithm for its solution. The thesis consists of an introduction, two main chapters concerning new mathematical formulations and a new heuristic for the CPP, technical issues, computational results, and conclusive remarks. The introduction provides a basis for appreciating the presented work and sets out the scope, motivation, purpose, and contributions of the thesis. Furthermore, the CPP is defined and described, an overview of port container terminal issues in general is provided, and relevant literature concerning the subject is reviewed. The research presented in this thesis is divided into two main parts: Construction and investigation of new mathematical programming formulations of the CPP and development and implementation of a new event-based heuristic for the problem. The first part presents three mathematical programming formulations. First, a conceptual mixed integer linear programming (MIP) model for the entire port container terminal is presented. Subsequently, two models for the CPP are suggested: A MIP model and a binary integer linear programming (BIP) model. The models provide a basis for analyzing the CPP, demonstrating its complexity, and investigating potentials in model-based exact solution approaches. The models are solved by standard optimization software and the results as well as perspectives for alternative solution methods, making use of the models, are discussed. The second part presents an efficient solution algorithm for the CPP. Based on a number of new concepts, an event-based construction heuristic is developed and its ability to solve real-life problem instances is established. The backbone of the algorithm is a list of events, corresponding to a sequence of operations in the storage block. This concept enables a representation of the time dimension of the problem which is very efficient. Furthermore, introducing a range of criteria for evaluating and selecting positions for containers makes both a highly effective and very flexible algorithm which is also robust to changes in parameters and input data. Two improvement routines are presented, one imbedded in the basic heuristic and the other constituting a repair algorithm with the purpose of improving an initial heuristic solution. The heuristic algorithm performance and a wide range of different planning strategies are investigated by solving a large number of test instances and real-life problems. A total of 60 small-scale, 60 medium-scale, and 288 large-scale instances are introduced and used in the conduction of the computational experiments on the models and the heuristic algorithm. Results from the model runs show that it is difficult to obtain optimal solutions to the CPP by solving the mathematical formulations using standard optimizers. Furthermore, investigation of the potential of applying a relaxation approach indicates that this may not be a fruitful direction. Results from the heuristic runs proves the proposed algorithm very suitable for the CPP as good solutions are obtained within very short run times. Some important issues for further improvement of the heuristic algorithm are presented. Conclusively it may be stated that the proposed mathematical models are complex and hard to solve by standard optimization software and that the presented heuristic algorithm is very robust and scalable and constitutes a highly efficient solution method for the CPP. The conclusive remarks are followed by some interesting perspectives for future research.