Trabajo Fin de Máster

Abstract

It is reviewes the theory involved in multicommodity-flow problems and it is analyzed several aspects concerning the optimal routing of pipelines in naval design motivated by a recent collaboration with a leading Naval Engineering company. We start by considerering branch-and-cut algorithm which is a important tool to implement some desired properties in naval design as the minimum required distance between the pipelines volumes or the minimum allowed distances between pipe elbows. We also study Lagrangian relaxation and columns generation, both imperative for a deeper comprehesion of multicommodity-flow problems. In addition, it is studied the minimum cost flows as the the most basic of all flow problems and base for solving multicommodity-flow problems. Moreover, we apply all these mathematical tools into multicommodity-flow problems. Finally, it is proposed a general methodology for the automatic routing. We construct a network-shape framework for feasible solutions of the problem and a cost-based structure for the network that incorporates diferent desired physical characteristics for the routings. Then, a multicommodity-flow based approach is proposed and a heuristic algorithm is designed to solve it that take into account some desired properties of the routes.