source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs @ 15617

Last change on this file since 15617 was 15617, checked in by rhanghof, 20 months ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 12.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 HeuristicLab.Encodings.PermutationEncoding;
23using HeuristicLab.Problems.BinPacking2D;
24using System;
25using System.Collections.Generic;
26using System.Linq;
27using System.Text;
28using System.Threading.Tasks;
29
30namespace HeuristicLab.Problems.BinPacking3D.Sorting {
31
32  /// <summary>
33  /// This is a extension class for sorting a permutation.
34  /// They are extension methods for the class Permutation.
35  /// </summary>
36  public static class PermutationPackingItemSorter {
37       
38    /// <summary>
39    /// Sorts a given permutation first by the volume and secoundly by the height.
40    /// </summary>
41    /// <param name="items">Permuation which should be sorted</param>
42    /// <returns>A new sorted permutation</returns>
43    public static Permutation SortByVolumeHeight(this IList<PackingItem> items) {
44      return new Permutation(PermutationTypes.Absolute,
45                    items.Select((v, i) => new { Index = i, Item = v })
46                         .OrderByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
47                         .ThenByDescending(x => x.Item.Height)
48                         .Select(x => x.Index).ToArray());
49    }
50
51    /// <summary>
52    /// Sorts a given permutation first by the heigth and secoundly by the volume.
53    /// </summary>
54    /// <param name="items">Permuation which should be sorted</param>
55    /// <returns>A new sorted permutation</returns>
56    public static Permutation SortByHeightVolume(this IList<PackingItem> items) {
57      return new Permutation(PermutationTypes.Absolute,
58                    items.Select((v, i) => new { Index = i, Item = v })
59                         .OrderByDescending(x => x.Item.Height)
60                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
61                         .Select(x => x.Index).ToArray());
62    }
63
64    /// <summary>
65    /// Sorts a given permutation first by the area and secondly by the height.
66    /// </summary>
67    /// <param name="items">Permuation which should be sorted</param>
68    /// <returns>A new sorted permutation</returns>
69    public static Permutation SortByAreaHeight(this IList<PackingItem> items) {
70      return new Permutation(PermutationTypes.Absolute,
71                    items.Select((v, i) => new { Index = i, Item = v })
72                         .OrderByDescending(x => x.Item.Depth * x.Item.Width)
73                         .ThenByDescending(x => x.Item.Height)
74                         .Select(x => x.Index).ToArray());
75    }
76
77    /// <summary>
78    /// Sorts a given permuation first by the height and secoundly by the area.
79    /// </summary>
80    /// <param name="items">Permuation which should be sorted</param>
81    /// <returns>A new sorted permutation</returns>
82    public static Permutation SortByHeightArea(this IList<PackingItem> items) {
83      return new Permutation(PermutationTypes.Absolute,
84                    items.Select((v, i) => new { Index = i, Item = v })
85                         .OrderByDescending(x => x.Item.Height)
86                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
87                         .Select(x => x.Index).ToArray());
88    }
89
90    /// <summary>
91    /// Sorts a given permutation. The items are being grouped by the cluster id.
92    /// The cluster id is calulated as followed: clusterId = Ceiling( (width * depth) / (width * depth * delta))
93    /// The permutation is first being sorted by the area and secoundly by the height.
94    /// </summary>
95    /// <param name="items">Permuation which should be sorted</param>
96    /// <param name="bin">The bin is needed for building the cluster</param>
97    /// <param name="delta">The delta is needed for building the cluster</param>
98    /// <returns>A new sorted permutation</returns>
99    public static Permutation SortByClusteredAreaHeight(this IList<PackingItem> items, PackingShape bin, double delta) {
100      double clusterRange = bin.Width * bin.Depth * delta;
101      return new Permutation(PermutationTypes.Absolute,
102                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
103                    .GroupBy(x => x.ClusterId)
104                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Height).ToList() })
105                    .OrderByDescending(x => x.Cluster)
106                    .SelectMany(x => x.Items)
107                    .Select(x => x.Index).ToArray());
108    }
109
110    /// <summary>
111    /// Sorts a given permutation. The items are being grouped by the cluster id.
112    /// The cluster id is calulated as followed: clusterId = Ceiling( (height) / (height * delta))
113    /// The permutation is first being sorted by the height and secoundly by the area.
114    /// </summary>
115    /// <param name="items">Permuation which should be sorted</param>
116    /// <param name="bin">The bin is needed for building the cluster</param>
117    /// <param name="delta">The delta is needed for building the cluster</param>
118    /// <returns>A new sorted permutation</returns>
119    public static Permutation SortByClusteredHeightArea(this IList<PackingItem> items, PackingShape bin, double delta) {
120      double clusterRange2 = bin.Height * delta;
121      return new Permutation(PermutationTypes.Absolute,
122                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
123                    .GroupBy(x => x.ClusterId)
124                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
125                    .OrderByDescending(x => x.Cluster)
126                    .SelectMany(x => x.Items)
127                    .Select(x => x.Index).ToArray());
128    }
129
130    /// <summary>
131    /// Sorts a given permutation first by the material, secoundly by the volume and finally by the height.
132    /// </summary>
133    /// <param name="items">Permuation which should be sorted</param>
134    /// <returns>A new sorted permutation</returns>
135    public static Permutation SortByMaterialVolumeHeight(this IList<PackingItem> items) {
136      return new Permutation(PermutationTypes.Absolute,
137                    items.Select((v, i) => new { Index = i, Item = v })
138                         .OrderByDescending(x => x.Item.Material)
139                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
140                         .ThenByDescending(x => x.Item.Height)
141                         .Select(x => x.Index).ToArray());
142    }
143
144    /// <summary>
145    /// Sorts a given permutation first by the material, secoundly by the heigth and finally by the volume.
146    /// </summary>
147    /// <param name="items">Permuation which should be sorted</param>
148    /// <returns>A new sorted permutation</returns>
149    public static Permutation SortByMaterialHeightVolume(this IList<PackingItem> items) {
150      return new Permutation(PermutationTypes.Absolute,
151                    items.Select((v, i) => new { Index = i, Item = v })
152                         .OrderByDescending(x => x.Item.Material)
153                         .ThenByDescending(x => x.Item.Height)
154                         .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
155                         .Select(x => x.Index).ToArray());
156    }
157
158    /// <summary>
159    /// Sorts a given permutation first by the material, secoundly by the area and finally by the height.
160    /// </summary>
161    /// <param name="items">Permuation which should be sorted</param>
162    /// <returns>A new sorted permutation</returns>
163    public static Permutation SortByMaterialAreaHeight(this IList<PackingItem> items) {
164      return new Permutation(PermutationTypes.Absolute,
165                    items.Select((v, i) => new { Index = i, Item = v })
166                         .OrderByDescending(x => x.Item.Material)
167                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
168                         .ThenByDescending(x => x.Item.Height)
169                         .Select(x => x.Index).ToArray());
170    }
171
172    /// <summary>
173    /// Sorts a given permuation first by the material, secoundly by the height and finally by the area.
174    /// </summary>
175    /// <param name="items">Permuation which should be sorted</param>
176    /// <returns>A new sorted permutation</returns>
177    public static Permutation SortByMaterialHeightArea(this IList<PackingItem> items) {
178      return new Permutation(PermutationTypes.Absolute,
179                    items.Select((v, i) => new { Index = i, Item = v })
180                         .OrderByDescending(x => x.Item.Material)
181                         .ThenByDescending(x => x.Item.Height)
182                         .ThenByDescending(x => x.Item.Depth * x.Item.Width)
183                         .Select(x => x.Index).ToArray());
184    }
185
186    /// <summary>
187    /// Sorts a given permutation. The items are being grouped by the cluster id.
188    /// The cluster id is calulated as followed: clusterId = Ceiling( (width * depth) / (width * depth * delta))
189    /// The permutation is being clusterd by the area, first sorted by the material, secoundly by the height.
190    /// </summary>
191    /// <param name="items">Permuation which should be sorted</param>
192    /// <param name="bin">The bin is needed for building the cluster</param>
193    /// <param name="delta">The delta is needed for building the cluster</param>
194    /// <returns>A new sorted permutation</returns>
195    public static Permutation SortByMaterialClusteredAreaHeight(this IList<PackingItem> items, PackingShape bin, double delta) {
196      double clusterRange = bin.Width * bin.Depth * delta;
197      return new Permutation(PermutationTypes.Absolute,
198                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
199                    .GroupBy(x => x.ClusterId)
200                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Height).ToList() })
201                    .OrderByDescending(x => x.Cluster)
202                    .SelectMany(x => x.Items)
203                    .Select(x => x.Index).ToArray());
204    }
205
206    /// <summary>
207    /// Sorts a given permutation. The items are being grouped by the cluster id.
208    /// The cluster id is calulated as followed: clusterId = Ceiling( (height) / (height * delta))
209    /// The permutation is being clusterd by the height, first sorted by the material, secoundly by the area.
210    /// </summary>
211    /// <param name="items">Permuation which should be sorted</param>
212    /// <param name="bin">The bin is needed for building the cluster</param>
213    /// <param name="delta">The delta is needed for building the cluster</param>
214    /// <returns>A new sorted permutation</returns>
215    public static Permutation SortByMaterialClusteredHeightArea(this IList<PackingItem> items, PackingShape bin,  double delta) {
216      double clusterRange2 = bin.Height * delta;
217      return new Permutation(PermutationTypes.Absolute,
218                items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
219                    .GroupBy(x => x.ClusterId)
220                    .Select(x => new { Cluster = x.Key, Items = x.OrderByDescending(z => z.Item.Material).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
221                    .OrderByDescending(x => x.Cluster)
222                    .SelectMany(x => x.Items)
223                    .Select(x => x.Index).ToArray());
224    }
225  }
226}
Note: See TracBrowser for help on using the repository browser.