Optimizacija denarnih tokov pri gradnji cest z genetskim algoritmom
Marko Šetinc1, Heda Kočevar2, Miro Gradišar3
1Merčnikova ulica 1, 1000 Ljubljana, marko.setinc@guest.arnes.si, 2heda.kocevar@gmail.com,
3Univerza v Ljubljani, Ekonomska fakulteta, Kardeljeva ploščad 17, 1000 Ljubljana, Slovenija, miro.gradisar@ef.uni-lj.si
V članku je prikazan primer optimizacije denarnih tokov pri gradnji in upravljanju cestnega omrežja. Na osnovi podatkovne baze iz zadnje uradne posodobitve Nacionalnega programa izgradnje avtocest (NPIA) v letu 2004 sta bila izdelana metodologija in računalniški program, ki omogočata simulacijo in optimizacijo denarnih tokov z genetskim algoritmom. V okviru računalniškega programa sta bila izdelana model, ki simulira denarne tokove, in optimizacijski algoritem, ki je na model navezan preko zamika gradnje posameznih cestnih odsekov. Za kriterija sta bila uporabljena maksimizirana neto sedanjo vrednost (NSV) in minimizirano časovno odstopanje od prvotnega načrta. Optimizacijski algoritem vključuje večkriterijsko optimizacijo z uporabo različnih uteži. Rezultat optimizacije so vrednosti izbranih finančnih in časovnih parametrov. Optimalne rešitve z uporabo različnih uteži oz. razmerij med NSV in časovnim odstopanjem od prvotnega načrta so prikazane s Paretovo krivuljo.
Ključne besede: Sistem za podporo odločanju, simulacija, optimizacija, denarni tok, gradnja cest
1 Uvod
Vsaka človekova odločitev vsebuje določeno stopnjo tveganja, kar ima lahko za posledico nepravilno odločitev. Osnovna naloga sistemov za podporo odločanju je, da proizvajajo informacije, ki zmanjšujejo tveganje in omogočajo učinkovitejše sprejemanje odločitev (Kovačič, 2004). Na voljo je široka paleta metod, tehnik in orodij za podporo odločanju na področju gradnje in obnove cestnega omrežja (Cundrič et al., 2008; Morcous in Lounis, 2005; Šelih et al., 2008; Lamptey et al., 2008; Higgins et al., 2008) ter na področju optimizacije denarnih tokov posameznih gradbenih projektov (Lui in Wang, 2008 Li, 1996). Po navedbah Iassinovskega et al. (2003) so metode pogosto preveč usmerjene bodisi v metodologijo modeliranja, bodisi v reševalna orodja. Vsaka zase so uporabne za svoj namen, vendar pa je glavni problem njihova medsebojna nezdružljivost. Zaradi nezdružljivosti orodij poteka razvoj na področju integriranih orodij, kjer se vključuje metode in orodja iz dveh ali več področij.
Običajno se ljudje pri odločanju zanašajo na razna poslovna poročila in nacionalne programe (Uradni list RS, št. 13/961, 41/982, 50/20043), ki so lahko zastareli že v trenutku, ko so napisani. Ti zaradi svoje oblike ne omogočajo nadaljnjega poizvedovanja. V nasprotju s tiskanimi poročili so sistemi za
podporo odločanju narejeni v obliki računalniških programov, ki omogočajo sprotno posodabljanje in spremljanje dogajanja oz. poslovanja. To je pomembno takrat, ko potrebujemo kakovostne informacije za sprejemanje odločitev.
Primer, kjer se kaže potreba po sistemu za podporo odločanju je nacionalni program izgradnje avtocest, ki je bil pripravljen v obdobju od leta 1993 do leta 1995 in objavljen v Uradnem listu RS, št. 13/961. V njem so vse ocene in predpostavke (investicijske vrednosti in časovni okviri) temeljile na dejstvih, podatkih in razmerah v tistem času. Že v letu 1998 so bile sprejete Spremembe in dopolnitve Nacionalnega programa izgradnje avtocest v Republiki Sloveniji (Uradni list RS, št. 41/982), s katerimi so bila upoštevana nova dejstva in vključeni tudi nekateri novi odseki. S to posodobitvijo naj bi dobili bolj realno sliko izvedbe programa. A po nekaj letih se je pokazalo, da tudi spremenjeni in dopolnjeni program ni mogoče izvajati po predvideni dinamiki in s predvidenimi stroški. V letu 2004 je bila zato izdelana Resolucija o Nacionalnem programu izgradnje avtocest v Republiki Sloveniji (Uradni list RS, št. 50/20043), za katero so bile izdelane nove strokovne podlage za gradnjo avtocest.
Nacionalni program izgradnje avtocest (NPIA) je živ projekt in se zaradi tehničnih, finančnih in političnih razlogov, spreminja že med samo realizacijo. Podvržen je različnim vplivom, kot so: omejen proračun, preoptimistična ocena
1	Nacionalni program izgradnje avtocest v Republiki Sloveniji (NPIA), Ur.I. RS, št. 13/1996.
2	Spremembe in dopolnitve nacionalnega programa izgradnje avtocest v Republiki Sloveniji (NPIA-A), Ur.l. RS, št. 41/1998.
3	Resolucija o Nacionalnem programu izgradnje avtocest v Republiki Sloveniji (ReNPIA), Ur.l. RS, št. 50/2004.
stroškov, politični in lokalni pritiski na pospešitev gradnje ali spremembo trase, sprememba cestninskega sistema ter dodatni avtocestni program. Pred sprejetjem sprememb je pomembno, da se preveri posamezne predloge s podatki, ki ustrezajo dejanskemu stanju in določi vpliv, ki ga imajo spremembe na celotni NPIA.
Na osnovi zadnje posodobitve NPIA (Uradni list RS, št. 50/20043), je bil zato izdelan sistem za podporo odločanju, ki deluje na podlagi simulacije in optimizacije denarnih tokov pri gradnji in upravljanju avtocestnega omrežja in torej omogoča tako modeliranje kot tudi reševanje problemov. Za avtomatsko izvedbo optimizacije smo razvili prilagojeno optimizacijsko metodo in določili kriterije po katerih se optimizacija izvaja. Prikaz te optimizacijske metode in optimizacijskih kriterijev je namen tega prispevka.
Prispevek je sestavljen iz šestih delov. Uvodu sledi opis modela, v katerem je predstavljena osnovna zgradba podatkovnega modela. V naslednjem poglavju so opredeljene opti-mizacijske metode, opis optimizacije z genetskim algoritmom in povezava algoritma z modelom. Sledijo izračuni z uporabo različnih kriterijev v optimizaciji in diskusija, kjer so izračuni interpretirani. Na koncu je zaključek, ki povzame glavne ugotovitve.
2 Opis modela
Pri odločanju potrebujemo model problemskega stanja. Model v splošnem ne zajame vseh parametrov in lastnosti realnosti, ampak je zaradi poenostavitve le njen približek. Pomembno je, da kljub temu vsebuje vse ključne elemente, ki vplivajo na odločitev in da ga je možno, zapisati v obliki matematičnih funkcij ali algoritmov.
V obravnavanem primeru so osnovni gradniki modela cestni odseki, ki skupaj predstavljajo celotno obravnavano
avtocestno omrežje. V modelu smo zajeli denarne tokove pri gradnji in upravljanju avtocestnega omrežja, ki vključujejo glavne prilive, odlive in časovno dinamiko (slika 1).
Med prilive denarnega toka v modelu so zajeta najeta posojila, sredstva iz proračuna oz. namenska sredstva, sredstva iz evropskih skladov in sredstva dobljena s pobiranjem cestnine. V odlivih denarnega toka pa so bili upoštevani stroški novogradnje, stroški vzdrževanja, vračilo glavnice kreditov in obresti, stroške pobiranja cestnine in stroške upravljanja cest.
Časovni dinamiki sta dve. Prva je relativna časovna dinamika posameznega odseka. To pomeni, da se določen odsek gradi N let in zato se v vsakem letu porabi določena količina sredstev. Druga dinamika pa je absolutna, saj pove, v katerem letu se projekt izgradnje odseka dejansko začne izvajati. Absolutna dinamika vpliva na razporeditev projektov po letih in je predmet optimizacije prilivov in odlivov. Model je bil izdelan z naslednjimi predpostavkami:
■	odlivi investicij in relativna časovna dinamika gradnje so fiksni;
■	odlivi vzdrževanja in upravljanja so funkcija dolžine in posebnosti odseka;
■	v denarnem toku so upoštevana posojila in njihovo vračilo;
■	prilivi od cestnin so funkcija prometa in dolžine odseka. V modelu je uporabljena predpostavka, da je cestnina
v funkciji prometa in dolžine odseka, kljub temi, da se od sredine leta 2008 cestnina na slovenskih avtocestah za vozila z največjo dovoljeno maso pod 3,5 t plačuje z vinjeto, za vsa ostala vozila pa še vedno neposredno na cestninskih postajah. Z načrtovano uvedbo satelitskega cestninjenja in odpravo vin-jet se bo zelo verjetno zopet uporabljalo sistem, pri kateri je priliv od cestnin funkcija prometa in dolžine odseka, zato smo v modelu te predpostavke obdržali.
1		1		-1
		z' N		^ N
