1. Introduction

As a result of technological advancements and regulatory changes, transportation and communication networks have evolved greatly over the past two decades. Hierarchical network configurations with hub facilities have proven to be flexible and cost-effective as is evidenced, for example, by their increased use in the transportation and telecommunication industries (Current, 1988; Pirkul and Shilling, 1998; Yoon et al, 1998). Such networks consist of hub-level and access-level components. The hub-level component connects the hub nodes, and the access-level component connects demand points to a node in the hub-level network. The access-level network may also contain direct connections between two demand points. Although hub networks often increase the total distance travelled by passengers/freight/communications versus direct link networks, they can reduce total costs by more efficient vehicle/network infrastructure utilization by better matching capacity to demand. As a consequence, air, less-than-truckload, intermodal freight and telecommunication networks have increased their use of hub networks (O'Kelly, 1986; Kuby and Gray, 1993; Daskin, 1995; Smith et al, 1996).

In this paper, we address a hub location and network design (HLND) problem that is found in many real-world applications such as transportation and telecommunication systems. The number and location of the hubs in such networks are obviously important to their efficiency and cost savings. When constructing such a network, three major cost components should be considered: the fixed cost of establishing a hub, and the fixed and variable costs of establishing and using an arc. The complex inter-relationships between the cost elements, together with the huge number of potential network configurations, make it extremely difficult to identify the optimal hub network design that considers all of these cost components.

Figure 1 shows an illustrative instance of an hierarchical network that is typically found in fibre optic transmission networks. In the fibre optic network, each user node represents a switching centre and hub nodes represent fibre optic transmission devices such as digital cross-connection systems (DCS) that connect a bundle of metallic cables with low-speed capacity to a single fibre with high-speed capability. The demand is defined as the number of DS3 (44.7 Mbps) channels between two user nodes for carrying the origin–destination (O–D) traffic. DS3 has been widely used as the basic unit in optical fibre transmission systems. The conversion process for O–D traffic measured in Erlang into the number of channels is given in Yoon et al (1998). Once an infrastructure network such as the conduit or duct system is given, the design problem is reduced to locating transmission devices and to installing cables in the infrastructure network.

Figure 1.

An example of fibre optic transmission network—a physical configuration.

Full figure and legend (17K)

Given the infrastructure network, the locations of the user and the candidate hub nodes, and the demand for each O–D pair of user nodes, we define a logical network where the links correspond to the shortest path between two nodes on the infrastructure network. The arcs on the logical network are undirected. The problem is to determine: (i) the number and locations of the hubs to be established, (ii) which hub-level and access-level arcs should be included and (iii) the routes used to satisfy O–D demands in such a way as to minimize the total network cost. Three cost elements are considered. These are the fixed costs of establishing the hubs, the fixed costs of including arcs in the network and the variable costs associated with traffic on the arcs needed to satisfy demand.

The problem is formulated and solved on the logical network. In addressing the problem, we have made several assumptions. (1) There is no limit on the flow capacity of an arc or on the number of user nodes assigned to a hub. (2) Each O–D demand can be served via hub nodes (ie via a hub path), or via a direct path between the origin and the destination nodes which does not pass through a hub node. (3) User nodes cannot serve as transshipment points. (4) There are no restrictions on the network topology and that a user node may be connected to multiple hub nodes.

The design of networks that include hub locations is an active area of research. Due to problems of solution complexity, most of this research has dealt with specific problems that consider only fixed cost components or a particular network topology such as a hub–spoke (O'Kelly, 1992; Jaillet et al, 1996; O'Kelly et al, 1996;), a tree (Kim and Tcha, 1992; Pirkul and Nagarajan, 1992; Lee et al, 1996), a ring (Lee et al, 1993), a full-meshed (Chung et al, 1992; Yoon et al, 2000) and a general mesh network with regional restrictions (Yoon et al, 1998). To our knowledge, there is no published research that addresses all three major network costs in a general network topology. Other related problems include location-allocation problems (Gavish and Pirkul, 1986; Aykin and Brown, 1992; Ghosh and Harche, 1993; Lee, 1995), location-routing problems (Leung et al, 1990; Srivastava and Benton, 1990; Aykin, 1995; Ball et al, 1995) and hierarchical network design problems (Current, 1988; Current and Pirkul, 1991).

The research most closely related to that presented here includes Melkote and Daskin (2001a, b) that studied an integrated model of facility location and network design problems. However, they did not consider the interconnection between established hubs that is an essential one in transportation and telecommunication networks. Yoon et al (1998) addressed the design problem of distributed fibre transport networks, where they integrated the above three decisions into a single framework of formulation. However, they assumed that the entire network could be partitioned into a few predetermined regions and that in each of the regions only one hub is to be opened. This decomposition makes the design problem much easier to solve, however, the total cost (ie, quality) of the resulting solution depends upon the initial partitioning. Yoon et al (2000) extended their previous work (Yoon et al, 1998). In Yoon et al (2000), with a logical fullmesh topology, they considered a design problem with no regional restrictions. In this paper, we are concerned with a general structure, in which the hub network is not restricted in its topology or any regional constraints. Figure 2 illustrates the problem addressed in this paper.

Figure 2.

An example of hub location and network design: (a) Given network configuration (b) A feasible network design.

Full figure and legend (155K)

The rest of this paper is organized as follows: The next section presents a mixed zero–one integer programming (IP) formulation of our problem, and shows how it is a generalization of some related problems. In Section 3, we describe our solution heuristic, a dual-based heuristic that incorporates as a subroutine, the extremely effective labelling dual ascent procedure developed by Balakrishnan et al (1989) for their uncapacitated network design problem. Some problem reduction methods are presented that improve the performance of this dual ascent procedure. Extensive computational results with randomly generated problems are reported in Section 4, and some concluding remarks and extensions of our design model are given in the last section.

2. Problem formulation

Consider an undirected network G=(N,E) where N and E represent a set of nodes and edges, respectively. N consists of the set of user nodes, I, and the set of candidate hub sites, J. We define the set of directed arcs, A, by associating each undirected arc in E with two directed arcs having opposite directions. In order to discriminate arc types, the undirected and directed arcs are represented as edge {ij} and arc (i,j), respectively, as was done in Balakrishnan et al (1989).

We formulate the problem as a variation of the multi-commodity flow problem because such a formulation facilitates the development of an effective solution method. Each O–D demand corresponds to an individual commodity k, and o(k) and d(k) denote its origin and destination nodes, respectively. Let K be the set of those commodities in G, and r_k be the demand of each commodity kK. To facilitate the problem formulation, we define the following:

z_j

a 0–1 variable that equals 1 if a hub is located at node j and 0 if not

y_ij

a 0–1 variable that equals 1 if edge {i,j} is included in the network and 0 if not

x_ij^k

a variable that denotes the fraction of demand of commodity k transported over arc (i,j)

g_j

the fixed cost incurred to establish a hub at candidate site jJ

f_ij

the fixed cost incurred to include edge {i,j}E, in the network

c_ij^k

the variable cost incurred if commodity k utilizes arc (i,j). Let c_ij be the variable cost per unit demand and c_ij^k is defined by c_ijr_k, and we assume c_ji^k=c_ij^k

Using this notation, we now present the multi-commodity flow formulation for our design problem.

s.t.

The objective function of (P) has three cost terms: the hub establishment costs, the fixed costs of establishing arcs and the variable costs associated with using the arcs to satisfy demand. The flow conservation constraints (2) enforce network connectivity for each commodity. The flow restrictions of (3) and (4) permit flow on an edge (in both directions) only if the edge is included in the network. Recall that the arc capacity is unlimited. Constraints (5) prohibit flow from a candidate hub unless it is opened.

To consider a non-hub path for a user node pair in (P), let _ij^k be the original variable cost associated with arc (i,j) for each O–D pair k (ie, commodity k). The variable cost on the arc connecting the user nodes is defined as follows:

This definition for variable costs prevents the transshipment of commodity flow through user nodes. Since the fixed cost of an edge is defined for all edges in E, a non-hub path incurs the fixed cost as well as the variable cost on the direct edge.

Formulation, (P), is flexible in that it is a generalization of several network design problems. For example, if every candidate hub node is fixed 'open' or 'closed', our model represents a fixed charged network design problem that can be easily transformed into various kinds of network design problems demonstrated in Magnanti and Wong (1984).

Model (P) can also be transformed into some network hub location problems having topological restrictions. For example, Campbell (1994) considered an uncapacitated hub location problem where each user node should be connected to at least one hub node and all O–D demand should be shipped via hub nodes. Campbell (1994) considered two kinds of costs: variable cost on an arc for each O–D demand and a fixed cost for establishing a hub. In our model, we can set f_ij=0 for all {i,j}E, and the hub establishment cost is left unchanged. Consider the following definition of the variable cost of each commodity k:

With these cost definitions, (P) is a formulation of uncapacitated hub location problem (Campbell, 1994).

Our model, (P), can also be extended to the hub–spoke network design problem widely used in airline networks. Set the hub fixed costs and the arc fixed costs to zero and define the variable cost for each commodity on the arc as follows:

where denotes the discount factor of variable costs on the hub arcs. The resulting model with these cost definitions denotes a special type of network design problem. If the number of hub nodes to be opened is restricted to not exceed p, we must add the following to (P): _iJz_ip. Consequently, formulation (P) can be extended to the hub–spoke network design problem with the re-defined costs and this additional constraint.

Another interesting hub network design problem requires a tree-star topology, in which the hub-level network has a tree structure and each user node must be connected to one of the hub nodes directly. This type of network has been used in the design of centralized communication networks (eg, Kim and Tcha, 1992; Pirkul and Nagarajan, 1992, Lee et al, 1996). To solve this problem using (P), select a user node i randomly and let it be the centre node. Define commodity k as a node pair between a user node kI and the center node, and set c_ij^k=0, iJ, jJ for all kI. These modifications to (P) result in the tree-star topology problem.

3. Solution method

The problem (P) is a mixed IP problem, which contains a facility location problem as well as a network design problem. When we relax constraint (5), the remaining problem is a NP-hard uncapacitated network design problem. Given the computational complexity of (P), we develop a heuristic algorithm to solve it.

Our heuristic solution method has three stages. The first, a dual ascent heuristic, solves a dual formulation of the LP relaxation of (P) to obtain a lower bound on its optimal solution. In general, a dual ascent heuristic cannot guarantee an optimal solution for a dual formulation of the LP relaxation, but it generates a good solution within a short computation time (Erlenkotter, 1978; Wong, 1984; Balakrishnan et al, 1989). The second stage uses information obtained from the dual solution to identify a feasible solution for the primal problem (P). The third stage also uses information gained from the dual solution to reduce the network by eliminating certain candidate arcs and hub nodes. The reduced network is then fed back into the dual ascent heuristic stage to see whether the lower bound can be improved. If there are no changes in the network, our heuristic is terminated.

Dual ascent procedures are not novel for problems similar to (P) (eg Wong, 1984; Balakrishnan et al, 1989; Crainic and Delorme, 1993; Balakrishnan et al, 1994; Yoon et al, 1998). The success of such procedures is dependent upon the primal problem under consideration and its dual formulation. Although (P) has a structure similar to the uncapacitated network design problem (Balakrishnan et al, 1989), it is complicated by constraint set (5).

Consider problem (D) which is the dual of the LP relaxation of (P), where all the 0–1 variables are relaxed into non-negative variables.

where

The dual variables v_i^k's correspond to constraint set (2), the w_ij^k's to constraint sets (3) and (4), and u_j^k's to constraint set (5) respectively. For brevity, s_ij^k, s_ij and s_j will be referred to as a commodity slack, arc slack and hub node slack, respectively. Since one member of constraint set (2) is redundant for each kK, we arbitrarily set the dual variables v_d(k)^k=0 for each commodity in K.

Let u, v and w be vectors of {u_j^k}, {v_i^k} and {w_ij^k} values, respectively. Given u and w, (D) can be decomposed into a subproblem for each commodity kK. The subproblem is to find the shortest path from o(k) to d(k) with arc lengths _ij^k's. Since the objective function of each subproblem, v_o(k)^k, denotes the length of the path, the main objective is how to increase v_o(k)^k for each kK by manipulating u and w effectively.

3.1. Stage 1: dual ascent procedure

Given u, (D) takes a form similar to that of the LP relaxed dual of an uncapacitated network design problem. This structural property suggests an iterative dual ascent-based approach to solve the problem. The efficiency of such an approach depends upon the method used to update the dual variable u during each iteration of the procedure. For a given u, we can apply the labelling dual ascent method (LDAM) developed by Balakrishnan et al (1989), which improves the dual objective value without violating dual feasibility by manipulating v and w. We further improve the dual objective value by increasing u iteratively in a way that does not violate dual feasibility. Our dual ascent heuristic procedure is based on the LDAM; however, it includes the above-mentioned adjustment of u. In this section, we focus on how u and w are updated and how the v_o(k)^k's are adjusted at each iteration.

For a commodity kK, we first identify directed arcs (i,j) whose w_ij^k and/or u_j^k values should be increased in order to increase the shortest path length v_o(k)^k. Let A(k) be a set of those directed arcs. Based upon A(k), separate the nodes in N into the two node sets N(k) and (k) such that o(k)N(k) and d(k)(k). A(k) can be divided into three types of arc sets: A₁(k)={(i,j)A(k): s_ij^k>0}, A₂(k)={(i,j)A(k): s_ij^k=0, s_ij>0} and A₃(k)={(i,j)A(k), iJ: s_ij^k=0, s_ij=0,s_i>0}.

Increasing w_ij^k and/or u_i^k in A(k) increases _ij^k, and hence v_o(k)^k. However, to increase v_o(k)^k, it is not necessary to increase all w_ij^k. For example, if an arc (i,j) is contained in A₁(k), the shortest path length may be increased by s_ij^k without increasing w_ij^k. However, for each arc (i,j)A₂(k), one must increase w_ij^k to increase v_o(k)^k. If one cannot increase w_ij^k by s_ij (ie, (i,j)A₃(k)) then, u_i^k is adjusted to increase _ij^k by using the hub node slack, s_i. Let ₁, ₂ and ₃ represent the maximum increase of _ij^k on the arcs in A₁(k), A₂(k) and A₃(k), respectively. ₁, ₂ and ₃ can be obtained as follows:

The increases of _ij^k are bounded by constraints (10), (11) and (12) to maintain dual feasibility; therefore, the maximum increase of _ij^k is determined by =min{₁,₂,₃}.

If w_ij^k and/or u_i^k are increased by on A(k), then the dual objective value v_o(k)^k, the shortest path length, will be increased by , and the corresponding slacks would be adjusted on the arcs in A(k). If there exists any arc (i,j) in A(k) having s_ij^k=s_ij=s_j=0, jJ, or s_ij^k=s_ij=0, , N(k) is adjusted by adding node j , and (k) and A(k) are updated. In this adjustment of slacks, special note should be taken on the hub nodes connected with arcs in A₃. Let HUB(k) be the set of those hub nodes:

Consider, for example, a hub node jHUB(k) where at least one of the incident arcs of node j is in the arc set A₃(k). We can increase u_j^k on the hub node j. From (10) and (11), one can see that an increase in u_j^k results in an increase to _ij^k for every arc incident to node j without adjusting w_ij^k. As a consequence, the w_ij^k value of any arc incident to a node in HUB(k) will not be changed, and therefore the value of s_ij, which may be used to increase w_ij^k' for some other commodity k' will not change.

In essence, our dual ascent heuristic is an iterative process to increase the shortest path length (v_o(k)^k) with arc lengths _ij^k by adjusting u and w for each commodity kK. This series of ascent operations is continued until the resulting dual objective value is not increased. The procedure is stated more formally as follows:

Dual ascent heuristic

Solutions generated by this dual ascent heuristic may provide useful information to identify a good feasible solution for (P). Close inspection of the dual ascent heuristic reveals that the dual solutions generated from this algorithm have some important properties. At every step in the algorithm, v_o(k)^k for kK represent the shortest path length from the origin to the destination node using the arc lengths _ij^k. For every commodity kK, all nodes in N(k) not only belong to at least one shortest path from the origin, but also are connected to the origin via shortest paths containing only zero-commodity slack arcs. Using these properties, we can utilize the dual solution as a starting point for constructing primal feasible solutions, in a manner similar to that proposed in (Balakrishnan et al, 1989; Tcha and Yoon, 1995; Yoon et al, 1998).

3.2. Stage 2: primal heuristic procedure

As noted in previous studies, the solution generated by the dual ascent heuristic can be used to construct a good solution for the primal problem (Balakrishnan et al, 1989; Yoon et al, 1998). This initial feasible solution may be improved by using an add-drop type heuristic. To accomplish this, we first construct a primal feasible solution satisfying the complementary slackness (CS) conditions for the LP relaxed problem of (P) as much as possible. When the dual ascent heuristic terminates, we can select the arcs having zero arc slack. To find a feasible design, we solve a shortest path problem using the variable costs as arc lengths for each commodity kK.

Let E^* be the set of arcs having zero arc slack (ie, s_ij=0) and J^* be the set of hub nodes having zero node slack (ie, s_j=0). Since an arc incident to a hub j can be used only if the hub j is established, we eliminate the arcs incident to the nodes in ^*=JJ^* from E^*. Consider G^*=(IJ^*,E^*). Let A_k^* be the set of arcs having zero commodity slacks on A^* obtained from E^* for all kK. We can find a shortest path for k using c_ij^k as arc lengths on G^*, and let A_k⁺ be the set of arcs on this shortest path. If any arc incident to a hub, say j, is contained in any A_k^{+, kK}, then hub j will be considered as an established one and be included in the set of established hubs J⁺J^*. We now define the network G⁺=(IJ⁺,E⁺), where E⁺={{i,j}E^*:(i,j)A_k⁺, or (j,i)A_k⁺, kK}.

The primal feasible solution is then given by the following:

This heuristic yields a feasible solution to the primal problem (P), but G⁺ may contain more arcs and hub nodes than necessary. A drop type heuristic is applied to remove unnecessary hubs and arcs from G⁺ one by one until no cost reduction can be made from such an arc or a node-drop (Billheimer and Gray, 1973; Balakrishnan et al, 1989). We apply the node-drop heuristic first, and then the arc-drop heuristic to remove unnecessary hub nodes and arcs from G⁺. The node(arc)-drop heuristic starts with an initial solution, and at each iteration drops a hub node(arc) from the current feasible solution to reduce the total cost. The procedure continues until no node(arc) can be dropped from the solution without increasing the total cost. The node(arc) drop heuristic can be described formally as follows:

Node/arc-drop heuristic

Step 0:

Set CANJ=J⁺. Let Z₀ be the objective value of the current best solution.

Step 1:

Select j' from CANJ. Set J₀=J^*-{j'}, CANJ=CANJ-{j'} and E₀=E^*-{{i,j'}, {i,j'}E^*}. Find a feasible solution on the new network G₀=(IJ₀,E₀) and the objective value Z_new. If Z_new<Z₀, then set Z₀=Z_new,j^*=j' and save the current solution as the best one.

Step 2:

If CANJ go to Step 1. If CANJ=, remove j^* and its incident arcs from J^* and E^*, respectively, and find the best solution on G^*=(IJ^*,E^*).

Step 3:

Set CANE=E⁺. Let Z₀ be the objective value of the current best solution.

Step 4:

Select {i,j}' from CANE, and E₀=E^*-{i,j}'. Find a feasible solution on the new network G₀=(IJ^*,E₀) and the objective value Z_new. If Z_new<Z₀, then set Z₀=Z_new, {i,j}^*={ij}' and save the current solution as the best one.

Step 5:

If CANE, go to Step 4. If CANE= and there are some improvement in the objective value, remove {i,j}^* from E^*. Find the best solution on G^*=(IJ^*,E^*) and go to Step 3 with the current best solution. If CANE=, CANJ= and there are no improvement in the objective value, then stop the drop heuristic. Otherwise, go to Step 0 with the current best solution.

3.3. Stage 3: problem reduction procedure

In this subsection, we explain a node exclusion test and an arc exclusion test that follow from the dual ascent heuristic. These tests reduce the original problem by eliminating potential hub locations and arcs from the original network.

From the dual solution generated by the dual ascent heuristic, we can obtain a lower bound and a primal feasible solution to (P). In addition to these advantages, dual solutions enable us to identify arcs and candidate hubs of the given network that must be included or excluded from the optimal solution. Consider the set of hub nodes having positive node slack that we denote by . Suppose a hub node j must be included (ie, have a hub) in the optimal solution. An additional constraint z_j=1 is added to (P), and we define _j as the dual variable corresponding to this constraint. The dual constraint corresponding to hub node j will be _kK u_j^k+_jg_j, and the new dual objective value will include the variable _js_j represents the node slack in constraint (12); therefore, setting _j=s_j gives a dual feasible solution to this new problem. Let Z_D denote the dual objective value of the original problem (ie, z_j is not fixed to 1) and Z_P denote the objective value of the current best fseasible solution. In this instance, the dual objective value of the new problem should be at least Z_D+s_j. Therefore, if Z_D+s_j is greater than Z_P, it means the additional constraint makes the problem infeasible, and hub j can be excluded from the original network. This is the node exclusion test.

The arc exclusion test is similar to the node exclusion test. Suppose an arc {i,j} having a positive arc slack should be included in the optimal solution. This assumption can be enforced by an additional constraint being added to (P): y_ij=1. Let _ij be the dual variable corresponding to this constraint. The dual constraint corresponding to the arc {i,j} will be _kK(w_ij^k+w_ji^k)+_ijf_ij. Since s_ij is the arc slack in constraint (11), setting _ij=s_ij gives a dual feasible solution to the new problem. The dual objective value of the new problem is greater than Z_D by at least s_ij. If Z_D+s_ij is greater than Z_P, the additional constraint makes the problem infeasible, and arc {i,j} can be excluded from the given network. This arc exclusion procedure is similar to that proposed in Balakrishnan et al (1989). With the node and arc exclusion tests, we can reduce the given network and then re-apply the dual ascent heuristic to the resulting network.

The worst case complexity of the overall heuristic approach is O(|N||K||E|⁴ or O(E⁴) where N and E represent the nodes and edges of the logical network, and K represents the number of commodities. This is determined by the complexity of the three stages that compose the heuristic. Stage 1 (the dual ascent heuristic) terminates after O(|N||K|) iterations. Stage 2 (the primal heuristic procedure including the drop heuristic) has a computational complexity O(|N||K||E|²) in the worst case (ie, only one arc or node drop occurs per iteration.) Stage 3 (problem reduction) requires O(|I|²+|E|²) iterations in the worst case where I is the set of user nodes.

4. Computational results

The solution procedure in the preceding section was implemented in Borland C++, and a series of computational experiments were performed on a Workstation HP 9000/715 (32 MHz PA_RISC processor running HP-UX operating system) to evaluate its efficiency. The main components of the program are the following three subroutines: the dual ascent heuristic for increasing the dual objective value, an initial primal construction and drop type heuristic for constructing a primal feasible network, and a node and arc exclusion tests for improving primal and dual solutions. To evaluate the quality of heuristic solutions, we tried to find optimal solutions of (P) using CPLEX (1998).

The test problems were generated randomly, but systematically, to obtain problems with differing levels of cost trade-offs. We first randomly located the prespecified number of candidate hub and user nodes on a (100100) grid in the plane. These randomly selected nodes were connected by a randomly generated spanning tree. Additional edges were added randomly until the pre-specified number of edges was obtained. During this process, we made certain that each user node was connected to at least one hub node with an arc. This was done to guarantee that a feasible solution existed.

To define various cost data, we first set a base cost, c_ij, on each arc {i,j}, which was the Euclidean distance between nodes i and j on the above plane. The fixed cost of arc {i,j} was obtained by multiplying the base cost by the scaling factor f that was the same for all arcs in a particular network. The variable cost of each commodity, k, on arc (i,j) was then obtained by multiplying the base cost, c_ij, by the demand U_k. Each demand U_k,kK was randomly selected from an interval (5.0, 20.0). The hub establishment costs, g_j, were chosen randomly from an interval (a,b). Where a ranged from 1000 to 10 000 and b ranged from 3000 to 20 000.

We solved a total of 81 test problems. In Table 1, the problems are divided into three different groups based on problem size, that is, the number of user and hub nodes, arcs and commodities. Each group is divided into three subsets based on the range of hub establishment costs, (a,b), and further split into three smaller subsets having different scaling factors f. Three randomly generated problems were tested for each subset. Table 1 presents a summary of the test problems that range from 15 nodes (hub+user), 50 arcs and 45 commodities to 35 nodes, 180 arcs and 300 commodities.

Table 1 - Computational results for heuristic algorithm.

Full table

Columns 6 and 7 of Table 1 report average solution time and the average percentage of total solution time required by the dual ascent heuristic, respectively, for the various problem subsets. Average CPU times vary from a little over a second for the smaller problems to over 800 s for some of the larger problem sets. As the last column demonstrates, the dual ascent component of the overall solution heuristic is very fast (ie, less than 10% of total solution time for the larger problems.) For the larger problems, most of the solution time was required to execute the primal heuristic (Stage 2).

In networks where the variable costs on the arcs are relatively low, the resulting network topology resembles a tree configuration. On the other hand, for higher variable costs on the arcs, the solutions are networks with a mesh topology. As one would expect, the number of direct, or non-hub, connections increase as the hub fixed costs increase. The percentage gaps between the best upper and lower bounds (duality gaps) for the various problem subsets are given in column 5 of Table 1. The primal heuristic solution and the dual ascent solution are used as the upper and the lower bounds, respectively. For the smaller two problem sets the gap averages are generally under 3% for 13 of 18 subcategories, and only one subcategory has an average above 5% at 6.6%. Gap averages for the largest problem set range from 10.1 to 15.1%. Average gaps of up to 15% are not uncommon in large hub location problems (eg, Yoon et al, 1998).

We attempted to solve all the test problems in Table 1 optimally by using CPLEX, but we could not get the optimal solutions within 1 h of computation time for the large sized networks. Table 2 shows the comparison between the heuristic and the optimal solutions for 18 test problems, just one problem for each subset of the small sized networks. From Table 2, one can see that the heuristic procedure identified the optimal solution in 13 of the 18 problems solved optimally with CPLEX. In the five problems that the heuristic did not identify the optimal solution, it was never as much as 1example, heuristic solution times ranged from 1.2 to 8.03 s with all but three problems requiring less than 5 s. Optimal solution times ranged from 6.74 to 99.72 s with all but five requiring more than 40 s. These computational results indicate that our heuristic generates good feasible solutions in reasonable time.

Table 2 - Computational comparison of optimal and heuristic solutions.

Full table

Finally, the duality gaps increase as the problem size and/or the arc fixed costs increase, and tend to decrease as the hub fixed costs, g_j increase. Given that hub fixed costs are relatively large in many real-world transportation and communication networks; our computational experience suggests that the heuristic solution procedure proposed in this paper will yield good solutions for such problems.

5. Conclusions

Hub topologies are frequently used in the design of transportation and communication networks because of their potential to reduce cost through economies of scale and/or more efficient use of technology on certain arcs of the network. Owing to the complexity of the design problem, previous researchers have decomposed the problem into location and network design subproblems, exogenously constrained the network topology, and/or omitted certain costs.

In this paper, we have formulated a direct approach to hub network design that includes the fixed costs of establishing the hubs and transmission/transportation arcs, as well as the variable costs of traversing these arcs. The problem is modelled as a variation of the multi-commodity network flow problem. As such, our heuristic solution procedure could incorporate the labelling dual ascent method developed by Balakrishnan et al (1989) to generate a lower bound on the optimal solution. The resulting dual solution is then used to generate a feasible solution to the primal problem. The third stage of the overall heuristic uses the information from the dual solution to eliminate nodes and arcs from the network. The dual ascent method is then applied to this reduced network to see if the dual solution can be improved.

The heuristic was tested on 81 randomly generated networks of varying sizes and cost structures. The results indicate that the approach generates good-quality solutions in reasonable computational time. Although presented with the framework of the design of fibre optic networks, the formulation and solution methodology proposed may be applied to transportation networks that employ hubs such as, air or less-than-truck load networks.

References

1. Aykin T (1995). The hub location and routing problem. Eur J Opl Res 83: 200–219. | Article |
2. Aykin T and Brown GF (1992). Interacting new facilities and location-allocation problems. Transport Sci 26: 212–222. | ISI |
3. Balakrishnan A, Magnanti TL and Wong RT (1989). A dual-ascent procedure for large-scale uncapacitated network design. Opns Res 37: 716–740.
4. Balakrishnan A, Magnanti TL and Mirchandani P (1994). A dual-based algorithm for multi-level network design. Mngt Sci 40: 567–581.
5. Ball MO, Magnanti TL, Monma CL and Nemhauser GL(1995) (eds). Handbooks in Operations Research and Management Science Vol. 7: Network Models. North-Holland: New York.
6. Billheimer J and Gray P (1973). Network design with fixed and variable cost elements. Transport. Sci. 7: 49–74.
7. Campbell JF (1994). Integer programming formulations of discrete hub location problems. Eur J Opnl Res 72: 387–405. | Article |
8. Chung SH, Myung YS and Tcha DW (1992). Optimal design of a distributed network with a two-level hierarchical structure. Eur J Opl Res 62: 105–115. | Article |
9. CPLEX Optimization 6.0, ILOG Inc.(1998)..
10. Crainic TG and Delorme L (1993). Dual-ascent procedures for multi-commodity location-allocation problems with balancing requirements. Transport Sci 27: 90–101. | ISI |
11. Current JR (1988). The design of a hierarchical transportation network with transshipment facilities. Transport Sci 22: 270–277. | ISI |
12. Current JR and Pirkul H (1991). The hierarchical network design problem with transshipment facilities. Eur J Opl Res 52: 338–347. | Article |
13. Daskin MS (1995). Network and Discrete Location: Models, Algorithms and Applications. John Wiley and Sons, Inc: New York.
14. Erlenkotter D (1978). A dual-based procedure for uncapacitated facility location. Opns Res 26: 992–1009.
15. Gavish B (1992). Topological design of computer communication networks—The overall design problem. Eur J Opl Res 58: 149–172. | Article |
16. Gavish B and Pirkul H (1986). Computer and database location in distributed computer systems. IEEE Trans Comput 35: 583–590. | Article | ISI |
17. Ghosh A and Harche F (1993). Location-allocation models in the private sector. Location Sci 1: 81–106.
18. Jaillet P, Song G and Yu G (1996). Airline network design and hub location problems. Location Sci 4: 195–212. | Article |
19. Kim JG and Tcha DW (1992). Optimal design of a two-level hierarchical network with tree-star configuration. Comput Indust Eng 22: 273–281. | Article | ISI |
20. Kuby MJ and Gray RG (1993). The hub network design problem with stopovers and feeders: the case of Federal Express. Transport Res 27A: 1–12.
21. Lee CY (1995). Application of cross decomposition algorithm to a location and allocation problem in distributed systems. Comput Commun 18: 367–377. | Article | ISI |
22. Lee CH, Ro HB and Tcha DW (1993). Topological design of a two-level network with ring-star configuration. Comput Opns Res 20: 625–637. | Article |
23. Lee YH, Lim BH and Park JS (1996). A hub location problem in designing digital data service networks: Lagrangean relaxation approach. Location Sci 4: 185–194. | Article |
24. Leung JMY, Magnanti TL and Singhal V (1990). Routing in point-to-point delivery systems: formulations and solution heuristics. Transport Sci 24: 245–260. | ISI |
25. Magnanti TL and Wong RT (1984). Network design and transportation planning: models and algorithms. Transport Sci 18: 1–55. | ISI |
26. Melkote S and Daskin MS (2001a). An integrated model of facility location and transportation network design. Transport Res Part A 35: 515–538. | Article | ISI |
27. Melkote S and Daskin MS (2001b). Capacitated facility location/network design problems. Eur J Opl Res 129: 481–495. | Article |
28. O'Kelly ME (1986). The location of interacting hub facilities. Transport Sci 20: 92–106.
29. O'Kelly ME (1992). Hub facility location with fixed costs. Papers Regional Sci 71: 293–306. | Article |
30. O'Kelly ME, Bryan D, Skorin-Kapov D and Skorin-Kapov J (1996). Hub network design with single and multiple allocation: a computational study. Location Sci 4: 125–138. | Article |
31. Pirkul H and Nagarajan V (1992). Locating concentrators in centralized computer networks. Ann Opns Res 36: 225–246.
32. Pirkul H and Shilling DA (1998). An efficient procedure for designing single allocation hub and spoke systems. Mngt Sci 44: 235–242.
33. Smith K, Krishnamoorthy M and Palaniswami M (1996). On the location of interacting hub facilities: neural versus traditional approaches. Location Sci 4: 125–138. | Article |
34. Srivastava R and Benton WC (1990). The location-routing problem: considerations in physical distribution system design. Comput Opns Res 17: 427–435. | Article |
35. Tcha DW and Yoon MG (1995). Conduit and cable installation for a centralized network with logical star-star topology. IEEE Trans Commun 45: 958–967. | Article |
36. Wong RT (1984). A dual ascent approach for Steiner tree problem on a directed graph. Math Programm 28: 271–287. | Article | ISI |
37. Yoon MG, Beak YH and Tcha DW (1998). Optimal design of a distributed fiber transport network with hubbing topology. Eur J Opl Res 104: 510–520. | Article |
38. Yoon MG, Beak YH and Tcha DW (2000). Optimal design model for a distributed hierarchical network with fixed-charged facilities. Int J Mngt Sci 6: 29–45.