cph-implementation.md

Capacitated p-hub Problem (CPH) — Implementation

🏠 Home · ← Prev: CPH — Description

This document describes the Java implementation of the multi-start local search for the Capacitated p-hub Problem. The problem itself and the algorithm design are covered in the CPH description.

The complete, runnable source code is available in this repository under problems/no-framework/CPH. The implementation targets Java 25 and uses modern language features such as records and switch expressions. Every class name below links to its source file.

Design

The diagram shows the main classes of the application and the relationships between them.

classDiagram
    direction LR

    class Experiment
    class ExperimentManager
    class InstancesManager
    class InstanceFile {
        <<record>>
        +String fileName
        +String name
        +String type
        +loadInstance() Instance
    }
    class Instance
    class Node
    class Solution
    class MultiStartSearch
    class MSConfig {
        <<enumeration>>
        RANDOM
        FIRST_IMPROVEMENT_RANDOM
        FIRST_IMPROVEMENT_LEXICOGRAPHICAL
        BEST_IMPROVEMENT
    }
    class Constructive {
        <<abstract>>
    }
    class RandomConstructive
    class ImprovementMethod {
        <<abstract>>
    }
    class FirstImprovement
    class BestImprovement

    Constructive <|-- RandomConstructive
    ImprovementMethod <|-- FirstImprovement
    ImprovementMethod <|-- BestImprovement

    MultiStartSearch --> MSConfig : configured by
    MultiStartSearch ..> Constructive : builds with
    MultiStartSearch ..> ImprovementMethod : improves with
    MultiStartSearch ..> Solution : returns

    Experiment ..> InstancesManager : reads instances
    Experiment ..> MultiStartSearch : runs configs
    Experiment ..> ExperimentManager : records solutions
    InstancesManager "1" o-- "*" InstanceFile : registers
    InstanceFile ..> Instance : loadInstance()
    Instance "1" o-- "*" Node
    Solution --> Instance
    Solution "1" o-- "*" Node : hubs
    ExperimentManager ..> Solution : saves + reports

Loading

Figure 1. Class diagram of the multi-start local search applied to the CPH.

Problem data — package cph.instance

• Instance: the in-memory representation of an instance — the number of hubs p, the hub capacity, and each node's coordinates and demand. It builds one Node per center.
• Node: a node of an Instance; it holds its index and computes the Euclidean distance to another node from the instance's coordinates.
• InstanceFile: a lightweight record (file name, display name and type) that lazily loads an Instance from a classpath resource.
• InstancesManager: holds the registered list of available InstanceFiles (each tagged with its type, i.e. its instance set — phub_50_5 or phub_100_10) and lets callers query them all, by type, by position, or by file name.
• FormatException: a checked exception signalling a malformed instance file.

The search — package cph.algorithm

• Solution: keeps the list of hub nodes and the spoke-assignment array (which hub serves each node, or -1 if the node is itself a hub), evaluates the objective (the total client-to-hub distance), and implements the hub-swap operation used by the local search.
• MultiStartSearch: drives the multi-start loop under a time limit. Its MSConfig enum selects one of the four configurations by wiring together a Constructive and an optional ImprovementMethod.
• Construction — package constructive: Constructive (abstract base) plus RandomConstructive.
• Improvement — package improvement: ImprovementMethod (abstract base) plus FirstImprovement (with a CandidatesOrder enum for random/lexicographical order) and BestImprovement.

Entry point — package cph

• Experiment: the main program. It loads the phub_50_5 instances through InstancesManager, runs the four MultiStartSearch configurations on each instance under a fixed per-run time budget (TIMEOUT_MILLIS, 10 seconds), and hands each resulting Solution to the ExperimentManager.
• ExperimentManager: collects the results, computes statistics (the mean percentage deviation from the best solution found and the number of instances where each method reached that best value), prints a comparison table to the console, and saves each run under experiments/<datetime>/ — one file per instance and algorithm plus an HTML report (report.html).

Implementation Details

This section shows the implementation of the most relevant classes.

Problem data: Instance and Node

