【學界】運籌學在航空業有哪些應用?
作者: @胖驍
『運籌OR帷幄』責任編輯: @愛牛氓的帆爺(東北大學系統工程碩士生)本篇文章是由以上作者在知乎上的優秀回答(原文鏈接:胖驍:運籌學在航空業有哪些應用?),通過『運籌OR帷幄』責任編輯整理修改而成的。歡迎原鏈接轉發。敬請關注和擴散本專欄及同名公眾號,會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態:
『運籌OR帷幄』大數據人工智慧時代的運籌學 【運籌OR帷幄】專欄徵稿
「前言」
運籌學的應用場景非常廣泛,本文主要是針對運籌學在航空業的應用。
1、機票定價
動態定價最早的應用就是在機票販賣上了。動態定價領域最著名的論文就是Gallego & Van Ryzin在1994年寫的『Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons』,考慮的是如何在有限的時間內通過動態定價最大化營收,其中最直接的應用就是機票定價了。很多人認為機票價格是一種價格歧視策略,其實不只是這樣,動態定價本身是對『時間』資源和『庫存』資源的實際價值的衡量(學過線性規劃對偶的應該知道影子價格,影子價格就是資源的實際價值)。早期的論文一般講需求看成一個已知的隨機過程,這些年也將機器學習的思想融入其中,邊學習需求函數邊定價,比如『Pricing from Observational Data』以及『Dynamic Pricing and Demand Learning with Limited Price Experimentation』。另外,過去人們常常認為動態定價是對消費者剩餘的剝削,最近Gallego的論文『Welfare Analysis of Dynamic Pricing』中討論了在成本不完全固定的情況下,對於大多數流行的需求模型,動態定價使消費者和賣家雙贏。
2、機票販售
定價和販售並不是一回事,實際上即使價格固定,如何更合理的賣票來最大化收入也是個很有趣的問題。舉下面三個例子:
最近很火的美聯航事件涉及到了超額售票的問題,其實超額售票是合法合理的,美聯航事件本身跟超額售票無關,否則一般在登機前就會攔下。
如何確定超額售票的數量是個應用概率的問題。之所以要超售,原因如下:
(a)每一班航班No Show人數的概率分布比較穩定,風險可控。
(b)航空業中的固定成本比例很大,在revenue上提升一點點可能會帶來利潤上極大的提升。比如收入100成本99的情況下,如果能夠增加1%的收入,那利潤就變成了原來的兩倍。因此這個風險是值得一冒的。
當你購票的時候,如果你想買北京到上海的機票,可能有一萬種路徑,可是真正顯示出來的只有那麼有限的幾個,那麼哪些機票航班會顯示給你呢?這個問題叫「optimal assortment problem」,最著名的當屬Van Ryzin在2004年發的『Revenue Management Under a General Discrete Choice Model of Consumer Behavior』,以及Gallego在同一年寫的『Managing Flexible Products on a Network』 (對就是1994年寫動態定價的那兩位大牛。。)由廣告排序引出來的問題可就多啦,比如通過學慣用戶的瀏覽記錄給顧客更針對的排序,這種問題叫online assortment以及online matching,最近幾年算是熱門的領域了,比較impressive的論文比如這個『Real-Time Optimization of Personalized Assortments』(好吧其實我只是聽了這個作者的Job Talk而已哈哈)
機票販售以及酒店預訂領域還有一個很有趣的東西叫模糊產品,其實就是不讓你選座位,床型等等,同時給予折扣。因為酒店的房間和飛機的座位都是成本固定的,所以通過這樣的方式可以相當程度上節約成本(降低空閑率),以此獲得更大的利潤。這種產品在上面提到的『Managing Flexible Products on a Network』 就有涉及。
3、航班規劃
上面絮絮叨叨扯了半天自己了解的領域,其實運籌學最直接的領域當然是航班路線規劃啦!網路優化在運籌學裡算是很大的一個領域,而航班路線本身又是一個天然的網路,由此引申出來的問題就很多很多啦。比如:
(a) 空運如何才能最大化效率,畢竟除了運人還有快遞。
(b) 每家航空公司要設計自己的航班路線,爭取覆蓋盡量全並且收入最大化等等。
(c)評估和最小化航班延誤的損失,其中發現比較重要的航班叫做critical path problem,評估損失叫survival analysis,金工里有些paper會假設金融機構是一個網路圖,然後用同樣的方法來評估系統性風險。
這個領域我了解的不多,兩年前好好學過一會,但是不太感興趣,現在能記得的paper只有這個survey paper:『Airline Schedule Planning: Accomplishments and Opportunities』。
4、其他
其實航空領域還有很多細小的地方應用到了運籌學。
機組指派問題,英文叫airline crew scheduling/pairing problem,看過的paper有這個『A Stochastic Programming Approach to the Airline Crew Scheduling Problem』。跟很多人在本科各種各樣的課上學過的指派問題(用匈牙利法那個)不同的是,機組指派問題需要考慮時間變數以及後續的事件,比如a機組從北京飛到上海就只能飛上海的航班了,而且人家還必須回到北京,這個問題的複雜度就大多了。類似的還有登機口指派問題,就不多說了。
計程車位規劃問題,這個是上學期聽隨機過程老師講的,說過去北京國際機場的計程車以前都是一個一個排好隊,來一個人走一輛車,司機要排好久才能排到。現在改成可以有好幾個車在前排候客,也就是人在排隊,車可以排好幾個隊。第一種情況可以看成single server queue system,而第二種可以看成multi-server queue system,後者的效率有系統性的提升。
如果你是運籌學/人工智慧碩博或在讀,請在下圖的公眾號後台留言:「加微信群」。系統會自動辨認你的關鍵字,並提示您進一步的加群要求和步驟,邀請您進全球運籌或AI學者群(群內學界、業界大佬雲集)。
同時我們有:【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群,想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕,獲得入群傳送門。
學術界|工業界招聘、徵稿等信息免費發布,請見下圖:
推薦閱讀: