Solving the uncapacitated hub location problem using genetic algorithms

https://doi.org/10.1016/j.cor.2003.09.008Get rights and content

Abstract

Hub location problems are widely studied in the area of location theory, where they involve locating the hub facilities and designing the hub networks. In this paper, we present a new and robust solution based on a genetic search framework for the uncapacitated single allocation hub location problem (USAHLP). To present its effectiveness, we compare the solutions of our GA-based method with the best solutions presented in the literature by considering various problem sizes of the CAB data set and the AP data set. The experimental work demonstrates that even for larger problems the results of our method significantly surpass those of the related work with respect to both solution quality and the CPU time to obtain a solution. Specifically, the results from our method match the optimal solutions found in the literature for all test cases generated from the CAB data set with significantly less running time than the related work. For the AP data set, our solutions match the best solutions of the reference study with an average of 8 times less running time than the reference study. Its performance, robustness and substantially low computational effort justify the potential of our method for solving larger problem sizes.

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)

There are more references available in the full text version of this article.

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.

View full text