Solving the uncapacitated hub location problem using genetic algorithms
Introduction
In many transportation and telecommunication networks, the cost of carrying a unit of traffic between two points decreases as the capacity of the connection joining the two points increases. It is possible to facilitate this connection by building dedicated channels between each pair of nodes that communicate with each other. However, this would result in higher costs. Because of this fact, it is often convenient to design networks in which traffic is concentrated on high capacity links, even if this traffic travels longer distances. In order to facilitate the flow of the traffic between nodes so as to decrease the overall cost of transportation, some centers known as hubs are introduced. Airline passenger flow, cargo or postal delivery networks, large telecommunication networks are examples of networks utilizing hubs.
There are different versions of the hub location problem [1]. There may be capacity restrictions on the volume of traffic a hub can collect, there may be a fixed cost associated with establishing any node as a hub and we may allocate nodes to one or more hubs [2]. However, in all of these variants, the objective function is to find the location of the hubs and the allocation of the nodes so that the total cost of the network is minimized. If all traffic flow via the hub nodes and each spoke (non-hub node) is allocated to a single hub node, this problem is specified as uncapacitated single allocation hub location problem (USAHLP). In this problem, the number of hubs is a decision variable and a fixed cost component is included in the formulation. If the number of hubs is fixed, say equal to p, this problem is referred to as an uncapacitated single allocation p-hub median problem (USApHMP).
The hub location problem was formulated as a quadratic integer program firstly by O'Kelly [1] and this problem is NP-hard even when the hub locations are fixed. The single allocation case has been studied by Aykin [3], Campbell [4], [5], Klincewicz [6], O'Kelly et al. [7]. The proposed methods for USAHLP are mainly heuristics that do not guarantee optimal solutions, such as problem specific heuristics [1], tabu search [6], hybrid of genetic algorithms and tabu search [9], and neural networks [10].
Genetic Algorithms (GA) has been adapted to many operational research problems such as scheduling problems and the traveling salesman problem; however, there are very few applications to location-allocation problems. In this paper, we present a novel solution based on a genetic search framework for USAHLP. We compare the quality of solutions from our method with the solutions from GATS algorithm, which stands for “Genetic Algorithm and Tabu Search”. The GATS algorithm is the most recent study for USAHLP and its results [9] match the best solutions found in the literature.
We evaluate the effectiveness of our method with both the CAB (Civil Aeronautics Board) data set and the AP (Australian Post) data set by considering the total transportation cost and the running time as the comparison metrics. The CAB data set [12] was originated by the CAB, and it has been the most popular data set used to benchmark algorithms for hub location problems. Based on the CAB data set, the results generated by our method match the best solutions found in the literature with an average of 8–14 times shorter running time than the related work. We also consider the AP data set [13] which was derived from a real-world location problem for AP. Similarly, our method obtains the best solutions found in the literature and it outperforms the related work with respect to the total cost of the network in 57% of the cases of AP data set with significantly less computational effort.
The remainder of this paper is organized as follows. In Section 2, we define the mathematical formulation of the problem that we address. Section 3 gives the details of our GA-based formulation, which is followed by the details of related work in Section 4. The experimental study with two data sets is given in Section 5. Section 6 presents conclusions and future work related to this problem.
Section snippets
Mathematical formulation
In this paper, we study the uncapacitated single allocation hub location problem (referred to as USAHLP), which is a location–allocation decision problem. A complete graph G=(V,E) is given, with a node set V=1,2,…,n where each node corresponds to origins, destinations and possible hub locations; and E is the set of edges between the nodes of the given network. The USAHLP was first formulated by O'Kelly [11] as a quadratic 0-1 optimization problem with linear constraints. The mixed integer
GA-formulation of the problem
A genetic algorithm (GA) is a search algorithm for finding the near-optimal solutions in large spaces, which is inspired from population genetics. The general idea was introduced by Holland [15] and genetic algorithms have been applied to a large set of problems in various fields in the literature. Two example sources for detailed information on GA are the books written by Goldberg [16] and Mitchell [17]. In this section, we present the details of our GA-based solution. The pseudocode of our
Related work
The uncapacitated single allocation hub location problem (USAHLP) has received less attention in the literature than the uncapacitated single allocation p-hub median problem (USApHMP), which has been extensively studied [1], [3], [4], [5], [6], [7], [10]. The most recent study for USAHLP is the GATS algorithm [9], which stands for “genetic algorithm and tabu search”. The results derived from the GATS algorithm matched the best solutions found in the literature so far. Therefore, we compared our
Experimental study
In this section, we present the results of computational experiments to evaluate the effectiveness of our GA-based method. We compared the solutions from our GA-based framework with the solutions from the GATS algorithm, and the best solutions presented in the literature so far. The two comparison metrics are the total cost given in Eq. (1), and the running time to derive the solution.
We coded the three algorithms (our GA-based solution, the GATS algorithm and the simulated annealing heuristic
Conclusions
In this paper, we applied the principles of genetic algorithms to solve the hub location problem. Our objective was to exploit the features of genetic algorithms in finding the number of hubs, the location of hubs, and the assignment of spokes to the hubs. A computational study based on several instances derived from CAB data set and AP data set was carried out to test the performance of our GA-based framework and the related work. The results clearly demonstrate that even for large problems
Haluk Topcuoglu is an Assistant Professor in the Computer Engineering Department at Marmara University, Istanbul, Turkey. He received the B.S. and M.S. degrees in Computer Engineering from Bogazici University, Istanbul. He received the Ph.D. degree in Computer Science from Syracuse University in 1999. His research interests are focused on task scheduling in parallel and distributed systems, evolutionary computation, parallel programming techniques and applications.
References (18)
A quadratic integer program for the location of interacting Hub facilities
European Journal of Operational Research
(1987)Lagrangian relaxation based approaches Hub-and-Spoke network design problem
European Journal of Operational Research
(1994)Integer programming formulations of discrete Hub location problems
European Journal of Operational Research
(1994)Heuristics for the p-Hub location problem
European Journal of Operational Research
(1991)- et al.
Tight linear programming relaxations of uncapacitated P-Hub median problems
European Journal of Operational Research
(1996) - et al.
Neural versus traditional approaches to the location of interacting Hub facilities
Location Science
(1996) Hub facility location with fixed costs
The Journal of the Regional Science Association International
(1992)- et al.
Efficient algorithms for the uncapacitated single allocation p-Hub median problem
Location Science
(1996) Solving large single allocation p-Hub problems with two or three Hubs
European Journal of Operational Research
(2001)
Cited by (0)
Haluk Topcuoglu is an Assistant Professor in the Computer Engineering Department at Marmara University, Istanbul, Turkey. He received the B.S. and M.S. degrees in Computer Engineering from Bogazici University, Istanbul. He received the Ph.D. degree in Computer Science from Syracuse University in 1999. His research interests are focused on task scheduling in parallel and distributed systems, evolutionary computation, parallel programming techniques and applications.
Fatma Corut received her B.S. degree in Computer Engineering Department at Marmara University in 2002. She is currently graduate student and research assistant in the same department. Her research interests include genetic algorithms and parallel programming.
Murat Ermis is an instructor in industrial Engineering Department at Turkish Air Force Academy. He received his M.S. degree and PhD in industrial Engineering from Middle East Technical University and Istanbul Technical University respectively. His main research interests are focused on mathematical modeling, metaheuristics and scheduling. He has published in international conferences and journals related with these areas.
Gulsah Yilmaz received her B.S. degree in Computer Engineering Department at Marmara University in 2002. She is currently a graduate student in the same department.