| In this research, we propose metaheuristics for solving two p-hub median problems. The first p-hub median problem, which is NP-hard, is the uncapacitated single p-hub median problem (USApHMP). In this problem, metaheuristics such as genetic algorithms, simulated annealing and tabu search, are applied in different types of representations. Caching is also applied to speed up computational time of the algorithms. The results clearly demonstrate that tabu search with a permutation solution representation, augmented with caching is the highest performing method, both in terms of solution quality and computational time among these algorithms for the USApHMP. We also investigate the performance of hybrid metaheuristics, formed by path-relinking augmentation of the three base algorithms (genetic algorithms, simulated annealing and tabu search). The results indicate that hybridrization with path-relinking improves the performance of base algorithms except tabu search since a good base metaheuristic does not require path-relinking. For the second p-hub median problem, the NP-hard uncapacitated multiple p-hub median problem (UMApHMP), we proposed Multiple TS. We identify multiple nodes using the convex hull and methods derived from the tabu search for the USApMHP. We find optimal allocations using the Single Reallocation Exchange procedure, developed for the USApHMP. The results show that implementing tabu search with a geometric interpretation allows nearly all optimal solutions to be found. |
