cph-description.md

Capacitated p-hub Problem (CPH)

🏠 Home · ← Prev: CWP — Implementation

This document describes the Capacitated p-hub Problem and the design of the algorithm used to solve it. The implementation details are covered in the CPH implementation notes.

Problem Description

There are n centers that can act either as clients or as servers (also called hubs). Exactly p of them must be selected as hubs; every remaining center is a client that must be connected to exactly one hub. Each hub has the same fixed capacity, and each client has a demand; a hub can only serve a set of clients whose total demand does not exceed its capacity. The goal is to choose the p hubs and connect every client to a hub so that the total client-to-hub distance is minimized while every capacity constraint is respected.

• Solution structure: a set of p hub nodes plus an assignment (a spoke) of every non-hub node to exactly one hub.
• Constraints:
  • exactly p nodes must be selected as hubs;
  • every non-hub node must be assigned to exactly one hub;
  • for each hub, the sum of the demands of its assigned clients cannot exceed the hub capacity.
• Objective function: the sum of the (Euclidean) distances between every client and the hub it is assigned to.
• Optimization sense: minimization — the lower the total distance, the better the solution.

Letting $x_{ij} = 1$ if client $i$ is assigned to hub $j$ (and $0$ otherwise), $y_j = 1$ if node $j$ is a hub, $d_{ij}$ the distance between nodes $i$ and $j$, $d_i$ the demand of client $i$, $c$ the hub capacity and $p$ the number of hubs, the CPH can be formulated as:

$$ \begin{aligned} \text{minimize} \quad & z(x) = \sum_{j} \sum_{i} d_{ij}, x_{ij} \\ \text{subject to} \quad & \sum_{j} x_{ij} = 1 \quad \forall i \\ & x_{ij} \le y_j \quad \forall i, \forall j \\ & \sum_{j} y_j = p \\ & \sum_{i} x_{ij} \cdot d_i \le c \quad \forall j \\ & x_{ij},, y_j \in {0,1} \end{aligned} $$

Note. The original assignment statement writes this objective as a maximization, but the intended goal — and the one implemented in the reference code — is to minimize the total client-to-hub distance.

Instance format

Two instance sets are used: phub_50_5 (small instances, 50 nodes of which 5 must be chosen as servers) and phub_100_10 (larger instances, 100 nodes of which 10 must be servers). Both sets share the same file format:

• A first line with the total number of nodes, the number of server nodes (p) and the capacity of each server (all servers have the same capacity).
• One line per node: the node number (numbered from 0), its two geometric coordinates (in a Euclidean space) and its demand as a client.

50 5 120
0 2 62 3
1 80 25 14
2 36 88 1
3 57 23 14
4 33 17 19
...

Algorithm Design

The CPH is solved with a multi-start local search: a random feasible solution is built and (optionally) improved with a local search, and this is repeated many times within a time budget, keeping the best solution found across all restarts. Four configurations are compared experimentally, differing in how each restart is improved.

Constructive: random hubs and assignment

The constructive method builds a feasible solution in two phases: it first picks p distinct nodes at random as hubs, and then repeatedly tries to assign a random unassigned node to a hub — accepting the assignment only when the hub still has enough spare capacity for that node's demand — until every node has been assigned. No objective (distance) information guides the construction.

Neighborhood and moves

The local search explores a hub-swap neighborhood: a move replaces one of the current hubs with a node that is not currently a hub. The candidate node becomes a hub and inherits all the clients previously served by the hub it replaces. Each candidate move is evaluated by recomputing the objective (the total client-to-hub distance) of the resulting solution; a move is improving when it decreases that value.

Local search strategies

Two classic neighborhood-exploration strategies are compared:

• Best improvement: the whole neighborhood is built and the move that improves the solution the most is applied. This repeats from the resulting solution until no improving move exists.
• First improvement: the first move found that improves the current solution is applied immediately, without examining the rest of the neighborhood. This repeats until no improving move exists.

For first improvement, the order in which candidates are visited matters. If the order is always lexicographical (smaller indices first), the search explores more exhaustively the region around low-index nodes and is unlikely to reach other regions that might contain the optimum. For this reason the candidate order is often randomized so that all regions of the search space are visited with similar probability. Both a lexicographical and a random candidate order are compared.

Configurations compared

Four configurations are run and compared:

Configuration	Construction	Improvement
Random	random hubs + assignment	none
First improvement (random)	random hubs + assignment	first improvement, random candidate order
First improvement (lexicographical)	random hubs + assignment	first improvement, lexicographical candidate order
Best improvement	random hubs + assignment	best improvement

Pseudocode

The multi-start driver builds and improves solutions until a restart budget or a time limit is reached, keeping the best (here, "better" means a smaller total distance, because the CPH is a minimization problem):

$$ \begin{aligned} &\textbf{function } \text{MultiStartSearch}(\text{instance},\ \text{timeout}) \\ &\quad best := \text{null} \\ &\quad \textbf{repeat } N \textbf{ times, or until } \text{timeout} \\ &\qquad s := \text{RandomConstructive}(\text{instance}) \\ &\qquad \textbf{if } \text{improvement enabled} \textbf{ then } \text{improveSolution}(s) \\ &\qquad \textbf{if } best = \text{null} \textbf{ or } s \text{ better than } best \textbf{ then } best := s \\ &\quad \textbf{return } best \end{aligned} $$

Best improvement applies, at each step, the hub swap with the largest improvement:

$$ \begin{aligned} &\textbf{function } \text{BestImprovement}(s) \\ &\quad \textbf{repeat} \\ &\qquad bestMove := \text{none} \\ &\qquad \textbf{for each } \text{hub } h,\ \textbf{for each } \text{non-hub node } v \\ &\qquad\quad \textbf{if } \text{replacing } h \text{ by } v \text{ improves } s \text{ the most so far} \textbf{ then } bestMove := (h,v) \\ &\qquad \textbf{if } bestMove \ne \text{none} \textbf{ then apply } bestMove \textbf{ to } s \\ &\quad \textbf{until } bestMove = \text{none} \end{aligned} $$

First improvement applies the first improving hub swap found over the ordered candidates:

$$ \begin{aligned} &\textbf{function } \text{FirstImprovement}(s,\ order) \\ &\quad candidates := \text{nodes sorted by } order\ (\text{random or lexicographical}) \\ &\quad \textbf{repeat} \\ &\qquad changed := \text{false} \\ &\qquad \textbf{for each } \text{hub } h,\ \textbf{for each } v \in candidates \\ &\qquad\quad \textbf{if } v \text{ is not a hub and replacing } h \text{ by } v \text{ improves } s \textbf{ then} \\ &\qquad\qquad \text{apply swap};\ changed := \text{true};\ \textbf{break} \\ &\quad \textbf{until } changed = \text{false} \end{aligned} $$

---

Next: CPH — Implementation →