Container Terminal Management: Integrated Models and Large-Scale Optimization Algorithms
This thesis deals with models and methods for large scale optimization problems; in particular, we focus on decision problems arising in the context of seaport container terminals for the efficient management of terminal operations. Large-scale optimization problems are both difficult to handle and important in many concrete contexts. They usually originate from real world applications, such as telecommunication, transportation and logistics, and their combinatorial complexity often represents a major issue; therefore, optimization models are crucial to support the decision making process. In particular, column generation and branch-and-price schemes currently represent one of the most advanced and efficient exact optimization approaches to solve large scale combinatorial problems. However, the increasing size and complexity of practical problems arising in real-world applications motivates the design of new solution approaches able to tackle current optimization challenges. In this thesis, we address two complementary research streams where both methods and applications play an important role. On the one hand, we focus on the specific application of container terminals: we propose a new model for the integrated planning of operations and we provide a heuristic and an exact solution algorithm; the broader objective is to devise solution methods that can be generalized and extended to other applications and domains. On the other hand, we aim to develop new methods and algorithms for general large scale problems and, in this context, we investigate a new column generation framework that exploits the relationship between compact and extensive formulation. In particular, we focus on a class of split delivery vehicle routing problems that generalizes a large number of applications arising in the real world, such as transportation and logistics, including container terminal management. In the context of container terminals, we propose a model for the integrated planning of berth allocation and quay crane assignment: the two decision problems are usually solved hierarchically by terminal planners, whereas in the Tactical Berth Allocation Problem we optimize the two problems simultaneously. We firstly present a mixed integer programming formulation that is embedded into a two-level heuristic algorithm based on tabu search and mathematical programming techniques: our heuristic proves to be very efficient, providing good-quality solutions in a reasonable time. The problem is reformulated via Dantzig-Wolfe decomposition and solved via column generation: we propose an exact branch-and-price algorithm and our implementation, that includes state-of-the-art techniques for the master and the pricing problem, outperforms commercial solvers. Furthermore, the exact approach allows us to provide an interesting experimental comparison between hierarchical and integrated planning: computational tests confirm the added value of integration in terms of cost reduction and efficient use of resources. From a methodological point of view, this dissertation investigates a new column generation concept for difficult large scale optimization problems. In particular, we study a class of split delivery vehicle routing problems that generalizes some interesting features of Tactical Berth Allocation Problem, which are relevant also to other applications such as transportation, logistics and telecommunication. The problem, called Discrete Split Delivery Vehicle Routing Problem with Time Windows, presents two main modeling features: demand is discrete and delivered in discrete orders, opposite to the usual assumption of continuously splittable demand; the service time is dependent on the delivered quantity, opposite to the usual assumption of constant service time, regardless of the quantity. The problem is used to validate and test the new column generation approach studied in this thesis. The proposed framework, called Two-stage column generation, represents a novel contribution to recent advances in column generation: the basic idea is to simultaneously generate columns both for the compact and the extensive formulation. We propose to start solving the problem on a subset of compact formulation variables, we apply Dantzig-Wolfe decomposition and we solve the resulting master problem via column generation. At this point, profitable compact formulation variables are dynamically generated and added to the formulation according to reduced cost arguments, in the same spirit of standard column generation. The key point of our approach is that we evaluate the contribution of compact formulation variables with respect to the extensive formulation: indeed, we aim at adding compact formulation variables that are profitable for the master problem, regardless of the optimal solution of the linear relaxation of the compact formulation. We apply two-stage column generation to the Discrete Split Delivery Vehicle Routing Problem with Time Windows. Computational results show that our approach significantly reduces the number of generated columns to prove optimality of the root node. Furthermore, suboptimal compact formulation variables are detected correctly and a large number of variables is not taken into account during the solution process, thus reducing the size of the problem. However, the additional effort required by such a sophisticated approach makes the method competitive in terms of computational time only for instances of a certain difficulty. To conclude, two-stage column generation is a promising new approach and we believe that further research in this direction may contribute to solve more and more complex large scale optimization problems.
Keywords: container terminal ; berth allocation ; quay crane assignment ; integrated planning ; large scale optimization ; Dantzig-Wolfe decomposition ; branch-and-price ; split delivery vehicle routing ; two-stage column generationThèse École polytechnique fédérale de Lausanne EPFL, n° 4926 (2011)
Programme doctoral Mathématiques
Faculté des sciences de base
Laboratoire transport et mobilité
Record created on 2010-11-11, modified on 2016-08-08