Az MTA doktorai: Békési József a közlekedési problémák megoldását is segítő operációkutatásról

Békési József operációkutatással foglalkozik, amely talán az alkalmazott matematika informatikához legközelebb eső területe. „Az operációkutatás legfőképpen optimalizálási feladatok megoldását jelenti. Rendszerint alkalmazott optimalizálással, tehát valamilyen gyakorlati probléma optimális megoldásának a kiszámításával foglalkozunk – mondja Békési József. – Ha elméleti optimalizálásról beszélünk, akkor általában egy függvény szélsőértékét, minimumát, maximumát szeretnénk kiszámolni. Ezen belül én diszkrét optimalizálással foglalkozom. Ez azt jelenti, hogy az általunk vizsgált pontok jól elkülönülnek egymástól, és ezeken a pontokon szeretnénk valamilyen függvényt optimalizálni.”

Békési József

Az optimalizálási feladatok legnagyobb nehézségét az adja, hogy nagyon sok gyakorlati probléma olyan összetett feladathoz vezethet, amelyre hiába készítünk matematikai modellt, annak tökéletesen optimális megoldását még a számítógépek is akár évezredekig, évmilliókig számolnák. Itt nem is kell különösen bonyolultnak tűnő problémákra gondolnunk. Békési József például

közlekedési problémákkal, a szállítmányozás során felmerülő problémákkal, illetve különböző pakolási és ütemezési problémákkal foglalkozik.

E területeken már a mindennapos nehézségek is, például amikor néhány száz helyre kell szállítani valamilyen termékeket, vezethetnek olyan mérvű feladatokhoz, amelyek optimális megoldását nagyon nehéz kiszámítani.

Békési József matematika szakon végzett, de már egyetemi hallgatóként érdekelte az informatika, a számítástudomány, mivel akkoriban kezdett elterjedni a világban a számítógépek használata. Így egyetemi tanulmányai után az akkori Juhász Gyula Tanárképző Főiskola Számítástechnika Tanszékén helyezkedett el, ami később a Szegedi Tudományegyetem egyik kara lett, jelenleg az SZTE TTIK Informatikai Intézetében dolgozik. Mindig is nagyon érdekelték a gyakorlati alkalmazások. „Sok úgymond hétköznapi problémával foglalkoztam, amelyek mindenki életében nap mint nap felmerülnek. Például útvonaltervezés közben két pont között kell meghatározni a legrövidebb utat – folytatja Békési József. – Ez egy viszonylag egyszerű optimalizálási probléma: gráfokkal szokás modellezni az úthálózatot, és ezen a gráfon könnyen ki lehet számolni két pont között az optimális távolságot. Ez ma már könnyen megy, mindenki telefonján vannak ilyen alkalmazások, de annak idején erre is meg kellett tervezni a megfelelő algoritmusokat. A gyakorlatban mi is algoritmusokat alkotunk, amelyek megoldják az éppen vizsgált optimalizálási problémát.”

Az operációkutatáson belül Békési József két nagyobb területtel foglalkozik: a pakolásokkal és az ütemezésekkel. E problémáknak elméleti és nagyon is gyakorlati vonatkozásaik egyaránt vannak. A ládapakolást lehet többféle dimenzióban és változatban értelmezni az elméleti kutatásokban, de sokszor szó szerint ládákról, illetve szállítandó csomagok optimális elhelyezéséről van szó. „Mindennapos probléma, hogy egy cég szeretné a termékeit dobozokba csomagolva elszállítani a megrendelőkhöz. E dobozokat föl kell pakolni raklapokra, a raklapokat pedig járművekre, majd meg kell tervezni a járművek útját is – magyarázza Békési József. – Minden lépést optimálisan kell megtervezni, hiszen a cél az, hogy minimalizálják a költséget. Ehhez el kell dönteni, hogy hogyan pakoljuk föl az árut, mely termékeket melyik járművekre helyezzük, és milyen úton közlekedjenek utána, hogy maximális legyen a teherautók kihasználtsága, és minimális az átaluk megtett táv. Ez már kis léptékben is nagyon összetett feladat.”

