Abstract
This paper presents a real-life problem of designing a teleprocessing communication network. This is a NP-hard combinatorial optimization problem. An approach based on simulated annealing has been developed and implemented. It exploits the nature of the problem and includes tabu search in the neighbour generation strategy. Several test examples are reported, and the approach yields better results than known algorithms based on graph theory and mathematical programming. Finally, a case study from Denmark is briefly presented.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Andersen, K.: Applied Simulated Annealing. IMSOR, Technical University of Denmark. Master Thesis 1990. 180 p. (In Danish)
Connolly, D.T.: An Improved Annealing Scheme for the QAP, European Journal of Operational Research, 46 (1990), pp. 43–100.
Esau, L. and Williams, K.: On Teleprocessing System Design. IBM System Journal, Vol. 5 (1966): 3, 142–147.
Evans, J.R.: Structural Analysis of Local Search Heuristics in Combinatorial Optimization, Computers and Operations Research, 14, 1987, pp. 465–477.
Gavish, B.: Topological Design of Centralized Computer Networks–Formulations and Algorithms. Networks, vol. 12 (1982) 355–377.
Glover, F. and Greenberg, H.J.: New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence. European Journal of Operational Research, Vol. 39 (1989) 119–130.
Hajek, B.: Cooling Schedules for Optimal Annealing, Mathematics of Operations Research, 13, 1988, pp. 311–329.
Johnson, et al: Optimization by Simulated Annealing- An Experimental Evaluation, Part I, Graph Partitioning, Operations Research, 37, 1989, pp. 865–892.
Kershenbaum, A. and Boorstyn, R.R..: Centralized Teleprocessing Network Design. Networks, Vol. 13 (1983) 279–293.
Kirkpatrick, S. et al: Optimization by Simulated Annealing, Science 220 (1983), pp. 671–680.
Laarhoven, van P.T.M., and Aarts, E.M.L.: Simulated Annealing: Theory and Applications, Reidel, 1987.
Lundby, L.: Design of Centralized Data Communication Network. IMSOR, Technical University of Denmark 1985. 104 pp (Master Thesis, in Danish).
Lundy, M., and Mess, A.: Convergence of An Annealing Algorithm, Mathematical Programming, 34 (1986), pp. 111–124.
Pilegaard Hansen, M.: Simulation of a Teleprocessing Network by Simulated Annealing. IMSOR. Technical University of Denmark, 1989. ( Student report, in Danish)
Prim, R.: Shortest Connection Networks and some Generalizations. Bell system Technical Journal, Vol. 36 (1957) 1389–1401.
Sharma, R.L.: Network Topology Optimization. Van Nostrand Reinhold, New York 1990. 349 pp.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Andersen, K., Vidal, R.V.V., Iversen, V.B. (1993). Design of a Teleprocessing Communication Network Using Simulated Annealing. In: Vidal, R.V.V. (eds) Applied Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, vol 396. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-46787-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-46787-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56229-0
Online ISBN: 978-3-642-46787-5
eBook Packages: Springer Book Archive