Prilivi		Odlivi		Časovna
				dinamika
V >		v J		V y
r ^				r ^				r ^				r ^		
Posojila		Proračun in		Cestnine		Stroški		Stroški		Vračilo dol ga		Stroški		Upravljanje
		EU sredstva				gradnje		vzdrževanja		in obresti		pobiranja		cest
												cestnine		
V J		V >		v J		V J		v J		v J		v J		V y
Slika 1: Prilivi, odlivi in časovna dinamika cestnega odseka
3 Metoda
V zadnjih treh desetletjih je bilo razvitih mnogo matematičnih programskih metod za reševanje optimizacijskih problemov (Rangel-Merino et al. 2005). Primerna metoda za optimizacijo je odvisna od problema oz. modela optimizacije. Model lahko vsebuje eno ali več spremenljivk, je diskreten ali zvezen, statičen ali dinamičen, z omejitvami ali brez (Haupt in Haupt, 2004). Dinamičen model z več spremenljivkami, ki je zapisan kot diskretna funkcija z določenimi omejitvami in ima poleg globalnega minimuma še več lokalnih, je izmed naštetih možnosti najzahtevnejši.
Tak model je potreben tudi za simulacijo denarnih tokov pri gradnji cest, saj je to problem reševanja diskretnega modela, kjer usklajujemo večje število projektov (spremenljivk) v času pri določenih omejitvah tako, da dosežemo optimum na nivoju nacionalnega programa. Za tak izračun lahko uporabimo točne, interaktivne, hevristične ali kombinirane metode. Točne metode so računsko zelo zahtevne, saj poleg vrednosti funkcije potrebujejo tudi odvod funkcije, ki se razmeroma enostavno izračuna pri zveznih funkcijah, pri diskretnih funkcijah pa se z večanjem števila spremenljivk kompleksnost izračunavanja zelo poveča, zato te metode za naš primer niso primerne. Hevristične metode (požrešni algoritmi, nepopolno sestopanje in dekompozcija) pogosto končajo v lokalnem minimumu, interaktivne pa zahtevajo interaktivno delo uporabnika. Zato so za obravnavani primer primerne le metahevristične metode, kot so tabu iskanje (Waligora 2008), simulirano ohlajanje, logično programiranje z omejitvami in genetski algoritem (Dreo et al., 2006; Morcous in Lounis, 2005; Cheng et al., 1999; Rangel-Merino et al. 2005).
Odločili smo se za metodo genetski algoritem, ker je robustna, praktična in splošno uporabna optimizacijska tehnika, ki v primerjavi z ostalimi konvencionalnimi tehnikami dosega primerljivo natančnost in večjo učinkovitost (Morcous in Lunis, 2005). Razvil jo je Holland (1975) v zgodnjih 70-ih letih, med pomembne reference pa sodita tudi Goldberg (1989) in Haupt in Haupt (2004). Genetske algoritme se uporablja na znanstvenih in inženirskih področjih. Članki in disertacije, kot na primer (Channon in Damper, 2000) potrjujejo, da je to učinkovita in kredibilna metoda pri globalni optimizaciji problemov. Optimizacija z genetskim algoritmom je računsko bolj učinkovita predvsem zato, ker drugi algoritmi izberejo eno samo rešitev in jo naključno spreminjajo toliko časa dokler ne dosežejo najboljše rešitve. To zahteva veliko ponovitev.
Genetski algoritmi pa obravnavajo več rešitev (populacijo) in z upoštevanjem postavljenih verjetnostnih pravil ustvarijo novo boljšo populacijo. Ponavljanje tega postopka zveča verjetnost, da bo v krajšem času najdena optimalna rešitev. Poleg tega genetski algoritem za izračun uporablja le vrednost funkcije in ne njenega odvoda, kar močno poenostavi izračune (Goldberg, 1989; Morcous in Lounis, 2005).
V prispevku smo metodo optimizacije, ki temelji na genetskem algoritmu, povezali s simulacijo denarnih tokov pri gradnji avtocestnih odsekov. V tem primeru gre za študijo primera, v katerem smo pokazali, kako metodo reševanja vpeljati v novo različico problema (optimizacija denarnih tokov pri gradnji cestnega omrežja). Glavni doprinos prispevka je izvedba povezave genetskega algoritma z modelom ter izbor in preveritev ustreznih finančnih in časovnih kriterijev.
3.1 Genetski algoritem
Genetski algoritem je iskalni algoritem, ki temelji na načelih naravne selekcije. Čeprav genetski algoritem temelji na poskusih, ti niso naključni, ampak so usmerjeni v iskanje vedno boljše rešitve. Osnovni princip genetskega algoritma je simulacija procesov, podobnih tistim, ki se odvijajo pri reprodukciji v naravi in deluje po principu preživetja najboljših. Tako kot v naravi, kjer poskrbi boj za omejene vire prevlado bolj primernih posameznikov, pri genetskih algoritmih ohranjamo vedno boljšo množico rešitev. Genetski algoritem je sestavljen iz naslednjih procesov:
■	naključno generiranje posameznikov,
■	preverjanje uspešnosti posameznikov,
■	izbiranje,
■	križanje,
■	mutiracija,
■	testiranje preživetja.
Delujejo na principu evolucijskih modelov. V teh modelih se potencialno rešitev zapiše v obliki kromosoma, to je niza števil, ki predstavlja rešitev problema. Evolucija populacije običajno izhaja iz naključno generiranih posameznikov. Posamezniki so testirani z oceno primernosti. Ocena primernosti določa kakovost oz. uspešnost rešitve. Nanjo vpliva izbor kriterijev, ki je lahko maksimalni dobiček, minimalni strošek, maksimalna neto sedanja vrednost (NSV), minimalno porabljen čas za dokončanje projektov, ali kombinacija naštetega.
Definicija ocene primernosti je zelo pomembna za iskanje novih rešitev. Na osnovi te ocene poteka izbor posameznikov,
Verjetnostna funkcija
Križanje
Starša
Generacija (N)
Slika 2: Delovanje genetskega algoritma
Mutacija
Preživetveni test
Potomca
Generacija (N+1)
ki se med seboj križajo in nato mutirajo. Če prestanejo test preživetja oziroma, če zadoščajo postavljenim omejitvam, preidejo v novo generacijo. Ta proces se ponavlja, dokler rešitve ne dosežejo željene vrednosti, ali presežejo določenega števila iteracij (Haupt in Haupt, 2004). Grafično je proces je prikazan na sliki 2.
Generacija (N) predstavlja kromosome oz. rešitve za posamezno različico celotnega obravnavanega omrežja. Starša predstavljata dva izbrana kromosoma, ki sta sestavljena iz genov (na sliki 2 so predstavljeni s kvadrati, ki predstavljajo rešitev za posamezni odsek). Pri križanju si kromosoma del rešitev izmenjata. Pri mutaciji kromosoma se vrednost naključno izbranega gena lahko naključno spremeni. Novo nastale kromosome imenujemo potomci. Če ti ustrezajo vsem določenim omejitvam jih vključimo v naslednjo generacijo (N+1). Pri optimizaciji z genetskim algoritmom se z usmerjenim kombiniranjem predstavnikov populacije razvijajo vedno boljše rešitve.
3.2 Navezava modela na genetski algoritem
Posamezni odseki so del celotnega nacionalnega programa. Povezava med posameznim investicijskim odsekom in celotnim programom je, če se navežemo na genetski algoritem, kot povezava med genom in kromosomom. Vsak posamezni investicijski odsek je funkcija prilivov, odlivov in časovne skale, kot je prikazano na sliki 1. Shema na sliki 3 prikazuje, kako so posamezni investicijski odseki povezani v celoten nacionalni program.
Posamezni investicijski odseki so določeni z modelom. Določeni členi v modelu so denarni tokovi za posamezen odsek in predviden začetek investicije. Nedoločen člen je zamik gradnje posameznega odseka (v letih), ki je na sliki
3	prikazan kot gen oz. rešitev za posamezni odsek. Zamik gradnje je celo število, ki pove za koliko let se zamakne gradnja posameznega odseka. Ta določa začetno leto gradnje in neto sedanjo vrednost posameznega investicijskega odseka. Gene vseh obravnavanih odsekov cestne mreže predstavlja kromosom, ki zajema vse tiste spremenljivke v modelu, ki jih optimiziramo z genetskim algoritmom. Iz posameznega kromosoma, ki ga optimiziramo z genetskim algoritmom, kot je prikazano na sliki 2, lahko izračunamo simulacijski model in določimo neto sedanjo vrednost celotnega avtocestnega programa.
4	Optimizacijski kriteriji
V tem razdelku je predstavljen izbor finančnih in časovnih kriterijev za posodabljanje sistema pri optimizaciji denarnih tokov in potek optimizacije katere izidi predstavljajo osnovno informacijsko podlago za odločanje. Model je bil izveden tako, da spremenljivke pri gradnji avtocestnega programa predstavljajo zamiki let gradnje posameznih odsekov. Če se na primer leto gradnje nekega odseka zamakne za dve leti, je »rešitev« za ta odsek 2. Rešitve za vse odseke pa je skupek genov, ki predstavlja celoten kromosom. Posamezen kromosom se preveri s testom preživetja, kar pomeni, da so parametri in rešitev ustrezni glede na predhodno določene omejitve. Tem rešitvam se določi uspešnost, ki pove kako dobra je posamezna različica. Ta je v obravnavanem primeru neto sedanjo vrednost (NSV) celotnega programa in povprečen zamik gradnje posameznih odsekov, pri čemer večja NSV in manjši zamik gradnje predstavljata boljšo rešitev. Uspešnost rešitve je povezana z verjetnostjo, da bo posamezen kromosom izbran proces za izdelave naslednje generacije.
Gen (N-1)	
	
