A solution to the hub center problem via a single-relocation algorithm with tabu search

Pamuk F., Sepil C.

IIE TRANSACTIONS, vol.33, no.5, pp.399-411, 2001 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 33 Issue: 5
  • Publication Date: 2001
  • Doi Number: 10.1023/a:1011053230283
  • Journal Name: IIE TRANSACTIONS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.399-411
  • Middle East Technical University Affiliated: No


Network designers for many transportation or telecommunication applications need to minimize the maximum (weighted) interaction time or distance in the networks, i.e., to solve the p-hub center problems. This study addresses the p-hub center problem. A single-relocation heuristic is proposed as a means of generating location-allocation strategies in a reasonable amount of time, and tabu search is superimposed on the underlying algorithm, so as to decrease the possibility of being trapped by local optima. Two single-allocation schemes are adapted from the literature, and a further one is developed specifically for the minimax objective function, for use in the evaluation phase of the algorithm. A greedy local search is employed to improve the resulting allocations. A number of strategies for choosing the initial hub locations are discussed and initial strategy - allocation scheme combinations are compared in terms of solution quality and pragmatic efficiency.