Algoritmi za optimalni smještaj čvorova u telekomunikacijskoj mreži : magistarski rad - Mikac, Domagoj; Kos, Mladen (Zagreb : D. Mikac ; Fakultet elektrotehnike i računarstva, 2004)
Optimalni smještaj opreme u telekomunikacijskoj mreži predstavlja jedan je od faktora koji utječe na konačnu cijenu i performanse planirane mreže. U radu su opisani različiti modeli za optimalni smještaj opreme koji se razlikuju ovisno o funkciji cilja. Općenito, postoje problemi s obzirom na maksimalnu udaljenost (cijenu) i problemi s obzirom na prosječnu udaljenost (cijenu). Kod prve skupine problema potrebno je odrediti lokacije čvorova tako da maksimalna udaljenost korisnika do najbližeg čvora ne prelazi neku definiranu vrijednost. Ukoliko je korisnik unutar dozvoljene udaljenosti smatra se da je poslužen (pokriven), a ukoliko je izvan dozvoljene udaljenosti smatra se nepokriven. Druga skupina problema razmatra prosječnu udaljenost korisnika do najbližeg čvora. Kod ove klase problema čvorove (poslužitelje) potrebno je razmjestiti tako da je prosječna udaljenost korisnika do poslužitelja minimalna.
U ovom magistarskom radu prvo su opisani različiti matematički modeli kojima se opisuju problemi optimalnog smještaja nakon čega su opisani algoritmi rješavanja pojedinih problema. U četvrtom poglavlju opisani algoritmi testirani su na test primjerima generiranih na računalu, a u petom poglavlju isti se algoritmi testiraju na stvarnoj mreži prema podacima jednog telekom operatora.
U sklopu magistarskog rada razvijen je i programski alat u kojem su implementirani svi opisani algoritmi. Svi rezultati prikazani u radu dobiveni su pomoću razvijenog alata.
Ključne riječi: optimalni smještaj čvorova, optimizacija, GRASP, Lagrangeova relaksacija, prekrivanje skupa, medijan, planiranje mreže
Optimal location of telecommunication equipment or service points can play an important role in network planning procedures. Number of required equipment and its positions influences overall price and performance of the network. Regarding of the application, equipment must be placed in such manner that the maximal distance or the average distance from the customer to the serving point is minimized. When the maximal distance is an objective function no customer can be further then allowed from the service point. Due to this limitation some of the customers might not be served (those who are to far from the service point). On the other side, when the average distance is an objective function, then all the customers will be served, but the service points are located in such manner that the average (or overall) distance from the customer to the service point is minimized. Both approaches have an application in real networks.
In this thesis, first the mathematical models for different location models are discussed. In third chapter methods for solving different location problems are described. In fourth chapter described methods are tested on computer generated examples. In fifth chapter a real case scenario is described with actual data from one Croatian future telecom operator.
As a part of the thesis accompanying software tool is developed. This tool contains all described methods for solving facility location problems and can be used for real case network planning.
Key words: facility location, optimization, GRASP, Lagrange relaxation, set covering, median, network planning
Bibliografija str. 95-96.