On the use of Path Relinking for the p: Hub median problem

The p - hub median problem is an NP hard location - allocation problem, which consists of finding p points to establish facilities and the assignment of the users to these points. A new evolutionary approach that has been very effective for solving optimisation problems is Path Relinking, an extension of Scatter Search that links solutions over neighborhood spaces. Path Relinking gives a framework for combining solutions that goes beyond the crossover mechanism of genetic algorithms, and introduces new fundamental principles, such as the use of systematic strategies instead of random strategies. In this paper, we present an application of Path Relinking to solve the p - hub median problem and compare its effectiveness with other classical techniques. This procedure provides high quality solutions in reasonable execution times and yields a significant improvement in the size of the problems that can be solved.