An Instance stores each node's coordinates and demand (nodeData[index] = {x, y, demand}), the number of hubs p and the hub capacity, and builds one Node per center. A Node computes the Euclidean distance to another node from those coordinates (truncated to an integer).

package cph.instance;

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

public class Instance {

    private int numHubs;
    private int hubCapacity;
    private int nodeData[][];
    private List<Node> nodes;
    private String name;

    public Instance(String name, int numNodes, int numHubs, int hubCapacity, int[][] nodeData) {
        this.name = name;
        this.numHubs = numHubs;
        this.hubCapacity = hubCapacity;
        this.nodeData = nodeData;
        nodes = new ArrayList<Node>();
        for (int i = 0; i < numNodes; i++) {
            nodes.add(new Node(i, this));
        }
    }

    public Node getNode(int index) {
        return nodes.get(index);
    }

    public int getX(int index) {
        return nodeData[index][0];
    }

    public int getY(int index) {
        return nodeData[index][1];
    }

    public int getDemand(int index) {
        return nodeData[index][2];
    }

    public int getNumNodes() {
        return nodes.size();
    }

    public int getNumHubs() {
        return numHubs;
    }

    public int getHubCapacity() {
        return hubCapacity;
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public String getName() {
        return name;
    }

    public String getDescription() {
        return name + " (n=" + getNumNodes() + ", p=" + numHubs + ", c=" + hubCapacity + ")";
    }

}

package cph.instance;

public class Node {

    private int index;
    private Instance instance;

    public Node(int index, Instance instance) {
        this.index = index;
        this.instance = instance;
    }

    public int getDistanceTo(Node node) {
        // Euclidean distance between the coordinates of the two nodes
        double dx = Math.pow(instance.getX(node.index) - instance.getX(index), 2);
        double dy = Math.pow(instance.getY(node.index) - instance.getY(index), 2);

        return (int) Math.sqrt(dx + dy);
    }

    public int getIndex() {
        return index;
    }

    @Override
    public int hashCode() {
        return index;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Node node) {
            return index == node.index;
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        return Integer.toString(index);
    }

}

Solution

The Solution holds the list of hubs and the spokes array (spokes[i] is the index of the hub that serves node i, or -1 if node i is itself a hub) and its objective value (totalWeight, the total client-to-hub distance). calculateWeightChangeHub evaluates the objective a hub swap would produce without modifying the solution — the operation used by the local search strategies — while changeHub applies the swap, making the new node a hub and reassigning to it every client the replaced hub was serving.

package cph.algorithm;

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

import cph.instance.Instance;
import cph.instance.Node;

public class Solution {

    private Instance instance;
    private List<Node> hubs;

    // spokes[i] holds the index of the hub that serves node i,
    // or -1 if node i is a hub
    private int[] spokes;

    private int totalWeight;

    public Solution(Instance instance, List<Node> hubs, int[] spokes) {
        this.instance = instance;
        this.hubs = hubs;
        this.spokes = spokes;
        calculateWeight();
    }

    public void calculateWeight() {
        totalWeight = calculateWeight(hubs, spokes);
    }

    private int calculateWeight(List<Node> solutionHubs, int[] solutionSpokes) {
        int weight = 0;

        // The solution weight is the sum of the distances from each
        // client to the hub that serves it
        for (Node hub : solutionHubs) {
            for (int i = 0; i < solutionSpokes.length; i++) {
                if (solutionSpokes[i] == hub.getIndex()) {
                    weight += hub.getDistanceTo(instance.getNode(i));
                }
            }
        }

        return weight;
    }

    public int calculateWeightChangeHub(Node oldHub, Node newHub) {

        // Build new hub list and spokes with the old hub replaced
        // by the new one (the new hub takes over all its clients)
        List<Node> newHubs = new ArrayList<>();
        for (Node hub : hubs) {
            if (hub.equals(oldHub)) {
                newHubs.add(newHub);
            } else {
                newHubs.add(hub);
            }
        }

        int[] newSpokes = new int[spokes.length];
        for (int i = 0; i < spokes.length; i++) {
            if (spokes[i] == oldHub.getIndex()) {
                newSpokes[i] = newHub.getIndex();
            } else {
                newSpokes[i] = spokes[i];
            }
        }
        newSpokes[oldHub.getIndex()] = newHub.getIndex();
        newSpokes[newHub.getIndex()] = -1;

        return calculateWeight(newHubs, newSpokes);
    }

