Abstract
We consider the problem of determining the optimal access topology to service based networks. The problem is formulated as a concentrator location problem with a discontinuous piece wise linear objective function that depends on the traffic of the nodes that are homed to the concentrator. Five heuristics are developed to solve the problem and are compared on an extensive set of examples. Based on this comparison a combination heuristic utilizing a Lagrangian relaxation and swap drop add approach was found to give the best solution in the minimal time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows (Prentice-Hall, New York, NJ, 1993).
U. Akinc, Multi-activity facility design and location problems, Management Science 31 (1985) 275-283.
G. Cornuejols, M. Fisher and G.L. Nemhauser, On the uncapacitated location problem, Annals of Discrete Mathematics 1 (1977) 163-177.
G. Cornuejols, M. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Management Science 23(8) (1997) 789-810.
G. Cornuejols and J.M. Thizy, Some facets on the simple plant location polytope, Mathematical Programming 23(1) (1982) 50-74.
G. Cornuejols, R. Sridharan and J.M. Thizy, A comparison of heuristics and relaxations for the capacitated plant location problem, European Journal of Operational Research 50 (1991) 280-297.
M. Fisher, The Lagrangian relaxation for solving integer programming problems, Management Science 27 (1981).
M. Fisher, An application oriented guide to Lagrangian relaxation, Interfaces 15 (1985).
M.J. Fischer, An overview of algorithms for the topological design of large telecommunications access areas, Technical Report No. 8, Center for Computational Statistics and Probability, George Mason University (December 1986).
M. Fischer, B. Roth, D. Garbin, F. Ferrante and H. Hsiung, On the design and analysis of telecommunication networks, The Telecommunication Review, MITRE (1995).
M.J. Fischer, G.W. Swinsky, D.P. Garland and L.E. Stanfel, A methodology for designing large private line transmission networks with multiple facilities, Telecommunication Systems 1 (1993) 243-261.
K. Holmberg, Solving the staircase cost facility location problem with decomposition and piecewise linearization, European Journal of Operational Research 75 (1994) 41-61.
K. Holmberg and J. Ling, A Lagrangean heuristic for the facility location problem with staircase costs, European Journal of Operational Research 97 (1997) 63-74.
C.Y. Lee, An algorithm for the design of multitype concentrator networks, Journal of the Operational Research Society 44 (1993) 471-482.
C. Lee, A cross decomposition algorithm for a multiproduct-multitype facility location problem, Computers and Operations Research 20 (1993) 527-540.
C. Lee, An optimal algorithm for the multiproduct capacitated facility location problem with a choice of facility type, Computers and Operations Research 18 (1991) 167-182.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations (Wiley, New York, 1990).
H. Pirkul, Efficient algorithms for the capacitated concentrator location problem, Computers and Operations Research 14 (1987) 197-208.
J. Soltys, M. Fischer and B. Roth, FTS2000 access optimization, in: Proc. of the 5th Internat. Conf. on Telecommunication Systems (March 1997).
C. Yoo and D. Tcha, A cross decomposition procedure for the facility location problem with a choice of facility type, Computers and Industrial Engineering 10 (1986) 283-290.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Soltys, J., Fischer, M. & Roth, B. Optimizing access to service based networks. Telecommunication Systems 10, 269–290 (1998). https://doi.org/10.1023/A:1019179303184
Issue Date:
DOI: https://doi.org/10.1023/A:1019179303184