|
Abstract:
|
In this work a genetic algorithm (GA) for solving Uncapacitated Multiple Allocaton
p-hub Median Problem (UMApHMP), Uncapacitated Multiple Allocaton p-hub Center
Problem (UMApHCP) and Discrete Ordered Median Problem (DOMP) is described.
These NP-hard problems have many applications in practice. Binary representation
is used, genetic operators adopted to the problems are constructed and hybridization
GA with modified interchange heuristic for solving DOMP is applied. Proposed
algorithm is tested on the corresponding instances from the literature. For both hub
location problems GA reaches all solutions that are proved to be optimal so far in a
reasonable computational time, even for problem instances of higher dimensions. In
this paper the solutions for the large-scaled problem instances (n=200, p=20) that are
not reported in the literature yet are also presented. Significant results are also
obtained on DOMP instances with dimensions n≤900, p≤200. For all problems GA
solutions are comparable or better than ones obtained by existing methods. |