For developers
Das 1D-Verschnittproblem
Wie man eine Reihe von benötigten Längen aus Rohmaterial zuschneidet und dabei die geringste Anzahl an Stangen verbraucht, ist das 1D-Verschnittproblem: ein klassisches, wirklich schwieriges Optimierungsproblem. Hier wird erklärt, was es ist, warum es sich Brute-Force-Methoden widersetzt und wie es in der Praxis gelöst wird, auch in der API, die dieser Website zugrunde liegt.
Was das 1D-Verschnittproblem ist
Gegeben sind Stangen einer festen Länge (z. B. 6000 mm) und eine Liste von benötigten Teilen, jeweils mit Länge und Stückzahl. Ein Zuschnittmuster ist eine Möglichkeit, eine einzelne Stange in einige dieser Teile zu zerschneiden; die übrig bleibende Länge ist Verschnitt. Das Problem besteht darin, Muster und die jeweilige Anzahl der danach zu schneidenden Stangen so zu wählen, dass jedes benötigte Teil produziert wird und die Gesamtzahl der Stangen bzw. der gesamte Verschnitt so gering wie möglich ist. Eindimensional, weil nur die Länge zählt: Das Sägeblatt durchtrennt den gesamten Querschnitt, daher spielen Breite und Profil bei der Anordnung keine Rolle.
1D-Behälterproblem und warum es NP-schwer ist
Das Verschnittproblem ist eine Verallgemeinerung des 1D-Behälterproblems: Beim Behälterproblem geht es darum, eine Reihe von Gegenständen unterschiedlicher Größe in die geringstmögliche Anzahl von Behältern fester Größe zu packen. Das Verschnittproblem ist dieselbe Frage, jedoch mit großen Stückzahlen pro Teil, sodass man über Muster statt über einzelne Teile nachdenkt. Das Behälterproblem ist eines der klassischen NP-schweren Probleme, und seine Entscheidungsform – passen diese Gegenstände in k Behälter? – ist NP-vollständig. Das Verschnittproblem erbt diese Komplexität.
Der Grund ist die kombinatorische Explosion. Die Anzahl der verschiedenen Zuschnittmuster wächst exponentiell mit der Anzahl der Teilgrößen, und die Anzahl der Möglichkeiten, die Stückzahlen auf diese Muster zu verteilen, explodiert darüber hinaus. Es ist kein Algorithmus bekannt, der das garantierte Optimum in einer Zeit findet, die polynomiell mit der Eingabe skaliert, und solange P nicht gleich NP ist, wird es auch keinen geben. Echte Solver listen daher nicht alle Möglichkeiten auf; sie schließen auf intelligente Weise ganze Lösungsräume aus.
Wie es in der Praxis gelöst wird
First-Fit-Decreasing (FFD)
Die gängigste Heuristik: Sortieren Sie die benötigten Teile von lang nach kurz und platzieren Sie jedes Teil auf der ersten Stange, auf die es noch passt. Eine neue Stange wird nur dann begonnen, wenn auf keiner anderen mehr Platz ist. FFD ist schnell und erstaunlich gut, nachweislich innerhalb von ca. 11/9 der optimalen Stangenanzahl plus einer kleinen Konstante. Die meisten Werkzeuge hören hier auf; ein gutes nutzt FFD als Ausgangspunkt, nicht als Endergebnis.
Spaltengenerierung (Gilmore und Gomory)
Die Formulierung, die große Probleminstanzen lösbar machte. Gilmore und Gomory (1961) beschrieben das Problem mit einer Variable pro Zuschnittmuster und lösten, da es exponentiell viele davon gibt, die lineare Relaxierung durch verzögerte Spaltengenerierung: Man beginnt mit einer Handvoll Muster und erzeugt wiederholt das nächstbeste, indem man ein beschränktes Rucksackproblem löst. Die dadurch erzeugte untere Schranke ist bekanntlich sehr scharf.
Branch-and-Bound und Branch-and-Price
Um diese gebrochene Relaxierung in eine ganze Anzahl von Stangen umzuwandeln, muss man suchen, aber nicht blind. Branch-and-Bound-Verfahren durchsuchen den Baum der ganzzahligen Entscheidungen und nutzen dabei die LP-Schranke, um ganze Äste abzuschneiden, die den bisher besten Plan nicht übertreffen können. Kombiniert mit der Spaltengenerierung wird daraus Branch-and-Price, die Grundlage der meisten exakten Solver für das Verschnittproblem.
Untere Schranken und der Beweis
Ein ernstzunehmender Solver liefert nicht nur einen Plan, er berechnet auch eine untere Schranke (aus der LP-Relaxierung oder einem einfacheren Argument über die Gesamtlänge) und vergleicht. Wenn ein Plan genau so viele Stangen verwendet, wie die Schranke als unvermeidbar beweist, ist er nachweislich optimal: Kein Plan kann besser sein, und der Solver kann dies bestätigen, anstatt nur auf einen Glückstreffer zu hoffen.
Wie LinearCutting das Problem löst
LinearCutting verwendet diese Abfolge: eine schnelle Heuristik für einen sofortigen, umsetzbaren Plan, dann eine schrankengesteuerte Suche, die sich so lange verbessert, bis sie entweder die untere Schranke erreicht (nachweislich optimal, was auch angezeigt wird) oder ihr Zeitbudget aufbraucht und den besten gefundenen Plan zurückgibt. Die Software modelliert auch die Physik: Sägeschnittbreite bei jedem Schnitt, Besäumen, Reststücke mit fester Stückzahl und Winkelschnitte, die zusätzliches Material verbrauchen. Denn ein Plan, der das Sägeblatt ignoriert, ist nicht nur suboptimal, er ist falsch. Die Benchmark-Aufträge sind veröffentlicht, sodass Sie die Ergebnisse mit jedem anderen Werkzeug vergleichen können.
Die Lösung wird als JSON-API bereitgestellt: Senden Sie Ihre Teile und Ihr Rohmaterial und Sie erhalten einen geprüften Zuschnittplan mit den Layouts, dem Verschnitt, der Anzahl der Anschläge und der Information, ob der Plan die optimale Schranke erreicht hat. Es gibt offizielle Clients für Python (pip install linearcutting) und JavaScript oder TypeScript (npm install linearcutting), sodass der Aufruf in beiden Sprachen nur wenige Zeilen Code erfordert.
Lösen Sie es aus Ihrem Code heraus
Sparen Sie sich das Schreiben eines Solvers und rufen Sie einen auf. Dieselbe Engine, die auch den Rechner dieser Website antreibt, ist eine JSON-API mit offiziellen Python- und JavaScript-Clients, einem kostenlosen öffentlichen Tarif und einem Live-Beispiel, das Sie in der Dokumentation ausführen können.
pip install linearcutting npm install linearcutting