智能算法解航企難題
——記同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院教授梁哲

2019-05-07 06:00:54李明麗

科學(xué)中國人 2019年5期

□ 李明麗

工作中的梁哲

2018年10月11日，“同濟(jì)大學(xué)—廈門航空算法聯(lián)合實驗室”正式揭牌成立，這是中國首個聚焦民航領(lǐng)域的算法實驗室，致力于通過運籌學(xué)、人工智能等方法解決航空企業(yè)面臨的實際難題，提升整體的運營效率。

這一聯(lián)合實驗室由同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院教授梁哲領(lǐng)銜。憑借在航空算法領(lǐng)域深耕多年積累的豐富實戰(zhàn)經(jīng)驗，2017年6月，在廈門航空（以下簡稱“廈航”）聯(lián)合阿里云舉辦的智慧航空AI大賽中，梁哲帶領(lǐng)的團(tuán)隊從全球1644支隊伍中脫穎而出，贏得最后的冠軍。賽后，為將方案實施落地，廈航與梁哲團(tuán)隊開展了合作，目前解決大面積航班延誤的相關(guān)算法已在廈航正式啟用。而此次聯(lián)合實驗室的成立，又為雙方合作繼續(xù)向深入推進(jìn)提供了新平臺。

航班恢復(fù)機(jī)器戰(zhàn)勝了人

航班延誤的問題不只困擾著中國，在世界范圍內(nèi)，它都是一個令人頭疼的問題。當(dāng)延誤發(fā)生時，航空公司的運控中心會怎樣重新配置資源，并重新安排旅客，力爭以最小的成本，恢復(fù)飛機(jī)到計劃排班上呢？

梁哲告訴記者，通常情況下都是航空管制員憑經(jīng)驗決定，靠手動的方式進(jìn)行調(diào)整。人工調(diào)控的方式，既缺乏科學(xué)性又缺乏精確性，本就有限的飛行資源會在調(diào)控中被無形地?fù)p耗。

為減小不正常航班的影響，降低損失，梁哲開展了不正常航班恢復(fù)問題的研究，并提出了航班恢復(fù)優(yōu)化模型。

梁哲提出的這套模型及相關(guān)算法可以在30分鐘內(nèi)對2000班航班的大規(guī)模恢復(fù)問題求得3%之內(nèi)的近似最優(yōu)解，適用于我國絕大部分航空公司。正是憑借這套模型和相關(guān)算法，梁哲參加了2017年由阿里巴巴集團(tuán)和廈航聯(lián)合舉辦的旨在降低我國航空延誤的智慧航空AI大賽，并取得了初賽、復(fù)賽、決賽第一名的好成績，更迎來了與業(yè)界合作的機(jī)會。目前，基于模型算法建立的航班恢復(fù)系統(tǒng)已正式在廈航上線應(yīng)用。

梁哲介紹，上線后廈航舉辦了一場人機(jī)比賽，結(jié)果是機(jī)器戰(zhàn)勝了人。“雖然人輸了，但是對于航空管制員來說這并不是壞事，因為從機(jī)器給的結(jié)論里面，他們可以學(xué)到一些調(diào)航班的新技巧。”梁哲笑著說。

求飛機(jī)維護(hù)路徑問題的最優(yōu)解

近年來，我國的航空公司、空域管理機(jī)構(gòu)、機(jī)場3個決定航班是否能順利運營的主要部門，都在積極應(yīng)對不斷增長的旅客出行需求。航空公司不斷購買最先進(jìn)的飛機(jī)型號以及信息系統(tǒng)，空管投入大量資金建立飛行信號跟蹤和控制系統(tǒng)，并不斷有大型的機(jī)場在建和擴(kuò)建。雖然在民用航空領(lǐng)域的硬件投入上我國已經(jīng)達(dá)到了世界先進(jìn)水平，然而，我國的航空管理水平仍然有進(jìn)步空間。因此，如何運用現(xiàn)代化的科學(xué)技術(shù)來管理好已有的航空設(shè)施及其運營系統(tǒng)，使其發(fā)揮出最佳的效率，便成為當(dāng)前學(xué)術(shù)界和航空業(yè)者面臨的重要課題。

在國家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項目、國家自然科學(xué)基金重點項目，上海市曙光學(xué)者項目的支持下，針對導(dǎo)致航班延誤的3個主要因素，梁哲開展了研究。除了面向航空公司的不正常航班恢復(fù)問題外，梁哲還重點研究了飛機(jī)維護(hù)路徑問題、繁忙航路排程問題這兩個有針對性的科學(xué)問題。