    public void changeHub(Node oldHub, Node newHub) {
        for (int i = 0; i < hubs.size(); i++) {
            if (hubs.get(i).equals(oldHub)) {
                hubs.set(i, newHub);
                break;
            }
        }

        for (int i = 0; i < spokes.length; i++) {
            if (spokes[i] == oldHub.getIndex()) {
                spokes[i] = newHub.getIndex();
            }
        }
        spokes[oldHub.getIndex()] = newHub.getIndex();
        spokes[newHub.getIndex()] = -1;

        calculateWeight();
    }

    public boolean isHub(Node node) {
        return hubs.contains(node);
    }

    public int getTotalWeight() {
        return totalWeight;
    }

    public List<Node> getHubs() {
        return hubs;
    }

    public int[] getSpokes() {
        return spokes;
    }

    public Instance getInstance() {
        return instance;
    }

    @Override
    public String toString() {
        List<List<Integer>> hubsWithClients = new ArrayList<>();

        for (Node hub : hubs) {
            List<Integer> elements = new ArrayList<>();
            elements.add(hub.getIndex());

            for (int i = 0; i < spokes.length; i++) {
                if (spokes[i] == hub.getIndex()) {
                    elements.add(i);
                }
            }

            hubsWithClients.add(elements);
        }

        return hubsWithClients.toString();
    }

}

The multi-start driver

MultiStartSearch wires a Constructive and an optional ImprovementMethod according to the chosen MSConfig, then repeatedly builds, improves and keeps the best solution until the restart budget or the time limit is reached. Because the CPH is a minimization problem, "best" means the smallest objective value.

package cph.algorithm;

import cph.algorithm.constructive.Constructive;
import cph.algorithm.constructive.RandomConstructive;
import cph.algorithm.improvement.BestImprovement;
import cph.algorithm.improvement.FirstImprovement;
import cph.algorithm.improvement.FirstImprovement.CandidatesOrder;
import cph.algorithm.improvement.ImprovementMethod;
import cph.instance.Instance;

public class MultiStartSearch {

    public enum MSConfig {
        RANDOM, FIRST_IMPROVEMENT_RANDOM, FIRST_IMPROVEMENT_LEXICOGRAPHICAL, BEST_IMPROVEMENT
    }

    private static final int NUM_SOLUTIONS = 5000;

    private Constructive constructive;
    private ImprovementMethod improvingMethod;

    public MultiStartSearch(Instance instance, MSConfig methodConfig) {

        constructive = new RandomConstructive(instance);

        switch (methodConfig) {
            case RANDOM -> improvingMethod = null;
            case FIRST_IMPROVEMENT_RANDOM ->
                improvingMethod = new FirstImprovement(CandidatesOrder.RANDOM);
            case FIRST_IMPROVEMENT_LEXICOGRAPHICAL ->
                improvingMethod = new FirstImprovement(CandidatesOrder.LEXICOGRAPHICAL);
            case BEST_IMPROVEMENT -> improvingMethod = new BestImprovement();
        }
    }

    public Solution calculateSolution(long millisTimeout) {

        long finishTime = System.currentTimeMillis() + millisTimeout;

        Solution bestSolution = null;

        for (int i = 0; i < NUM_SOLUTIONS; i++) {

            Solution solution = constructive.createSolution();

            if (improvingMethod != null) {
                improvingMethod.improveSolution(solution);
            }

            if (bestSolution == null
                    || solution.getTotalWeight() < bestSolution.getTotalWeight()) {
                bestSolution = solution;
            }

            // If the time limit has been exceeded, exit the algorithm
            if (System.currentTimeMillis() > finishTime) {
                break;
            }
        }

        return bestSolution;
    }

}

Construction: random hubs and assignment

Constructive methods are subclasses of the abstract Constructive. The random constructive picks p random hubs and then randomly assigns the remaining nodes to hubs, respecting the capacity constraint, until every node is assigned.

package cph.algorithm.constructive;

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

import cph.algorithm.Solution;
import cph.instance.Instance;

public abstract class Constructive {