Gen (N)	
	
Gen (N+1)	
	
Gen........	
Začetno leto (n-l)
PROJEKT (N-1)
NSV(n-1 )
Začetno leto (n)
PROJEKT (N)
NSV (n)
Začetno leto (n+1)
PROJEKT (N+1)
NSV (n+1)
N S V
P R O G R A M A
Slika 3: Niz investicijskih odsekov (genov) povezanih v celotni nacionalni program
Ker NSV in zamik gradnje nista primerljiva, smo za primerjavo uporabili indekse. V ta namen so bili najprej določeni kromosomi z maksimalno in minimalno NSV ter z maksimalnim in minimalnim zamikom let (zLet). Nato je bil indeks za vsak NSV in zamik let izračunan po naslednjih enačbah:
(a)	INDEX(NSV)n=(NSVn-NSVmin)/(NSVmax-NSVmin) + faktor
(b)	INDEX(zLet)n=1-(zLetn-zLetmin)/(zLetmax-zLetmin) + faktor
Vrednost indeksa je med vrednostjo faktorja in vrednostjo faktorja + 1. Če je faktor enak 0, se izloči najslabši kromosom, če pa je večji od 1, je le majhna razlika med posameznimi kromosomi. Da ne bi takoj izločili najslabših rešitev, hkrati pa ohranili čim večjo razliko med rešitvami smo dali faktorju vrednost 0,1.
Skupni indeks je bil določen glede na faktor vpliva (A in B). A ima vrednost med 0 in 1:
(c)	B = 1 - A.
(d)	INDEX(skupni) = A x INDEX(NSV)n+ B x INDEX(zLet)n
Verjetnost, da bo kromosom izbran v procesu izdelave naslednje generacije, je izračunana po naslednji enačbi:
(e) Verjetnostn= INDEXn/ E INDEXn
INDEXn je za posamezen kromosom je izračunan po enačbi (d), E INDEXn pa je vsota indeksov celotne populacije kromosomov. Pri višji izračunani verjetnosti ima kromosom večji potencial, da postane starš v genetskem algoritmu.
Po izboru dveh staršev se izvede križanje kromosomov. Križanje se lahko izvede enkrat ali večkrat. V našem primeru je bila 50 % verjetnost, da se križanje izvede le enkrat, ter 50 % verjetnost, da se izvede dvakrat. Po križanju je bila izvedena še mutacija kromosomov. Uporabili smo 10 % verjetnost
mutacije na naključno izbranem genu v določenem območju vrednosti. Če je nova rešitev prestala test preživetja, se je uvrstila v naslednjo generacijo in iteracija se je ponovila.
Pri križanju smo ohranili elitne kromosome. To pomeni, da se najboljših n - kromosomov prenese v naslednjo generacijo. S tem smo preprečili odmik od najboljše najdene rešitve.
5 Rezultati in diskusija
Optimizacija je bila izvedena na zadnji posodobitvi NPIA (Uradni list RS, št. 50/20043), pri čemer so bili optimizirani odseki in projekti, katerih izgradnja se v nastanku posodobitve še ni začela. Optimizacijo smo izvedli na primeru, kjer smo predpostavili, da se posamezen odsek kreditira v višini 50 %. Rezultati modela za tipični odsek so prikazani na sliki 4. Iz slike je razvidna primerjava NSV in dejanskega denarnega toka.
Iz slike 4 je razvidno, da je v letih gradnje denarni tok negativen, medtem ko je po izgradnji, po določenem času pozitiven, če se uporaba avtocest cestnini tako, da so prilivi večji od odlivov. Daljši negativni tok je posledica odplačevanja kreditov. Ob točki preloma, kjer preide negativni denarni tok v pozitivnega prične odsek prinašati pozitivni denarni tok. Iz slike 4 je tudi razvidno, da so prilivi v prihodnosti bistveno manjši z vidika neto sedanje vrednosti (NSV), kot pa je dejanski denarni tok.
Simulacija denarnih tokov in optimizacija z genetskim algoritmom je bila izdelana v programu Microsoft Visual Basic s podporo Microsoft Access podatkovno bazo. Ena iteracija na računalniku Intel Core Duo 2.4 GHz je trajala okoli 1 sekunde. Izvedenih je bilo 1500 iteracij za vsak izračun, rešitev pa se je običajno izoblikovala po okrog 800 iteracijah.
Prednost razvitega sistema za podporo odločanju z opti-mizacijsko metodo je, da omogoča poleg iskanja globalnega optimuma določenega sistema tudi iskanje optimumov sistema pri različnih kriterijih in primerjavo med njimi. To smo prikazali z uporabo sedmih različnih kriterijev za optimizacijo: ■ indeks maksimalne neto sedanje vrednosti,
20
10
										
