Odeljenje za matematiku, 14. april 2011.

Naredni sastanak Odeljenja za matematiku održaće se u četvrtak, 14. aprila 2011. u sali 2 SANU sa početkom u 14h.

Predavač: dr Zorica Stanimirović, Matematički fakultet, Univerzitet u Beogradu

Naslov predavanja: HIBRIDNI EVOLUTIVNI ALGORITAM ZA REŠAVANjE HAB LOKACIJSKOG PROBLEMA NEOGRANIČENIH KAPACITETA SA JEDNOSTRUKIM ALOKACIJAMA

Sadržaj: Hab lokacijski problemi su u poslednje dve decenije doživeli  pravu ekspanziju, najviše zahvaljujući svojoj širokoj primeni u praksi.  Mreže habova (eng. hub networks) su najviše zastupljene u modernim  transportnim i telekomunikacijskim sistemima, računarskim i internet  mrežama. Habovi (eng. hubs) predstavljaju centre konsolidacije i kolekcije protoka u mreži izmedju dve lokacije. Korišćenjem habova kao  tačaka preusmeravanja protoka i povećavanjem transporta između habova, kapacitet mreže se može iskoristiti dosta efikasnije a troškovi transporta smanjiti. U okviru predavanja biće razmatran hab lokacijski problem  neograničenih kapaciteta sa jednostrukim alokacijama pozicije habova  (Uncapacitated Single Allocation Hub Location Problem - USAHLP).
Cilj ovog NP-teškog problema kombinatorne optimizacije je sledeći:  uspostaviti skup habova i alocirati ne-hab čvorovi elementima skupa  uspostavljenih habova, tako da suma transportnih troškova u mreži i
fiksnih troškova lociranja habova bude minimalna. Biće predstavljena  matematička formulacija USAHLP i predložen hibridni heuristički algoritam (HEA) za rešavanje ovog problema. Dizajnirane su dve heuristike lokalnog pretraživanja u cilju poboljšanja lokacijskog i alokacijskog  aspekta problema, koje su zatim implementirane u okviru evolutivnog  koncepta za rešavanje USAHLP. Algoritam je testiran na postojećim  instancama hab problema iz literature, kao i na novim instancama realnih  dimenzija (do 900 lokacija). Dobijeni eksperimentalni rezultati i poređenja sa drugim metodama ukazuju na efikasnost predloženog hibridnog pristupa, posebno u slučajevima instanci realnih dimenzija. Algoritam daje optimalna i popravlja postojeća najbolja rešenja iz literature u veoma  kratkom vremenu izvršavanja. Prednosti HGA posebno dolaze do izražaja pri  rešavanju instanci problema velikih dimenzija, na kojima se postižu  značajna poboljšanja u pogledu i kvaliteta HGA rešenja i vremena izvršavanja.

(koautori na ovom istraživanju su dr Miroslav Marić i Predrag Stanojević sa Matematičkog fakulteta u Beogradu)


 Ostavite vaš komentar 

Komentari(0)

Ostavite vaš komentar:


(opciono)
(nece biti prikazano)