source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking.cs @ 14146

Last change on this file since 14146 was 14146, checked in by gkronber, 3 years ago

#1966: new implementation for 2d bin packing problem with permutation encoding

File size: 5.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Collections;
28using HeuristicLab.Problems.BinPacking;
29
30namespace HeuristicLab.Encodings.PackingEncoding {
31  [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
32  [StorableClass]
33  public abstract class BinPacking<D, B, I> : Item
34    where D : class, IPackingPosition
35    where B : PackingShape<D>
36    where I : PackingShape<D> {
37    #region Properties
38    [Storable]
39    public ObservableDictionary<int, D> ItemPositions { get; private set; }
40
41    [Storable]
42    public ObservableDictionary<int, I> ItemMeasures { get; private set; } // TODO: rename to items
43
44    [Storable]
45    public B BinMeasures { get; private set; }
46
47    [Storable]
48    public SortedSet<D> ExtremePoints { get; protected set; }
49
50    [Storable]
51    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
52
53    #endregion Properties
54
55    protected BinPacking(B binMeasures)
56      : base() {
57      ItemPositions = new ObservableDictionary<int, D>();
58      ItemMeasures = new ObservableDictionary<int, I>();
59      BinMeasures = (B)binMeasures.Clone();
60      OccupationLayers = new Dictionary<int, List<int>>();
61      InitializeOccupationLayers(); // TODO
62    }
63
64
65    [StorableConstructor]
66    protected BinPacking(bool deserializing) : base(deserializing) { }
67    protected BinPacking(BinPacking<D, B, I> original, Cloner cloner)
68      : base(original, cloner) {
69      this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
70      this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
71      this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
72      this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
73    }
74
75    protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
76
77    public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraints);
78    public abstract D FindPositionBySliding(I measures, bool rotated);
79
80    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures);
81    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, Dictionary<int, bool> rotationArray);
82    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints);
83    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
84
85    public void PackItem(int itemID, I measures, D position) {
86      ItemMeasures[itemID] = measures;
87      ItemPositions[itemID] = position;
88      ExtremePoints.Remove(position);
89      foreach (int id in ItemMeasures.Select(x => x.Key))
90        GenerateNewExtremePointsForNewItem(ItemMeasures[id], ItemPositions[id]);
91
92      AddNewItemToOccupationLayers(itemID, measures, position);
93    }
94
95    public double PackingDensity {
96      get {
97        double result = 0;
98        foreach (var entry in ItemMeasures)
99          result += entry.Value.Volume;
100        result /= BinMeasures.Volume;
101        return result;
102      }
103    }
104
105
106    public int PointOccupation(D position) {
107      foreach (var id in GetLayerItemIDs(position)) {
108        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
109          return id;
110      }
111      return -1;
112    }
113
114    public bool IsPointOccupied(D position) {
115      foreach (var id in GetLayerItemIDs(position)) {
116        if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
117          return true;
118      }
119      return false;
120    }
121    public bool IsPositionFeasible(I measures, D position) {
122      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
123      if (!BinMeasures.Encloses(position, measures))
124        return false;
125
126      foreach (var id in GetLayerItemIDs(measures, position)) {
127        if (ItemMeasures[id].Overlaps(ItemPositions[id], position, measures))
128          return false;
129      }
130
131      return true;
132    }
133    public abstract int ShortestPossibleSideFromPoint(D position);
134    public abstract bool IsStaticStable(I measures, D position);
135
136
137    protected abstract void InitializeOccupationLayers();
138    protected abstract void AddNewItemToOccupationLayers(int itemID, I measures, D position);
139    protected abstract List<int> GetLayerItemIDs(D position);
140    protected abstract List<int> GetLayerItemIDs(I measures, D position);
141  }
142}
Note: See TracBrowser for help on using the repository browser.