Hugging Face's logo

Spaces:
FajarHidaa
/
Nesting
No application file

App Files Community
Nesting / v7.2
FajarHidaa's picture
FajarHidaa
Create v7.2
a740478 verified
Raw History Blame Contribute Delete
92.9 kB
Option Explicit
Private Const EPS As Double = 0.000001
Private Const ROLL_GAP As Double = 5#
Private Const MAX_ROLLS As Long = 100
Private Const MAX_RIGHT_WASTE As Double = 10#
Private Const ALIGN_TOLERANCE As Double = 0.5
' Material area is the primary objective: roll width x actual used height.
' Secondary terms are intentionally much smaller so they cannot beat a
' meaningful material saving.
Private Const MATERIAL_SCORE_SCALE As Double = 1000000000#
Private Const RIGHT_WASTE_SCORE_SCALE As Double = 100000#
Private Const ALIGNMENT_SCORE_SCALE As Double = 0.01
Private Const ROLL_COUNT_SCORE_SCALE As Double = 0.0001
Private Const MAX_LOCAL_SEEDS As Long = 5
Private Const MAX_PAIR_MOVES As Long = 80
Private Const MAX_REINSERT_MOVES As Long = 100
Private Const MAX_TRIPLE_MOVES As Long = 40
Private Const MAX_LOCAL_PASSES As Long = 3
Private Const MAX_LNS_ITERATIONS As Long = 12
Private Const MAX_LNS_REPAIR_POSITIONS As Long = 30
Private Const MAX_ROTATION_MUTATIONS As Long = 24
Private Const LNS_ACCEPT_WORSE_PCT As Double = 0.003
Private Const CONTACT_TOLERANCE As Double = 0.05
Private Const CONTACT_PLACEMENT_WEIGHT As Double = 0.35
Private Const GUILLOTINE_PLACEMENT_WEIGHT As Double = 0.25
Private Const CONTACT_SCORE_WEIGHT As Double = 0.25
Private Const GUILLOTINE_SCORE_WEIGHT As Double = 0.35
Private Const MAX_CONTACT_MOVES As Long = 60
Private Const MAX_CUT_MOVES As Long = 50
' Multi-width search tests pairs from at most the first 6 entered widths.
Private Const MAX_MULTI_WIDTH_CANDIDATES As Long = 6
Private Type TBanner
Label As String
OrigW As Double
OrigH As Double
margin As Double
End Type
Private Type TFreeRect
x As Double
y As Double
w As Double
h As Double
End Type
Private Type TPlaced
rid As Long
x As Double
y As Double
w As Double
h As Double
Rotated As Boolean
End Type
Private Type TRoll
placed() As TPlaced
placedCount As Long
UsedHeight As Double
End Type
Private Function MinD(ByVal a As Double, ByVal b As Double) As Double
If a < b Then
MinD = a
Else
MinD = b
End If
End Function
Private Function MaxD(ByVal a As Double, ByVal b As Double) As Double
If a > b Then
MaxD = a
Else
MaxD = b
End If
End Function
Private Function AbsD(ByVal a As Double) As Double
If a < 0# Then
AbsD = -a
Else
AbsD = a
End If
End Function
Private Function AreaOf(ByRef item As TBanner) As Double
AreaOf = (item.OrigW + 2# * item.margin) * (item.OrigH + 2# * item.margin)
End Function
Private Function SortValue(ByRef item As TBanner, ByVal sortMode As Long) As Double
Dim w As Double
Dim h As Double
Dim shortSide As Double
Dim longSide As Double
w = item.OrigW + 2# * item.margin
h = item.OrigH + 2# * item.margin
shortSide = MinD(w, h)
longSide = MaxD(w, h)
Select Case sortMode
Case 1
SortValue = w * h
Case 2
SortValue = w
Case 3
SortValue = h
Case 4
SortValue = shortSide
Case 5
SortValue = longSide
Case 6
If shortSide > EPS Then
SortValue = longSide / shortSide
Else
SortValue = 0#
End If
Case Else
SortValue = w * h
End Select
End Function
Private Sub SortIndex(ByRef items() As TBanner, ByRef sourceIdx() As Long, ByVal n As Long, ByVal sortMode As Long, ByRef sortedIdx() As Long)
Dim i As Long
Dim j As Long
Dim tmp As Long
ReDim sortedIdx(1 To n)
For i = 1 To n
sortedIdx(i) = sourceIdx(i)
Next i
For i = 1 To n - 1
For j = i + 1 To n
If SortValue(items(sortedIdx(j)), sortMode) > SortValue(items(sortedIdx(i)), sortMode) Then
tmp = sortedIdx(i)
sortedIdx(i) = sortedIdx(j)
sortedIdx(j) = tmp
End If
Next j
Next i
End Sub
Private Sub BuildInitialOrder(ByRef items() As TBanner, ByVal n As Long, ByVal sortMode As Long, ByRef order() As Long)
Dim sourceIdx() As Long
Dim i As Long
ReDim sourceIdx(1 To n)
ReDim order(1 To n)
For i = 1 To n
sourceIdx(i) = i
Next i
SortIndex items, sourceIdx, n, sortMode, order
End Sub
Private Sub CopyOrder(ByRef source() As Long, ByVal sourceCount As Long, ByRef target() As Long)
Dim i As Long
If sourceCount <= 0 Then
ReDim target(1 To 1)
Exit Sub
End If
ReDim target(1 To sourceCount)
For i = 1 To sourceCount
target(i) = source(i)
Next i
End Sub
Private Sub CopyRotationPrefs(ByRef source() As Long, ByVal n As Long, ByRef target() As Long)
Dim i As Long
ReDim target(1 To n)
For i = 1 To n
target(i) = source(i)
Next i
End Sub
Private Sub SwapLong(ByRef arr() As Long, ByVal i As Long, ByVal j As Long)
Dim tmp As Long
If i = j Then Exit Sub
tmp = arr(i)
arr(i) = arr(j)
arr(j) = tmp
End Sub
Private Sub MoveItemOrder(ByRef arr() As Long, ByVal fromPos As Long, ByVal toPos As Long, ByVal n As Long)
Dim value As Long
Dim i As Long
If fromPos = toPos Then Exit Sub
If fromPos < 1 Or fromPos > n Then Exit Sub
If toPos < 1 Or toPos > n Then Exit Sub
value = arr(fromPos)
If fromPos < toPos Then
For i = fromPos To toPos - 1
arr(i) = arr(i + 1)
Next i
Else
For i = fromPos To toPos + 1 Step -1
arr(i) = arr(i - 1)
Next i
End If
arr(toPos) = value
End Sub
Private Sub InsertLongAt(ByRef arr() As Long, ByRef currentCount As Long, ByVal position As Long, ByVal value As Long)
Dim i As Long
If position < 1 Then position = 1
If position > currentCount + 1 Then position = currentCount + 1
For i = currentCount To position Step -1
arr(i + 1) = arr(i)
Next i
arr(position) = value
currentCount = currentCount + 1
End Sub
Private Sub RemoveLongAt(ByRef arr() As Long, ByRef currentCount As Long, ByVal position As Long)
Dim i As Long
If currentCount <= 0 Then Exit Sub
If position < 1 Or position > currentCount Then Exit Sub
For i = position To currentCount - 1
arr(i) = arr(i + 1)
Next i
currentCount = currentCount - 1
End Sub
Private Function ContainsLong(ByRef arr() As Long, ByVal count As Long, ByVal value As Long) As Boolean
Dim i As Long
For i = 1 To count
If arr(i) = value Then
ContainsLong = True
Exit Function
End If
Next i
ContainsLong = False
End Function
Private Function RectsIntersect(ByRef a As TFreeRect, ByRef b As TFreeRect) As Boolean
If a.x >= b.x + b.w - EPS Then
RectsIntersect = False
Exit Function
End If
If b.x >= a.x + a.w - EPS Then
RectsIntersect = False
Exit Function
End If
If a.y >= b.y + b.h - EPS Then
RectsIntersect = False
Exit Function
End If
If b.y >= a.y + a.h - EPS Then
RectsIntersect = False
Exit Function
End If
RectsIntersect = True
End Function
Private Function IsContained(ByRef a As TFreeRect, ByRef b As TFreeRect) As Boolean
If a.x + EPS < b.x Then
IsContained = False
Exit Function
End If
If a.y + EPS < b.y Then
IsContained = False
Exit Function
End If
If a.x + a.w > b.x + b.w + EPS Then
IsContained = False
Exit Function
End If
If a.y + a.h > b.y + b.h + EPS Then
IsContained = False
Exit Function
End If
IsContained = True
End Function
Private Sub PruneFree(ByRef freeRects() As TFreeRect, ByRef freeCount As Long)
Dim i As Long
Dim j As Long
Dim k As Long
Dim contained As Boolean
If freeCount <= 1 Then Exit Sub
i = 1
Do While i <= freeCount
contained = False
For j = 1 To freeCount
If i <> j Then
If IsContained(freeRects(i), freeRects(j)) Then
contained = True
Exit For
End If
End If
Next j
If contained Then
For k = i To freeCount - 1
freeRects(k) = freeRects(k + 1)
Next k
freeCount = freeCount - 1
Else
i = i + 1
End If
Loop
If freeCount <= 0 Then
ReDim freeRects(1 To 1)
Else
ReDim Preserve freeRects(1 To freeCount)
End If
End Sub
Private Sub AddIfValid(ByRef arr() As TFreeRect, ByRef count As Long, ByVal x As Double, ByVal y As Double, ByVal w As Double, ByVal h As Double)
If w <= EPS Then Exit Sub
If h <= EPS Then Exit Sub
count = count + 1
arr(count).x = x
arr(count).y = y
arr(count).w = w
arr(count).h = h
End Sub
Private Sub PlaceAndSplit(ByRef freeRects() As TFreeRect, ByRef freeCount As Long, ByVal placedX As Double, ByVal placedY As Double, ByVal placedW As Double, ByVal placedH As Double)
Dim oldCount As Long
Dim newCount As Long
Dim maxNew As Long
Dim i As Long
Dim fr As TFreeRect
Dim placed As TFreeRect
Dim tmp() As TFreeRect
oldCount = freeCount
If oldCount <= 0 Then Exit Sub
maxNew = oldCount * 4 + 10
ReDim tmp(1 To maxNew)
placed.x = placedX
placed.y = placedY
placed.w = placedW
placed.h = placedH
For i = 1 To oldCount
fr = freeRects(i)
If Not RectsIntersect(fr, placed) Then
AddIfValid tmp, newCount, fr.x, fr.y, fr.w, fr.h
Else
AddIfValid tmp, newCount, fr.x, fr.y, placed.x - fr.x, fr.h
AddIfValid tmp, newCount, placed.x + placed.w, fr.y, fr.x + fr.w - placed.x - placed.w, fr.h
AddIfValid tmp, newCount, fr.x, fr.y, fr.w, placed.y - fr.y
AddIfValid tmp, newCount, fr.x, placed.y + placed.h, fr.w, fr.y + fr.h - placed.y - placed.h
End If
Next i
If newCount <= 0 Then
ReDim freeRects(1 To 1)
freeCount = 0
Exit Sub
End If
ReDim freeRects(1 To newCount)
For i = 1 To newCount
freeRects(i) = tmp(i)
Next i
freeCount = newCount
PruneFree freeRects, freeCount
End Sub
Private Function OverlapLength(ByVal a1 As Double, ByVal a2 As Double, ByVal b1 As Double, ByVal b2 As Double) As Double
Dim lo As Double
Dim hi As Double
lo = MaxD(a1, b1)
hi = MinD(a2, b2)
If hi <= lo + CONTACT_TOLERANCE Then
OverlapLength = 0#
Else
OverlapLength = hi - lo
End If
End Function
Private Function SharedEdgeLengthBetween(ByRef a As TPlaced, ByRef b As TPlaced) As Double
Dim total As Double
Dim ov As Double
total = 0#
If AbsD(a.x + a.w - b.x) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.y, a.y + a.h, b.y, b.y + b.h)
total = total + ov
ElseIf AbsD(b.x + b.w - a.x) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.y, a.y + a.h, b.y, b.y + b.h)
total = total + ov
End If
If AbsD(a.y + a.h - b.y) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.x, a.x + a.w, b.x, b.x + b.w)
total = total + ov
ElseIf AbsD(b.y + b.h - a.y) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.x, a.x + a.w, b.x, b.x + b.w)
total = total + ov
End If
SharedEdgeLengthBetween = total
End Function
Private Function StrongGuillotineEdgeBetween(ByRef a As TPlaced, ByRef b As TPlaced) As Double
Dim ov As Double
Dim minSpan As Double
If AbsD(a.x + a.w - b.x) <= CONTACT_TOLERANCE Or AbsD(b.x + b.w - a.x) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.y, a.y + a.h, b.y, b.y + b.h)
minSpan = MinD(a.h, b.h)
If minSpan > EPS And ov >= minSpan * 0.9 Then
StrongGuillotineEdgeBetween = ov
Exit Function
End If
End If
If AbsD(a.y + a.h - b.y) <= CONTACT_TOLERANCE Or AbsD(b.y + b.h - a.y) <= CONTACT_TOLERANCE Then
ov = OverlapLength(a.x, a.x + a.w, b.x, b.x + b.w)
minSpan = MinD(a.w, b.w)
If minSpan > EPS And ov >= minSpan * 0.9 Then
StrongGuillotineEdgeBetween = ov
Exit Function
End If
End If
StrongGuillotineEdgeBetween = 0#
End Function
Private Function PlacementContactBonus(ByRef placed() As TPlaced, ByVal placedCount As Long, ByVal x As Double, ByVal y As Double, ByVal w As Double, ByVal h As Double) As Double
Dim candidate As TPlaced
Dim i As Long
Dim edge As Double
Dim total As Double
If placedCount <= 0 Then Exit Function
candidate.x = x
candidate.y = y
candidate.w = w
candidate.h = h
For i = 1 To placedCount
edge = SharedEdgeLengthBetween(candidate, placed(i))
total = total + edge
Next i
PlacementContactBonus = total
End Function
Private Function PlacementGuillotineBonus(ByRef placed() As TPlaced, ByVal placedCount As Long, ByVal x As Double, ByVal y As Double, ByVal w As Double, ByVal h As Double) As Double
Dim candidate As TPlaced
Dim i As Long
Dim edge As Double
Dim total As Double
If placedCount <= 0 Then Exit Function
candidate.x = x
candidate.y = y
candidate.w = w
candidate.h = h
For i = 1 To placedCount
edge = StrongGuillotineEdgeBetween(candidate, placed(i))
total = total + edge
Next i
PlacementGuillotineBonus = total
End Function
Private Function PlacementScoreWithContact(ByRef fr As TFreeRect, ByVal rw As Double, ByVal rh As Double, ByVal fitMode As Long, ByRef placed() As TPlaced, ByVal placedCount As Long, ByRef outContact As Double, ByRef outGuillotine As Double) As Double
Dim baseScore As Double
baseScore = PlacementScore(fr, rw, rh, fitMode)
outContact = PlacementContactBonus(placed, placedCount, fr.x, fr.y, rw, rh)
outGuillotine = PlacementGuillotineBonus(placed, placedCount, fr.x, fr.y, rw, rh)
PlacementScoreWithContact = baseScore - outContact * CONTACT_PLACEMENT_WEIGHT - outGuillotine * GUILLOTINE_PLACEMENT_WEIGHT
End Function
Private Function PlacementScore(ByRef fr As TFreeRect, ByVal rw As Double, ByVal rh As Double, ByVal fitMode As Long) As Double
Dim leftoverW As Double
Dim leftoverH As Double
Dim shortSide As Double
Dim longSide As Double
Dim areaWaste As Double
leftoverW = fr.w - rw
leftoverH = fr.h - rh
shortSide = MinD(leftoverW, leftoverH)
longSide = MaxD(leftoverW, leftoverH)
areaWaste = fr.w * fr.h - rw * rh
Select Case fitMode
Case 1
PlacementScore = shortSide
Case 2
PlacementScore = areaWaste
Case 3
PlacementScore = longSide
Case Else
PlacementScore = shortSide
End Select
End Function
Private Function AlignmentPenalty(ByRef placed() As TPlaced, ByVal placedCount As Long, ByVal x As Double, ByVal y As Double) As Double
Dim i As Long
Dim leftDist As Double
Dim topDist As Double
Dim bestLeft As Double
Dim bestTop As Double
If placedCount <= 0 Then
AlignmentPenalty = 0#
Exit Function
End If
bestLeft = 1E+30
bestTop = 1E+30
For i = 1 To placedCount
leftDist = AbsD(x - placed(i).x)
topDist = AbsD(y - placed(i).y)
If leftDist < bestLeft Then bestLeft = leftDist
If topDist < bestTop Then bestTop = topDist
Next i
If bestLeft <= ALIGN_TOLERANCE Then bestLeft = 0#
If bestTop <= ALIGN_TOLERANCE Then bestTop = 0#
AlignmentPenalty = bestLeft + bestTop
End Function
Private Function IsBetterPlacement(ByVal score As Double, ByVal alignScore As Double, ByVal tieY As Double, ByVal tieX As Double, ByVal bestScore As Double, ByVal bestAlign As Double, ByVal bestY As Double, ByVal bestX As Double) As Boolean
If score < bestScore - EPS Then
IsBetterPlacement = True
Exit Function
End If
If AbsD(score - bestScore) <= EPS Then
If alignScore < bestAlign - EPS Then
IsBetterPlacement = True
Exit Function
End If
If AbsD(alignScore - bestAlign) <= EPS Then
If tieY < bestY - EPS Then
IsBetterPlacement = True
Exit Function
End If
If AbsD(tieY - bestY) <= EPS Then
If tieX < bestX - EPS Then
IsBetterPlacement = True
Exit Function
End If
End If
End If
End If
IsBetterPlacement = False
End Function
Private Function FindBestPlacement(ByRef freeRects() As TFreeRect, ByVal freeCount As Long, ByVal reqW As Double, ByVal reqH As Double, ByVal allowRotation As Boolean, ByVal rotationMode As Long, ByVal fitMode As Long, ByRef placed() As TPlaced, ByVal placedCount As Long, ByRef bestX As Double, ByRef bestY As Double, ByRef bestW As Double, ByRef bestH As Double, ByRef bestRot As Boolean) As Boolean
Dim i As Long
Dim rw As Double
Dim rh As Double
Dim score As Double
Dim alignScore As Double
Dim bestScore As Double
Dim bestAlign As Double
Dim tieY As Double
Dim tieX As Double
Dim bestTieY As Double
Dim bestTieX As Double
Dim contactBonus As Double
Dim guillotineBonus As Double
Dim found As Boolean
Dim tryNormal As Boolean
Dim tryRotated As Boolean
bestScore = 1E+30
bestAlign = 1E+30
bestTieY = 1E+30
bestTieX = 1E+30
found = False
tryNormal = True
tryRotated = allowRotation
If allowRotation Then
If rotationMode = 1 Then
tryRotated = False
ElseIf rotationMode = 2 Then
tryNormal = False
End If
Else
tryRotated = False
End If
For i = 1 To freeCount
If tryNormal Then
rw = reqW
rh = reqH
If rw <= freeRects(i).w + EPS And rh <= freeRects(i).h + EPS Then
score = PlacementScoreWithContact(freeRects(i), rw, rh, fitMode, placed, placedCount, contactBonus, guillotineBonus)
alignScore = AlignmentPenalty(placed, placedCount, freeRects(i).x, freeRects(i).y)
tieY = freeRects(i).y
tieX = freeRects(i).x
If IsBetterPlacement(score, alignScore, tieY, tieX, bestScore, bestAlign, bestTieY, bestTieX) Then
bestScore = score
bestAlign = alignScore
bestTieY = tieY
bestTieX = tieX
bestX = freeRects(i).x
bestY = freeRects(i).y
bestW = rw
bestH = rh
bestRot = False
found = True
End If
End If
End If
If tryRotated Then
rw = reqH
rh = reqW
If rw <= freeRects(i).w + EPS And rh <= freeRects(i).h + EPS Then
score = PlacementScoreWithContact(freeRects(i), rw, rh, fitMode, placed, placedCount, contactBonus, guillotineBonus)
alignScore = AlignmentPenalty(placed, placedCount, freeRects(i).x, freeRects(i).y)
tieY = freeRects(i).y
tieX = freeRects(i).x
If IsBetterPlacement(score, alignScore, tieY, tieX, bestScore, bestAlign, bestTieY, bestTieX) Then
bestScore = score
bestAlign = alignScore
bestTieY = tieY
bestTieX = tieX
bestX = freeRects(i).x
bestY = freeRects(i).y
bestW = rw
bestH = rh
bestRot = True
found = True
End If
End If
End If
Next i
FindBestPlacement = found
End Function
Private Sub PackOneBinOrdered(ByRef items() As TBanner, ByRef order() As Long, ByVal orderCount As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef rotationPrefs() As Long, ByRef placed() As TPlaced, ByRef placedCount As Long, ByRef outIdx() As Long, ByRef outCount As Long)
Dim freeRects() As TFreeRect
Dim freeCount As Long
Dim k As Long
Dim rid As Long
Dim reqW As Double
Dim reqH As Double
Dim bestX As Double
Dim bestY As Double
Dim bestW As Double
Dim bestH As Double
Dim bestRot As Boolean
If orderCount <= 0 Then
ReDim placed(1 To 1)
ReDim outIdx(1 To 1)
placedCount = 0
outCount = 0
Exit Sub
End If
ReDim placed(1 To orderCount)
ReDim outIdx(1 To orderCount)
placedCount = 0
outCount = 0
ReDim freeRects(1 To 1)
freeCount = 1
freeRects(1).x = 0#
freeRects(1).y = 0#
freeRects(1).w = rollWidth
freeRects(1).h = maxHeight
For k = 1 To orderCount
rid = order(k)
reqW = items(rid).OrigW + 2# * items(rid).margin
reqH = items(rid).OrigH + 2# * items(rid).margin
If FindBestPlacement(freeRects, freeCount, reqW, reqH, allowRotation, rotationPrefs(rid), fitMode, placed, placedCount, bestX, bestY, bestW, bestH, bestRot) Then
placedCount = placedCount + 1
placed(placedCount).rid = rid
placed(placedCount).x = bestX
placed(placedCount).y = bestY
placed(placedCount).w = bestW
placed(placedCount).h = bestH
placed(placedCount).Rotated = bestRot
PlaceAndSplit freeRects, freeCount, bestX, bestY, bestW, bestH
Else
outCount = outCount + 1
outIdx(outCount) = rid
End If
Next k
End Sub
Private Sub PackMultiRollWithOrder(ByRef items() As TBanner, ByVal orderCount As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef rolls() As TRoll, ByRef rollCount As Long, ByRef notPlaced As Long)
Dim remaining() As Long
Dim nextRemaining() As Long
Dim placed() As TPlaced
Dim outIdx() As Long
Dim remainingCount As Long
Dim outCount As Long
Dim placedCount As Long
Dim i As Long
Dim safety As Long
rollCount = 0
notPlaced = 0
If orderCount <= 0 Then Exit Sub
ReDim rolls(1 To MAX_ROLLS)
ReDim remaining(1 To orderCount)
For i = 1 To orderCount
remaining(i) = order(i)
Next i
remainingCount = orderCount
Do While remainingCount > 0
safety = safety + 1
If safety > MAX_ROLLS Then
notPlaced = remainingCount
Exit Do
End If
PackOneBinOrdered items, remaining, remainingCount, rollWidth, maxHeight, allowRotation, fitMode, rotationPrefs, placed, placedCount, outIdx, outCount
If placedCount <= 0 Then
notPlaced = remainingCount
Exit Do
End If
rollCount = rollCount + 1
rolls(rollCount).placedCount = placedCount
ReDim rolls(rollCount).placed(1 To placedCount)
For i = 1 To placedCount
rolls(rollCount).placed(i) = placed(i)
Next i
rolls(rollCount).UsedHeight = CalcPlacedHeight(placed, placedCount)
If outCount <= 0 Then
remainingCount = 0
Exit Do
End If
ReDim nextRemaining(1 To outCount)
For i = 1 To outCount
nextRemaining(i) = outIdx(i)
Next i
ReDim remaining(1 To outCount)
For i = 1 To outCount
remaining(i) = nextRemaining(i)
Next i
remainingCount = outCount
Loop
End Sub
Private Function CalcPlacedHeight(ByRef placed() As TPlaced, ByVal placedCount As Long) As Double
Dim i As Long
Dim h As Double
h = 0#
For i = 1 To placedCount
h = MaxD(h, placed(i).y + placed(i).h)
Next i
CalcPlacedHeight = h
End Function
Private Function CalcMaterialUsed(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double
Dim r As Long
Dim total As Double
total = 0#
For r = 1 To rollCount
total = total + rollWidth * rolls(r).UsedHeight
Next r
CalcMaterialUsed = total
End Function
Private Function CalcTrueArea(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim r As Long
Dim i As Long
Dim rid As Long
Dim total As Double
total = 0#
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
rid = rolls(r).placed(i).rid
total = total + items(rid).OrigW * items(rid).OrigH
Next i
Next r
CalcTrueArea = total
End Function
Private Function CalcWaste(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double
Dim material As Double
Dim trueArea As Double
material = CalcMaterialUsed(rolls, rollCount, rollWidth)
trueArea = CalcTrueArea(items, rolls, rollCount)
If material <= EPS Then
CalcWaste = 1#
Else
CalcWaste = (material - trueArea) / material
End If
End Function
Private Function CalcRightWaste(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double
Dim r As Long
Dim i As Long
Dim rightEdge As Double
Dim maxRightEdge As Double
Dim waste As Double
Dim worstWaste As Double
worstWaste = 0#
For r = 1 To rollCount
maxRightEdge = 0#
For i = 1 To rolls(r).placedCount
rightEdge = rolls(r).placed(i).x + rolls(r).placed(i).w
maxRightEdge = MaxD(maxRightEdge, rightEdge)
Next i
waste = rollWidth - maxRightEdge
If waste < 0# Then waste = 0#
worstWaste = MaxD(worstWaste, waste)
Next r
CalcRightWaste = worstWaste
End Function
Private Function CalcAlignmentScore(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim r As Long
Dim i As Long
Dim j As Long
Dim score As Double
Dim leftDist As Double
Dim topDist As Double
Dim candidateVisualTop As Double
Dim otherVisualTop As Double
Dim bestLeft As Double
Dim bestTop As Double
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
bestLeft = 1E+30
bestTop = 1E+30
candidateVisualTop = rolls(r).placed(i).y
For j = 1 To rolls(r).placedCount
If i <> j Then
leftDist = AbsD(rolls(r).placed(i).x - rolls(r).placed(j).x)
otherVisualTop = rolls(r).placed(j).y
topDist = AbsD(candidateVisualTop - otherVisualTop)
bestLeft = MinD(bestLeft, leftDist)
bestTop = MinD(bestTop, topDist)
End If
Next j
If bestLeft <= ALIGN_TOLERANCE Then bestLeft = 0#
If bestTop <= ALIGN_TOLERANCE Then bestTop = 0#
If bestLeft < 1E+20 Then score = score + bestLeft
If bestTop < 1E+20 Then score = score + bestTop
Next i
Next r
CalcAlignmentScore = score
End Function
Private Function CalcSharedEdgeLength(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim r As Long
Dim i As Long
Dim j As Long
Dim total As Double
total = 0#
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount - 1
For j = i + 1 To rolls(r).placedCount
total = total + SharedEdgeLengthBetween(rolls(r).placed(i), rolls(r).placed(j))
Next j
Next i
Next r
CalcSharedEdgeLength = total
End Function
Private Function CalcContactSegments(ByRef rolls() As TRoll, ByVal rollCount As Long) As Long
Dim r As Long
Dim i As Long
Dim j As Long
Dim edge As Double
Dim count As Long
count = 0
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount - 1
For j = i + 1 To rolls(r).placedCount
edge = SharedEdgeLengthBetween(rolls(r).placed(i), rolls(r).placed(j))
If edge > CONTACT_TOLERANCE Then count = count + 1
Next j
Next i
Next r
CalcContactSegments = count
End Function
Private Function CalcGuillotineEdgeLength(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim r As Long
Dim i As Long
Dim j As Long
Dim edge As Double
Dim total As Double
total = 0#
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount - 1
For j = i + 1 To rolls(r).placedCount
edge = StrongGuillotineEdgeBetween(rolls(r).placed(i), rolls(r).placed(j))
total = total + edge
Next j
Next i
Next r
CalcGuillotineEdgeLength = total
End Function
Private Function CalcCutFriendlyPenalty(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double) As Double
Dim sharedEdge As Double
Dim strongEdge As Double
Dim segments As Long
Dim penalty As Double
Dim r As Long
Dim i As Long
Dim boundaryContact As Double
sharedEdge = CalcSharedEdgeLength(rolls, rollCount)
strongEdge = CalcGuillotineEdgeLength(rolls, rollCount)
segments = CalcContactSegments(rolls, rollCount)
boundaryContact = 0#
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
If AbsD(rolls(r).placed(i).x) <= CONTACT_TOLERANCE Then boundaryContact = boundaryContact + rolls(r).placed(i).h
If AbsD(rolls(r).placed(i).x + rolls(r).placed(i).w - rollWidth) <= CONTACT_TOLERANCE Then boundaryContact = boundaryContact + rolls(r).placed(i).h
If AbsD(rolls(r).placed(i).y) <= CONTACT_TOLERANCE Then boundaryContact = boundaryContact + rolls(r).placed(i).w
If AbsD(rolls(r).placed(i).y + rolls(r).placed(i).h - rolls(r).UsedHeight) <= CONTACT_TOLERANCE Then boundaryContact = boundaryContact + rolls(r).placed(i).w
Next i
Next r
penalty = CDbl(segments) * 2#
penalty = penalty - sharedEdge * 0.08
penalty = penalty - strongEdge * 0.18
penalty = penalty - boundaryContact * 0.03
If penalty < 0# Then penalty = 0#
CalcCutFriendlyPenalty = penalty
End Function
Private Function CalcContactScore(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim sharedEdge As Double
Dim segments As Long
Dim score As Double
sharedEdge = CalcSharedEdgeLength(rolls, rollCount)
segments = CalcContactSegments(rolls, rollCount)
score = sharedEdge
score = score - CDbl(segments) * 0.5
If score < 0# Then score = 0#
CalcContactScore = score
End Function
Private Function PackScore(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal notPlaced As Long, ByVal rollWidth As Double, ByRef rightWaste As Double, ByRef alignmentScore As Double, ByRef materialUsed As Double) As Double
Dim excessRight As Double
Dim contactScore As Double
Dim cutPenalty As Double
rightWaste = CalcRightWaste(rolls, rollCount, rollWidth)
alignmentScore = CalcAlignmentScore(rolls, rollCount)
' IMPORTANT: materialUsed is already the real material area consumed:
' sum over rolls of (rollWidth x roll UsedHeight).
' Therefore roll HEIGHT is already considered together with WIDTH.
materialUsed = CalcMaterialUsed(rolls, rollCount, rollWidth)
If notPlaced > 0 Then
PackScore = 1E+30 + CDbl(notPlaced) * 1E+25
Exit Function
End If
excessRight = rightWaste - MAX_RIGHT_WASTE
If excessRight < 0# Then excessRight = 0#
contactScore = CalcContactScore(rolls, rollCount)
cutPenalty = CalcCutFriendlyPenalty(rolls, rollCount, rollWidth)
' OBJECTIVE PRIORITY:
' 1) Feasible layout (handled above)
' 2) Minimum material area = width x used height
' 3) Minimum right waste above the 10 cm target
' 4) Alignment / contact / cut friendliness / roll count as tie-breakers
'
' The material scale is deliberately dominant. A meaningful reduction
' in material area must beat improvements in the secondary metrics.
PackScore = materialUsed * MATERIAL_SCORE_SCALE _
+ excessRight * RIGHT_WASTE_SCORE_SCALE _
+ alignmentScore * ALIGNMENT_SCORE_SCALE _
- contactScore * CONTACT_SCORE_WEIGHT _
+ cutPenalty * GUILLOTINE_SCORE_WEIGHT _
+ CDbl(rollCount) * ROLL_COUNT_SCORE_SCALE
End Function
Private Function EvaluateOrderScoreWithRotation(ByRef items() As TBanner, ByVal orderCount As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef outRollCount As Long, ByRef outNotPlaced As Long, ByRef outRightWaste As Double, ByRef outAlignment As Double, ByRef outMaterial As Double) As Double
Dim testRolls() As TRoll
PackMultiRollWithOrder items, orderCount, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRolls, outRollCount, outNotPlaced
EvaluateOrderScoreWithRotation = PackScore(items, testRolls, outRollCount, outNotPlaced, rollWidth, outRightWaste, outAlignment, outMaterial)
End Function
Private Sub AddSeed(ByRef seedOrders() As Long, ByRef seedScores() As Double, ByRef seedWidths() As Double, ByRef seedFits() As Long, ByRef seedSorts() As Long, ByRef seedCount As Long, ByVal maxSeeds As Long, ByRef candidateOrder() As Long, ByVal n As Long, ByVal candidateScore As Double, ByVal candidateWidth As Double, ByVal candidateFit As Long, ByVal candidateSort As Long)
Dim pos As Long
Dim i As Long
Dim j As Long
If maxSeeds <= 0 Then Exit Sub
pos = 0
For i = 1 To maxSeeds
If i > seedCount Then
pos = i
Exit For
End If
If candidateScore < seedScores(i) Then
pos = i
Exit For
End If
Next i
If pos = 0 Then Exit Sub
If seedCount < maxSeeds Then seedCount = seedCount + 1
For i = seedCount To pos + 1 Step -1
seedScores(i) = seedScores(i - 1)
seedWidths(i) = seedWidths(i - 1)
seedFits(i) = seedFits(i - 1)
seedSorts(i) = seedSorts(i - 1)
For j = 1 To n
seedOrders(i, j) = seedOrders(i - 1, j)
Next j
Next i
seedScores(pos) = candidateScore
seedWidths(pos) = candidateWidth
seedFits(pos) = candidateFit
seedSorts(pos) = candidateSort
For j = 1 To n
seedOrders(pos, j) = candidateOrder(j)
Next j
End Sub
Private Sub CopyOrderFromSeed(ByRef seedOrders() As Long, ByVal seedNo As Long, ByVal n As Long, ByRef order() As Long)
Dim i As Long
ReDim order(1 To n)
For i = 1 To n
order(i) = seedOrders(seedNo, i)
Next i
End Sub
Private Sub BuildDestroyScores(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double, ByVal n As Long, ByVal mode As Long, ByRef ids() As Long, ByRef scores() As Double)
Dim i As Long
Dim r As Long
Dim j As Long
Dim rid As Long
Dim bestLeft As Double
Dim bestTop As Double
Dim leftDist As Double
Dim topDist As Double
Dim rightWaste As Double
Dim alignment As Double
Dim xPos As Double
Dim area As Double
Dim shortSide As Double
Dim longSide As Double
Dim contactEdge As Double
Dim strongEdge As Double
ReDim ids(1 To n)
ReDim scores(1 To n)
For i = 1 To n
ids(i) = i
scores(i) = 0#
Next i
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
rid = rolls(r).placed(i).rid
rightWaste = rollWidth - rolls(r).placed(i).x - rolls(r).placed(i).w
If rightWaste < 0# Then rightWaste = 0#
bestLeft = 1E+30
bestTop = 1E+30
For j = 1 To rolls(r).placedCount
If j <> i Then
leftDist = AbsD(rolls(r).placed(i).x - rolls(r).placed(j).x)
topDist = AbsD(rolls(r).placed(i).y - rolls(r).placed(j).y)
bestLeft = MinD(bestLeft, leftDist)
bestTop = MinD(bestTop, topDist)
End If
Next j
If bestLeft >= 1E+20 Then bestLeft = 0#
If bestTop >= 1E+20 Then bestTop = 0#
alignment = bestLeft + bestTop
xPos = rolls(r).placed(i).x
contactEdge = 0#
strongEdge = 0#
For j = 1 To rolls(r).placedCount
If j <> i Then
contactEdge = contactEdge + SharedEdgeLengthBetween(rolls(r).placed(i), rolls(r).placed(j))
strongEdge = strongEdge + StrongGuillotineEdgeBetween(rolls(r).placed(i), rolls(r).placed(j))
End If
Next j
area = AreaOf(items(rid))
shortSide = MinD(items(rid).OrigW + 2# * items(rid).margin, items(rid).OrigH + 2# * items(rid).margin)
longSide = MaxD(items(rid).OrigW + 2# * items(rid).margin, items(rid).OrigH + 2# * items(rid).margin)
Select Case mode
Case 1
scores(rid) = rightWaste * 10# + alignment
Case 2
scores(rid) = area
Case 3
scores(rid) = alignment * 2# + rightWaste
Case 4
scores(rid) = longSide * 2# + rightWaste
Case 5
scores(rid) = xPos + rightWaste
Case 6
scores(rid) = -contactEdge + rightWaste * 0.2 + alignment * 0.1
Case 7
scores(rid) = -strongEdge + rightWaste * 0.1 + alignment * 0.1
Case Else
scores(rid) = rightWaste * 10# + alignment
End Select
Next i
Next r
For i = 1 To n - 1
For j = i + 1 To n
If scores(ids(j)) > scores(ids(i)) Then
SwapLong ids, i, j
End If
Next j
Next i
End Sub
Private Function GetDestroyCount(ByVal n As Long, ByVal iteration As Long) As Long
Dim d As Long
If n <= 12 Then
d = 3
ElseIf n <= 25 Then
d = 4
ElseIf n <= 50 Then
d = 5
Else
d = 6
End If
If iteration Mod 4 = 0 Then d = d + 1
If d > n - 1 Then d = n - 1
If d < 1 Then d = 1
GetDestroyCount = d
End Function
Private Sub BuildDestroyList(ByRef items() As TBanner, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double, ByVal n As Long, ByVal destroyCount As Long, ByVal mode As Long, ByRef selected() As Long, ByRef selectedCount As Long)
Dim ids() As Long
Dim scores() As Double
Dim i As Long
BuildDestroyScores items, rolls, rollCount, rollWidth, n, mode, ids, scores
selectedCount = destroyCount
If selectedCount > n - 1 Then selectedCount = n - 1
If selectedCount < 1 Then
ReDim selected(1 To 1)
selectedCount = 0
Exit Sub
End If
ReDim selected(1 To selectedCount)
For i = 1 To selectedCount
selected(i) = ids(i)
Next i
End Sub
Private Sub BuildOrderWithoutSelected(ByRef order() As Long, ByVal orderCount As Long, ByRef selected() As Long, ByVal selectedCount As Long, ByRef baseOrder() As Long, ByRef baseCount As Long, ByRef removed() As Long, ByRef removedCount As Long)
Dim i As Long
Dim rid As Long
ReDim baseOrder(1 To orderCount)
ReDim removed(1 To selectedCount)
baseCount = 0
removedCount = 0
For i = 1 To orderCount
rid = order(i)
If ContainsLong(selected, selectedCount, rid) Then
removedCount = removedCount + 1
removed(removedCount) = rid
Else
baseCount = baseCount + 1
baseOrder(baseCount) = rid
End If
Next i
End Sub
Private Sub SortRemovedByArea(ByRef items() As TBanner, ByRef removed() As Long, ByVal removedCount As Long)
Dim i As Long
Dim j As Long
Dim tmp As Long
For i = 1 To removedCount - 1
For j = i + 1 To removedCount
If AreaOf(items(removed(j))) > AreaOf(items(removed(i))) Then
tmp = removed(i)
removed(i) = removed(j)
removed(j) = tmp
End If
Next j
Next i
End Sub
Private Sub AddRepairPosition(ByRef positions() As Long, ByRef count As Long, ByVal value As Long, ByVal maxValue As Long)
Dim i As Long
If value < 1 Then value = 1
If value > maxValue Then value = maxValue
For i = 1 To count
If positions(i) = value Then Exit Sub
Next i
count = count + 1
positions(count) = value
End Sub
Private Sub BuildRepairPositions(ByVal baseCount As Long, ByRef positions() As Long, ByRef positionCount As Long)
Dim i As Long
Dim stepValue As Double
Dim value As Long
positionCount = 0
ReDim positions(1 To MAX_LNS_REPAIR_POSITIONS)
If baseCount + 1 <= MAX_LNS_REPAIR_POSITIONS Then
For i = 1 To baseCount + 1
AddRepairPosition positions, positionCount, i, baseCount + 1
Next i
Exit Sub
End If
AddRepairPosition positions, positionCount, 1, baseCount + 1
AddRepairPosition positions, positionCount, baseCount + 1, baseCount + 1
stepValue = CDbl(baseCount) / CDbl(MAX_LNS_REPAIR_POSITIONS - 2)
For i = 0 To MAX_LNS_REPAIR_POSITIONS - 3
value = 1 + CLng(Int(CDbl(i) * stepValue))
AddRepairPosition positions, positionCount, value, baseCount + 1
Next i
End Sub
Private Sub RepairDestroyedItems(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef baseOrder() As Long, ByVal baseCount As Long, ByRef removed() As Long, ByVal removedCount As Long, ByRef rotationPrefs() As Long, ByRef outOrder() As Long, ByRef outScore As Double)
Dim currentCount As Long
Dim positions() As Long
Dim positionCount As Long
Dim i As Long
Dim p As Long
Dim rid As Long
Dim mode As Long
Dim oldPref As Long
Dim testScore As Double
Dim bestLocalScore As Double
Dim bestPosition As Long
Dim bestMode As Long
Dim testRollCount As Long
Dim testNotPlaced As Long
Dim testRight As Double
Dim testAlign As Double
Dim testMaterial As Double
ReDim outOrder(1 To n)
currentCount = 0
For i = 1 To baseCount
outOrder(i) = baseOrder(i)
Next i
currentCount = baseCount
SortRemovedByArea items, removed, removedCount
For i = 1 To removedCount
rid = removed(i)
BuildRepairPositions currentCount, positions, positionCount
bestLocalScore = 1E+30
bestPosition = 1
bestMode = 0
oldPref = rotationPrefs(rid)
For p = 1 To positionCount
For mode = 0 To 2
If Not allowRotation And mode <> 0 Then GoTo NextRepairMode
InsertLongAt outOrder, currentCount, positions(p), rid
rotationPrefs(rid) = mode
testScore = EvaluateOrderScoreWithRotation(items, currentCount, rollWidth, maxHeight, allowRotation, fitMode, outOrder, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < bestLocalScore - EPS Then
bestLocalScore = testScore
bestPosition = positions(p)
bestMode = mode
End If
RemoveLongAt outOrder, currentCount, positions(p)
NextRepairMode:
Next mode
Next p
InsertLongAt outOrder, currentCount, bestPosition, rid
rotationPrefs(rid) = bestMode
Next i
outScore = EvaluateOrderScoreWithRotation(items, currentCount, rollWidth, maxHeight, allowRotation, fitMode, outOrder, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
End Sub
Private Function GetCurrentRotation(ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rid As Long) As Boolean
Dim r As Long
Dim i As Long
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
If rolls(r).placed(i).rid = rid Then
GetCurrentRotation = rolls(r).placed(i).Rotated
Exit Function
End If
Next i
Next r
GetCurrentRotation = False
End Function
Private Sub TryRotationMutation(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef currentScore As Double)
Dim currentRolls() As TRoll
Dim currentRollCount As Long
Dim currentNotPlaced As Long
Dim currentRight As Double
Dim currentAlign As Double
Dim currentMaterial As Double
Dim ids() As Long
Dim scores() As Double
Dim i As Long
Dim rid As Long
Dim oldPref As Long
Dim newPref As Long
Dim actualRotated As Boolean
Dim testScore As Double
Dim testRollCount As Long
Dim testNotPlaced As Long
Dim testRight As Double
Dim testAlign As Double
Dim testMaterial As Double
Dim mutationCount As Long
If Not allowRotation Then Exit Sub
PackMultiRollWithOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentRolls, currentRollCount, currentNotPlaced
If currentNotPlaced > 0 Then Exit Sub
BuildDestroyScores items, currentRolls, currentRollCount, rollWidth, n, 1, ids, scores
mutationCount = MinD(MAX_ROTATION_MUTATIONS, n)
For i = 1 To mutationCount
rid = ids(i)
oldPref = rotationPrefs(rid)
actualRotated = GetCurrentRotation(currentRolls, currentRollCount, rid)
If oldPref = 0 Then
If actualRotated Then
newPref = 1
Else
newPref = 2
End If
ElseIf oldPref = 1 Then
newPref = 2
Else
newPref = 1
End If
rotationPrefs(rid) = newPref
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testNotPlaced = 0 And testScore < currentScore - EPS Then
currentScore = testScore
PackMultiRollWithOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentRolls, currentRollCount, currentNotPlaced
Else
rotationPrefs(rid) = oldPref
End If
Next i
End Sub
Private Sub OptimizeOrder(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef finalScore As Double)
Dim currentScore As Double
Dim testScore As Double
Dim testRollCount As Long
Dim testNotPlaced As Long
Dim testRight As Double
Dim testAlign As Double
Dim testMaterial As Double
Dim i As Long
Dim j As Long
Dim moveCount As Long
Dim passNo As Long
Dim improved As Boolean
currentScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
For passNo = 1 To MAX_LOCAL_PASSES
improved = False
For i = 1 To n - 1
SwapLong order, i, i + 1
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, i + 1
End If
Next i
moveCount = 0
For i = 1 To n - 2
For j = i + 2 To n
moveCount = moveCount + 1
If moveCount > MAX_PAIR_MOVES Then Exit For
SwapLong order, i, j
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, j
End If
Next j
If moveCount >= MAX_PAIR_MOVES Then Exit For
Next i
moveCount = 0
For i = 1 To n
For j = 1 To n
If i <> j Then
moveCount = moveCount + 1
If moveCount > MAX_REINSERT_MOVES Then Exit For
MoveItemOrder order, i, j, n
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
MoveItemOrder order, j, i, n
End If
End If
Next j
If moveCount >= MAX_REINSERT_MOVES Then Exit For
Next i
moveCount = 0
For i = 1 To n - 2
If moveCount >= MAX_TRIPLE_MOVES Then Exit For
SwapLong order, i + 1, i + 2
moveCount = moveCount + 1
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i + 1, i + 2
End If
If moveCount >= MAX_TRIPLE_MOVES Then Exit For
SwapLong order, i, i + 1
moveCount = moveCount + 1
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, i + 1
End If
If moveCount >= MAX_TRIPLE_MOVES Then Exit For
SwapLong order, i, i + 2
moveCount = moveCount + 1
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, i + 2
End If
Next i
If Not improved Then Exit For
Next passNo
OptimizeContactAndCut items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentScore
finalScore = currentScore
End Sub
Private Sub OptimizeContactAndCut(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef currentScore As Double)
Dim i As Long
Dim j As Long
Dim moveCount As Long
Dim testScore As Double
Dim testRollCount As Long
Dim testNotPlaced As Long
Dim testRight As Double
Dim testAlign As Double
Dim testMaterial As Double
Dim improved As Boolean
Dim passNo As Long
For passNo = 1 To 2
improved = False
moveCount = 0
For i = 1 To n - 1
SwapLong order, i, i + 1
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
moveCount = moveCount + 1
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, i + 1
End If
If moveCount >= MAX_CONTACT_MOVES Then Exit For
Next i
If moveCount < MAX_CONTACT_MOVES Then
For i = 1 To n - 2
For j = i + 2 To n
SwapLong order, i, j
testScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
moveCount = moveCount + 1
If testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, j
End If
If moveCount >= MAX_CUT_MOVES Then Exit For
Next j
If moveCount >= MAX_CUT_MOVES Then Exit For
Next i
End If
If Not improved Then Exit For
Next passNo
End Sub
Private Function GetLNSIterationLimit(ByVal n As Long) As Long
If n <= 30 Then
GetLNSIterationLimit = MAX_LNS_ITERATIONS
ElseIf n <= 60 Then
GetLNSIterationLimit = 8
Else
GetLNSIterationLimit = 6
End If
End Function
Private Sub OptimizeWithLNS(ByRef items() As TBanner, ByVal n As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef finalScore As Double, ByRef lnsIterationsUsed As Long, ByRef lnsImprovements As Long)
Dim currentScore As Double
Dim repairedScore As Double
Dim optimizedScore As Double
Dim iteration As Long
Dim destroyCount As Long
Dim selectionMode As Long
Dim selected() As Long
Dim selectedCount As Long
Dim baseOrder() As Long
Dim baseCount As Long
Dim removed() As Long
Dim removedCount As Long
Dim trialOrder() As Long
Dim trialPrefs() As Long
Dim currentRolls() As TRoll
Dim trialRolls() As TRoll
Dim currentRollCount As Long
Dim currentNotPlaced As Long
Dim trialRollCount As Long
Dim trialNotPlaced As Long
Dim currentRight As Double
Dim currentAlign As Double
Dim currentMaterial As Double
Dim trialRight As Double
Dim trialAlign As Double
Dim trialMaterial As Double
Dim tempScore As Double
Dim acceptWorse As Boolean
Dim i As Long
Dim iterationLimit As Long
lnsIterationsUsed = 0
lnsImprovements = 0
currentScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentRollCount, currentNotPlaced, currentRight, currentAlign, currentMaterial)
OptimizeOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, optimizedScore
currentScore = optimizedScore
If n < 3 Then
finalScore = currentScore
Exit Sub
End If
iterationLimit = GetLNSIterationLimit(n)
For iteration = 1 To iterationLimit
lnsIterationsUsed = iteration
destroyCount = GetDestroyCount(n, iteration)
selectionMode = ((iteration - 1) Mod 7) + 1
PackMultiRollWithOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentRolls, currentRollCount, currentNotPlaced
If currentNotPlaced > 0 Then Exit For
BuildDestroyList items, currentRolls, currentRollCount, rollWidth, n, destroyCount, selectionMode, selected, selectedCount
BuildOrderWithoutSelected order, n, selected, selectedCount, baseOrder, baseCount, removed, removedCount
CopyRotationPrefs rotationPrefs, n, trialPrefs
For i = 1 To selectedCount
trialPrefs(selected(i)) = 0
Next i
RepairDestroyedItems items, n, rollWidth, maxHeight, allowRotation, fitMode, baseOrder, baseCount, removed, removedCount, trialPrefs, trialOrder, repairedScore
acceptWorse = False
If repairedScore < currentScore - EPS Then
acceptWorse = True
ElseIf iteration Mod 5 = 0 Then
If repairedScore < currentScore * (1# + LNS_ACCEPT_WORSE_PCT) Then
acceptWorse = True
End If
End If
If acceptWorse Then
CopyOrder trialOrder, n, order
CopyRotationPrefs trialPrefs, n, rotationPrefs
currentScore = repairedScore
lnsImprovements = lnsImprovements + 1
OptimizeOrder items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, optimizedScore
If optimizedScore < currentScore - EPS Then
currentScore = optimizedScore
End If
End If
TryRotationMutation items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, currentScore
tempScore = EvaluateOrderScoreWithRotation(items, n, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, trialRollCount, trialNotPlaced, trialRight, trialAlign, trialMaterial)
If tempScore < currentScore - EPS Then currentScore = tempScore
Next iteration
finalScore = currentScore
End Sub
Private Sub MoveShapeToBottomLeft(ByVal sh As Shape, ByVal targetX As Double, ByVal targetY As Double)
Dim bx As Double
Dim by As Double
Dim bw As Double
Dim bh As Double
sh.GetBoundingBox bx, by, bw, bh, False
sh.Move targetX - bx, targetY - by
End Sub
Private Sub ApplyNestingToObjects(ByRef items() As TBanner, ByRef sourceShapes() As Shape, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double)
Dim totalHeight As Double
Dim rollOffsetY As Double
Dim r As Long
Dim i As Long
Dim rid As Long
Dim margin As Double
Dim targetX As Double
Dim targetY As Double
Dim pageLeft As Double
Dim pageBottom As Double
Dim pageTop As Double
Dim rollTop As Double
Dim sh As Shape
totalHeight = 0#
For r = 1 To rollCount
totalHeight = totalHeight + rolls(r).UsedHeight
If r < rollCount Then totalHeight = totalHeight + ROLL_GAP
Next r
If totalHeight <= EPS Then totalHeight = 10#
ActivePage.SizeWidth = rollWidth
ActivePage.SizeHeight = totalHeight
pageLeft = ActivePage.LeftX
pageBottom = ActivePage.BottomY
pageTop = ActivePage.TopY
rollOffsetY = 0#
For r = 1 To rollCount
rollTop = pageTop - rollOffsetY
For i = 1 To rolls(r).placedCount
rid = rolls(r).placed(i).rid
Set sh = sourceShapes(rid)
margin = items(rid).margin
If rolls(r).placed(i).Rotated Then sh.Rotate 90#
targetX = pageLeft + rolls(r).placed(i).x + margin
targetY = rollTop - rolls(r).placed(i).y - rolls(r).placed(i).h + margin
MoveShapeToBottomLeft sh, targetX, targetY
Next i
rollOffsetY = rollOffsetY + rolls(r).UsedHeight
If r < rollCount Then rollOffsetY = rollOffsetY + ROLL_GAP
Next r
ActiveDocument.ClearSelection
For r = 1 To rollCount
For i = 1 To rolls(r).placedCount
rid = rolls(r).placed(i).rid
sourceShapes(rid).CreateSelection
Next i
Next r
End Sub
Private Sub ParseWidthList(ByVal txt As String, ByRef widths() As Double, ByRef widthCount As Long)
Dim parts() As String
Dim i As Long
Dim v As Double
widthCount = 0
parts = Split(txt, ",")
ReDim widths(1 To UBound(parts) + 1)
For i = LBound(parts) To UBound(parts)
If Len(Trim$(parts(i))) > 0 Then
v = Val(Trim$(parts(i)))
If v > 0# Then
widthCount = widthCount + 1
widths(widthCount) = v
End If
End If
Next i
If widthCount <= 0 Then
ReDim widths(1 To 1)
Else
ReDim Preserve widths(1 To widthCount)
End If
End Sub
Private Function SortModeName(ByVal mode As Long) As String
Select Case mode
Case 1
SortModeName = "Area Descending"
Case 2
SortModeName = "Width Descending"
Case 3
SortModeName = "Height Descending"
Case 4
SortModeName = "Short Side Descending"
Case 5
SortModeName = "Long Side Descending"
Case 6
SortModeName = "Aspect Ratio Descending"
Case Else
SortModeName = "Unknown"
End Select
End Function
Private Function FitModeName(ByVal mode As Long) As String
Select Case mode
Case 1
FitModeName = "BSSF"
Case 2
FitModeName = "BAF"
Case 3
FitModeName = "BLSF"
Case Else
FitModeName = "Unknown"
End Select
End Function
' -----------------------------------------------------------------------------
' MULTI-WIDTH HELPERS
' This version compares the existing best single-width result against layouts
' using two different roll widths. Each object is assigned to exactly one group.
' The partition candidates are generated from several sort strategies and
' split points, then both groups are packed and scored independently. This is a
' bounded heuristic: it compares one-width against two-width solutions, not all
' possible arbitrary partitions and not three-or-more-width combinations.
' -----------------------------------------------------------------------------
Private Sub OptimizeSubsetOrder(ByRef items() As TBanner, ByVal subsetCount As Long, ByVal rollWidth As Double, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByVal fitMode As Long, ByRef order() As Long, ByRef rotationPrefs() As Long, ByRef finalScore As Double)
Dim currentScore As Double
Dim testScore As Double
Dim testRollCount As Long
Dim testNotPlaced As Long
Dim testRight As Double
Dim testAlign As Double
Dim testMaterial As Double
Dim i As Long
Dim j As Long
Dim passNo As Long
Dim improved As Boolean
Dim moves As Long
If subsetCount <= 1 Then
finalScore = EvaluateOrderScoreWithRotation(items, subsetCount, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
Exit Sub
End If
currentScore = EvaluateOrderScoreWithRotation(items, subsetCount, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
For passNo = 1 To 2
improved = False
For i = 1 To subsetCount - 1
SwapLong order, i, i + 1
testScore = EvaluateOrderScoreWithRotation(items, subsetCount, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
If testNotPlaced = 0 And testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, i + 1
End If
Next i
moves = 0
For i = 1 To subsetCount - 1
For j = i + 1 To subsetCount
If j <> i + 1 Then
SwapLong order, i, j
testScore = EvaluateOrderScoreWithRotation(items, subsetCount, rollWidth, maxHeight, allowRotation, fitMode, order, rotationPrefs, testRollCount, testNotPlaced, testRight, testAlign, testMaterial)
moves = moves + 1
If testNotPlaced = 0 And testScore < currentScore - EPS Then
currentScore = testScore
improved = True
Else
SwapLong order, i, j
End If
If moves >= MAX_PAIR_MOVES Then Exit For
End If
Next j
If moves >= MAX_PAIR_MOVES Then Exit For
Next i
If Not improved Then Exit For
Next passNo
finalScore = currentScore
End Sub
Private Function TotalRollHeight(ByRef rolls() As TRoll, ByVal rollCount As Long) As Double
Dim r As Long
Dim totalHeight As Double
totalHeight = 0#
For r = 1 To rollCount
totalHeight = totalHeight + rolls(r).UsedHeight
If r < rollCount Then totalHeight = totalHeight + ROLL_GAP
Next r
If totalHeight <= EPS Then totalHeight = 10#
TotalRollHeight = totalHeight
End Function
Private Sub ApplyNestingToPage(ByRef items() As TBanner, ByRef sourceShapes() As Shape, ByRef rolls() As TRoll, ByVal rollCount As Long, ByVal rollWidth As Double, ByVal targetPage As Page)
Dim rollOffsetY As Double
Dim r As Long
Dim i As Long
Dim rid As Long
Dim margin As Double
Dim targetX As Double
Dim targetY As Double
Dim pageLeft As Double
Dim pageTop As Double
Dim rollTop As Double
Dim sh As Shape
Dim totalHeight As Double
totalHeight = TotalRollHeight(rolls, rollCount)
targetPage.SetSize rollWidth, totalHeight
targetPage.Activate
pageLeft = targetPage.LeftX
pageTop = targetPage.TopY
rollOffsetY = 0#
ActiveDocument.ClearSelection
For r = 1 To rollCount
rollTop = pageTop - rollOffsetY
For i = 1 To rolls(r).placedCount
rid = rolls(r).placed(i).rid
Set sh = sourceShapes(rid)
' Move the original object to the output page's active layer.
sh.MoveToLayer targetPage.ActiveLayer
margin = items(rid).margin
If rolls(r).placed(i).Rotated Then sh.Rotate 90#
targetX = pageLeft + rolls(r).placed(i).x + margin
targetY = rollTop - rolls(r).placed(i).y - rolls(r).placed(i).h + margin
MoveShapeToBottomLeft sh, targetX, targetY
sh.CreateSelection
Next i
rollOffsetY = rollOffsetY + rolls(r).UsedHeight
If r < rollCount Then rollOffsetY = rollOffsetY + ROLL_GAP
Next r
End Sub
Private Sub FindBestTwoWidthLayout(ByRef items() As TBanner, ByVal n As Long, ByRef widths() As Double, ByVal widthCount As Long, ByVal maxHeight As Double, ByVal allowRotation As Boolean, ByRef outOrderA() As Long, ByRef outCountA As Long, ByRef outWidthA As Double, ByRef outFitA As Long, ByRef outOrderB() As Long, ByRef outCountB As Long, ByRef outWidthB As Double, ByRef outFitB As Long, ByRef outMaterial As Double, ByRef outScore As Double)
Dim sortedOrder() As Long
Dim candidateOrderA() As Long
Dim candidateOrderB() As Long
Dim bestOrderA() As Long
Dim bestOrderB() As Long
Dim rotationPrefs() As Long
Dim candidateRollsA() As TRoll
Dim candidateRollsB() As TRoll
Dim rollCountA As Long
Dim rollCountB As Long
Dim notPlacedA As Long
Dim notPlacedB As Long
Dim candidateCountA As Long
Dim candidateCountB As Long
Dim candidateWidthA As Double
Dim candidateWidthB As Double
Dim candidateMaterialA As Double
Dim candidateMaterialB As Double
Dim candidateMaterial As Double
Dim candidateScoreA As Double
Dim candidateScoreB As Double
Dim candidateCombinedScore As Double
Dim rightA As Double
Dim rightB As Double
Dim alignA As Double
Dim alignB As Double
Dim j As Long
Dim k As Long
Dim widthLimit As Long
Dim sortMode As Long
Dim splitStep As Long
Dim splitPos As Long
Dim previousSplit As Long
Dim direction As Long
Dim fitMode As Long
Dim i As Long
outCountA = 0
outCountB = 0
outWidthA = 0#
outWidthB = 0#
outFitA = 1
outFitB = 1
outMaterial = 1E+30
outScore = 1E+30
If n < 2 Or widthCount < 2 Then Exit Sub
widthLimit = widthCount
If widthLimit > MAX_MULTI_WIDTH_CANDIDATES Then widthLimit = MAX_MULTI_WIDTH_CANDIDATES
ReDim rotationPrefs(1 To n)
For i = 1 To n
rotationPrefs(i) = 0
Next i
For j = 1 To widthLimit - 1
For k = j + 1 To widthLimit
If AbsD(widths(j) - widths(k)) > EPS Then
For sortMode = 1 To 6
BuildInitialOrder items, n, sortMode, sortedOrder
previousSplit = 0
' Split points at approximately 1/5, 2/5, 3/5 and 4/5.
For splitStep = 1 To 4
splitPos = CLng(Int((CDbl(n) * CDbl(splitStep)) / 5#))
If splitPos < 1 Then splitPos = 1
If splitPos > n - 1 Then splitPos = n - 1
If splitPos <> previousSplit Then
previousSplit = splitPos
candidateCountA = splitPos
candidateCountB = n - splitPos
ReDim candidateOrderA(1 To candidateCountA)
ReDim candidateOrderB(1 To candidateCountB)
For i = 1 To candidateCountA
candidateOrderA(i) = sortedOrder(i)
Next i
For i = 1 To candidateCountB
candidateOrderB(i) = sortedOrder(splitPos + i)
Next i
For direction = 1 To 2
If direction = 1 Then
candidateWidthA = widths(j)
candidateWidthB = widths(k)
Else
candidateWidthA = widths(k)
candidateWidthB = widths(j)
End If
For fitMode = 1 To 3
PackMultiRollWithOrder items, candidateCountA, candidateWidthA, maxHeight, allowRotation, fitMode, candidateOrderA, rotationPrefs, candidateRollsA, rollCountA, notPlacedA
candidateScoreA = PackScore(items, candidateRollsA, rollCountA, notPlacedA, candidateWidthA, rightA, alignA, candidateMaterialA)
If notPlacedA = 0 Then
PackMultiRollWithOrder items, candidateCountB, candidateWidthB, maxHeight, allowRotation, fitMode, candidateOrderB, rotationPrefs, candidateRollsB, rollCountB, notPlacedB
candidateScoreB = PackScore(items, candidateRollsB, rollCountB, notPlacedB, candidateWidthB, rightB, alignB, candidateMaterialB)
If notPlacedB = 0 Then
candidateMaterial = candidateMaterialA + candidateMaterialB
candidateCombinedScore = candidateMaterial * MATERIAL_SCORE_SCALE _
+ (candidateScoreA - candidateMaterialA * MATERIAL_SCORE_SCALE) _
+ (candidateScoreB - candidateMaterialB * MATERIAL_SCORE_SCALE)
If candidateMaterial < outMaterial - EPS _
Or (AbsD(candidateMaterial - outMaterial) <= EPS And candidateCombinedScore < outScore) Then
outMaterial = candidateMaterial
outScore = candidateCombinedScore
outWidthA = candidateWidthA
outWidthB = candidateWidthB
outFitA = fitMode
outFitB = fitMode
outCountA = candidateCountA
outCountB = candidateCountB
CopyOrder candidateOrderA, candidateCountA, bestOrderA
CopyOrder candidateOrderB, candidateCountB, bestOrderB
End If
End If
End If
Next fitMode
Next direction
End If
Next splitStep
Next sortMode
End If
Next k
Next j
If outCountA > 0 And outCountB > 0 Then
CopyOrder bestOrderA, outCountA, outOrderA
CopyOrder bestOrderB, outCountB, outOrderB
End If
End Sub
Public Sub RunNesting_BannerCorelDRAW()
Dim doc As Document
Dim sr As ShapeRange
Dim sh As Shape
Dim items() As TBanner
Dim sourceShapes() As Shape
Dim rolls() As TRoll
Dim candidateRolls() As TRoll
Dim candidateOrder() As Long
Dim bestOrder() As Long
Dim workOrder() As Long
Dim workPrefs() As Long
Dim bestPrefs() As Long
Dim seedOrders() As Long
Dim seedScores() As Double
Dim seedWidths() As Double
Dim seedFits() As Long
Dim seedSorts() As Long
Dim n As Long
Dim i As Long
Dim j As Long
Dim oldUnit As Long
Dim marginText As String
Dim margin As Double
Dim rollText As String
Dim widths() As Double
Dim widthCount As Long
Dim rotateAnswer As VbMsgBoxResult
Dim allowRotation As Boolean
Dim maxHeight As Double
Dim minNeeded As Double
Dim candidateWidth As Double
Dim bestWidth As Double
Dim candidateSortMode As Long
Dim candidateFitMode As Long
Dim bestSortMode As Long
Dim bestFitMode As Long
Dim candidateRollCount As Long
Dim candidateNotPlaced As Long
Dim bestRollCount As Long
Dim bestNotPlaced As Long
Dim candidateScore As Double
Dim bestScore As Double
Dim candidateMaterial As Double
Dim bestMaterial As Double
Dim candidateWaste As Double
Dim bestWaste As Double
Dim candidateRightWaste As Double
Dim bestRightWaste As Double
Dim candidateAlignment As Double
Dim bestAlignment As Double
Dim optimizedScore As Double
Dim seedCount As Long
Dim lnsIterationsUsed As Long
Dim lnsImprovements As Long
Dim bx As Double
Dim by As Double
Dim bw As Double
Dim bh As Double
Dim sumSide As Double
Dim maxMargin As Double
Dim msg As String
Dim errNumber As Long
Dim errDescription As String
Dim finalSharedEdge As Double
Dim finalContactSegments As Long
Dim finalGuillotineEdge As Double
Dim finalCutPenalty As Double
Dim multiOrderA() As Long
Dim multiOrderB() As Long
Dim multiPrefs() As Long
Dim multiRollsA() As TRoll
Dim multiRollsB() As TRoll
Dim multiCountA As Long
Dim multiCountB As Long
Dim multiWidthA As Double
Dim multiWidthB As Double
Dim multiFitA As Long
Dim multiFitB As Long
Dim multiBestMaterial As Double
Dim multiBestScore As Double
Dim multiMaterialA As Double
Dim multiMaterialB As Double
Dim multiCombinedMaterial As Double
Dim multiRollCountA As Long
Dim multiRollCountB As Long
Dim multiNotPlacedA As Long
Dim multiNotPlacedB As Long
Dim multiScoreA As Double
Dim multiScoreB As Double
Dim multiRightA As Double
Dim multiRightB As Double
Dim multiAlignA As Double
Dim multiAlignB As Double
Dim multiHeightA As Double
Dim multiHeightB As Double
Dim multiTrueArea As Double
Dim multiWaste As Double
Dim multiSavingPct As Double
Dim useMultiWidth As Boolean
Dim outputPageA As Page
Dim outputPageB As Page
On Error GoTo ErrHandler
Set doc = ActiveDocument
If doc Is Nothing Then
MsgBox "Tidak ada document CorelDRAW aktif.", vbExclamation, "Auto Nesting"
Exit Sub
End If
oldUnit = doc.Unit
Set sr = ActiveSelectionRange
If sr Is Nothing Then
MsgBox "Pilih object/banner terlebih dahulu.", vbExclamation, "Auto Nesting"
Exit Sub
End If
If sr.count <= 0 Then
MsgBox "Pilih minimal 1 object/banner terlebih dahulu.", vbExclamation, "Auto Nesting"
Exit Sub
End If
n = sr.count
doc.Unit = cdrCentimeter
ReDim items(1 To n)
ReDim sourceShapes(1 To n)
i = 0
For Each sh In sr
i = i + 1
Set sourceShapes(i) = sh
sh.GetBoundingBox bx, by, bw, bh, False
If bw <= EPS Or bh <= EPS Then
doc.Unit = oldUnit
MsgBox "Object nomor " & CStr(i) & " memiliki bounding box tidak valid.", vbCritical, "Auto Nesting"
Exit Sub
End If
items(i).Label = "Object " & CStr(i)
items(i).OrigW = bw
items(i).OrigH = bh
items(i).margin = 0#
Next sh
marginText = InputBox("Margin / clearance per sisi (cm):", "Auto Nesting - Margin", "0")
If Len(Trim$(marginText)) > 0 Then margin = Val(Trim$(marginText)) Else margin = 0#
If margin < 0# Then margin = 0#
For i = 1 To n
items(i).margin = margin
Next i
rollText = InputBox("Masukkan daftar lebar roll dalam cm." & vbCrLf & "Contoh: 150,200,250,300", "Auto Nesting - Roll Width", "109,159,219,259,319")
If Len(Trim$(rollText)) = 0 Then
doc.Unit = oldUnit
MsgBox "Lebar roll tidak diberikan.", vbExclamation, "Auto Nesting"
Exit Sub
End If
ParseWidthList rollText, widths, widthCount
If widthCount <= 0 Then
doc.Unit = oldUnit
MsgBox "Daftar lebar roll tidak valid.", vbCritical, "Auto Nesting"
Exit Sub
End If
rotateAnswer = MsgBox("Izinkan object diputar 90°?", vbYesNo + vbQuestion, "Auto Nesting - Rotation")
allowRotation = (rotateAnswer = vbYes)
sumSide = 0#
maxMargin = 0#
For i = 1 To n
sumSide = sumSide + MaxD(items(i).OrigW, items(i).OrigH)
maxMargin = MaxD(maxMargin, items(i).margin)
Next i
maxHeight = sumSide + maxMargin * (n + 2) + 100#
minNeeded = 0#
For i = 1 To n
If allowRotation Then
minNeeded = MaxD(minNeeded, MinD(items(i).OrigW, items(i).OrigH) + 2# * items(i).margin)
Else
minNeeded = MaxD(minNeeded, items(i).OrigW + 2# * items(i).margin)
End If
Next i
ReDim seedOrders(1 To MAX_LOCAL_SEEDS, 1 To n)
ReDim seedScores(1 To MAX_LOCAL_SEEDS)
ReDim seedWidths(1 To MAX_LOCAL_SEEDS)
ReDim seedFits(1 To MAX_LOCAL_SEEDS)
ReDim seedSorts(1 To MAX_LOCAL_SEEDS)
For i = 1 To MAX_LOCAL_SEEDS
seedScores(i) = 1E+30
Next i
seedCount = 0
bestScore = 1E+30
bestMaterial = 1E+30
bestWaste = 1#
bestRightWaste = 1E+30
bestAlignment = 1E+30
bestWidth = 0#
bestRollCount = 0
bestNotPlaced = n
bestSortMode = 1
bestFitMode = 1
ReDim bestOrder(1 To n)
ReDim bestPrefs(1 To n)
For i = 1 To n
bestPrefs(i) = 0
Next i
For j = 1 To widthCount
candidateWidth = widths(j)
If candidateWidth + EPS >= minNeeded Then
For candidateSortMode = 1 To 6
BuildInitialOrder items, n, candidateSortMode, candidateOrder
For candidateFitMode = 1 To 3
ReDim workPrefs(1 To n)
For i = 1 To n
workPrefs(i) = 0
Next i
PackMultiRollWithOrder items, n, candidateWidth, maxHeight, allowRotation, candidateFitMode, candidateOrder, workPrefs, candidateRolls, candidateRollCount, candidateNotPlaced
candidateScore = PackScore(items, candidateRolls, candidateRollCount, candidateNotPlaced, candidateWidth, candidateRightWaste, candidateAlignment, candidateMaterial)
If candidateNotPlaced = 0 Then
candidateWaste = CalcWaste(items, candidateRolls, candidateRollCount, candidateWidth)
Else
candidateWaste = 1#
End If
AddSeed seedOrders, seedScores, seedWidths, seedFits, seedSorts, seedCount, MAX_LOCAL_SEEDS, candidateOrder, n, candidateScore, candidateWidth, candidateFitMode, candidateSortMode
If candidateScore < bestScore - EPS Then
bestScore = candidateScore
bestWidth = candidateWidth
bestRollCount = candidateRollCount
bestNotPlaced = candidateNotPlaced
bestSortMode = candidateSortMode
bestFitMode = candidateFitMode
bestMaterial = candidateMaterial
bestWaste = candidateWaste
bestRightWaste = candidateRightWaste
bestAlignment = candidateAlignment
CopyOrder candidateOrder, n, bestOrder
CopyRotationPrefs workPrefs, n, bestPrefs
End If
Next candidateFitMode
Next candidateSortMode
End If
Next j
' Even if no single width can hold all selected objects, continue: a
' feasible combination of two widths may still exist.
For i = 1 To seedCount
CopyOrderFromSeed seedOrders, i, n, workOrder
ReDim workPrefs(1 To n)
For j = 1 To n
workPrefs(j) = 0
Next j
optimizedScore = 1E+30
OptimizeOrder items, n, seedWidths(i), maxHeight, allowRotation, seedFits(i), workOrder, workPrefs, optimizedScore
PackMultiRollWithOrder items, n, seedWidths(i), maxHeight, allowRotation, seedFits(i), workOrder, workPrefs, candidateRolls, candidateRollCount, candidateNotPlaced
candidateScore = PackScore(items, candidateRolls, candidateRollCount, candidateNotPlaced, seedWidths(i), candidateRightWaste, candidateAlignment, candidateMaterial)
If candidateNotPlaced = 0 Then
candidateWaste = CalcWaste(items, candidateRolls, candidateRollCount, seedWidths(i))
Else
candidateWaste = 1#
End If
If candidateScore < bestScore - EPS Then
bestScore = candidateScore
bestWidth = seedWidths(i)
bestRollCount = candidateRollCount
bestNotPlaced = candidateNotPlaced
bestSortMode = seedSorts(i)
bestFitMode = seedFits(i)
bestMaterial = candidateMaterial
bestWaste = candidateWaste
bestRightWaste = candidateRightWaste
bestAlignment = candidateAlignment
CopyOrder workOrder, n, bestOrder
CopyRotationPrefs workPrefs, n, bestPrefs
End If
Next i
lnsIterationsUsed = 0
lnsImprovements = 0
If bestNotPlaced = 0 And bestWidth > EPS Then
CopyOrder bestOrder, n, workOrder
CopyRotationPrefs bestPrefs, n, workPrefs
optimizedScore = bestScore
OptimizeWithLNS items, n, bestWidth, maxHeight, allowRotation, bestFitMode, workOrder, workPrefs, optimizedScore, lnsIterationsUsed, lnsImprovements
PackMultiRollWithOrder items, n, bestWidth, maxHeight, allowRotation, bestFitMode, workOrder, workPrefs, candidateRolls, candidateRollCount, candidateNotPlaced
candidateScore = PackScore(items, candidateRolls, candidateRollCount, candidateNotPlaced, bestWidth, candidateRightWaste, candidateAlignment, candidateMaterial)
If candidateNotPlaced = 0 And candidateScore < bestScore - EPS Then
bestScore = candidateScore
bestRollCount = candidateRollCount
bestNotPlaced = candidateNotPlaced
bestMaterial = candidateMaterial
bestWaste = CalcWaste(items, candidateRolls, candidateRollCount, bestWidth)
bestRightWaste = candidateRightWaste
bestAlignment = candidateAlignment
CopyOrder workOrder, n, bestOrder
CopyRotationPrefs workPrefs, n, bestPrefs
End If
End If
' Search for a two-width partition after the strongest single-width layout
' has been found. A second width is accepted only if it reduces total
' material area compared with the best single-width result.
If widthCount >= 2 And n >= 2 Then
FindBestTwoWidthLayout items, n, widths, widthCount, maxHeight, allowRotation, _
multiOrderA, multiCountA, multiWidthA, multiFitA, _
multiOrderB, multiCountB, multiWidthB, multiFitB, multiBestMaterial, multiBestScore
If multiCountA > 0 And multiCountB > 0 Then
ReDim multiPrefs(1 To n)
For i = 1 To n
multiPrefs(i) = 0
Next i
OptimizeSubsetOrder items, multiCountA, multiWidthA, maxHeight, allowRotation, multiFitA, multiOrderA, multiPrefs, optimizedScore
OptimizeSubsetOrder items, multiCountB, multiWidthB, maxHeight, allowRotation, multiFitB, multiOrderB, multiPrefs, optimizedScore
PackMultiRollWithOrder items, multiCountA, multiWidthA, maxHeight, allowRotation, multiFitA, multiOrderA, multiPrefs, multiRollsA, multiRollCountA, multiNotPlacedA
multiScoreA = PackScore(items, multiRollsA, multiRollCountA, multiNotPlacedA, multiWidthA, multiRightA, multiAlignA, multiMaterialA)
PackMultiRollWithOrder items, multiCountB, multiWidthB, maxHeight, allowRotation, multiFitB, multiOrderB, multiPrefs, multiRollsB, multiRollCountB, multiNotPlacedB
multiScoreB = PackScore(items, multiRollsB, multiRollCountB, multiNotPlacedB, multiWidthB, multiRightB, multiAlignB, multiMaterialB)
If multiNotPlacedA = 0 And multiNotPlacedB = 0 Then
multiCombinedMaterial = multiMaterialA + multiMaterialB
If multiCombinedMaterial < bestMaterial - EPS Then
useMultiWidth = True
multiBestMaterial = multiCombinedMaterial
End If
End If
End If
End If
If useMultiWidth Then
multiHeightA = TotalRollHeight(multiRollsA, multiRollCountA)
multiHeightB = TotalRollHeight(multiRollsB, multiRollCountB)
' Each chosen stock width receives its own accurately sized CorelDRAW page.
Set outputPageA = doc.AddPagesEx(1, multiWidthA, multiHeightA)
outputPageA.Name = "Nesting " & Format$(multiWidthA, "0.##") & " cm"
ApplyNestingToPage items, sourceShapes, multiRollsA, multiRollCountA, multiWidthA, outputPageA
Set outputPageB = doc.AddPagesEx(1, multiWidthB, multiHeightB)
outputPageB.Name = "Nesting " & Format$(multiWidthB, "0.##") & " cm"
ApplyNestingToPage items, sourceShapes, multiRollsB, multiRollCountB, multiWidthB, outputPageB
doc.Unit = oldUnit
multiTrueArea = CalcTrueArea(items, multiRollsA, multiRollCountA) + CalcTrueArea(items, multiRollsB, multiRollCountB)
If multiBestMaterial > EPS Then
multiWaste = (multiBestMaterial - multiTrueArea) / multiBestMaterial
Else
multiWaste = 0#
End If
If bestWidth > EPS And bestRollCount > 0 And bestNotPlaced = 0 And bestMaterial < 1E+29 Then
multiSavingPct = ((bestMaterial - multiBestMaterial) / bestMaterial) * 100#
Else
multiSavingPct = -1#
End If
msg = "AUTO NESTING V6 - MULTI-WIDTH SELESAI" & vbCrLf & vbCrLf
msg = msg & "Object total: " & CStr(n) & vbCrLf
msg = msg & "Halaman output: 2 halaman, masing-masing ukuran roll berbeda" & vbCrLf & vbCrLf
msg = msg & "Halaman " & CStr(outputPageA.Index) & ": lebar " & Format$(multiWidthA, "0.00") & " cm" & vbCrLf
msg = msg & "Object: " & CStr(multiCountA) & " | Jumlah roll: " & CStr(multiRollCountA) & vbCrLf
msg = msg & "Tinggi layout: " & Format$(multiHeightA, "0.00") & " cm" & vbCrLf & vbCrLf
msg = msg & "Halaman " & CStr(outputPageB.Index) & ": lebar " & Format$(multiWidthB, "0.00") & " cm" & vbCrLf
msg = msg & "Object: " & CStr(multiCountB) & " | Jumlah roll: " & CStr(multiRollCountB) & vbCrLf
msg = msg & "Tinggi layout: " & Format$(multiHeightB, "0.00") & " cm" & vbCrLf & vbCrLf
msg = msg & "Total material: " & Format$(multiBestMaterial, "0.00") & " cm2" & vbCrLf
msg = msg & "Estimasi waste: " & Format$(multiWaste * 100#, "0.00") & "%" & vbCrLf
If multiSavingPct >= 0# Then
msg = msg & "Penghematan material vs 1 ukuran: " & Format$(multiSavingPct, "0.00") & "%" & vbCrLf
Else
msg = msg & "Pembanding 1 ukuran: tidak ada solusi yang feasible" & vbCrLf
End If
msg = msg & "Rotasi diizinkan: " & IIf(allowRotation, "Ya", "Tidak") & vbCrLf
msg = msg & "Catatan: semua object dialokasikan tepat satu kali ke salah satu dari dua halaman output."
MsgBox msg, vbInformation, "Auto Nesting V6 - Multi-Width"
Exit Sub
End If
If bestWidth <= EPS Or bestRollCount <= 0 Or bestNotPlaced > 0 Then
doc.Unit = oldUnit
msg = "Tidak ditemukan konfigurasi roll yang feasible." & vbCrLf & vbCrLf
msg = msg & "Minimum roll width: " & Format$(minNeeded, "0.00") & " cm"
MsgBox msg, vbCritical, "Auto Nesting"
Exit Sub
End If
PackMultiRollWithOrder items, n, bestWidth, maxHeight, allowRotation, bestFitMode, bestOrder, bestPrefs, rolls, bestRollCount, bestNotPlaced
If bestNotPlaced > 0 Then
doc.Unit = oldUnit
MsgBox "Layout final menjadi tidak feasible. Object tidak akan dipindahkan.", vbCritical, "Auto Nesting V6"
Exit Sub
End If
bestMaterial = CalcMaterialUsed(rolls, bestRollCount, bestWidth)
bestWaste = CalcWaste(items, rolls, bestRollCount, bestWidth)
bestRightWaste = CalcRightWaste(rolls, bestRollCount, bestWidth)
bestAlignment = CalcAlignmentScore(rolls, bestRollCount)
finalSharedEdge = CalcSharedEdgeLength(rolls, bestRollCount)
finalContactSegments = CalcContactSegments(rolls, bestRollCount)
finalGuillotineEdge = CalcGuillotineEdgeLength(rolls, bestRollCount)
finalCutPenalty = CalcCutFriendlyPenalty(rolls, bestRollCount, bestWidth)
ApplyNestingToObjects items, sourceShapes, rolls, bestRollCount, bestWidth
doc.Unit = oldUnit
msg = "AUTO NESTING V6 SELESAI (SINGLE-WIDTH TERBAIK)" & vbCrLf & vbCrLf
msg = msg & "Object: " & CStr(n) & vbCrLf
msg = msg & "Roll width: " & Format$(bestWidth, "0.00") & " cm" & vbCrLf
msg = msg & "Jumlah roll: " & CStr(bestRollCount) & vbCrLf
msg = msg & "Tidak ditempatkan: " & CStr(bestNotPlaced) & vbCrLf
msg = msg & "Material digunakan: " & Format$(bestMaterial, "0.00") & " cm2" & vbCrLf
msg = msg & "Catatan: material = lebar roll x total height terpakai" & vbCrLf
msg = msg & "Waste estimasi: " & Format$(bestWaste * 100#, "0.00") & "%" & vbCrLf
msg = msg & "Waste kanan maksimum: " & Format$(bestRightWaste, "0.00") & " cm" & vbCrLf
If bestRightWaste <= MAX_RIGHT_WASTE + EPS Then
msg = msg & "Right waste status: OK" & vbCrLf
Else
msg = msg & "Right waste status: > 10 cm" & vbCrLf
End If
msg = msg & "Visual alignment score: " & Format$(bestAlignment, "0.00") & vbCrLf
msg = msg & "Shared edge: " & Format$(finalSharedEdge, "0.00") & " cm" & vbCrLf
msg = msg & "Contact segments: " & CStr(finalContactSegments) & vbCrLf
msg = msg & "Strong guillotine edge: " & Format$(finalGuillotineEdge, "0.00") & " cm" & vbCrLf
msg = msg & "Cut-friendly penalty: " & Format$(finalCutPenalty, "0.00") & vbCrLf
msg = msg & "Seed sort: " & SortModeName(bestSortMode) & vbCrLf
msg = msg & "Fitness: " & FitModeName(bestFitMode) & vbCrLf
msg = msg & "LNS iterations: " & CStr(lnsIterationsUsed) & vbCrLf
msg = msg & "LNS accepted moves: " & CStr(lnsImprovements) & vbCrLf
msg = msg & "Optimization: SWAP + REINSERT + 3-OBJECT + CONTACT-POINT + GUILLOTINE + DESTROY/REPAIR + ROTATION MUTATION"
MsgBox msg, vbInformation, "Auto Nesting V6"
Exit Sub
ErrHandler:
errNumber = Err.Number
errDescription = Err.Description
On Error Resume Next
If Not doc Is Nothing Then doc.Unit = oldUnit
On Error GoTo 0
MsgBox "Macro berhenti karena error." & vbCrLf & vbCrLf & "Error " & CStr(errNumber) & ": " & errDescription, vbCritical, "Auto Nesting V6"
End Sub