...........................ll	1	1	1	1	1	1	1	1	1	1
I .20
-30
-40
-50
]T]W[pTFTinFTPT ^ ^
^ ^ ^ V	T'

-9' '9

□	denarni tok
□	NSV
Leto
Slika 4: Denarni tok in NSV za tipičen odsek
■	indeks minimalnega povprečnega zamika let gradnje avtocestnih odsekov (zLet),
■	pet uteženih indeksov maksimalne NSV in minimalnega zamika let v razmerjih (A:B) (90:10, 75:25, 50:50, 25:50 in 10:90).
Kriteriji, ki bi jih bilo možno še dodatno vključiti v optimizacijo, so tudi: promet, cestninjenje, prometna varnost, investicija in prometna ekologija (Žura in Srdic, 2002). Pri posodabljanju ti kriteriji niso več tako pomembni kot pri sami zasnovi programa. Pomembno je, da se pri posodabljanju denarnih tokov na večletnem nivoju kot kriterij upošteva NSV in povprečen zamik začetka gradnje odsekov, ki sta prikazana v tem prispevku. Oba kriterija pomembno vplivata na časovno dinamiko gradnje in denarni tok. V nasprotnem primeru lahko pride do previsoke ocene upravičenosti projekta in nerealne optimizacije, če se na primer primerja odlive v sedanjosti in prilive v daljni prihodnosti kot enakovredne ali pa pride do prevelikega odstopanja od prvotno zasnovanega programa.
Tako zasnovan model ni več zgolj orodje za ekonomsko optimiranje denarnih tokov ampak tudi orodje, ki omogoča preveritev različnih scenarijev in omogoča argumentirano odločanje v političnem okolju. Za ocene razmerij po različnih kriterijih je rezultat optimizacije prikazan na slikah 5a in 5b. Na sliki 5a je prikazana NSV, na sliki 5b pa povprečen zamik začetka gradnje (zLet) v odvisnosti od razmerja indeksov med NSV in zLet.
Na sliki 5a je najboljša rešitev (100:0) z vidika NSV, na sliki 5b pa rešitev (0:100) z vidika čim hitrejšega začetka in s tem tudi dokončanja izgradnje avtocestnega programa. Cilj optimizacije je najti tako rešitev, ki bo ob čim višji NSV omogočila najhitrejše dokončanje avtocestnega programa. To lahko naredimo tako, da NSV in zamik let spremenimo v indeks od 0,1 do 1,1, in ju seštejemo. Rezultat je prikazan na sliki 6, kjer je razvidno, da je na podlagi te metode in kriterijev optimalno razmerje A:B med 75:25 in 25:75 z vrhom pri 40:60.
To je zgolj ena od možnosti. Dejansko pa pri optimizaciji združujemo dve lastnosti, ki nista neposredno primerljivi, zato obstaja veliko rešitev, kar najbolje ponazorimo grafično (slika 7).Temne točke so rešitve, dobljene z optimizacijo pri različnem razmerju uteži (A in B), ki ležijo na t.i. Paretovi krivulji (Martinez et al., 2009). Za vse točke na tej krivulji je značilno, da izboljšanje ene lastnosti poslabša drugo. Pri tem vse te točke predstavljajo najboljše rešitve glede na izbran kriterij (Kočevar in Šetinc, 2007). Svetle točke predstavljajo naključne rešitve, ki smo jih uporabili za vhod v optimizacijo z genetskim algoritmom.
Iz slike 7, kjer je prikazan primer optimizacije NPIA pri različnih razmerjih uteži A in B, je razvidno, da izbira najugodnejše rešitve ni enostavna in samo matematično opredeljiva. Dejansko je to »politična« odločitev, saj se moramo odločiti, koliko nam pomeni posamezen kriterij, ki je v obravnavanem primeru na eni strani cena (NSV) programa, na drugi pa pov-
0 -50 S -100
3 -150
I -200
~ -250
^tCs^	i—6 k 4)—S ftšp^ 0:6)—; 5:7
-300 -350 -400
Razmerje uteži (A;B) v (%)
Ä 4
1' o
-									
									
									
									I—1
									n
