Contributions to column-generation approaches in combinatorial optimization
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
Abstract
The thesis at hand deals with column-generation approaches for four different combinatorial optimization problems: The minimum tour duration problem, the active-passive vehicle routing problem, the vehicle routing and truck driver scheduling problem, and the optimal communication spanning tree problem. While the first three problems belong to the family of vehicle routing problems, the last one is in the family of constrained spanning tree problems. In all approaches, we develop effective column-generation algorithms that fully exploit the individual, problem-specific structures. This task can be roughly divided into two subtasks: Defining appropriate Dantzig-Wolfe decompositions and designing effective algorithms to solve the subproblems. The approaches for the optimal communication spanning tree problem focus on defining and comparing appropriate Dantzig-Wolfe decompositions. For the vehicle routing problems, the focus is on developing effective algorithms for the subproblem and strengthening the linear relaxation with valid inequalities. Moreover, we present a refined bidirectional labeling algorithm for the shortest path problem with resource constraints that often occurs as a subproblem in column-generation approaches for vehicle routing problems. Extensive computational results proving the usefulness of the proposed methods are reported.