Login | Register

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

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.

[thumbnail of MQ25999.pdf]
Preview
Text (application/pdf)
MQ25999.pdf
5MB

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
Item Type:Thesis (Masters)
Authors:Tomiuk, Daniel B
Pagination:xi, 148 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Sc.
Program:Administration
Department (as was):Faculty of Commerce and Administration
Date:1996
Thesis Supervisor(s):Bourjolly, Jean-M.
Identification Number:TK 5105.5 T66 1996
ID Code:260
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:10
Last Modified:20 Oct 2022 16:27
Related URLs:
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

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top