Designing Reliable Communication Networks with a Genetic Algorithm using a Repair Heuristic

Reichelt, Dirk ; Rothlauf, Franz ; Gmilkowsky, Peter

Vorschau

PDF
heinzl14.pdf - Veröffentlichte Version
Download (129kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/89
URN:	urn:nbn:de:bsz:180-madoc-893
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	2003
Titel einer Zeitschrift oder einer Reihe:	Working Papers in Business Administration and Information Systems
Band/Volume:	14/03
Ort der Veröffentlichung:	Mannheim
Sprache der Veröffentlichung:	Deutsch
Einrichtung:	Fakultät für Betriebswirtschaftslehre > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC-Schriftenreihe:	Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	Netzwerk , Algorithmus
Freie Schlagwörter (Deutsch):	Netzwerk , Algorithmus
Abstract:	This paper investigates GA approaches for solving the reliable communication network design problem. For solving this problem a graph with minimum cost must be found that satisfies a given network reliability constraint. To consider the additional reliability constraint different approaches are possible. We show that existing approaches using penalty functions can result in invalid solutions and are therefore not appropriate for solving this problem. To overcome these problems we present a repair heuristic, which is based on the number of spanning trees in a graph. This heuristic always generates a valid solution, which when compared to a greedy cheapest repair heuristic shows that the new approach finds better solutions with less computational effort.