Teoria e grafeve-PROJEKTIMI I SISTEMEVE TE TRANSPORTIT

KAPITULLI v
TEMA :
Teoria e grafeve

Per ndertimin e nje projekt transporti, duhet detyrimisht te merren ne
konsiderate shume elemente, ose kushte, te cilat konvertohen ne nje
bashkesi ndervaresie e quajtur Modeli i sistemit te transportit, ky model
eshte i afte ti simuloje keto kushte apo elemente, te projektit duke ne
dhene rezultatet respektive. Sa me siper, nje projekt per nje sistem
transporti, duhet te ece neper keto faza logjike:
Individualizimi i objeketve qe kerkojne levizje (kerkesa per transport)
Analiza sasiore e sistemit te transportit aktual (ose per disa sisteme)
Ndertimi i nje model varesie, qe perfaqeson nje sitem transporti, i cili
eshte ne gjendje te funksionoje me te dhenat (dati) aktuale, si edhe me
parametrat e vlerave te prespektives, ne lidhje me kete sistem qe po
projektojme, se bashkeu me sistemet e tjere konkurues
Verifikimi i modelit
Formimi i zgjidhjeve alternative
Zgjedhjen e variantit optimal
Faza kryesore e delikate e te gjithe procesit te projektimit, te
modulit te nje sitem transporti, eshte faza e ndertimit te ketij moduli, qe
duhet patjeter te shprehi realitetin, si dhe te jete ne gjendje te jape
rezultate mbi ndryshimet e mundeshme te kushteve, ose elementeve te
prespektives.
Perpunimi i ketij moduli, ose besueshmeria e ketij moduli, realizohet
nepermjet funksioneve, e teorive matematikore, te cilat jane mbeshtetur ne
koncepte specifike. Nje nder keto teori, eshte teoria e grafeve, e cila
eshte e besueshme ne projektimin e c'do modeli per c'do sistem livizje. Ne
po prezantojme kriteret kryesore te kesaj teorie, se si ajo e parametrizon
nje sistem transporti dhe ne c'form dalin zgjidhjet e mundeshme. Realizimi
konkret i nje zgjidhjeje kerkon atrecature speciale si Hardware, Software,
si dhe nje personel me eksperience ne perdorimin e kesaj fushe.









Perkufizimet per grafet dhe metodat e pergatitjes

Jepen nje bashkesi me N elemente, te quajtur Nyje dhe nje bashkesi me
L elemente, te quajtur Dege ose Harqe, te cilat lidhin keto nyje nga njera
tek tjetra. Bashkesia G e ndertuar nga keto lidhje te N (nyjeve), me L
(dege), perben ate qe quhet Graf. ( mund te jepet nga shprehja G={N,L} )
Nje graf mund te ndertohet per te paraqitur nje realitet fizik te
c'faredoshem. Nyjet qe e perbejne grafin, mund te tregojne pikat fizike te
nje teritori, ose komponente te ndryshem fizike te nje sistemi, ose
aktivitete te ndryshme te tij. Deget lidhese qe lidhin dy nyjet, tregojne
relacionet e pikave te teritorit, ose komponente te ndryshem fizike, ose
aktivitete te nje sistemi qe ekziston ndermjet tyre, ose relacion te nje
tipi te caktuar.
N.q.se dy nyje jane pikat e nje teritori, lidhja e ketyre nyjeve tregon qe
ato jane te lidhura nje e nga nje sipas:
a) Cifti i nyjeve mund te jene te Rregullta (n.q. se ekzistojne),
atehere kur cifti (i,j) eshte i ndryshem nga cifti (ji), ne kete rast
Harku (ij) quhet i Orientuar
b) Ciftet i nyjeve mund te jene jo te rregullta dhe harqet jo te
orientuarr .
Ne nje graf mund te kemi harqe te orientuar dhe jo te orientuar. Grafi ne
te cilin te gjithe harqet jane te orientuar, ai vete quhet graf i
orientuar. Ne nje hark te orientuar, nyja e pare e kapjes quhet Nyje
origjine, nyja e dyte Nyja fundore. Grafet qe perdoren pre prezantimin e
sistemeve te transportit ne pergjithesi jane te orientuar. Le te kemi
Nn (numuri i elementeve, nga bashkesia N e nyjeve)
Ln (numuri i elementeve, nga bashkesia L e degeve)
Per te dalluar nje dege, eshte e nevojshme qe te njihen elmentet e
bashkesise N dhe kapjet e marra nga kjo bashkesi, perbejne bashkesine e
degeve L. Paraqitja me e lehete dhe me e qarte per nje graf, eshte ajo
grafike, ne kete paraqitje nyjet konvertohen me nga nje pike, te emertuar
me nga nje numer, ndersa harqet paaqiten me segmente, qe lidhin cifte te
ndryshme nyjesh, duke formuar bashkesise e degeve L. Cdo hark i orientuar
konvertohet me nje shigjete, ne kete rast tregon kahun e orientimit. Per
komentimin e sa thame me siper, po prezantojme nje graf me keto elemente,
bashkesia e Nyjeve me 5 nyje qe mund te perfaqesojne 5 elemente qe kerkojne
nje levizje, dhe bashkesia e harqeve me 9 elemente qe perfaqesojne 9
levizje te ndryshme neper kato nyje. Paraqitja grafike e ketij Grafi (5
nyje / 9 harqe) po e japim ne figuren e meposhme,


