Optimalizálás és GIS¹

Dr Sárközy Ferenc

sarkozy@agt.bme.hu

Összefoglalás

Az optimalizálási feladatok összekapcsolása a térbeli tervezés munkaeszközeivel a térinformatika egyik legfontosabb megoldandó feladat csoportja. A tanulmány megvizsgálja a legfontosabb alkalmazás típusokat, felvázolja a rendelkezésre álló optimalizálási technikákat és megpróbálja kijelölni a GIS funkcionális kereteinek szükséges bővítését ahhoz hogy az optimalizálási feladatok a GIS elemző-tervező eszközeinek szerves részévé váljanak.

Kulcsszavak: térbeli tervezés, optimalizálás, GIS függvények

1. Bevezetés

A műszaki, gazdasági, szervezési feladatok általában több féle terv alapján oldhatók meg. Előfordulnak azonban olyan esetek, amikor az elvégzendő feladat a kor műszaki (vagy gazdasági) teljesítményének maximumát igényli ahhoz, hogy egyáltalán megoldható legyen. Ez volt a helyzet – műszaki vonatkozásban - a kozmosz meghódításának hajnalán, vagy gazdasági téren az amerikai piacgazdaság átállításakor központi irányítású tervgazdasággá a II. Világháború eredményes megvívása érdekében.

Lényegében ez utóbbi eseményhez kapcsolhatjuk a különböző optimális tervezési feladatok gyakorlati alkalmazott tudománnyá válását operáció kutatás névvel. Meg kell azonban jegyeznünk, hogy a gyakorlati feladatok jelentős számítás igénye miatt az operáció kutatási módszerek széleskörű elterjedését a számítástechnika gyors fejlődése tette lehetővé.

A GIS megjelenésének egyik kifejezett célja a térbeli elemzés volt, ami tulajdonképpen nem más, mint a térbeli tervezést előkészítő és alkotó lépések összefoglaló elnevezése. Ha tehát a GIS egyik legfontosabb feladata a térbeli tervezés elősegítése, úgy kézenfekvő, hogy ez alatt a folyamat alatt optimális tervezést kell értenünk, azaz a térbeli tervezési folyamatban az optimális tervezés eszközeivel is rendelkeznünk kell.

Nem szabad ugyanakkor elfelejtenünk, hogy a térbeli tervezési feladatok gyakran igényelnek különböző modellező algoritmusokat, melyek bár bemenő adataikat a GIS állományaiból nyerik, maguk különböző lazasággal kapcsolódhatnak a GIS szoftverhez, szoros kapcsolat hiányában pedig az optimalizálás tulajdonképpen a tervező modul és nem a GIS szoftver tulajdonsága.

Ha azonban az utóbbi tíz év szoftver fejlődési tendenciáiból indulunk ki, úgy joggal várhatjuk, hogy a GIS szoftverek olyan nyílt rendszerekké válnak, melyek szabadon bővíthetők különböző tervező modulokkal, ugyanakkor az optimalizáló eszközök egyre inkább az alap szoftver részeivé válnának.

2. A GIS és az optimalizálás kapcsolat típusai

Amint a bevezetőben már láttuk a mindenki számára kézenfekvő kapcsolat a GIS és az optimalizálás között a térbeli tervezésben nyilvánul meg. A térbeli tervezés során, felhasználva a GIS rétegekhez (objektumokhoz) rendelt attribútumokat a tervező modul meghatározza a tervezett létesítmény viszonyát a kérdéses rétegekhez (objektumokhoz), majd a GIS eszközei segítségével megjeleníti az eredményt egy réteg (objektum) formájában. Jól illusztrálja ezt a legáltalánosabb kapcsolatot például az IDRISI szoftver PATHWAY modulja, mely adott kezdő pont, súrlódási felület és cél esetén meghatározza és rétegként megjeleníti a „legrövidebb” utat.

Talán kevésbé közismert, de a széles felhasználói körök által eredményében igen gyakran használt optimalizálás az automatikus térkép-generalizálás szerves része. Ez viszont elkerülhetetlen az igény alapú térképezést realizáló webes alkalmazásokban.

Eredeti kapcsolat kialakítására tesz javaslatot az optimalizálás és GIS között E. Rolland és R. Gupta [1]. Elképzelésük szerint, a GIS szoftverek alkalmasak arra, hogy segítségükkel a kombinatorikus optimalizálás bizonyos paramétereit a felhasználó interaktívan határozza meg a GIS segítségével. A hivatkozott tanulmány bemutatja, hogy a szerzők által létrehozott grafikus interfész segítségével miként vezérelheti a felhasználó a p-medián hozzárendelési feladat „tabu keresés” szerinti megoldását. Az elképzelés jelentősége, véleményem szerint, abban van, hogy rámutat arra, hogy a térbeli feladatok kezelése valóban eredményesen csak a GIS-en belül valósítható meg.

3. Néhány gyakori feladat típus

Ha eltekintünk a térkép generalizálás érdekében végrehajtott optimalizálási feladatoktól, úgy a térbeli optimalizálás színtere vagy egy hálózat vagy a pixelekkel modellezett kvázi folyamatos síkbeli tartomány lehet.

Maga a hálózatos megközelítés is vagy generikus vagy csak a számítási módszereket támogató fogalmi modellként jelentkezhet.

Bizonyos, elsősorban közlekedési feladatok esetében a hálózatos megközelítés természetes követelmény, hiszen a modellek a feladatok lényegét hálózatos környezetre vetítve képesek megfogalmazni. A legegyszerűbb példaként erre az esetre két pont (postai cím) közötti optimális útvonal megtervezését említhetjük, ahol az optimalizálásnak azt kell meghatároznia, hogy a jármű a csomópontokban milyen útszakaszokat válasszon annak érdekében, hogy a szakaszok összege valamilyen tulajdonságra (például a megtételéhez szükséges időre nézve) optimumot biztosítson. Ebben az esetben tehát a csomópontokból nem lehet tetszőleges irányba fordulni, hanem csak azoknak az utcáknak valamelyikébe melyek a kérdéses csomópontból indulnak ki, és melyeket a hálózati modellben ívek (vagy gráfelméleti terminológiával élek) reprezentálnak.

Más a helyzet akkor, ha optimális útvonalat szeretnénk tervezni a terepen. Bár ebben az esetben is alkalmazhatunk a tervezéshez hálózati modellt ez a modell képzetes hálózat lesz mivel csak azért alkalmazzuk, hogy a számításhoz a hálózati útkereső algoritmusok felhasználhatók legyenek. A valóságban ugyanis a tervezett út bármely pontjában tetszőleges irányba fordulhat el, csak a számítási modellünk korlátozza az elfordulási pontokat a raszter cellák középpontjaira, illetve az e pontokból elvégezhető elfordulásokat a 8 főirányra.

Folyamatos raszter terekkel általában a földhasználati optimalizálások dolgoznak. Ezekben a módszerekben a különböző célokat úgy nevezett hasznossági térképek reprezentálják, melyek cella értékei arányosak a kérdéses cella jóságával az adott célra. A problémát az okozza, ha olyan területtel is találkozunk, mely több kitűzött célra is alkalmas. További problémát jelenthet az is, ha az egy célhoz rendelt területre alaki, folytonossági, területi megkötéseket is igyekszünk érvényre juttatni.

A földhasználati optimalizálás speciális típusa az optimális mezőgazdasági művelési mód hozzárendelése a táblákhoz [2]. Ebben az esetben a mezőgazdasági nagyüzemek táblái olyan rögzített vektoros objektumok, melyek különböző tulajdonságokkal jellemzett részobjektumokból épülnek fel. Az optimalizálás feladata annak az eldöntse, hogy az üzem egyes tábláin az adott agroklimatikus viszonyok között észszerűen alkalmazható művelési fajták közül mit alkalmazzanak. A modell kutatásaink szerint tovább fejleszthető földrendezési feladatok optimalizálására is, mely témával részletesen külön publikációkban foglalkozunk [16].

A továbbiakban ismerkedjünk meg a hálózatokra, raszteres terekre és tábla-objektumokra alkalmazható legfontosabb optimalizálási feladatokkal.

3.1 A p-medián modell lényege és legfontosabb alkalmazási területei

A vizsgált hálózatban P darab ellátó központ szerepel, mely feladata, hogy N darab felhasználó igényeit kielégítse. A feladat úgy elhelyezni a hálózati csomópontokon a P darab ellátó központot, és úgy hozzákapcsolni a központokhoz a felhasználókat, hogy a felhasználók igényei kielégítésre kerüljenek, s e mellett az igények súlyozott összege minimális legyen. Súlyként az ellátó központ elérhetőségét tekintjük, mely legegyszerűbb esetben a felhasználó és a számára kijelölt központ euklideszi távolsága. A feladat egyik variánsában (kapacitásos p-medián probléma) adottnak tekintik az ellátó központok kapacitásait is.

A feladat alkalmazásra kerül gyárak, raktárak elhelyezésénél, amikor a feladat a piaci igények optimális kielégítése, de alkalmazásra kerülhet a modell a közösségi ellátás területén is iskolák, kórházak, postahivatalok helykijelölésekor, vagy az utak jégtelenítéséhez használt só-depóniák elhelyezésének megtervezésekor [3].

A kapacitásos p-medián probléma az alábbi kifejezésekkel írható fel [1]:

ahol a_i – az i csomóponton fellépő igény, c_j – a j csomóponton lévő ellátó központ kapacitása, d_ij – az i csomóponttól a j csomópontig tartó távolság, P – az ellátó központok előre megadott száma, x_ij értéke 1, ha az i csomópont hozzá van rendelve a j ellátó központhoz, különben 0, y_j értéke 1, ha a j ellátó központ nyitva van, egyébként 0.

