Skip to content

Commit 657e785

Browse files
merschformannmerschformann
committed
Support container reorder
1 parent dbb8b3e commit 657e785

File tree

5 files changed

+47
-6
lines changed

5 files changed

+47
-6
lines changed

‎SC.Heuristics/PrimalHeuristic/PointInsertionSkeletonLib.cs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1667,6 +1667,9 @@ protected void ExtremePointInsertion(COSolution solution, List<Container> contai
16671667
MeshPoint bestEP = null;
16681668
double bestScore = double.PositiveInfinity;
16691669

1670+
// Reorder containers
1671+
containers = solution.ContainerOrderSupply.SortReorder(containers);
1672+
16701673
// --> EP-Insertion
16711674
// Try to greedy insert every piece
16721675
foreach (var piece in pieces)
@@ -1867,6 +1870,9 @@ protected void ExtremePointInsertionWithSpaceDefragmentation(COSolution solution
18671870
// Init
18681871
LinkedList<VariablePiece> pieces = new LinkedList<VariablePiece>(inputPieces);
18691872

1873+
// Reorder containers
1874+
containers = solution.ContainerOrderSupply.SortReorder(containers);
1875+
18701876
// --> EP-Insertion with space defragmentation
18711877
// Try to greedy insert every piece
18721878
LinkedListNode<VariablePiece> pieceNode = pieces.First;
@@ -2041,6 +2047,9 @@ protected void ExtremePointInsertionWithSpaceDefragmentation(COSolution solution
20412047

20422048
protected void InsertAndPush(COSolution solution, List<Container> containers, List<VariablePiece> pieces, int[][] orientationsPerPiece)
20432049
{
2050+
// Reorder containers
2051+
containers = solution.ContainerOrderSupply.SortReorder(containers);
2052+
20442053
// --> EP-Insertion with space defragmentation
20452054
// Try to greedy insert every piece
20462055
foreach (var piece in pieces)

‎SC.ObjectModel/Additionals/ContainerOrder.cs‎

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
using System;
12
using System.Collections.Generic;
23
using System.Linq;
34
using SC.ObjectModel.Elements;
@@ -20,10 +21,18 @@ public enum ContainerInitOrderType
2021
/// </summary>
2122
public enum ContainerReorderType
2223
{
24+
/// <summary>
25+
/// No reordering is done.
26+
/// </summary>
27+
None,
2328
/// <summary>
2429
/// Sorts the containers by their volume.
2530
/// </summary>
2631
Capacity,
32+
/// <summary>
33+
/// Sorts the containers randomly.
34+
/// </summary>
35+
Random,
2736
}
2837

2938
public class ContainerOrderSupply
@@ -56,6 +65,10 @@ public static List<Container> SortInit(List<Container> containers, ContainerInit
5665
/// BigM value for preferring containers indicated to be opened right away.
5766
/// </summary>
5867
public double OpenContainerBigM { get; private set; } = 1e6;
68+
/// <summary>
69+
/// The random number generator used for randomizing the order of containers.
70+
/// </summary>
71+
private Random _random;
5972

6073
/// <summary>
6174
/// Creates a new instance of the container order supply.
@@ -65,10 +78,17 @@ public static List<Container> SortInit(List<Container> containers, ContainerInit
6578
/// <param name="initType">The type of container initialization.</param>
6679
/// <param name="type">The type of container reorder.</param>
6780
/// <param name="openContainerByPieceRatio">The ratio of pieces to open containers.</param>
68-
public ContainerOrderSupply(List<Container> containers, List<VariablePiece> pieces, ContainerInitOrderType initType, ContainerReorderType type, double openContainerByPieceRatio)
81+
public ContainerOrderSupply(
82+
List<Container> containers,
83+
List<VariablePiece> pieces,
84+
ContainerInitOrderType initType,
85+
ContainerReorderType type,
86+
double openContainerByPieceRatio,
87+
Random random)
6988
{
7089
ReorderType = type;
7190
OpenContainers = new HashSet<Container>();
91+
_random = random;
7292
if (openContainerByPieceRatio > 0)
7393
{
7494
var pieceVolume = pieces.Sum(p => p.Volume);
@@ -94,6 +114,8 @@ public List<Container> SortReorder(List<Container> containers)
94114
{
95115
case ContainerReorderType.Capacity:
96116
return containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM : 0) + c.Mesh.Volume).ToList();
117+
case ContainerReorderType.Random:
118+
return containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM : 0) + _random.Next()).ToList();
97119
default:
98120
return containers;
99121
}

‎SC.ObjectModel/COSolution.cs‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,10 +24,11 @@ public class COSolution : IXmlSerializable
2424
/// </summary>
2525
/// <param name="instance">The instance this solution belongs to</param>
2626
/// <param name="config">The configuration being used.</param>
27-
internal COSolution(Instance instance, Configuration.Configuration config)
27+
internal COSolution(Instance instance, Configuration.Configuration config, Random random)
2828
{
2929
InstanceLinked = instance;
3030
Configuration = config;
31+
_random = random;
3132
ContainedPieces = new HashSet<VariablePiece>();
3233
OffloadPieces = new HashSet<VariablePiece>(instance.Pieces);
3334
Orientations = new int[instance.PiecesWithVirtuals.Count()];
@@ -41,7 +42,7 @@ internal COSolution(Instance instance, Configuration.Configuration config)
4142
for (int i = 0; i < instance.Containers.Count; i++)
4243
ContainerInfos[i] = new ContainerInfo(this, instance.Containers[i]);
4344
Objective = new Objective(this);
44-
ContainerOrderSupply = new ContainerOrderSupply(instance.Containers, instance.Pieces, config.ContainerOrderInit, config.ContainerOrderReorder, config.ContainerOpen);
45+
ContainerOrderSupply = new ContainerOrderSupply(instance.Containers, instance.Pieces, config.ContainerOrderInit, config.ContainerOrderReorder, config.ContainerOpen, _random);
4546
MaterialsPerContainer = new int[instance.Containers.Count, Enum.GetValues(typeof(MaterialClassification)).Length];
4647
}
4748

@@ -58,6 +59,10 @@ internal COSolution(Instance instance, Configuration.Configuration config)
5859
/// The configuration this solution is based on
5960
/// </summary>
6061
public Configuration.Configuration Configuration { get; private set; }
62+
/// <summary>
63+
/// The randomizer of this solution.
64+
/// </summary>
65+
private Random _random = null;
6166

6267
#region Core information
6368

@@ -288,7 +293,7 @@ public COSolution Clone(bool unofficial = true)
288293
}
289294
clone.EPCounter = EPCounter;
290295
clone.LevelPackingC = LevelPackingC;
291-
clone.ContainerOrderSupply = new ContainerOrderSupply(clone.InstanceLinked.Containers, clone.InstanceLinked.Pieces, Configuration.ContainerOrderInit, Configuration.ContainerOrderReorder, Configuration.ContainerOpen);
296+
clone.ContainerOrderSupply = new ContainerOrderSupply(clone.InstanceLinked.Containers, clone.InstanceLinked.Pieces, Configuration.ContainerOrderInit, Configuration.ContainerOrderReorder, Configuration.ContainerOpen, clone._random);
292297
// Copy construction information
293298
if (ConstructionContainerOrder != null)
294299
clone.ConstructionContainerOrder = ConstructionContainerOrder.ToList();

‎SC.ObjectModel/Configuration/Configuration.cs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -355,7 +355,7 @@ public Configuration(MethodType method, bool handleTetris)
355355
/// <summary>
356356
/// Defines the type of the container sorting to apply while improving.
357357
/// </summary>
358-
public ContainerReorderType ContainerOrderReorder { get; set; } = ContainerReorderType.Capacity;
358+
public ContainerReorderType ContainerOrderReorder { get; set; } = ContainerReorderType.None;
359359

360360
/// <summary>
361361
/// Defines the fraction of containers to be used automatically (opened) instead of aiming to fill as few containers as possible.

‎SC.ObjectModel/InstanceCore.cs‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,11 @@ public partial class Instance
2626
/// </summary>
2727
public string Name { get; set; }
2828

29+
/// <summary>
30+
/// The randomizer of this instance.
31+
/// </summary>
32+
public Random Random { get; set; } = new Random(0);
33+
2934
/// <summary>
3035
/// Contains all pieces which are part of this instance
3136
/// </summary>
@@ -113,7 +118,7 @@ public string GetIdent()
113118
/// <returns>The newly created solution</returns>
114119
public COSolution CreateSolution(Configuration.Configuration config, bool unofficial = false)
115120
{
116-
COSolution solution = new COSolution(this, config);
121+
COSolution solution = new COSolution(this, config, Random);
117122
if (!unofficial)
118123
{
119124
solution.ID = ++_solutionCounter;

0 commit comments

Comments
 (0)