KIT | KIT-Bibliothek | Impressum | Datenschutz

Crossing Minimal Edge-Constrained Layout Planning using Benders Decomposition

Sudermann-Merx, Nathan; Rebennack, Steffen 1; Timpe, Christian
1 Institut für Operations Research (IOR), Karlsruher Institut für Technologie (KIT)


We present a new crossing number problem, which we refer to as the edge-constrained weighted two-layer crossing number problem (ECW2CN). The ECW2CN arises in layout planning of hose coupling stations at BASF, where the challenge is to find a crossing minimal assignment of tube-connected units to given positions on two opposing layers. This allows the use of robots in an effort to reduce the probability of operational disruptions and to increase human safety. Physical limitations imply maximal length and maximal curvature conditions on the tubes as well as spatial constraints imposed by the surrounding walls. This is the major difference of ECW2CN to all known variants of the crossing number problem. Such as many variants of the crossing number problem, ECW2CN is NP-hard. Because the optimization model grows fast with respect to the input data, we face out-of-memory errors for the monolithic model. Therefore, we develop two solution methods. In the first method, we tailor Benders decomposition toward the problem. The Benders subproblems are solved analytically and the Benders master problem is strengthened by additional cuts. Furthermore, we combine this Benders decomposition with ideas borrowed from fix-and-relax heuristics to design the Dynamic Fix-and-Relax Pump (DFRP). ... mehr

Verlagsausgabe §
DOI: 10.5445/IR/1000133870
Veröffentlicht am 14.06.2021
DOI: 10.1111/poms.13441
Zitationen: 2
Web of Science
Zitationen: 2
Zitationen: 3
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Operations Research (IOR)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 10.2021
Sprache Englisch
Identifikator ISSN: 1059-1478, 1937-5956
KITopen-ID: 1000133870
Erschienen in Production and Operations Management
Verlag John Wiley and Sons
Band 30
Heft 10
Seiten 3429-3447
Vorab online veröffentlicht am 18.04.2021
Nachgewiesen in Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page