Az (1) célfüggvény minimalizálja az igények és a kielégítésükre létrehozott kapcsolat-távolságok szorzat összegét. Természetesen a távolság helyett egyéb, az elérést megnehezítő tényezőt is használhatunk a súlyozásra. A (2)-ben röviden leírt i darab korlátozás biztosítja, hogy minden igény csomópont csak egy darab ellátó központhoz legyen kapcsolva. A (3) korlátozás segítségével azt érjük el, hogy az igények csak nyitott ellátó központhoz legyenek kapcsolhatók. A (4) korlátozás biztosítja, hogy pontosan a megadott P számú ellátó központ legyen nyitva. Az (5)-el jelölt korlátozások veszik figyelembe, hogy minden ellátó központ csak előre meghatározott kapacitással rendelkezik. Ha az ellátó központok kapacitása nincs korlátozva, az (5) elhagyandó. A (6) korlátozások gondoskodnak arról, hogy a döntési változók egészértékűek legyenek.

Ha a feladatot megoldjuk, úgy eredményképpen meg fogjuk kapni, hogy mely csomópontokon van ellátó központ (amilyen j értékekre y_j= 1) és hogy melyik igényt jelentő csomópont melyik ellátó központhoz lesz kapcsolva (az összekapcsolásokat azoknak az x_ij –knek az indexei mutatják, melyek egyenlők 1-el).

Lineáris súlyok esetén, a feladat megoldására legalkalmasabbnak tekintett szigorú optimalizálási módszerrel, a Langrange féle relaxációval, mintegy 800-900 csomópontig lehetséges a megoldás [3]. A nagyobb feladatok megoldása - legalább is egyelőre - különféle heurisztikus eljárással végezhető el.

A heurisztikus eljárások az emberi gondolkodás módszereit hasznosítva olyan ötletek algoritmikus megvalósítását jelentik, melyek jó esetben gyors és hatékony megoldást szolgáltatnak, de nem garantálják a globális optimumot, azaz a legjobb megoldást. Az utóbbi másfél évtizedben a térbeli elhelyezési feladatok megoldására több heurisztikus eljárás számtalan variációját dolgozták ki a kutatók. Ezek közül is a p- medián feladatot legeredményesebben a tabu keresés módszerének különféle variációival oldották meg. Hasonlóképpen használják még a genetikus algoritmust és a szimulált hőkezelés (simulated annealing) módszerét is. Az előbbivel egy későbbi fejezetben, a földhasználatok táblákhoz rendelésével kapcsolatban fogunk megismerkedni.

3.1.1 A Tabu Keresés [4]

A tabu keresés, mint minden iteratív módszer egy kezdeti megengedett megoldásból indul ki. Megfelelő paraméterezés esetén elvileg a kezdeti megoldás nem befolyásolhatja a végeredményt. A gyakorlat azonban azt mutatja, hogy érdemes a feladat konkrét modellezésével külön heurisztikus eljárást kialakítani a kezdeti megoldás megválasztására, mivel a jó kiinduló megoldás nagymértékben meggyorsíthatja az optimumkeresési folyamatot. A kapacitásos p-medián feladat esetében például a kezdeti megoldást úgy határozhatjuk meg, hogy az N igény csomópontot P klaszterba soroljuk oly módon, hogy a klaszterenkénti összigény ne haladja meg az egyes ellátó központok kapacitását. Ezután az egyes ellátó központokat elhelyezzük a kapacitásuknak összigény szerint megfelelő klaszterek súlypontjához legközelebb eső csomóponton.

A következő lépésben kiválasztjuk a kezdeti helyzethez tartozó szomszédságot a megengedett megoldások halmazából. Ez a halmaz úgy jön létre, hogy meghatározzuk az ellátó központok elmozdulási lehetőségeit jelenlegi helyzetükből a hálózat valamely szomszédos csomópontjára, illetve a kapacitás korlátokon belül megváltoztatjuk az igény pontok hozzárendelési attribútumait az ellátó központokhoz.

Ezután megkezdjük a létrehozott tartományban a mozgásokat, minden egyes mozgáshoz kiértékeljük a célfüggvényt és minden mozgást rögzítünk a tabu listában.

A tabu lista elsődlegesen azt a funkciót látja el, hogy azokat a mozgásokat ne ismételjük meg, amelyekre a kiértékelést már elvégeztük. Ez az egyszerű megfogalmazás is utal rá, hogy a tabu keresés legfőbb gondolata az, hogy az algoritmus tanuljon az elvégzett keresések eredményeiből.

Ha a kiértékelés eredménye jobb az eddigi legjobb eredménynél, úgy új szomszédságot számítunk és a folyamat így folytatódik, amíg valamely megállási kritériumot el nem érünk.

A módszer számtalan változatában a már említett rövid távú memória mellett különböző erősséggel jelentkeznek a stratégia egyes komponensei.

Valamennyi megoldásban döntő szerepe van a tabu lista tartalmának és hosszának. A lista tartalma az aktuális változást (mozgást) jellemző attribútumok valamilyen formában történő rögzítése, például ha két csomópontot kicseréltünk úgy szerepelhet mindkét pont, de szerepelhet egy tagként a két pont uniója is. A másik paraméter – a tabu lista hossza általában 7 – 20 elem közt változhat.

A tabu keresés fejlettebb variánsai gondoskodnak a hosszú távú memóriáról is, mely elsősorban az intenzifikálás és diverzifikálás céljait szolgálja. Az intenzifikálás valamely jónak talált megoldáshoz hasonló még jobb megoldások keresését szolgálja, míg a diverzifikálás az eddig megtalált legjobb megoldáshoz nem hasonló új megoldási terek keresését.

Esetenként alkalmaznak olyan stratégiákat is, amikor két jó megoldás közt végzik lépésenként a mozgást a legrövidebb úton, átlépve az út közben talált meg nem engedett megoldásokon az úgy nevezett „alagutazás” segítségével. Ha a kiválasztott két jó megoldás hasonló volt, úgy ez a módszer intenzifikáláshoz vezet, ellenkező esetben diverzifikálást eredményez.

A helyi keresésre valamilyen ismert heurisztikus módszert használ a tabu lista módszer, ezért is nevezik meta-heurisztikus eljárásnak.

Általában a tabu keresést a kérdéses feladat gondos elemzése, modellezése alapján egyedileg szokták megtervezni, bár a legújabb időkben az OptQuest tabu keresésen alapuló megoldó program (solver) mint a kereskedelmi Crystal Ball döntés támogató Exceles szoftver modulja általános optimalizálási feladatokra is használható.

3.1.2 A váltakozó elhelyezés-hozárendelés (alternate location-allocation = ALA) eljárás [5]

Amint az előzőekben már utaltunk rá, a tabu keresés egy olyan stratégia, mely a helyi keresésre valamely heurisztikus módszert használ és az ez által megtalált lokális minimumokra támaszkodva jut el a globális optimumhoz, illetve annak közelébe.

A hosszú évek tapasztalatai azt bizonyítják, hogy az 1963-ban L. Cooper által kidolgozott ALA eljárás az elhelyezés-hozzárendelési probléma legeredményesebb helyi keresési eljárása. Az eljárás alapgondolata igen egyszerű. Az első lépésben felvesszük a P számú ellátó központot (az angol nyelvű irodalomban ezeket rendszerint NF –el jelölik a New Facility rövidítéseként. Ezután hozzárendelik az NF-ekhez a meglévő m számú fogyasztót (rövidítésük EF=Existing Facility). A következő lépésben a létrehozott hozzárendeléshez optimálisan elhelyezzük az NF-eket, azaz az ellátó központokat mozgatjuk míg a hozzárendeléseket változatlanul hagyjuk. Ezután az új ellátó központi elhelyezkedéshez elvégezzük az EF-ek hozzárendelését. A vázolt folyamatokat mindaddig ismételjük, amíg az utolsó lépés már nem okoz változást a hozzárendelésben. Ez a helyzet egy általában lokális optimumot jelent. Ezután valamely metaheurisztikus stratégiát alkalmazva, például a véletlen keresést, új helyeket jelölünk ki az ellátó központoknak és elvégezzük a helyi ALA keresést. Amikor már több lokális minimum hely áll rendelkezésünkre alkalmazhatjuk ezek között a tabu keresés korábban már felvázolt módszerét. Ilyenkor a legproblémásabb az új csomópontok mozgási szabályainak kialakítása. A mozgásokat a két legjobb megoldást eredményező helyzet között végezhetjük egy vagy több (egyidejűleg rendszerint maximum két) ellátó központ helyzetének megváltoztatásával.

Mindaz, amit eddig elmondtunk, arra az esetre vonatkozott, amikor az új pontoknak tetszőleges helyet választhattunk, az új pontok (ellátó központok) és meglévő pontok (ellátást igénylő helyek) távolságát pedig légvonalban számoltuk. Megjegyezzük, hogy bizonyos modellek a légvonalban vett euklideszi távolság helyett a koordináta különbségek összegéből megkapható úgy nevezett Manhattan távolságot használják, ez azonban további gondolatmenetünket nem befolyásolja.

A gyakorlati térbeli esetekben az ellátó központok kapcsolata az igénylőkkel a közlekedési hálózat segítségével megy végbe. Ebből viszont három dolog következik. Az első az, hogy az igény pontokat az igényt jelentő attribútum értékkel együtt hozzá kell kapcsolnunk a hálózat adatmodellel leképezett közlekedési rendszerhez. Ebben a rendszerben attribútumokkal csak a csomópontok és összeköttetések rendelkezhetnek, azaz az igény pontot vagy valamelyik csomóponttal azonosítjuk, vagy új csomópontot létesítünk az összeköttetésen.

Másodszor, az új pontok sem lehetnek akárhol hanem csak a hálózat közvetlenül címezhető helyein, azaz a csomópontokon. Ritka úthálózat esetén az új pontok helyének ilyetén korlátozása jelentősen csökkentheti a pontosságot, ezért ilyen esetekben a hálózati modell további finomítása válhat szükségessé.

Harmadszor a hálózati elrendezés esetén a hálózati csomópontok közötti legrövidebb utat az elhelyezési-hozzárendelési folyamat megkezdése előtt valamennyi csomópont párra meg kell határozni.

Míg az első és második feladat azt igényli, hogy a hálózati réteget más rétegek felhasználásával a feladatra alkalmas formájúvá szerkesszük addig a harmadik feladat meghatározásához meg kell határoznunk a csomópontok közötti legrövidebb utakat meghatározó mátrixot. Ez a mátrix esetünkben általában nem lesz szimmetrikus, mivel a `legrövidebb út’ meghatározás valójában a legkisebb impedanciájú út fogalmát takarja, az impedancia pedig két csomópont között oda illetve vissza irányban általában különböző lehet.

A következő részben megismerkedünk a legrövidebb út meghatározására szolgáló Dijkstra algoritmussal.

3.1.3 A Dijkstra algoritmus

A Dijkstra algoritmus a gráf valamely kiválasztott csomópontjától valamennyi csomóponthoz meghatározza a legrövidebb utat. Ahhoz, tehát, hogy valamennyi csomópont (P+m) között meghatározhassuk a `legrövidebb utat’ az algoritmust (P+m – 1) különböző kezdőponttal ismételten le kell futtatni.

A G = (C,E) gráf esetére (C – a csúcspontokat, E – az éleket jelöli) az algoritmus a csúcspontokat két halmazba csoportosítja: R-el jelöli azokat a csúcsokat, melyekhez már ismert a kiindulópontból a `legrövidebb út’ a többi csúcspont a C – R halmazba kerül.

Szüksége van a továbbiakban az algoritmusnak a d és pi tömbökre, melyek közül az első az egyes csomópontokra vonatkozó legjobb útbecsléseket tartalmazza, míg a második az ehhez az értékhez vezető úton a kérdéses csomópontot megelőző csomópontra mutató indexet.

Csúcspont	Megelőző pi
s	s*
u	x
v	x
x	s
y	x

1. ábra – a megelőző indexek magyarázata

A 1. ábra példájában a piros nyilak illusztrálják az indexeket. Ha valamelyik csomópontnak nincs megelőzője úgy az index saját magára mutat, ahogy ezt az s kiinduló csomópont esetében látjuk.

Az algoritmus fővonala a következő lépésekből épül fel:

d és pi inicializálása;
R beállítása üres halmazzá;
Mindaddig amíg C – R nem válik üres halmazzá:

1. rendezi a (C – R)-ben található csúcspontokat a szerint, hogy melyik aktuális távolság becslése kisebb (előre a legkisebb utána a második legkisebb, stb.),

2. a (C – R)-ben található legkisebb távolságú csúcspont – u átvitele az R halmazba,

3. az u-hoz csatlakozó, valamennyi még (C – R)-ben található csúcspont fellazítása.

A fellazítás során valamennyi u-hoz csatlakozó olyan v csomópont becsült távolság értékét megváltoztatja, mely csökkenni fog, ha az u-ból határozzuk meg azaz ha bekapcsoljuk a v útjába az (u,v) szakaszt.

A legrövidebb útkeresésre számtalan egyéb algoritmust is kidolgoztak a gyakorlati alkalmazások azonban a leggyakrabban az ismertetett Dijkstra algoritmuson alapulnak. Ez feltehetőleg a módszer hatékonyságán és egyszerű implementációján alapul. Az elmondottakat jól illusztrálja, hogy a 2.3.2 pontban bemutatásra kerülő optimális városi útvonal kijelölő rendszer is ezt az algoritmust használja.

3.2 A forgalmi viszonyok vizsgálata közlekedési hálózatokban

Az előző pontban megismerkedtünk a legrövidebb út algoritmusával egy olyan hálózatban, melynek szakaszaihoz (éleihez) kapcsolt tulajdonságai (például a szakaszok hossza) állandó. A gyakorlati útvonal optimalizálás során azonban rendszerint nem a megteendő út hosszát, hanem az utazási időt, esetleg az utazási költségeket kívánjuk minimalizálni. Ezek a jellemzők azonban nem csak az út hosszától, hanem annak állapotától és a forgalmi áramlatoktól is függnek. Ahhoz tehát hogy reálisan optimális útiterveket tudjunk meghatározni ismernünk kell az utazás időpontjára érvényes utazási időket a hálózat figyelembe veendő szakaszaira.

Mielőtt megvizsgálnánk a lehetőségeket az utazási idők meghatározására, érdemes egy pillantást vetni arra is, hogy az időpont-függő szakasz időket milyen körülmények között használhatjuk fel.

Az ezredfordulót megelőzően a hálózati modellező programot illetve jobb esetben a vele valamilyen szinten integrált GIS szoftvert csak off-line előzetes útvonal tervezésre használhatták mind a magán felhasználók, mind pedig a professzionális szállítási vállalkozások. Az ezredforduló azonban gyökeres változást hozott a felhasználási lehetőségekben. Az USA-ban, Japánban és az EU néhány országában (elsősorban Franciaországban) megkezdődőt az ITS (Intelligens Közlekedési Rendszer) koncepció átültetése a gyakorlatba, ezzel párhuzamosan világszerte, igaz különböző szolgáltatási szinten, megjelent az LBS (Hely Alapú Szolgáltatások) rendszere, mely megfelelő ITS infrastruktúra esetén biztosítja, hogy az útvonal választás (illetve a korábban már megválasztott útvonal megváltoztatása) menet közben is megtörténhessen. Bár túlnő a témánkon, de megjegyezzük, hogy a GIS-szel összekapcsolt feldolgozó szoftver ezekben az esetekben a városi központban működik és ez adja a válaszokat a mobil állomások megkereséseire (2. ábra).

Ahhoz, hogy a közlekedési hálózat áramlási képét valamilyen módszerrel modellezzük, ismernünk kell a hálózattal szemben támasztott átlagos vagy aktuális forgalmi igényeket. Forgalmi igények alatt egy olyan mátrixot értünk, mely megmutatja, hogy a hálózat melyik pontjából (kezdőpont) melyik pontjába (rendeltetési pont) átlagosan vagy adott időpillanatokban hány jármű kezdi meg az útját. Ezt a mátrixot az angol nyelvű szakirodalom OD (Origin-Destination) mátrixnak nevezi és a rövidítés kedvéért mi is ehhez az elnevezéshez tartjuk magunkat.

Ennek a mátrixnak az előállítása a hálózat elemzés különböző szintjein többféle módszerrel hajtható végre. Előzetes, kisfelbontású vizsgálatok esetén GIS felhasználásával a térbeli kölcsönhatás modell futtatásával lehet megvizsgálni, hogy a különböző földhasználati zónák (ipari övezet, kereskedelmi övezet, családi házas lakó övezet, stb.) milyen kölcsönös forgalmi igényeket támasztanak. Ebben a megközelítésben a legfőbb probléma a zónák aggregációs szintjének megválasztása, illetve a tömbnél nagyobb aggregációs szint választása esetén azoknak a pontoknak a kijelölése ahol a forgalmi igények belépnek a hálózatra. Amint már említettük ez a módszer alapvetően előzetes tervezésre szolgál, de nem csak a közlekedési hálózat tervezésére használják, hanem meglévő hálózat működésének a tökéletesítésére is olymódon, hogy a földhasználati zónák átalakításával igyekeznek a hálózat terhelését egyenletessé tenni.

Lényegesen megbízhatóbb eredményeket szolgáltatnak a forgalomszámlálási eredmények, melyeket gyakran a legkülönbözőbb automatikus forgalom figyelő elemek eredményeivel pontosítanak. Bár tagadhatatlan, hogy a forgalom modellezése szempontjából döntő jelentőségű az OD mátrix pontos és lehetőleg időfüggő kialakítása a létrehozási módszerek részletezése túlnő a jelen tanulmány témáján.

2. ábra – városi közlekedési információs rendszer tömbvázlata

A szakaszokhoz tartozó aktuális utazási idő becslésére a gyakorlat az alábbi módszereket alkalmazza:

statisztikai módszerek a korábbi, történelmi adatok fölhasználásával;
idősorok elemzése (szintén statisztikai módszerek, melyek azonban igyekeznek az adatokról leválasztani a mérési hibákat);
a paraméter nélküli regressziós analízis olyan korábbi helyzeteket keres, melyek hasonlítanak az aktuális állapotra és a korábbi hasonló helyzetek eredményeiből becsüli az aktuális utazási időt;
forgalom szimulációs modellek, melyek számítógépen utánozzák a való világ tulajdonságait;
dinamikus forgalom hozzárendelési modellek, melyek a matematikai programozás (optimalizálás) eszközeivel számítják ki a keresett szakasz- utazási időket.

Témánkból kiindulva ez utóbbi módszercsoport két megközelítését próbáljuk bemutatni a továbbiakban.

Az analitikus hálózat elemző módszerek a hálózat állapotát valamely egyensúlyi feltétel érvényre juttatásával határozzák meg. Ha a hálózatot központilag tudnánk irányítani, akkor a rendszer optimális egyensúlyt annak a feltételnek az érvényre juttatása jelenti, hogy valamennyi útvonal megtételéhez szükséges fajlagos költségek (idők) összege minimális. Megjegyezzük, hogy ennek a modellnek az alkalmazása annál inkább indokolt, minél nagyobb a központi területi vagy városi forgalomirányító központok szerepe. Ennek az a feltétele, hogy legyen ilyen rendszer és a közlekedők igénybe is vegyék a rendszer utasításait. Mivel a fejlődés egyértelműen ebbe az irányba mutat érdemes röviden megismerkedni ezzel a modellel.

Matematikailag a rendszer optimális egyensúly a következőképpen írható fel [6]

ahol az a szakasz teljes költsége (mely függ az a szakaszon haladó áramlattól f_a-tól), L az irányított élek (szakaszok) halmaza, P jelenti az összes hálózati útvonal halmazát, p egy útvonalat, W az összes OD párt, míg w egy OD párt, x_p az útvonalon haladó áramlat jelölése, d_w pedig az w OD páron fellépő igény (azaz a közlekedni akaró gépkocsik száma).

Mivel növekvő felhasználói költségfüggvényeket feltételezünk a (7) célfüggvény konvex, a lineáris korlátozásokkal megadott megengedett megoldások halmaza szintén konvex ezért az optimum feltételek a következők: minden w párra és minden p útvonalra a (8)-(10) feltételeket kielégítő x áramlatnak ki kell elégítenie az alábbi feltételeket:

ahol a p útvonalon felmerülő teljes összeg növekménye az alábbiak szerint:

ahol értéke 1 vagy 0 attól függően, hogy az a szakasz részt vesz-e a p útban vagy sem, pedig a (8) korlátozáshoz tartozó Lagrange szorzó.

A gyakorlati feladatok megoldásához ismernünk kell az OD pontok között fellépő közlekedési igények formáját, valamint a rendszerint időben mért költségek függését a szakaszon áthaladó áramlat nagyságától. E mellett azt is figyelembe kell venni, hogy az egyes szakaszoknak mi a kapacitása, milyen mértékű áramlás idéz elő torlódást, illetve a létrejövő torlódások miként változtatják meg a szakaszok megtételéhez szükséges időszükségletet.

A ma már klasszikusnak tekinthető statikus modellek esetén a forgalmi igények függetlenek az időtől, erre az esetre kidolgozott megoldások jellemzik a hetvenes, nyolcvanas éveket. Amikor azonban az Intelligens Közlekedési Rendszerek koncepciója kezdett határozottabb körvonalakat felvenni világossá vált, hogy a statikus modellek nem elégítik ki a forgalom irányító és tájékoztató rendszerekkel szemben támasztható követelményeket a gyakorlati feladatok megoldása során. Ennek tudható be, hogy a 80-as évek végétől kezdődően a kutatók figyelme a dinamikus, időben változó igényeket feltételező modellek felé fordult.

3.2.1 Rendszer optimális útvonal választási modell dinamikus forgalmi igények figyelembe vétele esetén

Míg a statikus modell azt feltételezi, hogy a szakaszokra jellemző haladási idő állandó és csak attól függ, hogy hány gépkocsi iktatja be a kérdéses szakaszt a tervezett útvonalába, addig dinamikus esetben a kérdéses szakaszon található gépkocsik száma, következésképpen a szakaszokra jellemző haladási idő is az időpont függvénye.

A modellt Kaufman és szerzőtársai elektronikus publikációja alapján vázoljuk fel [7].

Az időbeli változás szemléletes modellezési módszere a hálózatot leíró G = (N, A) gráf időbeli kiterjesztése. A kiterjesztett G(h) = (N,A) térbeli és időbeli gráfban az eredeti N csomópont halmazhoz tartozó minden x csomópontnak x(t)-vel jelölt, h+1 számú csomópont felel meg az új N csomópont halmazban, ahol a t = 0,...,h megadja, hogy az alapnak választott Dt idő szakasz hányszorosa adja meg a kérdéses időpontot. Az időbeli kiterjesztés eredményeképpen az eredeti A halmazba tartozó (x, y) élnek (x(t), y(t + s)) élek felelnek meg A-ban, ahol t = 0,...,h – 1, s = 1,...,h.

Azokat a d csomópontba mint végpontba tartó járműveket, melyek a t időpontban lépnek be az (x, y) élbe és t + s időpontban hagyják azt el a folytonos és nem negatív áramlat változók írják le. Valamennyi végpontba irányuló áramlat vizsgálata esetén az élbe a t időpontban belépő és azt t + s időpontban elhagyó áramlat jelölése a következő:

A továbbiakban arra lesz szükségünk, hogy meghatározzuk azt, hogy a t -ik periódus folyamán hány gépkocsi lesz az (x, y) élen. Ha bevezetjük a következő általános jelölést a g vektorokra és Z halmazokra: , valamint meghatározzuk a következő halmazokat: , akkor a keresett, a t -ik periódusban az élen található gépkocsik mennyisége röviden és részletesen is kifejtve:

A feladat matematikai programozással történő megoldásának célfüggvénye:

A célfüggvény első fele összegzi az egész vizsgálati időszakban valamennyi élen található gépkocsik számát, aminek a minimalizálása egyenértékű az összesített útidő minimalizálással, hiszen az él impedanciák, illetve az élre jellemző utazási idők annál nagyobbak minél több gépkocsi halad az élen. A kifejezés második fele arra keres megoldást, hogy a h időponthoz közel a hálózatba lépett gépkocsik, melyek már képtelenek a vizsgálat végéig elérni a d rendeltetési pontot, ne rekedjenek meg valamely közbenső élen, hanem helyezkedjenek el egy y(h) csomóponton. Ezt úgy lehet elérni, hogy valamennyi (x(t), y(h)) alakú élhez zérus kapacitást rendelünk. Emellett valamennyi gépkocsit, melynek nem sikerült eljutnia a rendeltetési helyére egy b(y,d) büntetéssel sújtunk, mely értéke megfelel a becsült időnek, mely alatt elérhetné rendeltetési pontját.

A figyelembe veendő korlátozások a következők:

Azok a gépkocsik, melyek azonos t periódusban lépnek be egy élre azonos idő alatt kell, hogy végighaladjanak az élen. A feltétel megvalósításához a modell hozzárendel minden egyes időben kiterjesztett élhez egy nevű, 0-1 értékű egész változót. Az élre belépő gépkocsi csomag csak akkor rendelkezik s utazási idővel ha ennek az egész változónak az értéke 1. A feltételt a következő egyenlőtlenség fejezi ki:

ahol M egy tetszőlegesen nagy konstans. Feltételezi a modell továbbá, hogy a gépkocsi csomagok egyben maradnak az élről történő kilépéskor, amit azzal ér el, hogy lehetővé teszi, hogy a t időpontban az (x,y) élre lépő gépkocsik válasszanak legfeljebb egy idő értéket az S-ből. Ha nem lép be gépkocsi a t periódusban az élre úgy megengedett hogy egy kiterjesztett élet se válasszanak: ekkor . Maga a feltétel pedig a következő alakban írható fel:

A hálózat modellezésben általánosan használt FIFO (first in first out) elvet, azaz, hogy a gépkocsi csomagok az élen nem előzhetik egymást, a következő korlátozással kényszeríti ki a modell:

minden Bár a feltétel formálisan nem lineáris, igen egyszerűen lineárissá tehető, ennek a részleteire azonban nem térünk ki.

A következő korlátozás a hálózati áramlás konzerválását hivatott biztosítani. Ha az csomópontba d rendeltetéssel gépkocsi lép be, akkor
Az utolsó korlátozás a forgalom okozta torlódásokat veszi figyelembe. A modell abból indul ki, hogy az (x,y) élen a t időpontban feltételezhető utazási idő csak az ebben az időben az élen lévő forgalom volumenétől függ (beleértve az éppen belépő jármű csomagot is). Továbbá, az élen belüli utazási időket a statikus modelleknek megfelelően vizsgálja. Ilyen feltételek mellett a modellt a kapacitás korlátozásokkal lehet felírni az alábbiak szerint: A (17)-ben c(x,y) az (x,y) él kapacitás függvénye. A (15)-hez hasonlóan a (17) kifejezést is egyszerűen át lehet alakítani lineáris formára.

A vegyes, egészértékű lineáris programozási feladat megoldásához bemenő adatként jelentkeznek az időfüggő utazási igények, melyek jelölésére a korábbiakban a kifejezést használtuk. Ezt a függvényt, amint már említettük, korábbi forgalomszámlálási eredményekre támaszkodva a forgalom automatizált érzékelőkkel történő monitorozásával határozzák meg.

A másik bemenő adat az élek kapacitás függvénye - , mely a modell alkotói szerint , ahol a kérdéses útszakasz gyakorlati kapacitása, pedig a szakasz megtételéhez szükséges idő, szabad gépjármű áramlás esetén.

A hivatkozott publikációban a szerzők az IBM szubrutin könyvtárban található, elágazáson és korlátozáson alapuló MILP algoritmussal egy kisméretű, 4 csomópontból és 4 élből álló hálózatot vizsgáltak 5, egyenként 1.5 perces periódusra. A kis hálózat és kevés periódus ellenére azt tapasztalták, hogy a feladat mérete még így is erősen leterhelte a használt IBM RS/6000 munkaállomás memóriáját, bár a megoldáshoz szükséges idő csak 6 perc volt. A kapott eredmények csak kismértékben javították a kiindulásként felvett szabad áramláson alapuló optimális megoldást, amit a kevés időperiódussal magyaráztak. Nagyobb hálózat és több időperiódus alkalmazása azonban új, hatékonyabb algoritmus kidolgozását igényelné.

Az említett számítási igények csökkentését szolgálják azok a törekvések, melyek a forgalommodellezést olyan algoritmusokkal végzik, melyek egyidejűleg több processzoron futnak. A parallel algoritmusok vizsgálata azonban túlnő jelen tanulmány témáján.

3.2.2 A felhasználó optimális modell

A rendszer optimális forgalmi modellek realizálása csak a nem túl távoli jövőben várható, így logikus volt, hogy a forgalmi egyensúly létrejöttét a rendszer résztvevőinek optimalitása szempontjából is megvizsgálják. A felhasználó optimális modell, mely megfogalmazását Wardrop 1952-es tanulmányának tulajdonítják [8] olyan egyensúlyi helyzetet tételez fel, melyben minden közlekedő számára az éppen választott útvonal az optimális, ennek tetszőleges megváltoztatása növeli az utazási ráfordításokat. Mielőtt felvázoljuk a rendszer matematikai leírását érdemes elgondolkoznunk a modell realitásán.

Ha a modellt az aktuális forgalmi viszonyok megismerésére kívánjuk felhasználni, úgy reális képet csak akkor képes nyújtani, ha a forgalom valamennyi résztvevője alapos ismerettel rendelkezik arra vonatkozóan, hogy adott OD pár és konkrét indulási időpont esetén melyik útvonal lesz a legkedvezőbb. A valóságban azonban megfelelő forgalmi információs rendszer hiányában a forgalom résztvevői nem feltétlenül rendelkeznek megfelelő ismeretekkel a legjobb útvonal kiválasztására. Ezt a tényt a kutatók valószínűségi modellek megalkotásával próbálják figyelembe venni. A valószínűségi modell kiterjedhet a felhasználók útválasztásán kívül az útszakaszok megtételéhez szükséges időkre is. Ilyen, mind a hálózatot, mind az útvonal választást valószínűségi alapon kezelő dinamikus forgalom hozzárendelési modellt mutat be Liu és szerzőtársai tanulmánya [9].

Bár a valószínűségi modellek használata egyelőre több mint indokolt, a jelen idejű forgalominformációs rendszerek fejlődésével várható a determinisztikus modellek valóságtartalmának fokozatos kiteljesülése, ami részben indokolja, hogy matematikai tárgyalásunkat ez utóbbiakra korlátozzuk. Másik indokunk pedig az, hogy a 3.2.2.2 pontban ismertetendő közelítő, előzetes útvonaltervező modell is ezeken az elvi alapokon nyugszik.

A felhasználó optimális modellben azokat az útvonal-, illetve szakasz-áramlatokat keressük, melyek kielégítik a (8), (9) és (10) feltételeket, és amelyekre érvényes a felhasználó optimalitás Wardrop féle megfogalmazása, melyet matematikailag a következőkeppen írhatunk fel:

minden OD párra és minden ezeket összekötő útvonalra igaz, hogy

ahol a kérdéses kezdő és végpontot összekötő útvonal minimális költsége.

A felhasználó optimális egyensúlyt abban az esetben, ha a szakaszon fellépő költség csak a szakasz áramlatának függvénye a következő optimalizálási feladat megoldása szolgáltatja:

a (8), (9) és (10) feltételek figyelembe vételével.

Ha a költségfüggvényre nem érvényesek a fenti feltételek, azaz a szakaszon fellépő költség nem csak a saját, hanem a többi szakasz áramlatától is függ és ez a függés nem szimmetrikus – másképpen befolyásolja az i szakasz áramlata a j szakasz költségét, mint a j szakasz áramlata az i szakasz költségét, úgy nincs lehetőség az egyensúlyi feltételek optimalizálási formára hozására és valamely szabványos optimalizálási technikával történő megoldására.

Az általános költségfüggvény esetében a variációs egyenlőtlenség módszerét alkalmazzák.

A variációs egyenlőtlenség matematikai keretet biztosít különböző, elsősorban egyensúlyi helyzethez kapcsolódó optimalizálási probléma megoldására a legkülönbözőbb szakterületeken. Ezekhez tartozik a forgalmi egyensúly is, de ezt a keretet használják különböző pénzügyi egyensúly problémák vizsgálatára, vagy hogy egy teljesen más területre is utaljunk, rugalmas anyagok akadály hatására felvett alakjának meghatározására.

A variációs egyenlőtlenségek problémája (angol nevének szókezdő betűivel rövidítve VIP) szabványos formában a következő kifejezéssel írható le:

ahol K egy adott, zárt, konvex halmaz, F adott, folytonos függvény K-ból R^N-be, pedig a belső szorzatot jelöli R^N-ben.

Konkrét feladat megfogalmazás esetén meg kell választani az F függvényt, a megengedett megoldások halmazát K-t és a változók vektorát X-et. A függvény az X^* megoldási pontban merőleges a megengedet megoldások halmazára.

A statikus, rögzített forgalmi igényű, felhasználó optimális, útvonal áramlatokkal kifejezett hálózati egyensúly VIP megfogalmazása a következő:

Az vektor csak akkor nyújtja a hálózat felhasználó optimális, útvonal áramlási képét, ha kielégíti az alábbi variációs egyenlőtlenségi problémát:

ahol C az útvonalakra eső felhasználói költségek n_P dimenziós oszlop vektora, K pedig azon nem negatív útvonal áramlatok halmaza, melyekre érvényes a (8) egyenlet.

A (21) természetesen a (20) analógiájára vektorosan is felírható. A feladat, tehát a statikus, rögzített forgalmi igényű, felhasználó optimális hálózati egyensúly felírható szakasz forgalmi terhelésekkel is, illetve készíthető olyan VIP leírás is, mely a hálózati igényeket rugalmasan kezeli, azaz a gépkocsik annak a függvényében kezdeményezik az OD pontok közötti utazást, hogy milyen mértékű az utazást kedvezőtlenül befolyásoló hálózati terhelés. A bekezdésben felsorolt problémák és még sok egyéb modell bemutatását is megtalálja az érdeklődő a [6] tanulmányban.

A VIP megoldására használt algoritmusok rendszerint optimalizálások sorozatára bontják le a feladatot, melyek aztán iterációval közelítik az egyensúlyi helyzetet. Ezek az algoritmusok igen számításigényesek, ezért a közlekedési hálózatok modellezésekor, különösen a felhasználói tanácsadást szolgáló dinamikus modellekben igyekeznek olyan heurisztikus módszereket is alkalmazni, melyek meggyorsíthatják a számítást. A dinamikus modellekben ugyanis a megoldás számítás igénye a vizsgálathoz alkalmazott időintervallumok számának függvényében jelentősen megnőhet. Tulajdonképpen arról van szó, hogy minden új időszakaszban új forgalmi áramlat vizsgálatot kell végrehajtani a kérdéses intervallumhoz tartozó OD adatokkal, figyelembe véve a korábbi szakaszokhoz tartozó OD adatokból már kialakult forgalmi áramlatokat a hálózatban. A dinamikus esetekben ezért a valós idejű előrejelzés megoldása érdekében, azaz hogy a számítás időigénye rövidebb legyen, mint a vizsgálati (vagy valós) idő, a heurisztikus algoritmusokat párhuzamos processzorokra implementálják. A [11] tanulmány szerzői például arra az eredményre jutottak, hogyha a hálózat topológiája alapján bontják fel az algoritmust a párhuzamos működésű processzorok között, úgy 10 processzor alkalmazása esetén a a feldolgozás sebessége ötszörösére növekszik, míg az idő szerinti felbontás ugyancsak 10 processzor esetében 6.5-szörös sebességnövekedést eredményez.

A továbbiakban röviden bemutatunk két felhasználó optimális dinamikus hozzárendelési modellt, hasonlóan ahhoz ahogy ezt a rendszer optimális esettel kapcsolatban a 3.2.1 pontban már megtettük. Míg az első modell a valósidejű forgalom szervezést illetve forgalmi tanácsadást szolgálja, addig a második előzetes szállítás tervezéshez készült, és külön érdekessége viszonylag szoros kapcsolata az ArcInfo GIS szoftverrel.

3.2.2.1 A felhasználó optimális, dinamikus forgalom hozzárendelési modell

Az ismertetendő modellt 1997-ben eredetileg diplomatervként dolgozta ki Yiyi He [10], de mivel ez a modell képezi az alapját a párhuzamos processzorokkal történő első, 2003-as algoritmusnak is [11] valószínűsíthető, hogy a jövőben egyre több gyakorlati alkalmazás fogja használni a modellt.

Az alapfeladatot, miszerint időfüggő, kiinduló pont – rendeltetési pont (azaz OD) adatok, hálózati topológia és terhelés nélküli szakasz teljesítmény adatok birtokában meg kell határozni, hogy mennyi lesz a konkrét időpontban induló jármű utazási ideje választott útvonalán, a modell három részmodellből építi fel. Megjegyzem, hogy a modell összefoglalása során meghagytam az eredeti jelöléseket azok dolgát megkönnyítendő, akik az eredeti munkát mélyebben is tanulmányozni szeretnék. Ez sajnos helyenként inkonzisztens mind a korábban bevezetett jelölésekkel, mind, legalább is formailag, helyenként önmagával is. A félreértések elkerülése érdekében minden matematikai megfogalmazáshoz külön-külön adom meg a jelölések magyarázatát.

Az első részmodell – a felhasználó viselkedési modell tulajdonképpen módosítja az eredeti Wardrop koncepciót, ugyanis háromféle felhasználói viselkedéssel számol:

az első felhasználói csoport (a képletekben 1 index-szel hivatkozunk rá) mindig ugyanazon az útvonalon halad a kiindulási pontból a rendeltetési pontba;
a második csoport (képlet hivatkozása 2) olyan útvonalat választ a kezdőpont és végpont között, melyről feltételezi, hogy az optimális;
a harmadik csoport (hivatkozás 3) a valóban minimális utazási időhöz tartozó útvonalat választja.

Matematikailag a részmodell a következő variációs egyenlőtlenséggel írható fel:

ahol

f – az áramlatot jelöli, a felső indexek (r,s) a kezdő és végpontra utalnak, míg az alsó indexben a szám a felhasználó típust, p pedig az útvonalat mutatja,

c – a t idő pontban a felső indexben szereplő r kezdő pontból az s végpontba induló jármű tényleges utazási ideje az alsó indexben szereplő p útvonalon,

K – az alsó indexben szereplő r és s pontokat összekötő valamennyi útvonal,

0-T_d a vizsgálat időtartama,

P – az az arány, amely a t időpontban az r kezdőpontból az s végpontba induló áramlatot a 2 típusú felhasználók révén a p útvonalhoz rendeli.

A második részmodell írja le a szakaszok teljesítményét. A részmodell segítségével határozhatók meg a szakaszokra érvényes utazási idők folyamatos haladás esetén a szakasz statikus paraméterei illetve az áramlat sűrűsége függvényében, torlódások esetében pedig az utazási idők sorba állítási modell felhasználásával fejezhetők ki. A szakasz utazási idő függvények biztosítják, annak a feltételnek a teljesülését is, hogy az elsőként belépő jármű elsőnek hagyja is el a szakaszt.

A t időpontban a szakaszra belépő jármű szakasz utazási ideje - a következő kifejezéssel írható fel:

A (23)-ban szereplő jelölések a következők:

w_a(t) – a mozgó járművek sebessége a szakaszon, mely az alábbi kifejezéssel adható meg: , ahol a szakaszra jellemző legkisebb és legnagyobb sebesség, - a járművek sűrűsége a szakasz torlódás mentes részén t időpontban, - a járművek sűrűsége a torlódó szakaszon (azaz a járművek száma osztva a torlódó szakasz hosszával), - az adott szakaszra jellemző tapasztalati állandók (a [10]-ben közölt teszt futtatások során a=1.4 és b=3.2 értéket használtak).

- a szakasz hossza mérföldben,

- a szakaszon található járművek száma,

- a szakasz végpontján a járművek kilépési sebessége (darab/másodperc).

Amint már említettük, ennek a részmodellnek kell biztosítania, hogy a szakaszra való belépés és az onnan való kilépés sorrendje ne változzon. Ezt az angolul FIFA-nak rövidített feltételt a szakasz utazási idő deriváltjával a következőképpen írhatjuk fel:

A harmadik részmodell a hálózati feltöltési modell, mely bemenő adatok és az előző részmodellek felhasználásával meghatározza a hálózat leterheltségét egy adott időpillanatban. A részmodellt négy típusú egyenletek rendszere alkotja.

Az első egyenlet típus a szakasz dinamikáját fejezi ki:

ahol - a t időpontban az r pontból az s pontba a p útvonalon haladó áramlat belépési sebessége az a szakaszra, - a t időpontban az r pontból az s pontba a p útvonalon haladó áramlat kilépési sebessége az a szakaszról, - a t időpontban az r pontból az s pontba a p útvonalon haladó összesített áramlat az a szakaszon, - az r pontot az s ponttal összekapcsoló összes lehetséges útvonal halmaza.

A második egyenlet típus az áramlás konzerválását szolgálja:

ahol - a t időpontban az r pontból az s pontba a p útvonalon elinduló áramlat indulási sebessége.

A harmadik egyenlet típus az áramlat terjedését írja le. Mivel az a szakasz összesített kimenő áramlata a t időpontban - kell, hogy tartalmazz az összes kimenő áramlatot a korábbi w időpontokból ezért

ahol , pedig az az időpont, amikor a t időpontban az a szakaszra belépő áramlat elhagyja az a szakaszt.

A negyedik egyenlet típust a határfeltételek alkotják:

ahol - a 0 időponthoz tartozó összesített belépő áramlat az r és s pontokat összekötő p útvonal a szakaszára.

A (25)-(28) egyenlet rendszerben ismertek az induló áramlatsebességek, illetve a teljesítmény modellből kiszámolhatók a szakasz utazási idők, az

változók pedig az ismeretlenek. Az ismeretlenek meghatározása után az szakasz terhelések a következő kifejezésből számíthatók:

Mivel a kiinduló feladat az volt hogy meghatározzuk a dinamikusan változó környezetben, amikor tehát a hálózati helyzet nem csak az indulási időtől függ, a felhasználó által megtett útvonal utazási idejét -t, ezt csak úgy tehetjük, ha figyelembe vesszük mindazokat az időpontokat amikor a felhasználó belép egy-egy új szakaszra az útvonalon. Jelöljük ezeket az időpontokat -vel, ( - a kérdéses szakasz neve, t pedig az az időpont, amikor a felhasználó belépett a hálózatra) és álljon a vizsgált útvonal n szakaszból akkor a keresett utazási idő:

A dinamikus hálózati hozzárendelés feladata úgy oldható meg, hogy az ismeretleneknek egyidejűleg ki kell elégítenie a felhasználók útvonal választási szokásait figyelembe vevő variációs egyenlőtlenséget (22) és a (25)-(28) hálózat feltöltési egyenletrendszert.

A feladat gyakorlati megoldása több lépésben történik.

Mindenek előtt a folyamatos időt diszkrét időintervallumokkal kell helyettesíteni, melyek hossza rövidebb kell, hogy legyen mind a legrövidebb szakasz utazási idő a hálózatban. Mivel a megoldás számításigénye az időintervallumok számával arányosan növekedik, ezért a felosztás finomításának a rendelkezésre álló számítási kapacitás szab határt. A diszkretizálás gyakorlatilag azt jelenti, hogy a folyamatos idő argumentumot (t) az intervallum idő k szorosaival helyettesítjük, ahol a k egész szám az intervallum sorszáma.

Az első algoritmus a hálózat feltöltését végzi, azaz minden egyes időintervallumra kiszámolja a (29) ismeretleneket a diszkretizált (25)-(28) egyenletrendszerből.

A második algoritmus az útvonal választást valósítja meg a különböző felhasználói típusok között. Először a feltöltési algoritmus által szolgáltatott szakasz utazási időkből kiszámítja az útvonal utazási időket, majd annak a valószínűségét, hogy a 2. típusú felhasználó bizonyos útvonalat választ az ismert „logit” modell felhasználásával határozza meg. A 3. típusú felhasználókhoz a legrövidebb utakat rendeli. A felhasználók megoszlását a típusok között, illetve az 1. típusú felhasználók kedvenc útvonalát bemenő adatként kell megadni.

A hálózat feltöltése és felhasználók útválasztásai a DTA nevű iterációs algoritmus felhasználásával kerülnek összhangba. Első lépésben az algoritmus kiszámolja a szabad áramlás esetére a k idő intervallumokra érvényes útvonal áramlatokat, a - értékeket. Ezután az eljárás magja végrehajtja a hálózati leterhelést majd elvégzi az útvonal választást, melynek eredményeképpen megkapja a 2 és 3 típusú felhasználók által választott útvonalakra vonatkozó áramlatok - értékeit, melyekkel megjavítja az előző iterációban kapott útvonal áramlatokat olymódon, hogy a korábbi útvonal áramlatokhoz hozzáadja az utolsó útválasztási algoritmus eredményének és a korábbi útvonal áramlat különbségének egy az iteráció fokától függő csökkentő tényezővel történő szorzatát, azaz n – az iteráció mérőszáma.

A modell első számítógépes implementálása során C++ objektum orientált nyelven készítették el a programot, melyhez az adatokat két osztályban a szakasz osztályban és az OD osztályban tárolták. Ez a tárolási struktúra azért lehet érdekes a számunkra, mivel mind a két osztály, kiegészítve a koordináta adatokkal része lehet bármely objektum orientált GIS adatbázisának.

A 2003-as implementáció során, amint erre a módszer bevezetése során már utaltunk a szekvenciális algoritmusokat párhuzamosították a célból, hogy a modell egyszerre több processzoron fusson. A feladat kétféle felbontását algoritmizálták. Az első esetben a hálózatot részekre bontották az egyes OD pontokat összekötő útvonalak szerint, a második esetben a vizsgálati időt elosztják a processzorok számával és az iterációs hálózat feltöltési algoritmus, mely minden egyes idő intervallumra külön iterációt hajt végre, processzoronként csak a szétosztott időintervallumokra számolja ki a megoldást. A reális hálózaton végzett kísérleti futtatások azt az érdekes eredményt szolgáltatták, hogy a számítás felgyorsítása függ a vizsgálati idő hosszától is, különösen az idő szerinti felbontás esetén. A hivatkozott tanulmány szerzői ezért azt javasolják, hogy a vizsgálati időszak 2000 másodperc legyen. Erre az időintervallumra jobb eredményt az időszerinti felbontás biztosít, a processzorok számával közel megegyező gyorsítással.

Az előzőekben ismertetett modell célkitűzése, hogy azokat a tanácsadó – adattovábbító rendszereket lássa el friss, élő információval, melyek a forgalom résztvevőit jelen időben támogatják optimális útvonaluk megválasztásában. A következő részben ismertetendő rendszert a szállítási időpontok előzetes meghatározására dolgozták ki.

3.2.2.2 Szabatos szállítási időpontok meghatározása városi környezetben

Az iparban és a szolgáltatásokban egyre nagyobb szerepe van az úgy nevezett Időre Érzékeny Szervezésnek (angolul Time-Critical Logistics = TCL), ami például azt jelenti, hogy a gyártó egység nem alkalmaz raktárkészletet, hanem akkora rendeli az alkatrészeket, amikorra beépítésüket a technológiai folyamat előírja. Talán egyszerűbb, de az egyén számára fontosabb példa, ha azt akarjuk megbecsülni, hogy a 8 órakor induló repülőgéphez mikor kell elindulnunk és milyen úton, ahhoz hogy pontosan érjünk a repülőtérre.

Az ilyen jellegű szervezési feladatok megtervezésére dolgozták ki azt a döntéstámogatási rendszert, mely a dinamikus, felhasználó optimális hálózat hozzárendelési modell közelítő megoldásával képes megadott kezdő és végpontok között adott időintervallumokban meghatározni az optimális útvonalakat és a hozzátartozó útidőket. E mellett a rendszer az ARC/INFO 7. szoftver felhasználásával meg is tudja jeleníteni a meghatározott útvonalakat, illetve ábrázolni tudja a torlódási viszonyokat [12], [13].

A rendszer forgalommodellező modulja a (19) kifejezés időbeli kiterjesztésén alapul, azaz azért tudja visszavezetni a felhasználó optimális modellt szabványos optimalizálási feladatra, mivel feltételezi, hogy az egyes szakaszok költsége (utazási ideje) csak ugyanezen szakaszok áramlataitól függ és a többi szakasz telítettsége – közvetlenül nem befolyásolja a vizsgált szakaszon elérhető sebességet.

Mielőtt a célfüggvényt, a feltételeket és a jelöléseket ismertetném meg kell jegyeznem, hogy megpróbáltam átírni a hivatkozott cikkek jelöléseit az általunk korábban már használt értékekre.

A célfüggvény a következő alakot nyeri:

ahol t - az időintervallumokat., T - pedig a vizsgálat teljes idejét jelöli. A többi jelölés megegyezik a (19) egyenlettel kapcsolatban már ismertetettel azzal a különbséggel, hogy a t felső index egy időintervallumra vonatkoztatja a kérdéses mennyiséget.

A célfüggvény minimalizálása az alábbi feltételek érvényesülése mellett valósítandó meg:

A figyelmes olvasó észreveheti, hogy a (31), (32) és (33) kifejezések a korábbi (9), (8) és (10) feltételek dinamikus (időfüggő) változatai. Az új jelölések közül i – az indulási időintervallumot jelenti, az - olyan 0 vagy 1 értékű változó, mely azt mutatja, hogy a p útvonalhoz rendelt, i időintervallumban induló járművek használják-e az a szakaszt a t időintervallumban. Az n index valamely csomópontot jelöl, tehát például a - az az idő, ami alatt az i időpontban a p útvonalon haladó jármű eléri az n csomópontot. Az összes a szakasz halmazát, mint korában, L jelöli. Az - a p útvonal összes szakaszának halmaza, az - a p útvonalon az n csomópontot megelőző szakaszok halmaza, míg - az n csomópontból kiinduló összes élet jelöli.

Az ismertetett rendszer azonban nem használ szabványos optimalizálási eljárást a feladat megoldására, mivel annak a számítási igénye mintegy négyszerese lenne az alkalmazott heurisztikus eljárásnak, és nem tenné lehetővé, hogy a programot egyszerű számítógépeken futtathassák a kisebb szállítási vállalatok is.

A heurisztikus algoritmus megkezdése előtt meg kell határozni a figyelembe veendő időintervallumok nagyságát. A tapasztalat azt mutatja, hogy ennek értékét a hálózatra jellemző, átlagos szakasz utazási idő 4-5 szörösére kell megválasztani.

Az első lépésben fel kell venni egy kiinduló hálózati terhelési állapotot, ebből ki kell számítani a szakasz utazási időket és a Dijkstra algoritmus felhasználásával minden kezdőpontról minden végpontra ki kell számítani az optimális útvonalakat. A kapott útvonalakra rá kell terhelni a kezdeti időintervallumban induló járműveket.

A következő lépésekben, minden időintervallumra meg kell határozni az új terheléseket az előzetesen tervezett és az újonnan belépő forgalom súlyozott átlagaként és a kérdéses intervallumban újonnan belépők számára meg kell határozni a leggyorsabb útvonalakat. Lényeges eleme a módszernek, hogy a korábbi intervallumokban belépett járművek várható terhelését meg kell határozni a későbbi szakaszokra is, melyek a következő ciklusokban folyamatosan javításra kerülnek.

A korábbi, t-1 intervallumban nyert végleges terhelésből és a jelen intervallumra számított előzetes terhelésből az a szakasz tervezett terhelései a következőképpen számíthatók:

ahol - a t időpontban a hálózatba belépő összes jármű száma, - arány, mely megmondja, hogy hanyadrésze nincs még hozzárendelve a hálózathoz a t intervallumban, .

A szakasz utazási idő kapcsolatát a hálózati terheléssel a következő szabványos kifejezés felhasználásával számítja a rendszer:

ahol T – az utazási idő percben, - az utazási idő percben szabad áramlás esetén, Q – az idő intervallumra eső járművek száma, - a szakasz stabil állapotú kapacitása (gépkocsi szám / idõintervallum)-ban kifejezve, - kísérleti paraméterek, melyeket városonként lehet meghatározni a szakaszra megengedett utazási sebesség függvényében.

A rendszer a DOS promptról indítható program, mely azonban kiolvassa illetve feltölti az Arc/Info GIS szoftver INFO fájljait. Ez lehetővé teszi, hogy a bemenő adatok, azaz a hálózat és az OD mátrix mint Arc/Info fedvények kerüljenek kialakításra. Hasonlóképpen az is lehetséges, hogy a lekérdezési eredményeket is az Arc/Info jelenítse meg.

Az ismertetett alapelveken működő program jelenleg is fejlesztés alatt áll, szerzői mindenek előtt felhasználó barát grafikus interfésszel szeretnék ellátni, de folyamatban van a többkritériumos optimalizáláson alapuló változat kifejlesztése is, illetve a megjelenítés tökéletesítését animációval kívánják elérni.

Jelen tanulmányban a GIS és optimalizálás összekapcsolását igénylő témák és ezek megoldásának legfontosabb elvi kérdéseit szeretném megvilágítani. Ennek a célnak megfelelően nem kívánom rendszerezetten tárgyalni a megoldásokban felhasználható kereskedelmi szoftvereket. Ennek ellenére, a közlekedési problematika hazánkban nem igazán felismert súlya indokolja, hogy néhány szóval felvázoljam az egyetlen közlekedés orientált kereskedelmi GIS szoftver – a TRANSCAD lehetséges szerepét a közlekedési feladatok optimalizálásában. Ezt a döntésemet az is indokolhatja, hogy ez a szoftver azok közé a nemzetközileg elismert GIS szoftverek közé tartozik (pld. GE Smallworld, Laser-Scan Lamps, stb.), melyek magyarországi ismertsége minimális.

3.2.3 A Caliper cég TRANSCAD nevű szoftverének használhatósága a közlekedési feladatok optimalizálására

A címben szereplő szoftver 4.0-ás demo verzióját a szállítási költségektől (50 USD) eltekintve ingyen beszerezheti akárki a Caliper cégtől és remélhetőleg ez a rövid ismertetés sokakat fog inspirálni a program részletes megismerésére.

A jelenleg forgalmazott szoftver verzió száma 4.5, két formában kerül árusításra a „Standard License”, mely tartalmazza az összes tervezési és közlekedési modulokat 9995 USD-be kerül, míg a „Base License” változat ára, melyből hiányoznak bizonyos közlekedés- és útvonal tervezési eljárások valamint más tervezési szoftverekkel készített termékek importját lehetővé tevő segédprogramok, 2995 USD.

A Transcad olyan, általános elemző és térképező képességekkel rendelkező, vektoros GIS szoftver, mely gazdag tervezési-optimalizálási eljárás együttessel is rendelkezik, különös tekintettel a közlekedési alkalmazásokra. Ez utóbbiak kiszolgálása érdekében a rendszert speciális objektum típusokkal is ellátták:

A közlekedési hálózatok azok az adat struktúrák, melyek alkalmasok többek közt a kanyarodási szabályok, felüljárók-aluljárók, egyirányú utcák, forgalmi csomópont jellemzők, szakasz kapacitás függvények egyszerű figyelembe vételére;
A mátrixok segítségével egyszerűen kezelhetők a kezdő és végpontok, a távolságok, utazási idők, stb.;
Az útvonalak és útvonal rendszerek, melyek létrehozását speciális függvények segítik, képezik a bemenő adatokat a szállítási feladat különböző változatai számára;
A lineáris referencia lehetővé teszi az útvonalon lévő objektumok vagy fellépő események egyszerű megcímzését valamely kezdőponttól mért távolság alapján.

A szoftver nagy előnye, hogy eljárásokkal rendelkezik nem csak a tanulmányunkban tárgyalt szinte valamennyi optimalizálási problémára, de biztosítja azokat az elemző eszközöket is, melyekkel a térbeli adatokból a helyhez kapcsolódó igényeket is meg lehet határozni. Az igények alapján el lehet helyezni az ellátó központokat, illetve meglévő objektumokhoz hozzá lehet rendelni az ellátandó körzeteket.

Az igények meghatározásával, (előzetes) közlekedés tervezési célokra OD mátrixokat is létre lehet hozni a szoftver segítségével.

Külön eljárások biztosítják a legrövidebb út meghatározás különböző variánsait beleértve az utazó ügynök problémát az áruházak és raktárak közötti optimális szállítási terveket vagy hókotrók optimális útvonalának a kijelölését is.

A forgalom hozzárendelési modell, többek közt, tartalmazza a felhasználó optimális és rendszer optimális egyensúly determinisztikus és sztohasztikus variánsait is. Mindez azonban csak statikus esetre vonatkozik, dinamikus forgalom hozzárendelési eljárás nincs a rendszerben.

Új, kiegészítő alkalmazásokat a rendszer GISDK nevű fejlesztő környezete segítségével lehet megvalósítani. A más szoftverekkel való kapcsolatot az teszi lehetővé, hogy a Transcad automatizált OLE szerver, ami azt jelenti, hogy makro függvényei elérhetők a Visual Basic, Visual C++ vagy más program nyelvből is.

3.3 Mezőgazdasági művelési típus optimális tervezése több kritérium figyelembevételével

3.3.1 A többcélú optimalizálásról

Az egy célú optimalizálás során az a feladatunk, hogy megtaláljuk azokat az x döntési változókat, melyek az y(x) célfüggvényt maximalizálják vagy minimalizálják az x feltétel teljesülése mellett, azaz a feltétel az, hogy a megoldás a lehetséges megoldások tartományán belül keletkezzen. A célfüggvény dimenziója rendszerint pénzben kerül kifejezésre.

Gyakran előfordul azonban a gazdasági, műszaki, társadalmi feladatokban, hogy az elvégzendő feladat több célt kell, hogy optimálisan kielégítsen, e mellett a célokban optimalizálandó célfüggvények dimenziói nem azonosak, azaz nem mindegyik cél eredményessége fejezhető ki pénzben. Gondoljunk arra az egyszerű, az észak amerikai település szerkezetre jól illeszkedő példára, amikor a tűzoltó állomás elhelyezésekor azzal a dilemmával állunk szemben, hogy a nagy értékű belvárosi épületek biztonságáról gondoskodjunk-e inkább (azaz helyezzük el az állomást közel a belvároshoz), vagy tekintsük elsődlegesnek az olcsó elővárosi ingatlanok biztosítását, ahol az emberek laknak és helyezzük az állomást a előváros közelébe.

Az összemérhetetlen és esetenként ellentétes célokra irányuló optimalizálás fogalmát Vilfredo Pareto (1848-1923) olasz szociológus és közgazdász, a Lusanne-i egyetem politikai gazdaságtan tanára 1896-97-ben kiadott Politikai Gazdaságtan Tankönyvében fogalmazta meg. Meghatározása szerint létezik a megengedett megoldás vektoroknak egy olyan felülete (két dimenziós esetben - görbéje) melyen haladva az egyik cél eredményessége csak úgy javítható, ha a többi célok eredményessége csökken. Ez a felület a Pareto felület illetve kétdimenziós esetben a Pareto görbe. Ha a döntési vektorok helyett az eredményességet (tehát a célfüggvények értékét) ábrázoljuk akkor a Pareto frontról beszélünk (3. ábra).

Amint az ábrából látható, a Pareto fronton mozogva az f₁ tengelytől az f₂ tengely felé az első cél értékei csökkennek a második cél értékei pedig növekednek. Az, hogy a front melyik pontjához tartozó döntési vektor értékét válasszuk végső megoldásként általában a politikusok elhatározásától függ. Ahhoz azonban, hogy a politikusok dönteni tudjanak meg kell határoznunk a teljes Pareto frontot.

A Pareto front előállítására használt hagyományos módszerek közül a legelterjedtebb a súlyozásos módszer volt. A módszer lényegét (a szemléletesség kedvéért) két cél esetében a következőképpen képzelhetjük el. Az első lépésben számítsuk ki az első majd a második cél maximális értékét olymódon, hogy az első súlynak 1-et választunk a másodiknak 0-t, illetve fordítva. A megkapott maximális értékekkel normáljuk a megfelelő célfüggvényeket (azaz az elsőt elosztjuk az első cél maximumával a másodikat pedig a második cél maximumával) és végezzük el ezután a célfüggvények súlyozott összegének optimalizálását különböző súlyokra azoknak a feltételeknek a figyelembe vételével, hogy a súlyok összege legyen 1, illetve, hogy a döntési vektorok ne lépjenek ki a megengedett megoldások tartományából.

3.ábra – Pareto front két cél esetén

Célunk az, hogy a frontot közelítő pontok lehetőleg egyenletesen oszoljanak meg, ehhez több cél esetén több súly-iterációra is szükség lehet.

Bár a felvázolt alapelvek igen egyszerűek egyes feladatok gyakorlati megoldása a hagyományos algoritmusokkal nem mindég problémamentes. A tapasztalatok azt mutatják, hogy az egyenletes front generálás és az egyéb problémák is megoldhatók szakszerűen megtervezett genetikus algoritmus felhasználásával.

3.3.2 A genetikus algoritmus

Az élővilág fejlődésének Darwin-i elvét modellezi a számítógépes feladat megoldásban a genetikus algoritmus.

A módszer megvalósításához mindenek előtt arra van szükség, hogy a döntési változók lehetséges értékeit valamilyen formában kódoljuk. Ez a kódolás többféle lehet, az általunk vizsgált esetben az érték szerinti kódolást alkalmazták, azaz minden döntési változó felvehet egy olyan kódértéket, mely a figyelembe vett művelési típusokat jelöli. A döntési változók kódolt értékeit géneknek nevezik. A döntési változók számának megfelelő gén összekapcsolásával kromoszómát kapunk. A kromoszóma tehát nem más mint egy megengedett döntési vektor kódja.

A feladat indításához létre kell hozni a megengedett tartományból egy a feladat jellegétől függő, kísérletileg becsülhető számú kromoszómából álló halmazt, amit populációnak nevezünk. A populáció minden egyes kromoszómájának megfelelő döntési vektort behelyettesítve a célfüggvényekbe megkapjuk a kromoszómák jóságát. A jóságok alapján a populáció egy kis részét átvesszük az új populációba, ezt a lépést nevezzük elitizmusnak. Szintén a jóságok felhasználásával kiválasztunk egy tapasztalatilag megválasztott számú kromoszómát, melyeket keresztezünk és utódaikat beillesztjük az új populációba. A régi populáció egy, általában kis százalékát mutáció után visszük át az új populációba. Mivel a populáció mérete egy vizsgálat során kötött, a régi populáció azon elemeit, melyek egyik művelethez (elitizmus, keresztezés, mutáció) sem lettek kiválasztva elhagyjuk az új populációból.

A populációk vizsgálatát és cseréjét mindaddig folytatjuk, amíg a célfüggvény (többcélú optimalizálás esetén a dominancia) értéke néhány populációban már nem javul.

A jósági sorrend felállítására egycélú optimalizálás esetén két lehetőségünk van: vagy magát a célfüggvény értéket tekintjük jóságnak vagy a sorrendet tekintjük a jóság alapjának. A két módszer közötti különbség érzékeltetésére képzeljük el, hogy 5 kromoszómánk van, melyek jósági értékeit az 1. táblázatban tüntettük fel.

Sorszám	Célfüggvény szerinti jóság	Egységre redukált jóság	Sorrend szerinti jóság	Egységre redukált jóság
1	100	0.8474	5	0.3333
2	10	0.0847	4	0.2666
3	5	0.0424	3	0.2000
4	2	0.0169	2	0.1333
5	1	0.0085	1	0.0667
összesen	118	1.0000	15	1.0000

táblázat

4. ábra – érték és sorrend szerinti jóság ábrázolása

Mivel a kiválasztás úgy történik, hogy egy véletlen szám generátor 0-1 közötti számokat generál, kézenfekvő, hogy abban az esetben, ha a jóságok között nagy az eltérés a célfüggvény szerinti jóság alapján történő kiválasztásnál nagyon kicsi az esélye annak, hogy az első két kromoszómán kívül más is kiválasztásra kerüljön, míg a sorrend szerinti jóság figyelembe vétele esetén nincs jelentősége a célfüggvény eltérés mértékének. A továbbiakban a sorrend szerinti jóság alapján végzett kiválasztást fogjuk kiterjeszteni a több kritérium alapján történő optimalizálás esetére is.

A több kritériumú optimalizálásnál minden egyes célnak külön célfüggvénye van. Ha ebben az esetben behelyettesítünk két döntési vektort a különböző kritériumokat reprezentáló célfüggvényekbe akkor két eset lehetséges:

az első vektor behelyettesítése eredményeképpen valamennyi célfüggvény értéke nagyobb (ha maximalizálásra törekszünk), mint a második vektor behelyettesítésekor, ebben az esetben az első vektor diminálja a másodikat;
a döntési vektorok behelyettesítése után egyes célfüggvényeket az első, másokat a második vektor maximalizál, ebben az esetben a két vektor indiferens.

A dominancia bevezetésével úgy is megfogalmazhatjuk a Pareto optimális frontot, hogy azt a nem dominált megoldások eredményei alkotják, azaz olyan megoldások eredményei, melyekhez képest nem található domináns megoldási eredmény a lehetséges megoldások tartományában.

A többcélú optimalizálás során a rangsor szerinti jóságot előzetesen a dominanciából vezetik le, majd egy megadott "fülke" sugár (s_share) nevű paraméter felhasználásával a közelítő jóságokat csökkentve véglegesítik.

Az első lépésben tehát előzetes jósági értéket rendelnek az x_i kromoszómához mely értéke

jóság(x_i, t) = 1 + p_i^t, (41)

ahol p_i^t azon kromoszómák száma, melyek az x_i kromoszómát dominálják a t populációban. A nem dominált kromoszómák előzetes jósági értéke tehát 1, minél „rosszabb” a kromoszóma, annál nagyobb az előzetes jósági értéke.

5. ábra – a dominancia fogalom illusztrálása

Ezután sorba állítjuk valamennyi kromoszómát olymódon, hogy az első helyen szerepeljenek a legjobb (tehát 1 előzetes jósági értékű) a végén pedig a legrosszabb (n* ≤ N) előzetes jósági értékű kromoszómák.

Elvégezzük a

Jóság(Ssz) = 2 - SP + 2·(SP - 1)·(N - Ssz) / (N - 1) (41)

kifejezés szerinti másodlagos jósági érték interpolálást, ahol Ssz – a sorszám SP – a szelektív hangsúly ( SP = selective pressure) nevű súlyozási paraméter, majd az azonos előzetes jósági értékű kromoszómák másodlagos jósági értékeit átlagoljuk (gondoljunk arra, hogy több olyan kromoszóma is van amelyek előzetes jósági értéke azonos, pld. 1 mégis a sorba állítás után a képletből különböző másodlagos jósági értéket kapnak, ami nem indokolt, ezért kell másodlagos jósági értékeiket átlagolni, nem változtatva meg ezzel az össz-jósági érték mennyiséget).

Hogy az elmondottak világosabbak legyenek a 5. ábra egyszerű példájára elvégeztük a hivatkozott számításokat, melyeket a 2. táblázatban és a belőle készült torta-diagramot tartalmazó 6. ábrán mutatunk be.

2. táblázat

6. ábra – a példa rangsor szerinti jóság diagramja

A végső jósági értékek kialakításához még szükség van az azonos rangú egyedek jósági értékeinek csökkentésére bizonyos távolsági paraméter alapján. Arról van tehát szó, hogy ha egymáshoz túl közel helyezkednek el azonos rangú egyedek, úgy jósági értéküket egyedileg csökkentik, de e mellett gondoskodnak arról, hogy a ranghoz tartozó össz-jósági érték ne változzon. A távolság meghatározható a kód térben, döntési térben vagy a cél térben. Mivel a módszer azt kívánja elérni, hogy a Pareto front egyenletesen, de ne túl sűrűn legyen meghatározva, ezért célszerű a távolság fogalmat a cél térben értelmezni.

A s_share küszöb távolság meghatározása bonyolult feladat, a bemutatandó LADSS döntéstámogató rendszer Fonseca és Fleming javaslatát [14] alkalmazza, mely a célfüggvények maximális és minimális értékeiből illetve a Pareto frontot alkotó optimális pontok számából vezeti le s_share értékét.

Ha a küszöbérték megvan, akkor az i∈P egyed végleges F(i) jósági értékét a F'(i) előzetes jósági értékből a következő kifejezésből nyerjük:

F(i) = F'(i) / ∑_j_∈Ps(d(i,j)) (42)

A fülke szám azaz a kifejezés nevezője tehát nem más, mint a kérdéses egyed illetve a populáció egyéb egyedei között fellépő s csökkentő függvények összege.

Gyakran használt csökkentő függvény:

s(d(i,j)) = 1 - ( d(i,j) / s_share)^a, ha d(i,j) < s_share,

s(d(i,j)) = 0 egyébként. (43)

A kitevőben szereplő a értéke rendszerint 1, a távolságok pedig a célfüggvény értékek négyzet összegéből vont négyzetgyökkel számíthatók, bár természetesen más normák is használhatók.

Ne felejtsük el, hogy a [14]-ben lévő eredeti javaslat szerint a fülkeszámmal csökkentett egyedi jóságok rangonkénti összege meg kell, hogy egyezzen a kérdéses rang szerinti jóság csökkentés előtti összegével, azaz, ha az r rangú csökkentés elõtti jóság összeget S'(r)-el, a csökkentés utáni összeget pedig S(r)-el jelöljük, úgy az r rangú i egyed végleges F_r^veg(i) jóságát a következő képletből nyerjük: