Publication: IIE Transactions
Publication Date: 01-MAY-07
Delivery: Immediate Online Access
Author: Obreque, Carlos ; Marianov, Vladimir
Article Excerpt
1. Introduction
The Hierarchical Network Design Problem (HNDP), introduced by Current et al. (1986), consists of building a minimum cost bilevel network connecting all the nodes in a set. The network includes a main path or route (higher-level subnetwork), and a forest (lower-level subnetwork). The main path is a chain of primary (higher cost) arcs, connecting an origin node to a destination node, usually through other nodes. The forest, created from the secondary (lower cost) arcs, connects every node not on the main path, to a node on the path itself. All of the nodes must be spanned by this hierarchical network. The total cost of the network is the sum of all the costs of the primary and secondary arcs. Note that unlike the median path problem (Current et al., 1987), in which there are investment costs and operation or transportation costs, the HNDP includes only investment or building costs.
Whilst the HNDP can be seen as simply a particular case of the Two-Level Network Design Problem (TLNDP), good techniques that are applicable to the HNDP are of considerable interest since there are many practical examples of HNDP networks, particularly in long and narrow countries such as Chile, Japan, Norway and Finland whose populations can be linked using this type of network. Applications include telecommunication networks consisting of a high-capacity, optical fiber bus or backbone, and lower-cost "last mile" connections consisting of coaxial cable or twisted pair cable; transportation networks consisting of high-cost main highways and lower-cost secondary roads; some power transmission and distribution systems consisting of high-cost, high-voltage transmission lines and lower-cost distribution lines, and so on. In all these practical cases, the primary and secondary costs are proportional, because both costs are roughly a function of the length of the arcs. For the cases in which the proportionality assumption holds, we provide an efficient solution method.
The HNDP is NP-hard, even for the case in which the primary and secondary costs are proportional (Balakrishnan et al., 1994a; Chopra and Tsai, 2002), and it has been formulated and solved using a variety of techniques (note that we prove this NP-hardness in the Appendix). Current et al. (1986) formulate the HNDP as an integer programming model, in which the number of constraints that avoid the formation of subtours increases exponentially with the number of nodes in the network. They also propose a heuristic procedure based on computation of the k shortest paths between the origin and destination of the main path. Duin and Volgenant (1989) introduce some tests for identifying a priori arcs that are optimal, as well as identifying arcs and nodes that can not possibly appear in the solution of the HNDP, and Duin and Volgenant (1990) provide a method for finding good upper and lower bounds for the solution. Pirkul et al. (1991) propose a heuristic for the HNDP, based on a Lagrangean relaxation. Sancho (1995) proposes a procedure based on dynamic programming that finds a suboptimal solution of the HNDP. Pirkul and Nagarajan (1992) design a centralized computer network with concentrators in the nodes of the main path. This problem can be also seen as a particular case of more general problems: Duin and Volgenant (1991), Balakrishnan et al. (1994a, 1994b), Mirchandani (1996), Chopra and Tsai (2002) and Gouveia and Telhada (2001) address the TLNDP that consists of tree-connecting primary nodes, as well as a secondary forest. Sancho (1996) formulates a problem in which there are p primary paths and a secondary forest, and Current (1988) and Current and Pirkul (1991) consider an additional objective consisting of fixed costs of transshipment facilities on the nodes of the main path.
Due to the fact that the problem is NP-hard, there is considerable interest in finding methods to reduce its size before attempting to find a solution. The idea behind this preprocessing is to use whatever structural information is available about the problem, to determine which variables cannot possibly enter the solution, or which ones must belong to it (Koch and Martin, 1998; Chopra and Tsai, 2002). In particular, the HNDP possesses certain properties that make it possible to find arcs and nodes of the network that can be eliminated a priori, because they can not possibly belong to an optimal solution. Duin and Volgenant (1989) show that for the HNDP, all arcs in the secondary forest must belong to a Minimum Spanning Tree (MST) of the original problem, computed using secondary arcs. Thus, once an MST is found, all secondary arcs not belonging to the MST can be eliminated, and the number of variables reduced. They later find optimal or near-optimal solutions using a Lagrangean relaxation technique. The same property is shown and used by Balakrishnan et al. (1994b). A multicommodity flow model and a dual-based algorithm are used to solve the problem, not necessarily to optimality. The same type of reduction is again used in Mirchandani (1996). All these reductions make feasible the solution of larger instances of the HNDP, or the reduction of the solution times for any problem size.
Obreque and Marianov (2004) solve the HNDP with unknown origin and destination nodes to optimality, in a two-stage procedure that also uses the same MST property stated by Duin and Volgenant (1989), and a multicommodity flow formulation which, as opposed to previous formulations, does not need a combinatorial number of constraints.
In this paper, we propose procedures to reduce the size of the problem. The reduction is possible after finding bounds for the solution. Once the problem is reduced, we solve it to optimality, using either a multicommodity formulation with a polynomial number of variables and constraints, or an iterative, optimal procedure based on the model by Current et al. (1986).
Bounds could be found for reduction purposes by solving the integer programming formulation of the problem, and stopping the software as soon as a good feasible integer solution (bound) is found. However, this procedure is not efficient, because solving each linear relaxation of the problem takes a very long time. The Duin--Volgenant procedure (Duin and Volgenant, 1990) is also a good bounding method.
The reduction in the size of the problem in our test examples ranges from 62 to 99.3%, and in all the instances we tried, it is uniformly better than earlier procedures. In general, this reduction depends on the structure of the network, the location of the origin and destination nodes of the main path, and on how good is the best encountered upper bounding solution.
The remainder of this paper is organized as follows. Section 2 shows some fundamental results that make possible the reduction procedure, which is described in Section 3. Section 4 presents an algorithm for finding tighter bounds and Section 5 shows how to find the optimal solution to the reduced problem and outlines the full algorithm. Section 6 presents computational results on networks ranging from 100 nodes and 396 arcs, up to 600 nodes and 14 144 arcs. Conclusions are drawn in Section 7. A proof of the NP-hardness of the problem is provided in the Appendix.
2. Upper bounds and properties
We assume known origin (O) and destination (D) nodes of the main path. We also assume that the primary arc (i,j) costs [c.sub.ij] are proportional to the secondary costs [d.sub.ij]. In other words, [c.sub.ij] = [alpha][d.sub.ij] for all (i,j), where [alpha] > 1. Note that all the secondary arcs in the optimal forest of the Hierarchical Network (HN), must belong to a secondary MST of the same network (Duin and Volgenant, 1989). Due to this fact, we can reduce the solution time by first computing an MST, and then restricting the secondary forest arcs to belong to that MST. The problem is still NP-hard.
Recall that over any spanning tree, a unique path can be always found connecting two nodes of the network. Particularly, we can find a path S over the MST, connecting the origin and destination nodes of the HN. We call this path S, the path over the MST, or the MST-induced path. Conversely, for any O - D path T created by secondary arcs, a minimum-cost secondary spanning tree, necessarily including the path T, can always be built. We label this spanning tree induced by path T as MST(T). Note that MST(T) is not an MST, except if the path T coincides with a path over an MST. A solution to the HNDP can be obtained from MST(T), by simply replacing all arcs on the path T by primary arcs. Then
[c.sub.hn(T)] = [c.sub.mst(T)] - [c.sub.T] + c[p.sub.T],
where [c.sub.hn(T)] is the cost of the HN whose main path is T, [c.sub.mst(T)] is the cost of MST(T), [c.sub.T] is the sum of all secondary costs of the arcs belonging to the path T, and c[p.sub.T] is the sum of all primary costs of the arcs belonging to path T. Since c[p.sub.T] = [alpha][c.sub.T]:
[c.sub.hn(T)] = [c.sub.mst(T)] + (a - 1)[c.sub.T].
Recall that S is the MST-induced path, so it is always true that [c.sub.mst(S)] [less than or equal to] [c.sub.mst(T)], for all T, by definition of MST. After finding the MST, we can easily find a feasible solution for the HNDP (the...
NOTE: All illustrations and photos have been removed from this article.
More articles from
IIE Transactions
Locating capacitated facilities to maximize captured demand, 01-NOV-07
Erratum, 01-NOV-07
Sequencing with limited flexibility, 01-OCT-07
Looking for additional articles?
Click here to search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Click here to search our complete database of Industry & Market reports by text, subject, publication name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.
Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information. |
