metaheuristics-in-java/problems/jmh/CPH/src/main/java/cph/algorithm/CPHRandomConstructive.java at master · codeurjc/metaheuristics-in-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package cph.algorithm;
import cph.instance.CPHInstance;
import cph.instance.CPHNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import jmh.algorithm.Constructive;

/**
 * Builds a random CPH solution: picks {@code p} random hubs and then assigns
 * random clients to them while respecting each hub's capacity.
 */
public class CPHRandomConstructive extends Constructive<CPHInstance> {

    private static final Random random = new Random();

    public CPHRandomConstructive(CPHInstance instance) {
        super(instance);
    }

    @Override
    public CPHSolution createSolution() {

        List<Integer> assignedNodes = new ArrayList<>();
        List<CPHNode> hubs = new ArrayList<>();
        int[] hubLoads = new int[instance.getNumNodes()];
        int[] spokes = new int[instance.getNumNodes()];

        // A random client assignment can become infeasible (no open hub has enough
        // remaining capacity for any unassigned client): give up and restart the
        // whole construction with a fresh random draw instead of retrying forever.
        int stagnantIterations = 0;
        int maxStagnantIterations = 4 * instance.getNumNodes() + 10;

        do {
            boolean progressed = false;

            if (hubs.size() != instance.getNumHubs()) {

                // Select a random node as hub
                int randomNode = random.nextInt(instance.getNumNodes());

                if (!assignedNodes.contains(randomNode)) {
                    hubs.add(instance.getNode(randomNode));
                    spokes[randomNode] = -1;
                    assignedNodes.add(randomNode);
                    progressed = true;
                }

            } else {

                // Try to assign a random client to each hub, respecting
                // the hub capacity
                for (CPHNode hub : hubs) {
                    int randomNode = random.nextInt(instance.getNumNodes());

                    if (!assignedNodes.contains(randomNode)) {
                        int demand = instance.getDemand(randomNode);

                        if (hubLoads[hub.getIndex()] + demand <= instance.getHubCapacity()) {
                            hubLoads[hub.getIndex()] += demand;
                            spokes[randomNode] = hub.getIndex();
                            assignedNodes.add(randomNode);
                            progressed = true;
                        }
                    }
                }
            }

            if (progressed) {
                stagnantIterations = 0;
            } else if (++stagnantIterations > maxStagnantIterations) {
                assignedNodes.clear();
                hubs.clear();
                java.util.Arrays.fill(hubLoads, 0);
                java.util.Arrays.fill(spokes, 0);
                stagnantIterations = 0;
            }

        } while (hubs.size() != instance.getNumHubs()
                || assignedNodes.size() != instance.getNumNodes());

        return new CPHSolution(instance, hubs, spokes);
    }

}