Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Industrial Engineering


Kurz, Mary E

Committee Member

Cho , Byung R

Committee Member

Ferrell , William G

Committee Member

Mason , Scott J


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 improvees 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.