Ha túlságosan nagy léptékű problémával állnak szemben, előfordul, hogy az optimális (legnagyobb hatékonyságú) megoldás kiszámítása a gyakorlatban megvalósíthatatlan, hiszen egy romlandó árut szállító vállalat nem várhat ezer évig a műszak elején, mire a számítógép előáll a tökéletes válasszal. Békési József sok tökéletesen szinte megoldhatatlan problémával foglalkozik elméleti és gyakorlati szempontból egyaránt.

Ilyenkor olyan algoritmusokat használnak, amelyek nem garantálják az optimális megoldást, de a lehető legjobban megközelítik.

Ezeknek a közelítő algoritmusoknak hatalmas a gyakorlati jelentősége, viszont elméleti szempontból is vizsgálni kell őket, hiszen értékelni kell a hatékonyságukat.

„Az elméleti kutatások során azt vizsgáljuk, hogy az adott algoritmus mennyire lehet jó. Ezáltal információt tudunk szolgáltatni arról is, mennyire hatékonyan lehet az adott problémát megoldani – mondja a matematikus. – Vizsgálhatjuk, mennyire lehet gyors egy algoritmus. Ez az egyik legfontosabb kérdés, hiszen hiába van egy nagyon jó algoritmusunk, ha nem képes elfogadható időn belül megoldani a problémát. Ilyenkor keresnünk kell egy olyan algoritmust, ami ha nem is olyan pontos, de elfogadható idő alatt végez.” Ez a terület az algoritmuselemzés, Békési József szűkebb szakterülete.

A pakolási és útvonalkeresési feladatok mellett az operációkutatás sokszor ütemezési megoldásokat keres. Rendszerint adottak bizonyos feladatok, amelyeket gépekhez kell rendelni. Nemcsak gyártógépeknél merül fel ez a probléma, hanem például közlekedési eszközöknél is. A közlekedési vállalatoknak mindennap végre kell hajtaniuk a menetrendben meghatározott feladatokat, és ehhez optimálisan kell egymáshoz rendelniük a járműveket, a járművezetőket és a járatokat. „Ez még egy közepes méretű városban is, például itt Szegeden igen összetetté válhat. Budapesten pedig már nem is lehet egyben kezelni az egész tömegközlekedést, hanem részekre kell bontani az optimalizációs számítások előtt.

Ha jól sikerül megtervezni a rendszer működését, akkor az nap mint nap nagy eredményt hozhat: kisebb költséggel lehet jobb szolgáltatást nyújtani”

– vélekedik a kutató.

Vannak olyan gyakorlati optimalizációs feladatok, amelyek rendszeresen és tervezhetően ugyanúgy ismétlődő problémákat kezelnek. De gyakran előfordul – és ezekkel Békési József is sokat foglalkozott –, hogy nem tudják előre, mik lesznek az aktuális inputok. Például nem ismerik a hamarosan beérkező megrendeléseket. Ilyenkor úgy kell megtervezni az optimalizációs algoritmust, hogy fel legyen készülve azokra a jövőbeli körülményekre, amelyek megváltoztathatják a helyzetet, és amelyek miatt esetleg át kell alakítani a tervet. Ugyanígy a közlekedésben is előfordulhatnak váratlan események, például az egyik jármű működésképtelenné válik, vagy baleset történik. „Hogyan lehet megoldani e helyzeteket? Hogyan lehet úgy átalakítani a napi munkát, hogy az új környezetben is minden működjön? A gyakorlati optimalizáció során fel kell készítenünk az algoritmust a váratlan (de mégis előre látható) helyzetekre is – mondja Békési József. – Nagyban függ a feladattól, hogy milyen hosszú időtávra lehet előre tervezni. A személyzetvezénylési problémáknál előfordul, hogy akár egy egész hónapra megtervezhetjük a dolgozók napi munkáját, hiszen ott ritkábbak a rendkívüli helyzetek, bár ott is előfordulhatnak. A szállítmányozás és a közlekedés viszont olyan területek, ahol rendkívül sok körülmény ismeretlen előre, és folyamatosan kell reagálnunk a dinamikusan változó szituációra.”