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

『运筹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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180508G0WKIX00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券