Name
Abstract | ||
|---|---|---|
A distribution network problem arises in a lower level ofan hierarchical modeling approach for telecommunication networkplanning. This paper describes a model and proposes a lagrangianheuristic for designing a distribution network. Our model is acomplex extension of a capacitated single commodity network designproblem. We are given a network containing a set of sources withmaximum available supply, a set of sinks with required demands, and aset of transshipment points. We need to install adequate capacitieson the arcs to route the required flow to each sink, that may be anintermediate or a terminal node of an arborescence. Capacity can onlybe installed in discrete levels, i.e., cables are available only incertain standard capacities. Economies of scale induce the use ofa unique higher capacity cable instead of an equivalent set of lowercapacity cables to cover the flow requirements of any link. A pathfrom a source to a terminal node requires a lower flow in the measurethat we are closer to the terminal node, since many nodes in the pathmay be intermediate sinks. On the other hand, the reduction of cablecapacity levels across any path is inhibited by splicing costs. Theobjective is to minimize the total cost of the network, given by thesum of the arc capacity (cables) costs plus the splicing costs alongthe nodes. In addition to the limited supply and the node demandrequirements, the model incorporates constraints on the number ofcables installed on each edge and the maximum number of splices ateach node. The model is a NP-hard combinatorial optimization problembecause it is an extension of the Steiner problem in graphs.Moreover, the discrete levels of cable capacity and the need toconsider splicing costs increase the complexity of the problem. Weinclude some computational results of the lagrangian heuristics thatworks well in the practice of computer aided distribution networkdesign. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1023/A:1009669927855 | J. Heuristics |
Keywords | DocType | Volume |
distribution network,network design,lagrangian heuristics | Journal | 6 |
Issue | ISSN | Citations |
1 | 1572-9397 | 7 |
PageRank | References | Authors |
0.55 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Geraldo R. Mateus | 1 | 134 | 13.00 |
| H. P. Luna | 2 | 55 | 7.39 |
| Adriana B. Sirihal | 3 | 7 | 0.55 |