飛機(jī)維護(hù)路徑問題之所以成為航空運營的主要問題之一，除了因為飛機(jī)維護(hù)是保障航空安全運營的重要環(huán)節(jié)外，更因為在保證飛機(jī)及時維護(hù)的同時，如果飛機(jī)航班路徑安排合理，就可以緩解延誤在航班間的傳播，從而減少航班延誤并提高航空公司的利潤。因此，飛機(jī)維護(hù)路徑問題是一個同時涉及飛行安全、航班延誤和公司利潤，極具重要經(jīng)濟(jì)和社會意義的問題。

針對傳統(tǒng)主流方法的局限性，自攻讀博士開始，梁哲就一直致力于飛機(jī)維護(hù)路徑問題解決方案的研究。經(jīng)過多年堅持不懈的探索，他提出了以周為單位的回旋時空網(wǎng)絡(luò)模型。該模型決策變量數(shù)量隨航班數(shù)線性增加，可以利用商業(yè)軟件直接求解，求解速度非常快，對近似全球最大規(guī)模的飛機(jī)維護(hù)路徑問題，可以在15分鐘內(nèi)得到最優(yōu)解。另外，梁哲提出的機(jī)型分配與飛機(jī)維護(hù)路徑聯(lián)合模型，克服了傳統(tǒng)模型依次求解的缺陷，可以得到全局最優(yōu)解。此聯(lián)合模型適用于我國多數(shù)中小型航空公司。

換思路解航路排程問題

算法實驗室揭牌儀式

梁哲告訴記者，導(dǎo)致航班延誤的因素很多，但我國空域管理的現(xiàn)狀本身就是一個無法繞開的坎兒。我國大部分空域為軍事管制區(qū)域，只有15%的陸地空域為民用航空空域，歐美國家正好相反。這就導(dǎo)致了我國的可用航路相比歐美國家來說非常有限，特別是京津冀城市群、長三角城市群、珠三角城市群之間的航路，非常擁堵。當(dāng)不同航班要求使用同一航路的同一飛行高度，且航班之間間隔過短時，就會產(chǎn)生航班沖突，影響飛行安全。

以歐美為主的航空網(wǎng)絡(luò)中，空域航路由于較為開闊，出現(xiàn)航路航班沖突的情況遠(yuǎn)少于我國。因此，其主流的航路航班排程方式主要依靠由美國工程院院士Dimitris Bertsimas于1998年提出的模型。但遺憾的是該模型主要利用調(diào)整航班時間來避免航路的沖突，這并不適用于我國航空業(yè)面臨的問題。

“如果換個思路呢？除了時間能調(diào)整，航班飛行的高度層也可以調(diào)整，這和道路交通中換一個車道避開擁堵是同樣的道理。”梁哲是這樣想的也是這樣做的，而且做成了。

按照這個思路，他提出了在時間和空間兩個維度同時優(yōu)化航班排程的方案，并提出了在考慮航班延誤的同時，也考慮不同飛行高度層對飛機(jī)飛行油耗的影響。而且為了增加模型的實際應(yīng)用價值，他還提出了在調(diào)整航班時考慮不同航空公司所受影響的公平性問題。梁哲提出的這套模型及相關(guān)算法可以在1小時內(nèi)解決400架航班的航路排程問題，非常適用于我國京津冀城市群、長三角城市群、珠三角城市群之間的擁堵航路。

理論方法研究可圈可點

除了在航空運營管理上有所建樹外，在大規(guī)模整數(shù)規(guī)劃的理論方法研究上，梁哲取得的成績也是可圈可點。以分支定界和列生成為主要研究手段，梁哲解決了一系列在交通、物流、數(shù)據(jù)挖掘等領(lǐng)域的大規(guī)模整數(shù)問題。

在分支定界理論研究中，梁哲將數(shù)據(jù)科學(xué)的一些有效方法用于分支定界中，提出了逐步選擇變量法。他利用大量算例驗證了將數(shù)據(jù)科學(xué)方法融入整數(shù)規(guī)劃求解方案的有效性，并利用此方法解決了兩個較為復(fù)雜的組合優(yōu)化問題，產(chǎn)生了優(yōu)于傳統(tǒng)方法的效果。梁哲的研究成了為數(shù)不多的試圖將數(shù)據(jù)科學(xué)理論與傳統(tǒng)整數(shù)規(guī)劃相結(jié)合的理論研究之一。

在列生成方法對不確定性問題的應(yīng)用研究中，通過轉(zhuǎn)換建模的方式，梁哲將不確定性分解在變量中，變成了確定性問題。通過建立的模型，梁哲解決了兩個帶有不確定性的優(yōu)化問題，首先是利用列生成解決了不確定性延誤的飛機(jī)維護(hù)路徑問題；其次是解決了生物信息學(xué)中的種群重組問題。梁哲的模型得到的結(jié)果無論在耗時還是準(zhǔn)確性上都優(yōu)于傳統(tǒng)的方法。