    protected Instance instance;

    public Constructive(Instance instance) {
        this.instance = instance;
    }

    public Instance getInstance() {
        return instance;
    }

    public List<Solution> createSolutions(int numSolutions) {
        List<Solution> solutions = new ArrayList<Solution>();
        for (int i = 0; i < numSolutions; i++) {
            solutions.add(createSolution());
        }
        return solutions;
    }

    public abstract Solution createSolution();

}

package cph.algorithm.constructive;

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

import cph.algorithm.Solution;
import cph.instance.Instance;
import cph.instance.Node;

public class RandomConstructive extends Constructive {

    private static final Random random = new Random();

    public RandomConstructive(Instance instance) {
        super(instance);
    }

    @Override
    public Solution createSolution() {

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

        do {
            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);
                }

            } else {

                // Try to assign a random client to each hub, respecting
                // the hub capacity
                for (Node 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);
                        }
                    }
                }
            }

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

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

}

Improvement: best and first improvement

Improvement methods are subclasses of the abstract ImprovementMethod, which exposes a single improveSolution operation that improves a solution in place.

package cph.algorithm.improvement;

import cph.algorithm.Solution;

public abstract class ImprovementMethod {

    public abstract void improveSolution(Solution solution);

}

BestImprovement scans the entire hub-swap neighborhood and applies the move that reduces the total distance the most, repeating until no improving move remains:

package cph.algorithm.improvement;

import cph.algorithm.Solution;
import cph.instance.Instance;
import cph.instance.Node;

public class BestImprovement extends ImprovementMethod {

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        boolean hubChanged;
        int bestWeight;
        Node bestOldHub;
        Node bestNewHub;

        do {
            hubChanged = false;
            bestWeight = solution.getTotalWeight();
            bestOldHub = null;
            bestNewHub = null;

            for (int i = 0; i < solution.getHubs().size(); i++) {
                Node oldHub = solution.getHubs().get(i);

                for (Node newHub : instance.getNodes()) {

                    if (!solution.isHub(newHub)) {

                        int newWeight = solution.calculateWeightChangeHub(oldHub, newHub);

                        // Keep the best change that improves the solution
                        if (newWeight < bestWeight) {
                            bestWeight = newWeight;
                            bestOldHub = oldHub;
                            bestNewHub = newHub;
                        }
                    }
                }
            }

            if (bestNewHub != null) {
                solution.changeHub(bestOldHub, bestNewHub);
                hubChanged = true;
            }

        } while (hubChanged);
    }

}

FirstImprovement applies the first improving hub swap it finds, visiting candidates in the order selected by its CandidatesOrder (random or lexicographical):

package cph.algorithm.improvement;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import cph.algorithm.Solution;
import cph.instance.Instance;
import cph.instance.Node;

public class FirstImprovement extends ImprovementMethod {

    public enum CandidatesOrder {
        RANDOM, LEXICOGRAPHICAL
    }

    private final CandidatesOrder order;

    public FirstImprovement(CandidatesOrder order) {
        this.order = order;
    }

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        List<Node> candidates = new ArrayList<>(instance.getNodes());
        switch (order) {
            case RANDOM -> Collections.shuffle(candidates);
            case LEXICOGRAPHICAL -> candidates.sort(Comparator.comparingInt(Node::getIndex));
        }

        boolean hubChanged;

        do {
            hubChanged = false;

            for (int i = 0; i < solution.getHubs().size(); i++) {
                Node oldHub = solution.getHubs().get(i);

                for (Node newHub : candidates) {

                    if (!solution.isHub(newHub)) {

                        int newWeight = solution.calculateWeightChangeHub(oldHub, newHub);

                        // Keep the first change that improves the solution
                        if (newWeight < solution.getTotalWeight()) {
                            solution.changeHub(oldHub, newHub);
                            hubChanged = true;
                            break;
                        }
                    }
                }
            }

        } while (hubChanged);
    }

}

---

Next: MDP — Description →