#region License Information /* HeuristicLab * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Problems.BinPacking.Interfaces; using HeuristicLab.Problems.BinPacking.PackingItem; using HeuristicLab.Problems.BinPacking.Shapes; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Core; using HeuristicLab.Common; using HeuristicLab.Data; using HeuristicLab.Collections; using HeuristicLab.Problems.BinPacking.Dimensions; using HeuristicLab.Problems.BinPacking.PackingBin; using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector; using HeuristicLab.Encodings.PackingEncoding.GroupingVector; using HeuristicLab.Encodings.PackingEncoding.PackingSequence; using HeuristicLab.Encodings.IntegerVectorEncoding; namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan { [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")] [StorableClass] public abstract class PackingPlan : ParameterizedNamedItem, IPackingPlan where D : class, IPackingDimensions where B : PackingShape, IPackingBin where I : PackingShape, IPackingItem { #region Properties public int NrOfBins { get { if (BinPackings != null) return BinPackings.Count; else return 0; } } [Storable] protected bool StackingConstraints { get; set; } [Storable] protected bool UseExtremePoints { get; set; } [Storable] public B BinMeasures { get; private set; } [Storable] public ObservableList> BinPackings { get; set; } [Storable] private DoubleValue quality; public DoubleValue Quality { get { return quality; } set { if (quality != value) { if (quality != null) DeregisterQualityEvents(); quality = value; if (quality != null) RegisterQualityEvents(); OnQualityChanged(); } } } #endregion public PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints) : base(){ BinMeasures = (B)binMeasures.Clone(); StackingConstraints = stackingConstraints; UseExtremePoints = useExtremePoints; BinPackings = new ObservableList>(); } [StorableConstructor] protected PackingPlan(bool deserializing) : base(deserializing) { } protected PackingPlan(PackingPlan original, Cloner cloner) : base(original, cloner) { this.BinPackings = new ObservableList>(original.BinPackings); } public abstract BinPacking NewBinPacking(); public void UpdateBinPackings() { BinPackings.RemoveAll(x => x.ItemPositions.Count == 0); BinPackings = new ObservableList>(BinPackings.OrderByDescending (bp => bp.PackingDensity)); } public void Pack(MultiComponentVectorEncoding solution, ItemList itemMeasures) { var sequenceMatrix = solution.GenerateSequenceMatrix(); Dictionary rotated = solution.GenerateRotationArray(); //Fill bins according to grouping vector List remainingIDs = new List(); foreach (var sequence in sequenceMatrix) { remainingIDs = remainingIDs.Concat(sequence).ToList(); var bp = NewBinPacking(); if (!UseExtremePoints) bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated); else bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated); BinPackings.Add(bp); } UpdateBinPackings(); //Try to put remaining items in existing bins var temp = new List(remainingIDs); foreach (int id in temp) { foreach (var bp in BinPackings) { var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]); if (position != null) { bp.PackItem(id, itemMeasures[id], position); remainingIDs.Remove(id); break; } } } //Put still remaining items in new bins while (remainingIDs.Count > 0) { var bp = NewBinPacking(); if (!UseExtremePoints) bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated); else bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated); BinPackings.Add(bp); } UpdateBinPackings(); var newSolution = new ObservableDictionary> (); foreach (var bp in BinPackings) { int binIndex = newSolution.Count; newSolution[binIndex] = new ItemList(); foreach (var entry in bp.ItemPositions) newSolution[binIndex].Add(new PackingInformation (entry.Key, entry.Value.Rotated)); } solution.PackingInformations = newSolution; } public void Pack(GroupingVectorEncoding solution, ItemList itemMeasures) { var sequenceMatrix = solution.GenerateSequenceMatrix(); //Fill bins according to grouping vector List remainingIDs = new List(); foreach (var sequence in sequenceMatrix) { remainingIDs = remainingIDs.Concat(sequence).ToList(); var bp = NewBinPacking(); if (!UseExtremePoints) bp.SlidingBasedPacking(ref remainingIDs, itemMeasures); else bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints); BinPackings.Add(bp); } UpdateBinPackings(); //Try to put remaining items in existing bins var temp = new List(remainingIDs); foreach (int id in temp) { foreach (var bp in BinPackings) { var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false); if (position != null) { bp.PackItem(id, itemMeasures[id], position); remainingIDs.Remove(id); break; } } } //Put still remaining items in new bins while (remainingIDs.Count > 0) { var bp = NewBinPacking(); if (!UseExtremePoints) bp.SlidingBasedPacking(ref remainingIDs, itemMeasures); else bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints); BinPackings.Add(bp); } UpdateBinPackings(); var newSolution = new int[solution.GroupingVector.Length]; int binIndex = 0; foreach (var bp in BinPackings) { foreach (var entry in bp.ItemPositions) newSolution[entry.Key] = binIndex; binIndex++; } solution.GroupingVector = new IntegerVector (newSolution); } public void Pack(PackingSequenceEncoding solution, ItemList itemMeasures) { List remainingIDs = new List(solution.PackingSequence); while (remainingIDs.Count > 0) { var bp = NewBinPacking(); if (!UseExtremePoints) bp.SlidingBasedPacking(ref remainingIDs, itemMeasures); else bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints); BinPackings.Add(bp); } UpdateBinPackings(); } #region Events public event EventHandler QualityChanged; private void OnQualityChanged() { var changed = QualityChanged; if (changed != null) changed(this, EventArgs.Empty); } private void RegisterQualityEvents() { Quality.ValueChanged += new EventHandler(Quality_ValueChanged); } private void DeregisterQualityEvents() { Quality.ValueChanged -= new EventHandler(Quality_ValueChanged); } private void Quality_ValueChanged(object sender, EventArgs e) { OnQualityChanged(); } public event EventHandler BinPackingsChanged; private void OnBinPackingsChanged() { var changed = BinPackingsChanged; if (changed != null) changed(this, EventArgs.Empty); } private void RegisterBinPackingsEvents() { BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged); } private void DeregisterBinPackingsEvents() { BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged); } private void BinPackings_PropertyChanged(object sender, EventArgs e) { OnBinPackingsChanged(); } #endregion } [Item("PackingPlan2D", "Represents a concrete solution for a 2D bin-packing problem.")] [StorableClass] public class PackingPlan2D : PackingPlan { public PackingPlan2D(RectangularPackingBin binMeasures) : this(binMeasures, false, false) { } public PackingPlan2D(RectangularPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { } [StorableConstructor] protected PackingPlan2D(bool deserializing) : base(deserializing) { } protected PackingPlan2D(PackingPlan2D original, Cloner cloner) : base(original, cloner) { } public override IDeepCloneable Clone(Cloner cloner) { return new PackingPlan2D(this, cloner); } public override BinPacking NewBinPacking() { return new BinPacking2D(BinMeasures); } } [Item("PackingPlan3D", "Represents a concrete solution for a 3D bin-packing problem.")] [StorableClass] public class PackingPlan3D : PackingPlan { public PackingPlan3D(CuboidPackingBin binMeasures) : this(binMeasures, false, false) { } public PackingPlan3D(CuboidPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { } [StorableConstructor] protected PackingPlan3D(bool deserializing) : base(deserializing) { } protected PackingPlan3D(PackingPlan3D original, Cloner cloner) : base(original, cloner) { } public override IDeepCloneable Clone(Cloner cloner) { return new PackingPlan3D(this, cloner); } public override BinPacking NewBinPacking() { return new BinPacking3D(BinMeasures); } } }