Meghívó

         Szeretettel várunk minden kedves érdeklődőt a BME
                          Optimalizálás Szemináriumán!

Az előadás részletei:
április 27. (csütörtök), 14:15 órakor a H. 46-os teremben

Morapitiye Sunil (BME) Operációkutatási modellek buszvezető hozzárendelési feladatra és alkalmazása címmel tart előadást.

Absztrakt: 

Napjaink igen aktuális problémája az erőforrás ütemezési kérdések, amely számos alkalmazást nyer a hétköznapi életben is. Alapvetően egy olyan hozzárendelési feladatról beszélünk, pl. pilóták, stewardessek repülőgépjáratokhoz rendelése, bolti eladók műszakokhoz rendelése, vonatok és járatok egymáshoz rendelése, amelyek számos további megkötést tartalmaznak (pl. pihenők vagy szabadnapok kiadása). Ezek a további feltételek alkalmazás specifikusak és alapvetően a hozzárendelési feladat folyamfeladat jellegét tönkreteszik és a probléma leírása csak általános egészértékű lineáris programozási feladattal lehetséges. Ennek következtében – általában – NP-teljes feladathoz jutunk, ami a feladat megoldását igazi szakmai kihívássá teszi.

Diplomamunkám keretein belül a T-Systems Magyarország Zrt.-vel együttműködve, a budapesti tömegközlekedés optimalizálásával foglalkoztam. Bár a menetrend útvonalai, időpontjai ritkán változnak, folyamatosan szükséges új (lehetséges) menetrendek gyártása, ami – meglepő módon – még mindig emberi erővel, szakértő munkájának felhasználásával excelben szerkesztve történik. Egyrészt az a probléma ezzel, hogy számottevő erőforrást, sok munkaidőt kell ráfordítani, másrészt természetesen adódik a kérdés: mennyire lesz az így kapott megoldás jó? Esetleg optimális. Hogyan lehetne a megoldás optimalitását bizonyítani?

Első lépésben meg kell fogalmazni a problémát a matematika nyelvén, ami egy NP-nehéz feladat, vagyis nincs rá „hatékony" algoritmus. A cél, egy olyan modell elkészítése, amely – heurisztikát is alkalmazva – használható legyen a gyakorlatban, vagyis elfogadható eredményt adjon, minél nagyobb méretű bemenetre, ésszerű időkorláton belül.

Az előadás során egy ilyen matematikai modell kerül részletes ismertetésre. A modell a T-Systems Magyarország Zrt. által szolgáltatott adatokra (menetrendek, műszakok szabályai) kimenetként megadja, a sofőrök szükséges számát, és az egyes sofőrök műszakjainak leírását. A megoldás – a heurisztika alkalmazása és a futási idő korlátja miatt – nem (feltétlenül) optimális. A buszvezető hozzárendelési modellt a FICO-XPRESS program segítségével oldottuk meg, jóval gyorsabban, mint a szakértők. A megoldási módszerünk előnyei:

·         több hasonló minőségű (közel optimális) megoldást állít elő;

·         gyorsabb, mint a szakértők;

·         a szakértők feladata a probléma megoldásáról, áttevődik a modell megoldások elemzésére és a gyakorlat szempontjából legjobb megoldás kiválasztására,

·         a szakértő további feltételek/célok megfogalmazásán dolgozhat;

·         lehetővé válik a menetrend variánsok, minőségi összehasonlítása eggyel több szempont (buszvezetők hozzárendelése) szerint.