运筹学在航空业有哪些应用？

『运筹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,后者的效率有系统性的提升。

以上『运筹OR帷幄』专栏所有文章都会同步发送至@留德华叫兽的头条主页，以及同名微信公众号，目前预计受众10w +

ENG

转载请联系本公众号获得授权