Preskoči na vsebino Preskoči na navigacijo

Inštitut za matematiko, fiziko in mehaniko

Language:
RSS:
Navigacija

Where a calculator like the ENIAC today is equipped with 18,000 vacuum tubes and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes and perhaps weigh only 1 1/2 tons.

Popular Mechanics, March 1949
Nahajate se tu: Domov Raziskave in projekti Raziskovalni projekti Algoritmi za analizo dodeljevanja lokacij
Akcije dokumenta

Algoritmi za analizo dodeljevanja lokacij

temeljni raziskovalni projekt

Zaradi široke uporabnosti na raznih področjih z ekonomskimi, sociološkimi in demografskimi posledicami sta problem dodeljevanja lokacij in lokacijska analiza v zadnjih letih deležna vse večjega zanimanja predvsem na področju operacijskih raziskav. Vedno, kadar je treba postaviti novo proizvodno, upravno ali skladiščno mesto, želimo preveriti, kakšen vpliv bo imela naša odločitev. Pri tem naletimo na optimizacijski problem, katerega rešitev opisuje najboljšo možno odločitev. Taki primeri so na primer: kje postaviti novo gasilsko postajo, da bo povprečni odziv gasilcev čim hitrejši, kje locirati skladišče nevarnih snovi, da bo pri prevozu snovi do skladišča minimizirana možnost škode ob morebitni nesreči, kje zgraditi mrežo skladišč tako, da bodo logistični stroški minimalni. Lokacijska analiza ima neposredni vpliv na varnost prebivalcev, zelo uporabna pa je tudi pri odločanju in pri razvoju podjetij.

Osnovni podatki lokacijske teorije so nabor lokacij, ki so lahko opremljene z različnimi atributi, kot so neizogibnost, centralnost itd. in so predstavljene s koordinatami na zemljevidu. Med njimi so vzpostavljene povezave, ki ustrezajo cestam ali pa medsebojnemu vplivu (na primer konkurenci), povezave pa imajo prirejene cene ali druge atribute. Kot matematični model uporabimo uteženi graf, katerega vozlišča so točke v Evklidski ravnini ali celo v splošnejših metričnih prostorih. Kriterijska funkcija prirejene optimizacijske naloge je lahko dokaj splošna, vendar je v večini vsakodnevnih aplikacij sestavljena iz primerjave prednosti in slabosti lokacije. Za tako splošne probleme je težko najti učinkovite splošne postopke, zato je potreben razvoj bistveno različnih algoritmov za različne tipe podproblemov.

V projektu bomo obdelali probleme, ki se pojavljajo v lokacijski analizi, in za vse glavne tipe nalog poiskali učinkovite pristope in razvili praktično uporabne algoritme za njihovo reševanje. Pri tem bomo uporabili moderne tehnike računske in diskretne geometrije, algoritmov na grafih in teorije podatkovnih struktur, ki so bili na teh področjih razviti v zadnjem času.

TRAJANJE: 1.9.2005 - 31.8.2008