SomAla is a new hybrid heuristic for the capacitated p-median problem (CPMP) which combines a self-organising map (SOM), integer-programming, an alternating location-allocation 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.

  1. SOM-GAP-based heuristic to solve a continuous,capacitated p-median problem:
    A SOM is used to solve a continuous, uncapacitated p-median 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 p-median problem by solving a generalised assignment problem (GAP).

  2. Capacitated alternating location-allocation 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 relaxing-fixing 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.

  3. 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 (SomAla-MS) or by solving a size-reduced CPMP (SomAla-MM). This procedure is repeated until all medians are optimised or a maximum number of steps with no improvements is reached.