Genetic algorithms for solving the discrete ordered median problem

Abstract

In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.