p-Hub Location Allocation Problem in MATLAB

This package solves the p-Hub Location Allocation Problem in MATLAB using Particle Swarm Optimization (PSO).

In a hub network, traffic between many origins and destinations does not travel directly. It is first collected at a hub, moved between hubs, and then sent to its destination. Links between hubs carry a lot of traffic, so the cost per unit on them is lower. The problem has two linked decisions: where to open the hubs (location) and which hub serves each node (allocation). Morton O’Kelly gave the first formal model of this problem, the p-hub median problem, in 1987. It is NP-hard, which makes it a good case for metaheuristics.

The problem

There are $N$ nodes. Node $i$ sends $r_{ij}$ units of flow to node $j$, and $c_{ij}$ is the transport cost per unit between $i$ and $j$. Opening a hub at node $k$ costs $f_k$.

The version in this code is single allocation and uncapacitated:

• At most $P$ nodes are chosen as hubs.
• Every node is allocated to exactly one hub. A hub is allocated to itself.
• Hubs have no capacity limit.

If node $i$ is allocated to hub $h(i)$, a unit of flow from $i$ to $j$ travels $i \to h(i) \to h(j) \to j$. The cost of the middle leg, between the two hubs, is multiplied by a discount factor $\alpha < 1$:

ParseSolution.m computes two cost terms from this:

• SumOCR, the total transport cost $\sum_{i}\sum_{j} r_{ij} \, \text{OC}_{ij}$,
• SumXF, the total fixed cost $\sum_{k \in \text{hubs}} f_k$ of the open hubs.

MyCost.m returns the weighted sum

So the transport cost has five times the weight of the fixed cost. Because opening a hub has a cost, the best solution may use fewer than $P$ hubs.

How a particle becomes a hub network

Each particle is an $N \times N$ matrix with values in $[0, 1]$. ParseSolution.m decodes it in two steps:

1. Location. The diagonal value of node $i$ says how much it “wants” to be a hub. Nodes with a diagonal value of at least 0.5 become hubs, up to $P$ of them, starting with the largest values. If no value reaches 0.5, the node with the largest one becomes the only hub.
2. Allocation. For each node $i$, the code looks at column $i$ of the matrix and picks the open hub with the largest value. That hub serves node $i$.

After the PSO move, Mutate.m changes the particle with one of seven operators: swap two rows, swap two columns, swap two elements, swap two diagonal elements, reverse a part of the diagonal, turn a hub off (halve its diagonal value) or turn a hub on (double it). Before that, it halves the diagonal value of one hub that serves at most one other node, which usually closes that hub. The mutated particle is kept when it is not worse, and also with probability 0.1. In each iteration, the global best gets three extra mutation attempts.

What is in the download

• pso.m: the PSO algorithm.
• CreateRandomSolution.m, ParseSolution.m and Mutate.m: create a solution, convert a particle position into hubs and allocations, and mutate a solution.
• MyCost.m: the cost function. It is a weighted sum of two terms computed in ParseSolution.m.
• PlotSolution.m: plots a solution.
• SelectModel.m and the files phlap_20.mat, phlap_30.mat and phlap_40.mat: three saved problem models.
• A Model Creation folder with CreateRandomModel.m and CreateAndSaveModels.m, which generate random models and save them.

The three saved models have 20, 30 and 40 nodes. In CreateRandomModel.m, the nodes lie near a grid on a 100 by 100 area, the cost per unit is 10 times the distance, the discount factor is $\alpha = 0.7$, flows are between 10 and 50, and $P$ is between 15 and 20 percent of $N$.

How to run

Open the folder in MATLAB and run pso.m. There is no separate main.m.

A file dialog opens. Choose one of the phlap_*.mat files. The program prints the best cost in every iteration. PlotSolution.m draws the hubs as yellow squares, the other nodes as circles, and a colored line from each node to its hub. At the end, a second figure shows the best cost against the iteration. The code calls randsample and unifrnd, so it probably needs the Statistics and Machine Learning Toolbox.

Parameters in the code

Check the result

Confirm that at least one hub is open, no more than P hubs are used, and every node is assigned to an open hub. Report opening costs and transport costs separately so that the effect of w1 and w2 is visible. This implementation allows fewer than P hubs, unlike an exactly-p formulation, and it has no hub-capacity constraint. Check those assumptions before adapting the model to a real network.

Applications

Hub networks are common in transport and communication:

• Airline networks with hub airports.
• Parcel and express delivery, with sorting centers as hubs.
• Freight transport by truck and rail.
• Telecommunication and computer networks.

Related posts

• Particle Swarm Optimization in MATLAB
• Capacitated Vehicle Routing Problem using Simulated Annealing, another logistics problem.
• Facility Layout Design using PSO in MATLAB

Mostapha Kalami Heris, p-Hub Location Allocation Problem in MATLAB (YPAP110), Yarpiz, 2015. https://yarpiz.com/hub-location-allocation-ypap110

@misc{yarpiz-ypap110,
  author = {{Mostapha Kalami Heris}},
  title = {{p-Hub Location Allocation Problem in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPAP110},
  url = {https://yarpiz.com/hub-location-allocation-ypap110}
}