Verschnittplanung

[El Fluppe]

Liebe Delphi Community,

ich hoffe der ein oder andere von euch hatte bereits mit solch einer oder einer ähnlichen Problemstellung zu tun und
kann mir aufgrund seiner Erfahrungen Input zur möglichen Umsetzung geben.

Oder kennt gar ein Tool was solch eine Anforderung bereits abdeckt.

Beispiel:
Es gibt 11 unterschiedlich große Rechtecke.

Nr	Länge	Breite
1	39,15	5,18
2	39,15	5,18
3	31,55	2,85
4	31,55	2,85
5	31,55	2,85
6	38,67	4,01
7	38,67	4,01
8	38,67	4,01
9	38,67	4,01
10	38,68	4,38
11	38,68	4,38

Diese Rechtecke sollen nun bestmöglichst (also mit dem geringsten Verschnitt) kombiniert werden.

Die fertige Fläche ist mit einer Breite von bspw. 9m begrenzt und darf die Länge von maximal 100m nicht überschreiten.
(Die Abmessungen der einzelnen Rechtecke und die Breite der fertigen Fläche sind variabel.)

Zudem darf der Abstand der einzelnen Rechtecke zueinander nicht kleiner als 60cm ausfallen.

Welche Komponente würdet ihr dazu verwenden? Die PaintBox?
Was wären eure Ansätze bzw. mit welchen Themen würdet ihr euch befassen, um dies zu lösen?

Danke für eure Unterstützung und Wegweisung!

Viele Grüße,
Heico

[freimatz]

Geht es dir um die Kombination oder um das Malen der Lösung. Bei ersterem wird Dir die Paintbox nicht helfen.

Zu der Kombination viel mir ein: https://de.wikipedia.org/wiki/Proble...lungsreisenden
Ist zwar eine etwas andere Sache, aber Dein Problem ist ähnlich.
Nachtrag: dort ist der link zu https://de.wikipedia.org/wiki/Kombin...he_Optimierung. Da ist sicher was für Dich dabei.

[himitsu]

Zitat von freimatz:

Geht es dir um die Kombination oder um das Malen der Lösung. Bei ersterem wird Dir die Paintbox nicht helfen.

Wenn ihm ein externes Tool die Koordinaten (Positionen und Anordnung) nennt, dann kann er es schon selber malen.


Bei wenigen einfachen rechteckigen und maximal in 90°-Schritten gedrehten Flächen,
lassen sich noch problemlos alle möglichen Lösungen durchprobieren und davon die Beste auswählen.

Aber je mehr und je komplizierter die Formen, um so schlimmer wird das und kann schnell "ewig" dauern. (außer du hast einen Quantencomputer)

packing or cutting stock problem

[Uwe Raabe]

Zitat von himitsu:

Bei wenigen einfachen rechteckigen und maximal in 90°-Schritten gedrehten Flächen,
lassen sich noch problemlos alle möglichen Lösungen durchprobieren und davon die Beste auswählen.

Das müssen aber wirklich schon sehr wenige sein. Auch ist es meist schwierig überhaupt ein Kriterium für besser zu definieren.

[Rollo62]

Hallo Heico,

da hast Du wohl eine Aufgabe ausgesucht an der sich viele die Zähne ausbeissen

Hier ist glaube ich mal eine gute Übersicht, aber es gibt da sicher auch Einiges in der KI-Forschung mittlerweile.
http://algo2.iti.kit.edu/documents/T...%20Sanders.pdf

Als Komponenten würde ich Image32 nehmen und darin wird die Clipper1 und die aktuelle Clipper2 schon vorbereitet.
Da hättest Du erstmal Alles aus einer Hand, von Angus Johnson, der das auch sehr gut und aktiv pflegt.

Clipper als Polygon-Schnitt-Library deswegen, weil es erfahrungsgemäß irgendwann mal nicht bei Rechtecken bleibt.

Die Image32 Komponente kann auch SVG, das wäre vielleicht ein passendes Datenformat um das Ergebnis gut und portabel zu speichern.

[Jens01]

http://delphiforfun.org/Programs/CutList.htm
https://www.tmachines.com/cutlogic-2d/
https://www.boole.eu/fr/opticoupe.php
https://optimalprograms.com/
http://www.nesting-technologies.com/
http://www.optimalon.com/Index.htm
https://www.scai.fraunhofer.de/de/ge.../produkte.html
https://github.com/Jack000/SVGnest

noch Fragen?

[El Fluppe]

Hallo,

Zitat:

da hast Du wohl eine Aufgabe ausgesucht an der sich viele die Zähne ausbeissen

Ja, das glaube ich.
Deshalb auch zusätzlich die Frage, ob jemand etwas "fertiges" in diese Richtung kennt.
Bin da in jegliche Richtung offen - hab die Freigabe es "notfalls" auch extern zu beschaffen.

Danke für eure Rückmeldungen.
Ich werde mir die verlinkten Seiten mal anschauen.

Zitat:

Geht es dir um die Kombination oder um das Malen der Lösung. Bei ersterem wird Dir die Paintbox nicht helfen.

In Bezug auf das Malen hatte ich mir die PaintBox mal angesehen.

Zitat:

noch Fragen?

Danke, da habe ich was an Lektüre.

Gruß,
Heico

[jaenicke]

Zitat von El Fluppe:

Oder kennt gar ein Tool was solch eine Anforderung bereits abdeckt.

Dieses vielleicht?
https://www.maxcutsoftware.com/

Günstiger kannst du das sicher nicht selbst entwickeln, wenn es nicht um viele Benutzer geht.

[nevolab]

Oder vielleicht

https://www.optimalon.com/cutting_op...on_library.htm

[Jens01]

Vielleicht eine Sache noch. Bei Google ist manchmal der Suchbegriff entscheidend.
Du mußt hier auch mit "Nesting" suchen.