A probléma

A légiközlekedésben az üzemeltetési költségek jelentős része a repülőgépek üzemeltetéséhez szükséges munkaerőhöz kötődik. Ezért a légitársaságok komoly erőforrásokat fordítanak a személyzettel kapcsolatos költségek optimalizálására, miközben be kell tartaniuk a munkajogi szabályokat, a működési korlátokat és a szakszervezeti megállapodásokat. A személyzettervezés összetettsége miatt a teljes problémát általában egymást követő részproblémákra bontják, amelyek mindegyike önálló optimalizálási kihívást jelent.

Az egyik ilyen részprobléma a műszakok megtervezése (Airline Crew Pairing, ACP), azaz a légiközlekedési műszaktervezési probléma. Ebben az összefüggésben egy repülőút-sorozatot akkor nevezünk repült munkaperiódusnak (pairing), ha az a bázis, ahonnan az első repülőút (szektor) indul, megegyezik azzal, ahová az utolsó szektor megérkezik, és emellett minden működési és szabályozási követelmény is teljesül.

A kapcsolódó költségek több elemből állnak, például a menetrend teljesítéséhez szükséges személyzeti munkanapok számából, a szállásköltségekből, valamint a rendkívüli események - például késések vagy a személyzet megbetegedése - iránti ellenálló képességből.

A vizsgálat célja

Azt vizsgáltuk, hogyan alkalmazhatók a kvantumszámítógépek a légiközlekedési személyzetbeosztás-tervezési problémára egy mélyen integrált, hibrid kvantumos-klasszikus optimalizálási megoldás részeként.

Az eredmény

Teljesen hibrid megoldási módszer készült, amelyben a kvantum- és a klasszikus rendszerek ugyanazon optimalizálási folyamaton belül működnek együtt. A megközelítés hosszú távon ígéretes gyakorlati lehetőséget mutat, a jelenlegi kvantumhardver képességei azonban ma még jelentősen korlátozzák a megoldható problémák méretét és összetettségét.

A munka tudományos összefoglalása

A probléma bemenete a menetrend - az egyes repülőutak listája a hozzájuk tartozó működési adatokkal, például az indulási és érkezési időkkel, a repülőgéptípussal és a személyzeti igénnyel -, továbbá a teljesítendő működési szabályok és az érvényes körutakhoz (repült munkaperiódusokhoz) tartozó költségek.

A választott algoritmikus megközelítés kétszintű, generálás-kiválasztás (generate-then-select) keretet követ. Először az érvényes repült munkaperiódusok előállítása történik: az összeillő szektorokból érvényes körutak épülnek. Ezután ezek közül egy olyan részhalmazt választunk ki, amelyben minden szektor pontosan egyszer szerepel.

A második szakaszt bináris lineáris optimalizálási problémaként, egyenlőségi feltételekkel fogalmazzuk meg; ez az úgynevezett halmazpartícionálási probléma (Set Partitioning Problem, SPP). A gyakorlati alkalmazásokban számos technika alkalmazható a számítási teljesítmény javítására. Ebben a munkában azonban a hangsúly azon volt, hogy a megközelítés kvantumhardveren megvalósítható-e.

Az SPP-t hibrid feltételgenerálási (constraint generation) módszerrel oldottuk meg. Az algoritmus úgy indul, hogy az összes feltételt relaxálja (elhagyja). Ezután megoldja a problémát kvantumszámítógép segítségével, majd a kapott eredmény alapján visszavezeti a feltételek egy részét. Ezután ismét megoldja kvantumszámítógépen a kapott problémát. Ezt addig ismétli, míg vissza nem kapja az eredeti problémát, azaz minden feltételt visszavezet, vagy talál megoldást, amely legtöbb esetben a konstrukció miatt jó minőségű is.