Kvantumtechnológia a légi közlekedésben
Azt vizsgáltuk, hogyan alkalmazhatók a kvantumszámítógépek a légi kö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.
A probléma
A légi kö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. Ennek során 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égi közlekedési műszaktervezési probléma. Itt 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 abból, mennyire ellenálló a terv a rendkívüli eseményekkel, például a késésekkel vagy a személyzet megbetegedésével szemben.
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, vagyis az egyes repülőutak listája a hozzájuk tartozó működési adatokkal (indulási és érkezési idő, repülőgéptípus, személyzeti igény). További bemenetek 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, majd a kapott problémát ismét megoldja kvantumszámítógépen. Ezt addig ismétli, amíg vagy minden feltételt visszavezetett, és így az eredeti problémához jutott, vagy olyan megoldást talált, amely a konstrukció miatt a legtöbb esetben jó minőségű.