Title:

# Using simulated annealing to minimize the cost of multi-point lines in centralized computer networks : implementation for Windows 3.1

Tomiuk, Daniel B (1996) Using simulated annealing to minimize the cost of multi-point lines in centralized computer networks : implementation for Windows 3.1. Masters thesis, Concordia University.

 Preview
PDF
4Mb

## Abstract

We focus on a problem encountered when designing centralized telecommunications networks, namely, the terminal layout problem. Given each terminal's geographical location, the problem consists in creating multipoint lines rooted at a central site (typically a concentrator) in order to save on connection costs. Well-known multipoint line topologies are the tree, the bus, and the loop. When terminals are assigned a weight representing the average traffic amount exchanged with the central site and lines are constrained by the amount of traffic they can carry, the tree-topology problem is referred to as the Capacitated Minimum Spanning Tree (CMST) problem. Algorithms that generate solutions for CMST problems create tree structured networks but can also be used to produce bus structured networks by imposing additional constraints. As for the loop topology, the problem is analogous to the Vehicle Routing problem found in Operation Research. These problems are NP-Complete. Finding an optimal solution in an acceptable amount of time is, therefore, unlikely due to the exponential growth in complexity relative to problem size. Nevertheless, techniques yielding exact solutions have been developed but are limited to networks of no more than, say, 50 terminals. Alternatively, heuristics solve the problem to near-optimality with acceptable computational effort. We designed applications with graphical output capabilities for Windows 3.1$\sp{\rm TM}$ using simulated annealing (SA) in an attempt to improve upon well-known heuristic solutions. Our SA programs are presented along with computational results on data sets containing up to 250 terminals. Results are evaluated and compared with those obtained with other heuristic methods.

Divisions: Concordia University > John Molson School of Business Thesis (Masters) Tomiuk, Daniel B xi, 148 leaves : ill. ; 29 cm. Concordia University Theses (M.Sc.Admin.) Faculty of Commerce and Administration 1996 Bourjolly, Jean-M. 260 Concordia University Libraries 27 Aug 2009 13:10 08 Dec 2010 10:13 http://clues.concordia.ca/search/c?SEARC...
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page