Crossing Minimal Edge‐Constrained Layout Planning using Benders Decomposition

Nathan Sudermann‐Merx, Steffen Rebennack and Christian Timpe

Production and Operations Management, 2021, vol. 30, issue 10, 3429-3447

Abstract: 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). Based on an initial solution, DFRP improves successively feasible points by solving dynamically sampled smaller problems with Benders decomposition. Because the optimization model is a surrogate model for its time‐dependent formulation, we evaluate the obtained solutions for different choices of the objective function via a simulation model. All algorithms are implemented efficiently using advanced features of the GuRoBi‐Python API, such as callback functions and lazy constraints. We present a case study for BASF using real data and make the real‐world data openly available.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1111/poms.13441

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:popmgt:v:30:y:2021:i:10:p:3429-3447

Ordering information: This journal article can be ordered from
http://onlinelibrary ... 1111/(ISSN)1937-5956

Access Statistics for this article

Production and Operations Management is currently edited by Kalyan Singhal

More articles in Production and Operations Management from Production and Operations Management Society
Bibliographic data for series maintained by Wiley Content Delivery ().