文/程一祥
如果有一天,你能用第一手航空實戰數據,留下一個算法,帶走一個世界級航空難題,順便拿走幾十萬獎金,聽起來是不是還蠻酷的?
聽說你的航班又雙叒叕延誤了?
DT君曾經有一個夢想,就是成為一個「空中飛人」:坐著高端的航班,帥氣地穿梭在藍天白雲間,日程滿滿地出席一個又一個高大上的活動,分享自己在成為數據網紅道路上的微小經驗。
如今,夢想常常只能實現一半,我本應是個「飛人」,卻由於航班延誤,經常呆在「地上」。尤其是遇到北京的冬天和上海的夏天,霧霾和梅雨常常讓準點飛行都成了奢望。
當遇上航班大面積延誤,作為乘客的DT君也只能幹著急。
(圖片說明:DT君今年的部分空中痕跡,橫跨祖國南北,霧霾、梅雨什麼的簡直是DT君的航班剋星。)
面對航班大面積延誤恢復問題,航空公司其實比DT君更著急。極端的天氣狀況、運營的調配困難、飛機故障等問題,都有可能導致機場出現大面積航班延誤。一旦出現這種問題,航空公司所承擔的損失也非常巨大。比如地處東南沿海的廈門航空公司,就深受其擾。
廈航目前使用輔助人工決策的航班調整系統處理航班計劃,但在颱風等極端天氣對多基地運行造成影響的情況下,仍需要6小時左右才能將航班計劃梳理完畢。隨著運力的增長以及運行環境的日益複雜化,後續航班大面積延誤情況下,需要更長的時間梳理航班計劃,這顯然不能滿足對運行的快速響應需求。
為了縮短航班計劃恢復時間,必須有一套更智能、更科學的航班自動恢復系統算法,當遇到大規模延誤時,能夠自動對航班進行快速調整,快速恢復航班計劃,並有效優化公司的運營成本。
要開發這樣一套滿足要求的人工智慧算法可並不容易。航班延誤恢復問題是一個真正的世界級難題,目前沒有哪些航空公司能夠有效解決它。
讓更多的大數據人才參與進來或許是一個突破口。2017年6月,廈門航空聯合阿里雲舉辦智慧航空AI大賽,把這個「世界級難題」放在天池大賽的平臺上,交給了眾多數據俠來群策群力。
(圖片說明:廈門航空總信息師王洪建在現場觀看選手答辯)
廈門航空總信息師王洪建稱,「這是大數據及人工智慧在航空領域的一次重大嘗試」。來自全球17個國家和地區的1664支團隊參加了比賽,最終5支團隊脫穎而出,進入最後的決賽。
條條算法通羅馬,延誤再多也不怕
在這次天池智慧航空AI大賽中,廈航提供了脫敏後的真實業務數據,考題的設置也是依託運營中出現的實際情況而來。這對於數據俠們來說是一次真刀真槍的「實戰演練」。
歸根結底,數據俠就是要在航班大面積延誤後,提供一套「恢復算法」,能夠自動指導相關航班進行調整,使得受影響的航班旅客儘快疏散,未受影響的航班運行受影響最小,且恢復的綜合成本最低。
由同濟大學經管學院梁哲教授帶領的「同濟經管優化」隊,建立了基於列生成(column generation)框架求解的連接網絡模型,創新地改進了行列生成算法(column-row generation),克服了傳統時空網絡只能採取離散延誤策略的弊端。通過模型求解器結合遺傳算法、禁忌搜索算法和標籤算法,迅速求解該大規模整數規劃問題,精確求解了航班延誤時長以及籤轉大量航班取消的旅客。
數夢工場團隊的解決方案則是大領域搜索(Large Neighborhood Search,LNS)與混合整數線性規劃(Mixed Integer Linear Programming,MILP)。通過MILP模型可以精確地表達競賽提出的問題,但由於數量大,工程上無法直接求解 。用LNS框架每次只取一部分飛機和航班計算,可以實現快速迭代,在合理時間內獲得滿意的結果。
(圖片說明:數夢工場團隊在答辯現場展示團隊的算法過程)
來自新加坡的博士後夫妻組合「坡村坑U」,採用三階段迭代優化法來解決問題,步步為營。第一個階段主要優化飛機路徑和航班時間;第二階段固定飛機路徑,在精確考慮乘客取消、乘客延誤、普通乘客轉籤的前提下,優化航班時間和乘客安置;第三階段固定飛機路徑和航班時間,總體優化乘客成本。
(圖片說明:「坡村坑U「團隊在答辯現場展示團隊的算法過程)
雖然各個團隊使用的算法不盡相同,但是在解決實際問題方面都取得了非常好的預期效果,差別並不太大。
廈門航空運行指揮部副總經理林晴表示,如果將選手提出的算法方案應用在實際業務中,預期可以將航班大面積延誤恢復的時間,降低一個數量級,從小時縮減到分鐘。
以競賽的方式解決社會問題,讓數據落地
答辯時,同濟大學的梁哲教授很是感慨。他從碩士時就開始研究航空優化問題,當時導師告訴他說,這些研究一定會有用的。結果一等就是15年,直到今天(天池大賽)才真正把研究應用到實際業務中。
(圖片說明:梁教授和他的團隊最終獲得這次比賽的第一名)
這麼說雖然有些誇張,但是至少可以看出,過去學界和業界之間的聯繫不太緊密。這次天池的參賽隊伍絕大部分來自高校和科研單位,有72%具有碩士及以上學位。一直以來,學界往往有豐富的人才儲備,和前沿的算法研究,卻距離實際業務較遠。
另一方面,諸如廈航等公司往往在實際業務中積累了大量的數據和問題,但沒有時間和精力去優化業務。在大數據時代,雙方合作的模式已經成為不可避免的大趨勢。
馬雲在雲棲大會上也說到,在數據時代,企業家和科學家的完美結合,才有利於社會的長遠發展。阿里巴巴甚至投入了1000億元成立「達摩院」,整合學界和業界資源。
回到這次智慧航空大賽,如果這些算法要應用到廈航真實的業務場景中,還需要添加更多的數據維度限制,也就是說還有很大距離。但林晴副總經理告訴DT君,這些人工智慧算法未來若跟廈航業務相結合,將極大提升大面積延誤情況下航班恢復效率。
(圖片說明:所有決賽團隊在雲棲大會合影)
將企業問題放到天池平臺上,用實戰數據邀請社會範圍內的數據俠群策群力,以競賽的方式解決社會問題,DT君認為這是一個讓數據落地的積極嘗試。
最終,梁哲教授帶領的「同濟經管組合優化隊」取得了本屆大賽的冠軍。想知道這套算法最後是否真的能夠應用到廈航的系統中,等下次再當「空中飛人」的時候,不妨親自感受一下廈航的航班吧。
加入數據俠
數據俠計劃是由第一財經旗下DT財經發起的數據社群,包含數據俠專欄、數據俠實驗室系列活動和數據俠聯盟,旨在聚集大數據領域精英,共同挖掘數據價值,投稿、合作請與我們聯繫。