100:0 90:10 75:25 60:40 50:50 40:60 25:75 10:90 0:100 Razmerje uteži (M) v (%)
Slika 5: Optimizacija pri različnih razmerjih uteži (A in B) za NSV in povprečen zamik začetka gradnje
	1,30
s	1,20
—I N	
	1,10
>	
	1,00
g	
1	0,90
■Ö	
C	0,80
ro	
O s	0,70
	0,60
100:0 90:10 75:25 60:40 50:50 40:60
Razmerje uteži (A:B) v (%)
25:75
10:90 0:100
Slika 6: Vsota indeksov NSV in povprečnega zamika let gradnje (zLet) v funkciji uteži A in B
—optimizirane o nal<ljučne
-50 -100
£
I -200
> -250 z
-300 -350 -400
Povprečen zamik začetka granje (leta)
Slika 7: NSVproti povprečnemu zamiku začetka gradnje (Paretova optimizacijska krivulja)
prečen zamik gradnje. Prikazana metoda omogoča preveriti možnosti in pokazati razlike v scenarijih, če želimo čim bolj ugodno finančno izvedbo, čim hitrejše dokončanje avtocestnega programa ali nek kompromis med njima. Končna izbira je »politična« odločitev, ki je strokovno in objektivno utemeljena, glede na relativno pomembnosti NSV na eni in povprečnega zamika gradnje na drugi strani.
6 Zaključki
Sistem za simulacijo in optimizacijo denarnih tokov je primeren za izvedbo optimizacije denarnih tokov, ki nastajajo oz. se porabljajo pri gradnji, vzdrževanju in upravljanju večjega števila cestnih odsekov ali projektov, ki se zaradi tehničnih, finančnih in političnih razlogov med izvajanjem spreminjajo. Genetski algoritem, ki smo ga uporabili za optimizacijo denarnih tokov, se je izkazal kot primeren za optimizacijo predstavljenega problema. Izdelana povezava med simulacij-skim modelom in optimizacijskim algoritmom, ki predstavlja zamik gradnje posameznih odsekov, se je izkazala kot ustrezna. Razvit sistem za podporo odločanju z optimizacijo simulacijskega modela omogoča iskanje optimuma sistema pri različnih kriterijih ter primerjavo med izidi, kar je pokazano na sedmih različnih kriterijih: maksimalna neto sedanja vrednost, minimalni povprečen zamik gradnje avtocestnih odsekov in 5 skupnih uteženih faktorjev maksimalne NSV in minimalnega zamika let v različnih razmerjih A in B (90:10, 75:25, 50:50, 25:50 in 10:90). Cilj optimizacije je bil najti rešitev, ki bo ob čim višji NSV omogočila najhitrejše dokončanje avtocestnega programa. Ker pri optimizaciji združujemo dve lastnosti, ki nista neposredno primerljivi, smo več najboljših rešitev, ki so odvisne od kriterija optimizacije, ponazorili grafično s Paretovo krivuljo. Pri tem vse te optimizirane točke predstavljajo enakovredne rešitve. Končna izbira je »politična« odločitev, ki mora biti strokovno in objektivno utemeljena, glede
na relativno pomembnosti NSV na eni in povprečnega zamika začetka gradnje na drugi strani.
7 Viri in literatura
Channon, A.D. & Damper, R.I. (2000). Towards the evolutionary emergence of increasingly complex advantageous behaviours, Special Issue on Emergent Properties of Complex Systems, International Journal of System Science, 31(7): 843-860.
Cundrič, A., Kern T. & Rajkovič V. (2008). A qualitative model for road investment appraisal, Transport Policy, 15: 225-231. DOI: 10.1016/j.tranpol.2008.05.003.
Cheng, R, Gen, M. & Tsujimura, Y. (1999). A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computer & Industrial Engineering, 36: 343-364. PII: S0360-8352(99)00136-9.
Dreo J., Petrowski A., Siarry P. & Taillard E. (2006). Metaheuristics for Hard Optimization, Springer-Verlag, Berlin.
Goldberg, D.E. (1989). Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing, New York.
Haupt, R.L. & Haupt, S.E. (2004). Practical Genetic Algorithms, John Wiley & Sons, Inc., New Jersey.
Higgins, A.J., Hajkowicz, S. & Bui, E. (2008). A multi-objective model for environmental investment decision making, Computer & Operation Research, 35: 253-266. DOI: 10.1016/j. cor.2006.02.027.
Holland, J. H. (1975). Adaptive in natural and artifitial systems, Ann Airbor, University of Michigan Press.
Iassinovski, S., Artiba, A., Bachelet, V. & Riane F. (2003). Integration of simulation and optimization for solving complex decision making problems. International Journal of Production Economics, 85, 3-10. DOI: 10.1016/j.dss.2008.07.004.
Kočevar, H. & Šetinc, M. (2007). Environmental protection and investment cost as factor of road placement, RMZ- Materials and Geoenvironment, 54(2): 223-234.
Kovačič B., (2004), Predavanja iz informacijskih sistemov v prometu in cestnem prometu, dosegljivo na: http://fg.uni-mb.si/predmeti/ GEOD/predavanja/Informacijski sistemi.pdf (5.3.2004)
Lamptey, G., Labi, S. & Li, Z. (2008). Decision support for optimal scheduling of highway pavement preventive maintenance within resurfacing cycle, Decision Support Systems, 46: 376-387. DDI: 10.1016/j.dss.2008.07.004.
Lui, S.S. & Wang, C.J. (2008). Resource-constrained construction project scheduling model for profit maximization considering cash flow, Automation in Construction, 17: 966-974. D01:10.1016/j.autcon.2008.04.006.
Li, S. (1996). New Approach for Optimization of Overall Construction Schedule, Journal of Construction Engineering and Management, 122(1): 7-13. D01 10.1061/(ASCE)0733-9364(1996)122:1(7)
Martinez, M., Garcia-Nieto, S., Sanchis, J. & Blasco, X. (2009). Genetic algorithms optimization for normalized normal constraint method under Pareto construction, Advances in Engineering Software, 40:260 - 267. D01:10.1016/j.adveng-soft.2008.04.004.
Morcous, G. & Lounis, Z. (2005). Maintenance optimization of infrastructure networks using genetic algorithms, Automation in Construction, 14: 129 -142. D01:10.1016/j.autcon.2004.08.014
Rangel-Merino, A, Lopez-Bonilla, J.L., Linares y Mranda, R. (2005). Optimization method based on genetic algorithms, Apeiron, 13(4): 393-408.
Šelih J., Kne, A., Srdic A. & Žura M. (2008). Multiple-criteria decision support system in highway infrastructure management, Transport, 23(4): 299-305. DO1:10.3846/1648-4142.2008.23.299-305.
Waligora, G. (2008). Discrete-continuous project scheduling with discounted cash flows - A tabu search approach, Computer & Operation Research, 35: 2141-2153. DO1: 10.1016/j. cor.2006.09.022.
Žura, M. & Srdic, A. (2002). Multikriterialno določanje prioritetnega vrstnega reda gradnje cestnih odsekov, 6. Slovenski kongres o cestah in prometu, Porotorž 23.-25. oktober 2002, Družba za raziskave v cestni in prometni stroki Slovenije, Ljubljana.
Marko Šetinc je doktoriral na področju kemijskega inženirstva. V času podiplomskega študija se je ukvarjal z razvojem in analizo kemijskih procesov. Po študiju se je ukvarjal s področjem poslovne informatike v povezavi s cestno infrastrukturo. Glavna področja dela in raziskovanja so bila izdelava podatkovnih baz, geografski informacijski sistemi in sistemi za podporo odločanju. Trenutno je zaposlen na Kemijskem inštitutu, kjer se ukvarja z razvojem vodikovih tehnologij. Poleg tega pa se ukvarja z razvojem filtrirnih naprav za odstranjevanja kontaminantov in smradov iz zraka pri čistilnih napravah in industrijskih procesih.
Heda Kočevar je doktorirala leta 1996 na Univerzi v Ljubljani in postala doktorica geoloških znanosti. Delovno pot je nadaljevala na več področjih, predvsem kot raziskovalka na različnih projektih. V njeno delo sodi strokovno-raziskovalno delo na področju cest, prometa, varstva okolja in prostora, raziskovalno pedagoško delo na področju geologije in delo na področju projektnega managementa. Trenutno je vodja projektne pisarne za velik projekt, sofinanciran s sredstvi kohezijskega sklada.
Mirko Gradišar je zaposlen na Ekonomski fakulteti Univerze v Ljubljani kot redni profesor za področje poslovne informatike. Raziskovalno se ukvarja predvsem z razvojem informacijskih sistemov in zahtevnejših algoritmov na področju operacijskih raziskav. Na pedagoškem področju sodeluje tudi z Univerzo v Mariboru in Univerzo v Bremnu. Kot gostujoči profesor pa je sodeloval z Univerzo v Baltimoru. Dr. Gradišar je izdal več univerzitetnih učbenikov, znanstvenih monografij in znanstvenih člankov. Njegova dela so citirana v revijah, ki jih indeksirata SCI in SSCI.