1. Racionalizacija zbirnih in transportnih poti komunalnih vozil s pomočjo optimizacijskih metod : magistrsko deloDarko Bečaj, 2008, magistrsko delo Ključne besede: tehnologija zbiranja odpadkov, transportne poti, komunalna vozila, zbirna območja, eng, waste collection, routing, transferring goods, process of gathering
Objavljeno: 05.01.2009; Ogledov: 3433; Prenosov: 485
 Polno besedilo (5,17 MB) |
2. |
3. UPORABA HIBRIDNIH METAHEVRISTIK PRI REŠEVANJU OPTIMIZACIJSKIH PROBLEMOVIgor Pesek, 2009, doktorska disertacija Opis: V doktorski disertaciji sta predstavljena dva algoritma za reševanje težkih kombinatoričnih problemov. Prvi problem se imenuje Problem razvrščanja poslov z omejitvami virov, za katerega smo razvili algoritem z združevanjem konstrukcijske hevristike RAR z algoritmom vzpenjanja na hrib. Drugi problem, ki ga v obravnavamo, je problem načrtovanja usmerjenih omrežij z minimalno ceno in enotnimi vsi-do-vseh komunikacijskimi zahtevami med vozlišči. Za drug algoritem smo razvili algoritem, ki združuje metahevristiko izbiranja s pragom, lokalno iskanje in metodo za obdelavo podatkov. Oba algoritma sta med najboljšimi v primerjalnih testih.
Ključne besede: hevristični algoritem, lokalno iskanje, metahevristike, optimizacijske metode, NP-težki problemi, razvrščanje poslov z omejitvami virov, načrtovanje usmerjenih omrežij
Objavljeno: 07.04.2009; Ogledov: 2460; Prenosov: 170
Polno besedilo (1,28 MB) |
4. PROBLEM KITAJSKEGA POŠTARJA S PRIORITETNIMI VOZLIŠČITomaž Kramberger, 2010, doktorska disertacija Opis: V doktorski disertaciji z naslovom Problem kitajskega poštarja s prioritetnimi vozlišči je preučevana posplošitev problema kitajskega poštarja, v kateri je podmnožica vozlišč utežena in vrstni red obiska vozlišč vpliva na vrednost namenske funkcije. Preučevan problem je dokazano NP-težek. V disertaciji sta predstavljeni in preučevani dve konstrukcijski hevristiki. Za eno izmed njih je dokazano, da ob določenih pogojih vrne optimalne rešitve. Hevristiki sta implementirani in testirani na več razredih naključno tvorjenih instanc.
Ključne besede: problem kitajskega poštarja, problemi usmerjanja, Eulerjev graf, prioritetna vozlišča, modificiran algoritem Dijkstre, modificiran Kruskalov algoritem
Objavljeno: 27.05.2010; Ogledov: 2624; Prenosov: 266
Polno besedilo (10,28 MB) |
5. Povezavni, vozliščni in mešani okvarni premeri kartezičnih grafovskih produktov in svežnjevRija Erveš, 2011, doktorska disertacija Opis: V disertaciji raziskujemo povezanost in okvarne premere kartezičnih grafovskih svežnjev in kartezičnih produktov. Vpeljemo mešano povezanost in mešani okvarni premer grafa, ki posplošujeta povezanosti in okvarna premera definirana glede na eno vrsto okvarjenih elementov.
Nekatere rezultate na kartezičnih grafovskih svežnjih
in produktih glede na eno vrsto okvarjenih elementov posplošimo in v določenih primerih tudi izboljšamo.
Ključne besede: povezanost po vozliščih, povezanost po povezavah, mešana povezanost, okvarni premer, povezavni okvarni premer, mešani okvarni premer, kartezični grafovski sveženj, kartezični grafovski produkt, telekomunikacijska omrežja, okvarna toleranca
Objavljeno: 21.09.2011; Ogledov: 2783; Prenosov: 90
Polno besedilo (640,76 KB) |
6. Hamiltonskost kartezičnega in direktnega grafovskega svežnjaIrena Hrastnik Ladinek, 2012, doktorska disertacija Opis: Ciklična svežnjevska Hamiltonskost cbH(G) grafa G je najmanjši n, za katerega obstaja tak avtomorfizem grafa G, da je kartezični grafovski sveženj, katerega baza je cikel na n točkah in vlakno graf G, Hamiltonov graf. Podamo oceno za cbH(G) in to oceno dokažemo. Podamo potrebne in zadostne pogoje za povezanost direktnih grafovskih svežnjev katerih vlakna so cikli. Pokažemo tudi, da so vsi povezani direktni grafovski svežnji ciklov nad cikli Hamiltonovi grafi.
Ključne besede: kartezični produkt, direktni produkt, kartezični grafovski sveženj, direktni grafovski sveženj, povezanost, Hamiltonov graf, Hamiltonova dekompozicija.
Objavljeno: 01.03.2012; Ogledov: 2084; Prenosov: 46
Polno besedilo (19,55 MB) |
7. |
8. 2-local 3/4-competitive algorithm for multicoloring hexagonal graphsPetra Šparl, Janez Žerovnik, 2005, izvirni znanstveni članek Opis: An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference.A cellular network is generally modeled as a subgraph of the infinite triangular lattice. Frequency assignment problem can be abstracted asa multicoloring problem on a weighted hexagonal graph, where the weights represent the number of calls to be assigned at vertices. In this paper we present a distributed algorithm for multicoloring hexagonal graphs using only the local clique numbers ▫$omega_1(v)$▫ and ▫$omega_2(v)$▫ at each vertex v of the given hexagonal graph, which can be computed from local information available at thevertex. We prove the algorithm uses no more than ▫$4omega(G)/3$▫ colors for any hexagonal graph G, without explicitly computing the global clique number ▫$omega(G)$▫. We also prove that our algorithm is 2-local, i.e., the computation at a vertex v ▫$in$▫ G uses only information about the demands of vertices whose graph distance from v is less than or equal to 2.
Ključne besede: mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning
Objavljeno: 01.06.2012; Ogledov: 928; Prenosov: 2
 Polno besedilo (0,00 KB) |
9. |
10. Chinese postman problem with priorities (high cost of delays)Tomaž Kramberger, Janez Žerovnik, 2008, objavljeni znanstveni prispevek na konferenci Opis: Several real-world problems, such as street sweeping, mail delivery, solid waste collection, salt gritting and snow plowing can be modeled as Chinese postman problems with some additional constraints. In the paper we present a formal definition of the special case of CPP problem where a subset of priority nodes are given that must be visited as soon as possible, i.e. the cost of delays is much bigger than the cost of additional edges traversed. A heuristical algorithm is proposed which gives near optimal feasible solutions.
Ključne besede: combinatorial optimization, discrete optimization
Objavljeno: 05.06.2012; Ogledov: 691; Prenosov: 6
Polno besedilo (0,00 KB) |