Por paraqitja grafike e nje grafi mund te ekujvalentohet, ose transformohet
ne menyre qe te perpunohet nga aparati matematikore, si:
Paraqitje Matricor
Paraqitje Vektorial,
Ne keto paraqitje, nyjet e bashkesise Nn tregohen gjithmone me numura
progresive. Per dallimin e kapjeve perberese te bashkesise L perdoren
teknika te ndryshme. Po prezantojme disa prej tyre:

Matrice Katrore

Paraqitja grafike e nje grafi me forme matricore k atrore, eshte konceptuar
si nje mtrice katrore, me dimensionet sa eshte numuri i nyjeve te grafit.
Matrica mbushet me elementet e saj me kete logjike. Elementi "ij" i
matrices, eshte i barabarte me 1 n.q.se kapja e nyjes "ij" (fillohet nga
emertimi i rreshtit, tek emertimi i kolones), ben pjese ne bashkesine
harqeve L, me dalje nga "i" dhe me 0 ne te kundert

" "1 "2 "3 "4 "5 "
"1 "0 "0 "0 "1 "0 "
"2 "1 "0 "1 "0 "1 "
"3 "0 "0 "0 "1 "1 "
"4 "0 "0 "0 "0 "0 "
"5 "1 "0 "1 "1 "0 "


Matrice e varesise Nyje-Dege

Nje forme tjeter e paraqitjes matricore te grafit, eshte paraqitja matrica
varesi nyje dege. Dimensionimet e kesaj matrice jane ne perputhje me
sasiene nyjeve e degeve, konketisht, c'do rrjeshti i korespondon nje nyje
dhe c'do klone nje dege. Mbushja e matrices realizohet sipas kesaj logjike,
elementi "ij" i matrices eshte 0 n.q.se nyja "i" nuk i perket harkut
korespondues te kolones "j" dhe e barabatre me 1 n.q.se nyja "i" eshte nyje
fillestare e harkut te orientuar (d.m.th. elementi i pare i kapjes se
harkut te orientuar) dhe me –1 n.q. se nyja "i" eshte nyja fundore e harkut
te orientuar. Per ta bere me te qarte paraqitjen matrice varesise nyje dege
dhe korespondencen e saj, kemi prezantuar nje matrice qe perfaqeson kete
logjike dhe qe i referohet po te njejtin graf, kjo matrice quhet paraqitjen
matricore me varesi nyje dege.
Ne emertimin e cdo rreshti, eshte vendosur sipas rendirjes progresive,
numuri i nyjeve te grafit (1-5). Ne emertimin e c'do kolone, eshte vendosur
kapja e nyjeve qe percaktojne harkun ne graf (1-9). Dhe mbushja e matrices
(me 1, ose 0, ose –1)behet me logjiken e cituar me siper, duke na dhene
kete paraqitje:

" "1-4 "2-1 "2-3 "2-5 "3-4 "3-5 "5-1 "5-3 "5-4 "
"1 "1 "-1 "0 "0 "0 "0 "-1 "0 "0 "
"2 "0 "1 "1 "1 "0 "0 "0 "0 "0 "
"3 "0 "0 "-1 "0 "1 "1 "0 "-1 "0 "
"4 "-1 "0 "0 "0 "-1 "0 "0 "0 "-1 "
"5 "0 "0 "0 "-1 "-1 "-1 "1 "1 "1 "


Matrice e nyjeve me-harqet maksimale qe dalin nga nje nyje

Paraqitja e gafit jepet nga nje matrice te dimensionuar sipas ketij
koncepti, numuri i rreshtave eshte i barabarte me numurin e nyjeve
(progresion rrites), ndersa numuri i kolonave merret i barabarte me numurin
maksimal te harqeve qe dalin nga nje nyje (s'ka rendesi e sata nyje eshte
ne gaf). Mbushja e matrices rrealizohet sipas kesaj logjike, vlera e
elementit "ij" eshte sa numuri rendore i nyjes, qe shikon harkun dales,
n.q. se nuk ka hark (eshte me e vogel se mumuri max. i harqeve dalese),
atehere merr vleren 0. Sa thame me siper ne mund ta dimensionojme dhe
ndertojme te njejtin shembull me matricen nyje harqesh maksimale si me
poshte:

" "1 "2 "3 "
"1 "4 "0 "0 "
"2 "1 "3 "5 "
"3 "4 "5 "0 "
"4 "0 "0 "0 "
"5 "1 "3 "4 "


Matrica e varesise Harqe-Rrugekalim A

Ne paraqitjen e grafit, sipas matrice varesi harqe rrugekalimi, kemi kete
konceptim. Ndertohet nje matrice me numurin e rreshtave te barabarte me
numurin e harqeve, ose lidhjeve, ndersa numuri i kolonave, eshte me numurin
e mundeshem te intinerareve te realizuara ne kete graf, (levizjeve neper
nyje, po per te njejtin shembull te treguar, rezulton 4 intenerare 2-3-5-1-
4/ 2-5-1-4/ 2-5-3-4/ 2-3-4 ), pra c'do rrjesht lidhet me nje hark te grafit
dhe c'do kolone me nje intinerar. Mbushja e matrices konceptohet ne vleren
1 dhe 0, Vlera 1 eshte atehere kur harqet (emertimi i rreshtit) ben pjese
ne intinerarin qe korespondon me kolonen "j" dhe 0 kur nuk ben pjese ne
kete intenerar.

" "1 "2 "3 "4 "
"1-4 "1 "1 "0 "0 "
"2-1 "0 "0 "0 "0 "
"2-3 "1 "0 "0 "1 "
"2-5 "0 "1 "1 "0 "
"3-5 "1 "0 "0 "0 "
"4-3 "0 "0 "1 "1 "
"5-1 "1 "1 "0 "0 "
"5-3 "0 "1 "0 "0 "
"5-4 "0 "0 "0 "0 "