秉持立足實際、解現(xiàn)實難題的原則，在“航空運營管理”和“大規(guī)模組合優(yōu)化”兩個研究領(lǐng)域，梁哲將理論和應(yīng)用相結(jié)合，盡量做到了“頂天立地”，他的研究成果引起了國內(nèi)外學(xué)者的廣泛關(guān)注，并得到了航空業(yè)界的認(rèn)可。目前，梁哲已與國際著名航空服務(wù)供應(yīng)商Sabre、廈門航空、東方航空公司開展了深度合作，并和兩位美國優(yōu)化領(lǐng)域的著名學(xué)者——密歇根大學(xué)工業(yè)工程系的Amy Cohn教授以及得克薩斯州立大學(xué)奧斯汀分校工業(yè)工程系的Jonathan Bard教授，一起成為2016年Sabre的高校合作者。

讓中國軟件走出去

團(tuán)隊合影

其實，航空運營管理領(lǐng)域的這些研究只是梁哲諸多研究方向中的其中一個，物流、港口、電信等很多領(lǐng)域，他的研究都有所涉及。雖然涉及的面很多，但梁哲說他個人的大部分精力還是投在了航空領(lǐng)域。“一輩子能做好一件事情挺不容易，我個人的愿望就是把國內(nèi)航空運營這一塊做好、做透。”梁哲這樣說。

2018年梁哲又迎來了一項新任務(wù)，他負(fù)責(zé)的“航空運營中的大規(guī)模組合優(yōu)化問題及算法研究”獲得國家自然科學(xué)基金杰出青年科學(xué)基金項目的支持。以前期大量的研究、調(diào)研以及與航空業(yè)者的深入溝通為基礎(chǔ)，梁哲計劃發(fā)揮已有的經(jīng)驗，在夯實自身研究的同時，從航空公司和機(jī)場這兩個較易入手的層面，基于飛機(jī)、機(jī)場以及人員3個視角，解決4個航空業(yè)者特別關(guān)注的影響航班正常運營的科學(xué)問題。其中，前兩個問題是航空公司和機(jī)場協(xié)同合作的運營管理問題，分別是考慮維護(hù)靈活性的航班恢復(fù)問題以及考慮不確定性飛行速度和轉(zhuǎn)機(jī)時間的飛機(jī)航班恢復(fù)問題。后兩個問題主要是機(jī)場面臨的重要問題，分別是考慮旅客轉(zhuǎn)機(jī)的登機(jī)門分配問題以及考慮移動時間的機(jī)場人員分配問題。

梁哲希望，通過探索適用于新問題的最大完全圖或較大完全圖的多項式算法，給出較為緊湊的整數(shù)規(guī)劃模型；開發(fā)大規(guī)模問題的快速算法，去求解此類問題；并通過與航空企業(yè)的合作讓這些算法盡快落地。

習(xí)近平總書記說過：“廣大科技工作者要把論文寫在祖國的大地上，把科技成果應(yīng)用在實現(xiàn)現(xiàn)代化的偉大事業(yè)中。”對這句話的內(nèi)涵梁哲深有體會。參加智慧航空AI大賽前，每次去航空企業(yè)推銷他的方案，對方都會問：“這個東西有人用過沒有？用處大不大？”“現(xiàn)實很殘酷，只有有用的東西才有市場。”梁哲說。

正是智慧航空AI大賽給了梁哲一個被業(yè)界檢驗的機(jī)會，廈門航空肯定了他的工作，通過后續(xù)開展的實際合作，梁哲的研究終于落了地，有了好口碑后，國內(nèi)的航空公司陸續(xù)找上門，多年的理論研究終于有了實際應(yīng)用的機(jī)會。“同濟(jì)大學(xué)—廈門航空算法聯(lián)合實驗室”的正式成立，對梁哲來說更是如虎添翼。現(xiàn)在，他最大的夢想就是讓中國的航空運營軟件走出國門，展示我們自己的實力。

在新加坡、美國求學(xué)工作多年的梁哲，除掌握了國際領(lǐng)先的科學(xué)知識外，在國外的所見所聞更讓他認(rèn)識到了中國潛在的實力。“國家有充足的人才儲備，中國人勤勞又不缺乏智慧，只要我們認(rèn)真鉆研，一定能比外國人做得更好。”對于梁哲來說，做中國自己的航空運營軟件已成為他一以貫之的目標(biāo)。