Network Flow based approaches for the Pipelines Routing Problem in Naval Design
The authors of this research acknowledge financial support by the Spanish Ministerio de Ciencia y Tecnologia, Agencia Estatal de Investigacion and Fondos Europeos de Desarrollo Regional (FEDER) via project PID2020-114594GB-C21. The authors also acknowledge partial support from projects FEDER-US-1256951, Junta de Andalucda P18-FR-1422, CEI-3-FQM331, B-FQM-322-UGR20, Netmeet-Data: Ayudas Fundacin BBVA a equipos de investigacin cientifica 2019, and Contratacion de Personal Investigador Doctor (Convocatoria 2019) 43 Contratos Capital Humano Linea 2. Paidi 2020, supported by the European Social Fund and Junta de Andalucia. The first author was also partially supported by the IMAG-Maria de Maeztu grant CEX2020-001105-M/AEI/10.13039/501100011033. ; In this paper we propose a general methodology for the optimal automatic routing of spatial pipelines motivated by a recent collaboration with Ghenova, a leading Naval Engineering company. We provide a minimum cost multicommodity network flow based model for the problem incorporating all the tech-nical requirements for a feasible pipeline routing. A branch-and-cut approach is designed and different matheuristic algorithms are derived for solving efficiently the problem. We report the results of a battery of computational experiments to assess the problem performance as well as a case study of a real-world naval instance provided by our partner company. ; Spanish Government ; European Commission ; Agencia Estatal de Investigacion ; European Commission PID2020-114594GB-C21 ; Junta de Andalucda P18-FR-1422 CEI-3-FQM331 B-FQM-322-UGR20 ; Netmeet-Data: Ayudas Fundacin BBVA a equipos de investigacin cientifica 2019 ; European Social Fund (ESF) ; Junta de Andalucia ; IMAG-Maria de Maeztu grant CEX2020-001105-M/AEI/10.13039/501100011033 ; FEDER-US-1256951