We here propose an efficient tabu search (TS) for solving the uncapacitated single allocation hub location problem. To decrease the computational time, in the proposed tabu search, some new tabu rules are considered. Also, to compute the changes in the objective function’s value in each move, some new results are given. The performance of the proposed tabu search is compared with a recently proposed tabu search (Silva & Cunha, 2009) on all standard ORLIB instances (CAB and AP data sets), modified AP data set and finally on four large instances with 300 and 400 nodes proposed by Silva and Cunha. The numerical experiments show that the proposed tabu search can find all optimal solutions of CAB data and the best known solution of other standard test problems in less computational time than Silva and Cunha’s tabu search. Also, the proposed tabu search can improve the best known solutions for some standard test problems.
Hub location problems are widely applied in postal networks (Ebery, Krishnamoorthy, Ernst, & Boland, 2000; Kuby & Gray, 1993), airlines (Aykin, 1995; Bania, Bauer, & Zlatoper, 1998; Karimi & Bashiri, 2011; Yang, 2009), telecommunication networks (Carello, Croce, Ghirardi, & Tadel, 2004; Helme & Magnanti, 1989; Kim & OKelly, 2009), transportation systems (Aversa, Botter, Haralambides, & Yoshizaki, 2005; Cunha & Silva, 2007; Don, Harit, English, & Whisker, 1995), emergency services (Campbell, 1994; Hakimi, 1964), etc. Generally, hub location problems are used in systems which have many origins and destinations, and direct link between each o–d1 is impossible or expensive. In these location–allocation problems, flows consolidate at hub nodes. Thus, all transportation become possible through hubs and also, costs are reduced because of the economical advantages of the scale. In hub location problems, usually, hubs are fully interconnected, transferring between hubs includes a discount factor, and direct links between non-hub nodes are not allowed. In addition, in most of hub location problems, hubs are a subset of discrete nodes, however there are some researches on continuous hub location problems (see Aykin & Brown, 1992; Campbell, 1990; OKelly, 1992).
We here proposed an efficient tabu search (TS) for solving the uncapacitated single allocation hub location problem (USAHLP). To decrease the computational time, in the proposed tabu search, some new tabu rules were considered. Also, to compute the changes in the objective function’s value in each move, some new results were given. The performance of the proposed tabu search was compared with recently proposed approaches on all standard ORLIB instances (CAB and AP data sets), modified AP data set and finally on four large instances with 300 and 400 nodes proposed by Silva and Cunha. The numerical experiments showed that the proposed algorithm obtained the optimal solution for instances which optimal solutions are proven. Furthermore, our proposed tabu search obtained the best known solution found in the literature or surpass them in a very short computational time. It is notable that our proposed tabu search obtained the same solution in each run against other methods proposed for USAHLP. Our proposed TS outperforms the recently proposed TS (Silva & Cunha, 2009) in both solution values and computational times.