The main contributions of this thesis are the comparison of existing and the design of new exact approaches based on linear, quadratic and semidefinite relaxations for row layout problems and several applications in logistic. In particular we demonstrate that our suggested semidefinite approach is the strongest exact method to date for most row layout problems. Due to the generality of our semidefinite method, we can also use it to simultaneously optimize over multiple machine cells exhibiting different layout types. Furthermore we introduce three new layout problems, namely the Directed Circular Facility Layout Problem, the Checkpoint Ordering Problem and the weighted Linear Ordering Problem. We indicate the relevance and applications of these new problems and suggest both heuristic and exact methods for solving them. We also examine two new variants of the Traveling Salesman Problem. The Target Visitation Problem considers, additionally to the distances travelled, preferences for visiting the different targets. We propose a semidefinite formulation and demonstrate the efficiency of our approach on a variety of benchmark instances. We also conduct a polyhedral study of the corresponding polytope, improving a semidefinite relaxation proposed by Newman. We also examine another variant of the Traveling Salesman Problem with applications in beam melting.
Citation
PhD Thesis, Alpen-Adria-Universitaet Klagenfurt, 2014