Matrice e ciftit Nyje-Rrugekalimi

Ne te cilen c'do rresht i korespondon nje cift nyjesh, dhe c'do kolone i
korespondon nje rrugekalimi (intinerare), mbushja me elemente kete matrice
realizohet sipas kesj logjike elementi "ij" eshte 1 n.q.se ciftin "i"
lidhet me intinerari "j" (d.m.thene intinerari ka nyje te ekstremeve, ato
qe ndertojne ciftin e "i") dhe 0 ne kundert. Ne kete rast numeri i
elementeve te matrices, varet nga numuri i cifteve per te cilat merren
parasysh intineraret, psh. Me posht po japim per nje cift nyjesh nje
matrice cift nyje rruge kalim, qe mbeshtetet ne po te njejtin graf.

" "1 "2 "3 "4 "
"1-5 "1 "1 "1 "0 "
"5-1 "0 "0 "0 "1 "


Metoda e Yjeve e Harqeve (Algoritmi DIJKSTRA)

Prezantimi i grafit qe perdoret me shume ne programet llogaritese dhe qe do
te perdoret me vone eshte quajtur si prezantim me metoden e Yjeve e
Harqeve.
Nje prezantim i tille bazohet ne faktin qe ne nje graf c'do nyje eshte
origjina e nje ylli prej harqesh, qe dalin prej saj. Ne nje vektor
fillestar a sillen nyjet ekstreme te yjeve te ndryshem, ne blloqe te
njepasnjeshem, c'do bllok vendoset pas tjetrit, me te njejten rregulll, me
te cilin gjenden nyjet origjine te yjeve.
Komponentet e vektorit te dyte b (me numur te njejte me numurin e nyjeve te
grafit), jane "shenjuesit " ose numurat qe tregojne vendet e zena ne
vektorin e pare, nga nyjet e fundit te blloqeve te njepasnjeshme. Sa thame
me siper, mund te paraqesim po te njejten paraqitje te grafit, me nje
koncept tjeter (shif figuren per ndertimin e vektoreve). Keshtu pranojme te
lexohen te parin ne bllok, e pastaj te njohe per c'do bllok, harqet qe kane
per origjine. Si perfundim, nyjet e lidhur ne dalje me nyjen "i" jane
komponente te vektorit a perfshire nga bI-1 +1 e atij b1 . Eshte e mundur
te vleresohet se sa pozicione te memories, ose sa elemente nevoiten per
paraqitjen e nje grafi, ne memorien e nje makine llogaritese. duke perdorur
tre metodat e paraqitjes se grafeve, te prezantuar me lart. Ato jane n2N ;
nNxnL dhe nNx(nm +1) ku nm eshte numuri mesatare i harqeve qe ndertojne
ne nje yll.
P.sh. marrim nje graf, me nyjet si qender levizje, ku deget e grafit i
atribojme me cilesite si, gjatesise se rruges, ose kosto e rruges etj.
Kerkojme te marrim levizjen (intineraret) per te gjitha nyjet e grafit me
vleren minimale (leviz neper minimum)
Qellimi i levizjes nga Nyja 1 ne nyjen 6 (pretendojme levizjen ekstreme).
Per kete detyre prezantojme bashkesine e intenerareve, bashkesin e
qendrave:
Q{1,} bashkesia e intenerarit ne qendren 1, me vleren e intenerarit dint=0
(gjatesi, kosto)
N{2,3,4,5,6} bashkesia e qendrave te grafit, per tu kapur gjate levizjes
Krijojme te gjitha lidhjet qe ka qendra fillestare ne te cilen ndodhemi, me
te gjitha qendrat e tjera te bashkesise N, duke i vleresuar vektoret si
shumen e tyre nga nyja fillestare1.
1 2 (mini [(distanca direkte 1-2)] 1
1 4 (mini [(distanca direkte 1-4)] 2
1 3 /5 /6 (mini [(distanca direkte 1-3 etj)] eshte ( pasi nuk kemi lidhje
direkte
per kete hap, eleminojme levizjet ( dhe ndertojme dy intinerare paralele,
kjo kondicionohet nga vlera direkte e kapjes 1-4 me distance levizje dmin
=2, pra tani na krijohen 2 intinerare 1-2 dhe 1-4, levizjeje paralele, qe
do te merren ne konsiderate gjate gjith procedures, se levizjes
Kalojme ne hapin e dyte, me kete situacion te grafit
Intinerari i pare 1-2 , kapet nyja 2, me distance intinerari dintinerari=1
Q{1,2} bashkesia e intenerarit me levizjen min dint=1 (minimumi i levizjes)
N{3,5,6} bashkesia e qendrave te grafit, per tu kapur
Krijojme te gjitha lidhjet qe ka qendra ne te cilen ndodhemi 2, me te
gjitha qendrat e tjera, te bashkesise N duke i vleresuar vektoret levizes,
si shumen e tyre nga nyja fillestare1.
2 3 (mini [(distanca direkte1-3)(1+d2-3)] ( (1+1.5) min=2.5
2 5 /6 (mini [(distanca direkte 1-5 /6 )] eshte (
per kete hap, pranojme qe kemi kete levizje minimale dintinerari=2.5 (kapet
nyja 3)
Intinerari i dyte 1-4, kapet nyja 4, me distance intinerari dintinerari=2
Q{1,4 } bashkesia e intenerarit me levizjen min dint=2 (minimumi i
levizjes)
N{3,5,6} bashkesia e qendrave te grafit, per tu kapur
Krijojme te gjitha lidhjet qe ka qendra ne te cilen ndodhemi 4, me te
gjitha qendrat e tjera, te bashkesise N duke i vleresuar vektoret levizes,
si shumen e tyre nga nyja fillestare1.
4 3 (mini [(distanca direkte 1-3)(2+d4-3)] ( (2+()
4 5 /6 (mini [(distanca direkte 1-5 /6 )] eshte (
sic shikohet nuk kemi vlere, pra ky intinerar eshte i mbyllur, nuk vazhdon
me tej, problemin e vazhdon intenerari mbetes 1-2-3 me levizje min dinti
=2.5
Kalojme ne hapin e trete me kete situacion te grafit (jemi ne nyjen
3)
Q{1,4 dhe 1,2,3} bashkesia e intenerarit me levizjen mini. dint=2.5
N{5,6} bashkesia e qendrave te grafit, per tu kapur
Krijojme te gjitha lidhjet qe ka qendra ne te cilen ndodhemi 3 me te gjitha
qendrat e tjera, te bashkesise N duke i vleresuar vektoret levizes, si
shumen e tyre nga nyja fillestare1.
3 5 (mini [(distanca direkte1-5)(2.5+d3-5)] ( (2.5+2) min=4.5 (nyja 5)
3 6 (mini [(distanca direkte 1-6)(2.5+d3-6)] ( (2.5+()
per kete hap, pranojme qe kemi kete levizje min. dintinerari=4.5 (kapet
nyja 5)
Kalojme ne hapin e katert, me kete situacion te grafit (jemi ne nyjen
5)
Q{1,4 dhe 1,2,3,5} bashkesia e intenerarit levizja min. neper nyjet
dint=4.5
N{6} bashkesia e qendrave te grafit, per tu kapur
Krijojme lidhjet qe ka qendra ne te cilen ndodhemi 5, me qendren 6 te
bashkesise se njeve N, duke i vleresuar vektoret levizes, si shumen e tyre
nga nyja fillestare1.
5 6 (mini [(distanca direkte 1-6)(4.5+d5-6)] ( (4.5+2) min=6.5
Sic shikohet nga rezultati, bashkesia e nyjeve N{ } eshte bosh qe do te
thote qe te gjitha nyjet jane kapur sipas nje logjike renditese tek
bashkesia Q { } e internerareve, kjo bashkesi mund te jete vlere kostoje
ose vlere distance etj.
Levizja neper Graf, sipas logjikes me minimumin e levizjes, rezolton kjo
kapje e bashkesise se Nyjeve, ne bashkesine Q te Intinerareve me 2
elemente, ose me intenerare, te cilat konkretisht jane
Intinerari i pare 1-4
Intinerari i dyte 1-2-3-5-6
Me poshte po japim grafikisht grafin e dimensionuar, te trajtuar me siper,
se bashku me logjiken e kapjeve te nyjeve


figura qe tregon menyren e ndertimit te vektoreve



Disa karakterristika te grafeve

Ne nje graf do ta quajme Rruge kalimi ose intenerare, nje lidhje te harqeve
ne te cilin nyja fundore e harkut, cilido, koincidon me nyjen fillestare te
harkut ndjekes ose pasues. P.sh. ne grafin e mesiper lidhja
(5,1);(1,4);(4,3);(3,5) eshte nje intenerar.
Nje ruge kalimi quhet e mbyllur "me lak" n.q. se nyja finale e
rruges se kalimit perputhet me ate fillestare.
Nje rrugekalim quhet me mungese laku n.q.se asnje pjese e tij nuk
perben lak, d.m. thene se nje nyje, nuk eshte njeheresh fillim dhe
fund i nje harku.
P.sh.ne figuren tone kemi :
Intenerari (5,1);(1,4);(4,3);(3,5) eshte nje lak
Intenerari (2,1);(1,4);(4,3);(3,5) ka mungese laku
Ne te ardhme edhe pa e perdorur termin, do te referohemi gjithnje
intenerarit te privuar nga harqet Lak. (keto jane pothuaise te perhershme
ne projektet e transportit, per efekt eficenses ekonomike.)
Nje graf, ne te cilin c'do nyje eshte e lidhur me anen e nje harku, me
sejcilen nyje, quhet komplet i lidhur. Keto grafe, jane grafet qe
perdoren per te perfaqesuar sistemet e transportit ajror ose detar. Ne
nje hapsire te caktuar gjeografike. Ne kete rast nyjet jane aeroportet,
ose portet dhe harqet jane lidhjet ajrore, ose detare, midis tyre.
Nje graf quhet i lidhur n.q.se ne c'do nyje eshte origjina e te pakten
e nje intenerari qe ka si ekstrem nje nyje c'fardo te grafit.
Grafet qe perdoren per paraqitjen e sistemeve te transportit jane shpesh jo
komplet te lidhur.
Nje graf (ne te cilin nuk eshte prezent asnje lak) ne te cilin ekziston
nje intenerare i vetem, qe lidh nje nyje (i) me c'do nyje tjeter quhet
pema me rrenje i
Nje peme e siper treguar, eshte shembulli i grafeve jo te lidhur. N.q.se ne
nje graf eleminojme ndonje nyje dhe harqet e te cileve iu perkasin keto
nyje, atehere perfitohet nje nengraf i grafit te dhene.
Ne nje graf ku shenojme, pemet, duke pasur si origjine nyje te ndryshme, do
te perfitonim shembuj grafesh te pjeseshem. P.sh. duke iu referuar grafit
ne figuren e mesiperme, grafet e ndertuara nga harqet
(2,1);(1,4);(2,5);(5,3), te perfituar nga grafi fillestar, si dhe duke
hequr te gjithe harqet e tjere, eshte nje graf i pjeseshem, qe krijon nje
peme me rrenje 2
Numuri i intenerareve (pa leqe) qe mund te dallojme ne nje graf, eshte i
fundem.
Ne rrjetat e transportit jane vene ne dukje vetem rruget e kalimit, qe
lidhin cifte nyjesh, te cilet fillojne e mbarojne zhvendosjet. Nyje te
tilla, sic do te shohim me vone, do te quajme qendra. Per nje graf te
dhene, me nje numur te caktuar nyjesh qender, eshte e mundur te numurohen
te gjithe rruget e kalimit te mundeshme pa leqe, duke pasur nyje qendre, si
nyje fillestare dhe fundore.
N.se i dhe j jane dy qendra, mund te percaktojme bashkesine e rrugeve te
kalimit te lidhura (i) e (j), bashkesia e rrugeve te kalimit I ij , duke
patur (i) si nyje fillestare dhe (j) si nyje fundore.

Teknika e ndertimit te nje rrjeti

Rrjeti, eshte grafi i cili harqet posedojne nje karakterikstike sasiore.
C'do hark i nje grafi i perdorur per te prezantuar nje sistem transporti,
karakterizohet nga koha e levizjes dhe nga treguesit te tjere, qe
konkretizojne perdoruesin e sistemit te transportit, per levizjen nga nje
nyje e harkut tek tjetra, te gjitha keto marrin pjese, ne percaktimin e te
ashtuquajtures Kosto e Tansportit te harkut. Elementet qe perbejne koston e
transportit jane madhesi te karaktereve te ndryshme, pra jo homogjene p.sh.
koha/ kostoja monetare/ stresi/ etj d.m. se kostoja eshte nje vektor, dhe
keto elementet jane komponente te tij. Megjithate kostoja gjithnje
konsiderohet si nje madhesi skalare, sepse ose merret ne konsiderate vetem
koha e levizjes, ose te gjithe komponentet homogjenizohen. Nga ana tjeter,
ne i referohemi gjithmone perdoruesit mesatare, keshtu qe kostoja e nje
harku te grafit, merret konstante per te gjithe perdoruesit e tjere

Vektori i kostos se harkut

Do te gjuajme nje vektor (C tek i cili komponentet cij jane emertuar nga
kostoja e transportit te harkut (ij). Vektori i kostos se grafit do te kete
dimensionin (nLX1).
Numuri i perdoruesave qe perdorin sistemin e transporit, (kerkesa per
transport) ndryshon ne kohe (sic do te shohim me vone). Ne pergjithesi nje
sistem transporti studiohet duke iu referuar nje intervali kohore, me te
cilin funksioni i tij eshte konstant, qe do te thote, se shmangjet
rastesore te numurit te perdoruesave te jete konstant dhe I pranueshem. Ne
kete rast numuri mesatar i perdoruesave, qe ne intervale te vogla kohe te
njepasnjeshme, te supozuar si te njesishme, pershkruajne harkun e nje
grafi, perfaqesues te nje sistemi transporti, I cili eshte konstante. Ky
numur quhet ndryshe edhe fluksi i harkut
Fluksi gjithmone konsiderohet si nje madhesi skalare, n.q.se perdoruesit
qe e perbejne jane jo homogjene, ato homogjenizohen mesatarisht duke
perdorur koeficente te pershtatshem te transformimit.

Vektoret te fluksit te harkut

Perkufizohet vektori (f me dimesionet (n L x1), komponentet e tij (fij)
jane krijuar nga fluksi mbi harkun (ij) . Ndonjehere ne te ardhmen ai do te
tregohet me nje indeks te vetem, me te cilin eshte e mundur te shoqerohet
me nje numer per sejcilen kapje te nyjeve, d.m. se fluksi mbi harkun i do
te tregohet fi. Konceptet e kostos se transportit dhe i fluksit, mund ti
referohen edhe "rruges se kalimit" / intenerarit.
Do te quajme kosto e transporti te rruges se kalimit, koston (e
pergjithesuar ) e mbajtur nga perdoruesi mesatar, per te kaluar nje
intenerar te cktuar. Zakonisht supozohet qe kostoja Ck e nje rruge kalimi,
te pergjithshme k, jepet nga shuma e kostove te harqeve qe e perbejne ate
rruge kalimi. Duke kujtuar perkufizimin e matrices se varesive Harqe-
Rrugekalim mund te shkruajme
Ck = ( aki * Ci kostojaa e harqeve (i)
Ose ne forme matricore
C = (A * c ku

C eshte vektori i kostove te rrugkalimit me kompponente Ck
A eshte matrica e transformuar te varesise Harqe-Rruge
c eshte vektori i kostove te harkut

Vektore te fluksit te rruges te kalimit

Do te quajmme vektorin (F, komponentet e te cilit Fk jane krijuar nga
numuri i perdoruesave (i homogjenizuar) qe e pershkruajne intenerarin k, ne
njesine e kohes. Fluksi qe pershkruan nje hark i, eshte shuma e flukseve te
rrugeve qe perdorin kete hark. Duke perdorur matricen e varesise Hark-Rruge
mund te shkruajme:
fk= ( aik Fk
Ne forme matricore
f = A * F
kostoja e transportit, ne lidhje me sejcilin hark te grafit, eshte ne
pergjithesi funksion si i fluksit, qe e pershkruan kete hark, ashtu edhe i
atyre qe pershkruajne harqet e tjere te grafit, (sic do ta shohim me vone).
Nje funksion i tille skalar Ci(f), pergjithesish me shume variabla, i jepet
emri funksion i kostos dhe eshte karakteristike sasiore qe e kthen nje
graf ne nje rrjet te transportit , pra me perkufizim.
Rrjet transporti, eshte bashkesia T e perbere nga bashkimi i bashkesive N
te nyjeve, bashkesia L e cifteve te nyjeve qe i takojne bashkesise se
linjave, dhe nga nje bashkesi Fc e funksioneve te kostos per sejcilin
element te bashkesise L
T= (N,L,Fc)

Skematizimi i nje sistemi ofertash per transport, nepermjet nje rrjeti

Teoria e rrjeteve, si dhe algoritmet qe derivojne per kete teori, formojne
nje instrument teorik adapt dhe shume efikas per projektimin e studimin e
nje sistemi transporti. Nje rrjete eshte efektivisht nje pershkrim i
thjeshtezuar i fenomenit te komplikuar, rreal. Ndertimi i nje rrjete kalon
neper disa operacione, te cilat paraprakisht duhet te grupohen sipas
problematikave: Siperfaqja e studimit/ zonifikimi i siperfaqes/ permbledhje
e perafert e grafit te realitetit fizik/ individualizimi I pozicioneve ne
hapsire dhe kohe te perdoruesave per sistemin rreal/ si dhe funksionet e
kostos per elementet e transportit. Sa me siper eshte e thjeshte nderttimi
i nje rrjeti, kur behet fjale per nje transport detar apo airor, ne kete
rast veshtiresia eshte ne percaktimet e mesatareve te orevonesave apo te
cikleve kohore etj. Veshtiresite e medha per ndertimin e nje rrjeti, jane
kur kemi raste te nderthurjes se llojeve te transportit, si dhe te formave
te infrastruktures. Kjo baze sherben per vleresimet sasiore dhe cilesore te
nyjeve dhe harqeve, kombinacionet e te cilave japin sistuatet, ose modelet
e grafeve, dhe rrjetave te prezantuar me siper. Ne pergjithesi, ndertimi i
nje modeli rrjeti, kalon nepermjet nje serie operacionesh, per te cilet, me
poshte do te pershkruajme kriteret e pergjitheshme.
Persa i perket nyjeve mund te dallojme per nje siperfaqe:
a) vleresimet ne siperfaqe per nyjet qender.
Perfaqesojene nyjet, ne te cilat ipotezohen levizjet e koncentruar per
hyrjet dhe daljet ne c'do zone e trafikut (ose e intenerarit)
b) vleresimet per nyjet reale
Perfaqessojne ato nyje te cilat fizikisht, ne terren paraqesin pozicione
fikse
Persa i perket harqeve, per nje rrjet transporti, c'do njera korespondon
njesise se fluksit ne nje drejtim perdorimi, me te njejtat karakteristika,
konkretisht :
harqet rreale
Pefaqesojne bashkimet e dy nyjeve reale
harqe fiktive
Perfaqesojne ose c'faqen kur basshkojne nje nyje qender te zones me nje
nyje rreale kur keto nuk ekzistojne aktualisht po e njejeta

A) Kufizimi i zones se studimit

Ne kete faze percaktohen zonat gjeografike me te cilan gjendet sistemi i
transportit ne studim,( sistemi ne projekt), ose me te cilin do te
trajtohen hollesisht, pjesa me e madhe e efekteve te nderhyrjeve te
projektuara. C'fare gjendet ne pjesen e jashteme te kordonit te supozuar,
qe kufizon zonen e studimit, perben ambjentin e jashtem te atij, ne ket
rast, ne na intereson vecanerisht, nderlidhjet me sistemin ne projekt.
Zona e studimit mund te jete I gjithe vendi ne rastin e studimeve te nje
plani nacional per transportin, por mund te jete dhe nje pjese e rrjetit
rrugore, me te cilin tentohet, nje nderhyrje ne shfrytezim.

B) Zonifikimi

Zhvendosjet qe ndikojne ne nje zone te dhene mundet ne pergjithesi te
fillojne dhe mbarojne ne ne pike c'fardo te teritorit. Per trajtimin e
fenomenit eshte permbi te gjitha e nevojhme nendarja e zones se studimit
(dhe eventualisht zona e brendeshme e saj) ne zona trafiku , midis se
cileve zhvillohen zhvendosje qe I perkasin sistemit te projektimit.
Zhvendosje te tilla quhen zhvendosje nderzonave, ndersa per zhvendosje
zonale zhvillohen zhvendosje qe fillojne dhe mbarojne ne brendesi te se
njejtes zone te trafikut.
Zonat mundt te jene te ndertuar nga i gjithe qyteti, ose grupe qytetesh, ne
planin nacional, deri ne zona te vogla, ne planin e trafikut urban.
Perderisa objektivi i zonifikimit eshte te perofroje te gjitha pikat e
fillimit dhe te mbarimit te zhvendosjeve zonale ne nje pike te vetme
(qendra e zones). Kriteri teorike qe do te ndiqet per zonifikimin eshte,
individualizimi i pjeseve te tilla te zones se studimit, per te cilat
koncentrime te tilla paraqesin hipoteza te pranueshme. Nga pikpamja
praktike, si ato, te nohjes se zones se studimit, egzistojne mundesi te
ndryshme zonifikimi per te nejtin problem, nendarja e zones se studimit ne
nje numer te madh zonash, zakonisht con ne nje prezantim me te sakt te
fenomenit real, por edhe nje ngarkese te madhe per skematizimin e
simulimeve te sistemeve te transportit. Kriteret praktike, per arritjen e
nje kompromisi te mire, midis nevojave te ndryshme, varen akoma edhe nje
here nga tipi i vecante i planit. Edhe ambjenti i jashtem i zones se
studimit, zakonisht ndahet ne zona me te gjera, ( medha ) se sa ato te
brendeshme, te zones vete. Zonat e jashme, na interesojne vecanerisht si
zona me te cilat fillojne e mbarojne zhvendosja, qe zhvillohen (te pakten
pjeserisht) , ne brendesi te zones se studimit. Zonofikimi konsiston ne
nendarjen e zones se studimit, ne zona te trafikut, ne menyre qe origjinat
dhe destinacionet e zhvendosjeve e sejciless zone, te hipotezohen te
koncentruara ne jne pike te vetme te quajtur qender e zones ose qendra e
brendeshme. Edhe per origjinat dhe destinacionet e zhvendosjeve jashte
zones se studimit, hipotezohen te perqendruara ne qendra te jashteme

C) Nxjerrja e grafit

Nyjet e nje grafi te perdorur per prezantimin e nje sistemi transporti
tregojne pozicione ne kuptimin me hapsiren e ne kohe me te cilin mund te
vijme e te gjejme nje perdorues te sistemei te transportit . Keshtu dy
nyjet te lidhura nga nje hark, mund te tregojne dy pika te teritorit te
bashkuara nga nje rruge . Ata kane koordinata te ndryshme gjeografike dhe
kohore perdrisa egziston koha e zhvendosjes nga nje nyje ne nje tjeter. Dy
nyje te lidhura nga nje hak, mund te kene edhe te njejtat koordinata
gjeografike dhe ndryshojne vetem nga ato kohore, sic ndodh kur dy nyjet
tregojne situata te ndryshme ne te cilen gjendjet nje perdorues i sistemit
te transporti, ne castin me te cilin ai arrin nje pike te caktuar (p.sh.
nje terminali i transportit puplik) dhe atehere me te cilin ai largohet. Si
rrjedhim harqet mund te tregojne realitete fizike te ndryshme, nje
infrastrukture (rrugore ose hekurudhore) qe lidh dy nyje, ekzistenca e nje
sherbimi e ofruar nga nje mjet i pershtatshem i transportit , por jo ajo e
nje infrastrukture lidhese, dy gjendje te njepasnjeshme me te cilin, ne te
njejten vend gjeometrik, por ne kohe te ndryshme, mund te vijne e te gjejne
perdorues (p.sh. ardhja ne je modelim te autobuzit dhe ngjitja ne makine
pas nje kohe te caktuaar pritjeje )
Mbi bazen e karakteristikave te ndryshme eshte e mundur qe te bejme ndarjen
e bashkesise se nyjeve N dhe te harqeve L ne nenbasshkesi:
Per sa thame me siper problemi I skematizimit te nje sistem transporti
nepermjet nje grafi ose, sic mund te themi, nxjerrja e grafit, nga
rrealiteti fizike, konsiston ne thelb ne percaktimin e ketyre pozicioneve
hapsire/kohe perdoruesave qe ndalojne qellimisht ne menyre te detajuar ne
analizen e sistemeve te transportit real dhe harqeve qe I lidhin.
Ky operacion ka gradee te ndryshme teveshtiresise ne pershtatje me sistemin
ne projektim. Ne vazhdim do te jepen disa shembuj te ndryshem ne lidhje me
nxjerrjen e grafit per sisteme transporti te caktuar.
Skematizimi eshte ne pergjithesi mjaft I thjeshte kur flitet per nje sistem
transporti detar ose ajrore qe sherben ne nje zone te caaktuar, nyjet jane
portet ose aeroportet dhe harqet jane udhet qe lidhen midis tyre . N.q. se
marrim ne konsiderate kohen e pritjes ne porte ose aeroporte te ndryshme
dhe se keto kohe nuk jane te paperfillshme krahasuar me kohen e udhetimit ,
porti ose aerroporti do te percaktohen nepermjet dy nyjeve qe paraqesin te
njejten pike fizike por karakterizohen nga kohe te ndryshme, ajo e mbritjes
dhe ajo e nisjes. Ne hakun qe I lidh do te vendoset kostoja e pritjes.
Eshte shume e thjeshte te perfitosh nje graf qe paraqet nje sistem
transporti tokesore, kur ky eshte I perbere nga nje menyre e vetme
transporti, p.sh. mjeti hekurudhore. Ne kete rast, nyjet jane pikat me te
cilat flukset emetohen ose dalin nga sistemi I infrastruktures (stacionet
hekurudhore, qe mund te jene qendra edhe si qendra) dhe atyre ne te cilet
infrastrukturet I intersektohen me njera tjetren, dhe harqet jane deget e
ndryshme hekurudhash qe lidhin
Skematizimi I jne sistemi transporti rezulton shume kompleks kur ehste
perbere nga shume menyra transporti (p.sh. hekurudha tramvaj, autobuza
etj) si dhe nga infrastruktura te niveleve te ndryshme cilesie sic ndodh ne
pergjithesi ne zonat urbane dhe metropolitane.
Ne rastin e sistemeve urbane dhe metropolitane eshte e mundur te ndertosh
nje graf shume te detajuar te sistemit te transportit ne nje zonim shume
te imet deri ne izolimin e nje elementi te vetem, ose duke marre ne
konsiderate , paraqitjet me te komplikuara (agregate) me zona me te medha
dhe ne nje graf me me pak harqe.
Ne pergjithesi ne nxjerrjen e nje grafi merren ne konsiderate pikat e
zhvendosjes nga nje menyre transporti ne nje tjeter , keto pergjithesisht ,
paraqiten nga shume nyje qe percaktojne te njejten vend fizik por
karakterizohen nga kohe te ndryshme ajo e arritjes ne kete vend me nje
menyer transporti dhe ajo e nisjes ne menyre pasqrdhese dhe eventualisht
nga cmimi I perdorimit te menyres se daljes. \shembuj tipike te kesaj
menyre paraqitje jane ndalesat e autobuzave urbane ku e ka fundin nje rruge
kembesore dhe fillimin nje rruge me menyren e transportit publik dhe kur
mbi harkun qe I lidh dy nyjet vendoset koha e pritjes ne ndalese dhe
kostoja e biletes, ose stacionit hekurudhore ku pranohet kembimi midis
mjeteve peersonale dhe hekurudhore.
Jo gjithmone ne nxjerrjen e grafit eshte e nevojshme I njejti nivel
drejtimi , sic u tha dhe me siper menyra me te cilen grafi do te nxiret nga
nje realitet teritorial (ne vecanti urban) varet nga objektivi I studimit.
Nje przantim I detajuar eshte I nevojshem kur I referohemi nje realiteti
teritorial te dimensioneve modeste, d.m. thene kur p.sh. duhet te
projektohet nje plan I ushtrimit te autobuzave ne nje lagje urbane . Ose
kur I referohemi ne nje zone te tere urbane nje skematizem shume I
detajuari sistemit te transportit nuk duhet te perdoret per dy arsye :
1) Do te duheshin nje numer shume I madh elementesh te se njejetes (nyje
dhe harqe), edhe per zona urbane te vogla , dhe keshtu veshtiresi te
shumta te llogaritjes.
2) Do te duhej te rrezikohej po te futeshin analizen e sistemit te
transportit edhe gabime te medha te cilet lidhen me nje rrjet shume
te detajuar, ne vecanti per sa I perket cmimit te kerkeses per
traansport .
Ne nje mjet transporti c'do hark i korespondon nje fluksi i vetem, me nje
hark kohore i perdoruesave me karakteristikat dalluese, keshtu p.sh.nje
rruge dy drejtimeshe mbi te cilinudhetojne vetem autobuza private paraqiten
nepermjet nje qifft harqes me drejtime te kunderta. por nje rruge
njedrejtimeshe mbi te cilen udhetojne autobuza private dhe automjete
publike paraqiten nepermjet nje harku perkates te autoveturave private dhe
nje harku per sherbimin publik ose per sejcilen vije ne varesi te nivelit
te detajizimit te perdorur. Nese ne te kundert duhet te vendosen ne
kategori te ndryshme perdoruesit qe perdorin te njejten infrastrukture
p.sh. sipas shkakut te udhetimit, ose tarifes se paguar se njejtes
infrastrukture fizike, e cila i bashkengjitet nje hark per c'do kategori
perdoruesish.
Ne figure jane sjelle grafet e rrjetit rrugore dhe te transportit publik
per nje pjese te zones urbane. Po atu ne figuren e meposhteme eshte
paraqitur nje pjese e grafit shumemodulesh per gjithe vendin, per nje plan
te pergjithshem te transportit .
Nga sa thame me siper eshte e dukshme qe operacioni i trafikimit dhe i
nxjerrjes se grafit jane shume te lidhur me njera tjetren. Niveli i
zonifikimit duhet ne fakt te perputhet me nivelin e paraqitjes te sistemit
real dhe e anasjellta, per me teper ne vcanti ne zonat urbane struktura e
sistemit te transportit ekzistues dhe atij te projektuar, do te
influencoje ne mase te konsiderueshme zonifikimin e zones se studimit.

D) Funksioni i kostos

Kostoja ( e pergjitheshme) e kalimit te nje harku ne graf te nje sistemi
transporti eshte elementi qe lejon te kalohet nga grafi, tek paraqitja me
rrjet, e nje sistemi transporti. Ne pergjithesi ne mjete e transportit
private ku ne shume raste qarkullojne edhe mjete publike kostoja e kalimit
te nje harku, eshte nje rrelacion matematikor qe jep ose perfaqeson koston
mesatare te transportit per fluksin, sigurisht qe varet nga numuri I
perdoruesave qe e perdorin harkun vete dhe harqe te tjere te rrjetit.
Komponentet qe perbejne koston e kalimit te nje harku, jane komplekse, por
ne perafrojme ne nje limit duke i konsideruar si te homogjenizuar, dhe i
vetmi faktor viziv, mbetet koha, per te cilen vleresohet si nje kohe
mesatare e harkut. Ne fakt, kjo kohe, prezantohet ne kohen e levizjes
urbane dhe dhe kohen e levizjes extraurbane, kjo e fundit perfshin nocionet
e nderhyrjes me rrjetat e tjere.

Teknikat e sgjidhjes se nje rrjete te ndertuar per nje sistem transporti

Per zgjidhjen matematikore qe propozohen te kryhen mbi rrjetat e sistemeve
te transportit, ose shkurt do ti permendim rrejtat e transportit, jane
Algoritmi sipas "Dijkstras";"Gjenerimit te pemes" etj.