SomAla
SomAla is a new hybrid heuristic for the capacitated pmedian problem (CPMP) which combines a selforganising map (SOM), integerprogramming,
an alternating locationallocation algorithm (ALA) and a partial neighbourhood optimisation heuristic.
The CPMP is intended to find optimal locations of sources which
have to serve a set of demand nodes in order to minimise
the total distances between the sources and the destinations.
SomAla consists of three working steps.

SOMGAPbased heuristic to solve a continuous,capacitated pmedian problem:
A SOM is used to solve a continuous, uncapacitated pmedian problem.
The locations of the sources and the allocations of the demand nodes
are the basis to find a solution for a continuous, capaci
tated pmedian problem by solving a generalised assignment problem (GAP).

Capacitated alternating locationallocation heuristic:
The solution found in the first step is used in a ca pacitated ALA heuristic to find and improve a solution for the CPMP.
The allocation of the destinations to the sources is based on a GAP which is solved by using a size reducing technique and variable relaxingfixing heuristic.
The locations are modified by determining new medians for each allocation cluster. Both steps are repeated as long as improvements for the CPMP occur
or a maximum number of steps is not reached.

Partial neighbourhood optimisation heuristic:
In the last step, the best solution found so far is improved by us ing a partial neighbourhood optimisation heuristic.
In each step, a subregion, surrounding a selected median, is solved. If the solution found for this subregion improves
the objective function value of the entire problem, then the partial solution updates the entire solution. The optimisation of the subregions can be
done either by the first two SomAla steps (SomAlaMS) or by solving a sizereduced CPMP (SomAlaMM).
This procedure is repeated until all medians are optimised or a maximum number of steps with no improvements is
reached.