A hybrid VNS–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 assign users to these points. Over the last few decades, the field of hybrid metaheuristics has been continuously growing. Variable neighbourhood search and path relinking are two recent evolutionary approaches that have proven very effective in solving optimization problems. In this paper, we present a hybrid algorithm that combines these new heuristics to solve the p-hub median problem and compare its effectiveness with other classical techniques. This procedure provides high-quality solutions in reasonable time frames.