运筹学在航空运输管理中的应用12.27PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,OR in Air Transportation,中国民航大学管理学院,*,运筹学在航空运输管理中的应用12.27,主要内容,国内外有关航空运输管理研究的杂志、研究机构,运筹学在航空运输管理中的主要应用领域,典型问题研究,OR in Air Transportation,2,中国民航大学管理学院,国内外有关航空运输管理研究的杂志、研究机构,国内外有关航空运输管理研究的杂志,Transportation Research,Transportation Research Part B:Methodological,Transportation Research Part E:Logistics and Transportation Review,Journal of Air Transport Management,European Journal of Operational Research,Transportation Science,Operational Research,国内外有关航空运输管理研究的机构,AGIFORS,The Airline Group of the International Federation of Operational Research Societies,M.I.TInternational Center for Air Transportation,NASA Center,Langley Research Center,Manchester Metropolitan University The Centre for Aviation Transport and the Environment,George Mason University Center for Air Transportation Systems Research,Embry-Riddle Aeronautical University,，,Cranfields,University,OR in Air Transportation,3,中国民航大学管理学院,IFORS&AGIFORS,国际运筹学会（,IFORS,）除包括各国或地区运筹学会外，还包括航空运输组,(AGIFORS,Airline Group of IFORS),，专门研究运筹学在航空运输中的应用问题,50,年来至少,1000,多篇文章在,Operation Research,，,Transportation Science,等相关刊物上发表,UA,，,AA,，,BA,，,AF,等国际著名航空公司都设有,OR Group,OR in Air Transportation,4,中国民航大学管理学院,AGIFORS,AGIFORS is the outcome of informal discussions between six airline Operational Research workers(from Trans Canada,Air France,Sabena,BEA,and Swissair)who were present at the second international conference in Operational Research at Aix en Provence,France,in,1960,.These informal discussions led to the formation of a committee,which organized a Symposium on the use of,Operational Research within the airline industry,at Spring Valley,New York in October 1961.This Symposium was deemed successful and resulted in the formation of AGIFORS as,a professional society,dedicated to the free exchange of ideas and new advances in Operations Research within the airline industry.,Today the AGIFORS membership exceeds 1,200 professionals representing more than,200,airlines,airline manufacturers and aviation related industries and associations.,OR in Air Transportation,5,中国民航大学管理学院,运筹学各分支在航空运输管理中的应用,运筹学分支,应用案例,典型文献,规划技术,机队规划,机队规划模型的建立及其应用 Airline fleet assignment concepts,models,and algorithms,航班计划编排,Airline Schedule Planning,机组人员指派问题,aircrew assign problem,航空公司收益管理,航空公司收益管理研究综述 Yield Management at American Airlines,飞机排班,航空公司飞机排班问题的分阶段指派算法,网络技术,航线网络规划（网络拓扑、网络最大流、网络结点选择）,轴_辐侍服理念下的中国航空网络模式构筑 Airline Network Design and Profitabil ty A Case for Re-regulation,空管流量控制,空中交通流量管理研究综述,停机位分配问题,民用机场停机位优化配置,机场进出港航班控制,空中交通地面等待的指派问题模型,决策技术,枢纽机场选址问题,枢纽航线网络的构建方法及应用,机场运营效率评价,An analysis of the operational efficiency of major airports in the United States,航线经营决策,航空公司航线决策的一种系统方法,排队论,值机柜台、安检服务问题,跑道容量管理,空中交通流量管理中的多机场地面等待策略,库存论,航班坐位控制,Air Travel Demand and Airline Seat Inventory Management,航材库存问题,对策论,航空联盟,airline alliance,航空公司竞争问题,Airline Competition,航空公司与机场竞争合作问题,Regulation,competition and network evolution in aviation,OR in Air Transportation,6,中国民航大学管理学院,运筹学在航空运输管理中的典型领域,运筹学,对,有限的资源,进行优化配置，,以求系统最优,的科学决策方法,飞机和机组排班,飞机维修计划,空中流量控制,停机坪作业管理,航空公司收益管理,航线网络规划,机场运营效率评价,OR in Air Transportation,7,中国民航大学管理学院,收益管理,我们应用运筹学方法解决管理问题的实践,鲍伯,克兰于,80,年代中期率先将收益管理应用于美利坚航空公司，使该公司的收益每年增加,5,千万美元以来，收益管理在美国国内已被广泛应用于铁路、宾馆等行业。,收益管理是在经济学、统计学、预测技术、优化技术和计算机技术基础上形成的一套科学的营销管理方法，核心内容是在合适的时间，将合适的产品以合适的价格销售给合适的消费者，实现收入最大化。,对航空公司来讲，收益管理就是在激烈的市场竞争条件下，决定同一航班上针对不同的等级票价，分别出售多少座位的问题。航空公司收益管理的两个主要因素为,等级价格和座位优化分配,。,OR in Air Transportation,8,中国民航大学管理学院,收益管理的发展历史,早期的航空客运方式,最早的航空客运，与今天的公共汽车一样谁先来，谁先上，到时间就开车。,SABRE电脑预定系统,1962年美利坚航空公司(AA)的SABRE公司造出了世界上第一台电脑订座系统（CRS）。,超售(Overbooking),航空公司发现有些订了座位的旅客不来上机，给航空公司造成了不少浪费。于是，航空公司开始实行超售（Overbooking)。,折扣票产生,航空公司为了吸引客人，采取降低票价(折扣票)的办法，来增加旅客人数。多级票价收益管理雏形。,放松管制，价格大战,废除了政府对航线和票价的所有管制,“92航空血战”1992年4月由美利坚航空公司发起的“92航空血战”。大陆航空公司，依靠他们的一套客运收益优化系统(Passenger Revenue Optimization System)赢得胜利。,OR in Air Transportation,9,中国民航大学管理学院,收益管理发展的三大条件,收益管理的发展主要有三个基本条件:应用条件航空运输业的发展;理论条件运筹学与管理科学的发展;技术条件计算机和网络技术的发展。,收益管理的理论基础 运筹学,运筹学和现代管理科学的发展为收益管理的产生、发展和成熟提供了必不可少的理论基础。,收益管理解决的是航空公司资源的优化配置问题，其研究几乎应用了运筹学大部分的理论和模型，尤其是线性规划、动态规划、网络分析技术等。,在早期的座位超售和座位分配问题的研究中，多是采用线性规划来建立模型求解，现在动态规划模型在收益管理问题的研究中己经得到了更多的应用，而仿真技术、博弈理论等也在航空收益管理中的到了越来越多的应用。,国际运筹学,协会,(IFORS),航空运输组，专门又设立了“,订座与收益管理研究小组”，专门研究航空公司收益管理的各种应用问题。,美国运筹学与管理科学学会也正在设立新的分支机构“收益管理部”。,OR in Air Transportation,10,中国民航大学管理学院,收益管理-一个简单的例子,设PEK-CAN的CA1311航班仅剩一个座位，有三种可能的需求：,票价等级,价格（元）,订座时间,订座概率（%）,A,500,航班起飞前一周,100,B,1000,航班起飞前三天,80,C,1300,航班起飞当天,50,应如何进行销售？,需要准确的预测需求，并随时间推移不断地更新预测结果！,OR in Air Transportation,11,中国民航大学管理学院,收益管理-一个复杂的例子,PEK-CAN的CA1311航班每一个座位都有多种可能的需求：,PEK-CAN：8种票价等级；,-马尼拉：10种票价等级,-新加坡：10种票价等级,-墨尔本：10种票价等级,如何销售这个座位？,需要预测每个航段、不同订座时间、不同票价等级的需求,需要计算不同航段不同时间不同票价等级的组合销售收入,每销售一个座位，对剩余座位的需求就会发生变化，需要重新计算,OR in Air Transportation,12,中国民航大学管理学院,收益管理决策支持系统结构,OR in Air Transportation,13,中国民航大学管理学院,收益管理系统核心模块,销售控制,超售管理,座位优化控制,团队管理,销售分析,需求预测,控制效果分析,销售信息系统,ICS、CRS、,离港系统,财务信息,市场信息,其它信息,定价(价格和限制条件),航班计划,OR in Air Transportation,14,中国民航大学管理学院,多级票价与座位优化控制,需求量,价格,0,经济舱需求曲线,2000元,100人,160人,1500元,多级票价是对不同消费群体提供不同的舱位和票价等级，以满足不同的需要，增加航空公司的收入,，,OR in Air Transportation,15,中国民航大学管理学院,多级票价与座位优化控制,基本思想是寻求每个座位的期望边际收益最大化,fi(s)、Bi、Pi,分别代表,i,等级的需求密度函数、i等级第B个座位和该等级的运价，,B,i,的期望边际收益表示为：,使用下列模型确定每个等级的座位分配数,xi,：,（CAP为给定运力）,OR in Air Transportation,16,中国民航大学管理学院,期望边际座位收益（EMSR）,闲暇旅客,拒绝,接受,将座位售给公务旅客的概率P,座位空闲的概率1-P,公务旅客运价￥y,闲暇旅客运价￥q,EMSR,座位分配方法的核心用下面的,决策树,说明：,P,为得到潜在公务旅客的概率，￥,yP,为将座位售给公务旅客的收益，￥,q,为将座位售给闲暇旅客的收益。设有两个运价等级：,Y,，,Q,；舱位虚拟运力为,AC,。,OR in Air Transportation,17,中国民航大学管理学院,座位分配中的嵌套结构,座位分配仅是概率意义上的优化,为保护潜在的全价收入，在座位分配中使用嵌套结构，使折扣票可订到的座位，全价票也能订到,子等级 需求 保护座位数 分配座位数,Y Yd=10 Yd=10 CAP=50,Q Qd=15 Qd=15 CAP-Yd=40,V Vd=25 CAP-Yd-Qd=25,Q舱分配座位=CAP-Yd,V舱分配座位=CAP-Yd-Qd,Yd,Qd,全部可售座位=CAP,OR in Air Transportation,18,中国民航大学管理学院,网络座位控制,也称O&D控制，在轮辐式航线网络中，航空公司要在不同航程的旅客间进行选择，以获取更高的收入。优化的座位分配取决于所有相关航程的价格和需求,每个座位在出售之前进行实时评价，确定每个航班的最低可售价格，即bid price，它代表获得一个座位的机会成本。每个给定运价等级只要高于bid price，就可获得座位,OR in Air Transportation,19,中国民航大学管理学院,超售,重复订座,虚假订座,订座后又取消（Cancel），,使航空公司失去销售机会,旅客错过,航班,出票后不去机场乘机（No-Show），,造成空座损失,航空公司不得不超过航班座位数接受订座和售票，,既避免损失，也更好的为旅客服务,超售的原因,OR in Air Transportation,20,中国民航大学管理学院,超售计算模型主要概念,超售（OverBooking）就是在需求旺盛时，允许航班订座数大于航班物理座位数。但在实际要求登机人数大于航班舱位物理容量时，必须有偿拒绝部分旅客的合理登机要求（DB）。因此，需要在超售和DB之间均衡。超售计算是针对物理舱位的，不针对订座等级。,定义1：舱位虚拟运力VC：VC=实际座位数+订座减少数DC（和订座取消数相关）,定义2：舱位可获得座位数AU：考虑虚拟运力、Goshow、Noshow后得出的虚拟销售座位数，是超售模型的计算目标。,AU值确定,OR in Air Transportation,21,中国民航大学管理学院,超售量计算-不确定性模型,NO_SHOW率的不确定性,NO_SHOW率根据历史数据预测，实际NO_SHOW率可能大于或小于预测值,NO_SHOW,率的不确定性会导致,空座损失,=,空位数乘以票价（,NO_SHOW,率高于预计值）,拒绝登机成本（,Denied,Boarding,DB,成本）（实际,NO_SHOW,率低于预计值）,赔偿金额,信誉损失,提供食宿费用,票价差额,航班延误,OR in Air Transportation,22,中国民航大学管理学院,不确定性模型的基本思路,载客量,空座损失,超量订票的成本,客舱预定水平,预计总成本,DB成本,设,AU,为允许销售的座位数，,AU,小，,DB,成本小，空位损失大,AU,大，空位损失小，,DB,损失大,比较每个,AU,值的净收益，找出成本最小，收益最大的最佳,AU,值,OR in Air Transportation,23,中国民航大学管理学院,基于二项分布的AU计算模型步骤,2.对每一个k计算其空位损失,、DB损失,、期望损失,（2）,（3）,令,k=,+1到,（1）,+MAXob，（MAXob为,最大超售数）,b为每DB一个乘客的平均赔偿标准。,；VC为运力；y为舱位平均票价；,3.AU=min(,，k=,+1,+MAX,ob,（4）,）,OR in Air Transportation,24,中国民航大学管理学院,厦航使用收益管理系统的效益,06,年,4-7,月，销售折扣率平均上升,1,个百分点，相当于全年增收近亿元,高客座率航班预测准确率达到,78%,以上,较好的解决了不同航空公司之间的竞争问题,迅速在公司的全部航线上推广使用,OR in Air Transportation,25,中国民航大学管理学院,航线网络规划问题,航线网络基本知识介绍,航线网络规划研究内容,航线网络研究现状,研究方法,OR in Air Transportation,26,中国民航大学管理学院,航线网络基础知识,航线：连接两个或两个以上地点的空中交通运输线路,航路：空中走廊,起迄点,航班,航线网络：,航空运输线路的有机整体，航空运输产品的“骨架”,航线网络结构：各条航线之间的连接状态，科学合理的航线网络结构可以产生1+1,2的效果,航线网络就是赋权有向图,A,D,E,C,B,航班,速度,安全,服务,品牌,OR in Air Transportation,27,中国民航大学管理学院,航线网络结构模式1,1、城市对式航线网络结构,是在两个通航点之间开辟直达航线，航线网络中基本没有通过枢纽中转联接的通航点,基本形式,直达航线（点对点航线,point to point,）,补充形式,甩鞭子航线（中间增加经停点）、环飞航线,直达航线,甩鞭子航线,环飞航线,w,ij,i,j,K,OR in Air Transportation,28,中国民航大学管理学院,城市对航线,直达航线,甩鞭子航线,OR in Air Transportation,29,中国民航大学管理学院,国航每日,3-6,班的国内城市对,2002年资料，下同,OR in Air Transportation,30,中国民航大学管理学院,国航每日,1-2,班的国内城市对,OR in Air Transportation,31,中国民航大学管理学院,国航每日不足,1,班的,国内城市对,OR in Air Transportation,32,中国民航大学管理学院,航线网络结构模式2,2、中枢辐射航线,是通过在枢纽中转航班来连接周边城市的一种航线网络结构，主要特点是,航空公司建立一个或多个中心枢纽站（,Hub,），,客流量较小的城市（,Spoke,）,之间不直接通航，,而是通过在枢纽站中转的方式加以联接,中枢辐射航线的基本形式,沙漏式,内地馈运式,OR in Air Transportation,33,中国民航大学管理学院,沙漏式中枢辐射航线,是一种定向式的中枢辐射航线，通过枢纽站的航班方向大致相同，于相近时间在枢纽站经停，“漏”下转机旅客，很快衔接到经停的其他航班上,方向性,航班在枢纽点,经停,沙漏式,OR in Air Transportation,34,中国民航大学管理学院,内地馈运式中枢辐射航线,在适当的地点建立枢纽,机场，周围客流量较小,的城市之间不直接通航，,通过在枢纽机场中转航,班的方式实现周边城市,之间的连接及与其他枢,纽的连接,不强调方向性,点对点航班的衔接,网络覆盖范围更广,OR in Air Transportation,35,中国民航大学管理学院,American,airlines,route network,Nodes,:,airports,Links,:,direct flight,OR in Air Transportation,36,中国民航大学管理学院,城市对式与轮辐式航线网络的比较,航线网络形式,优点,缺点,城市对航线网络,（两个通航点间开辟直达航线）,直达目的地,最短的飞行时间,易于排班,减少拥塞,不能最大限度开发市场,载运率低，航班频度低,飞机利用率低,轮辐式航线网络,（,通过在枢纽中转航班来连接周边城市,）,网络连接的市场数增加,增加航线运量,增加航班密度,降低单位成本,促进支线运输发展,转机给旅客带来不便,机场和航路拥挤,航班编排复杂,单独事件系统影响很大,OR in Air Transportation,37,中国民航大学管理学院,研究的主要问题,航空公司如何设计自己的航线网络？,航空公司如何优化现有的航线网络？,国家航线网络规划（优化）问题,OR in Air Transportation,38,中国民航大学管理学院,航线网络规划主要研究内容,航线网络特征研究,如何选择枢纽（Hub）与辐射点(Spoke),航空公司航班编排研究，如何设计航班波（Bank 或 Wave）,航空公司机队规划研究,枢纽机场中转流程设计,有大量亟待研究的课题！,是,政府、航空公司、机场,的共同关注问题,OR in Air Transportation,39,中国民航大学管理学院,国内外航线网络研究现状,国外理论研究：,有关航线网络优化模型的理论研究较多，主要采用,整数规划,方法或最短路径法来优化航线网络设计。一般以整个航线网中的运输成本最小为目标函数，假定网络中不存在竞争，旅客的需求是确定的、无弹性的,或把旅客在直达航线和中枢辐射航线之间的分配作为航线网络优化的结果。,模型的解法多采用启发式算法，以及分枝定界法、枚举法等。,由于模型假定不符合实际，所以实用性不强,国内理论研究：集中在建设中枢航线的必要性上，如何建设中枢航线，如何将中枢航线与城市对航线相结合，缺少定量的分析方法和探索,OR in Air Transportation,40,中国民航大学管理学院,国内外主要研究,国外有关航线领域方面的研究和文献较多，主要包括航线网络设计研究、现有航线优化研究、中枢辐射航线网络设计研究、航线网络经济性研究等方面的研究,M.E.OKELLY,1987,年 提出了解决“不确定的、单一分配的、拥有,P,个枢纽点的中枢辐射航线网络结构设计问题”的整数规划模型,1994,年,Teodorovic,D,KalicM,Pavkovic,G,利用建立的模糊线性规划模型来构造航线网络,1996,年,Jaillet,P,Song G,Gang Yu,根据城市对之间的,O,D,流,分别建立了基于,One,stop,，,Two,stop,，,All,stop,策略的航线网络设计模型,并给出了一种启发式算法,1998,年,Lederrer,PJ,，,Nambimadom,R S,描述了旅客需求、航班频率和城市间的距离等网络参数对,4,种基本航线网络的影响,提出了航线网络结构设计的一些主要参考因素,2000,年,Yuh-Horng,Wen,Chaug-Ing,Hsu,把灰色理论应用到航线规划中,并利用,GINO,软件来求解建立的航班频率的多目标规划模型,2006,年,Yuh-Horng,Wen,Chaug-Ing,Hsu,运用交互多目标规划方法研究了国际航空联盟下的航空公司航线网络设计问题,柏明国先后运用多目标决策方法和多属性决策方法对构建中枢辐射航线网络进行了研究，利用所提方法构建了中国,15,城市的枢纽航线网络,OR in Air Transportation,41,中国民航大学管理学院,航线网络规划的基本研究思路和方法,枢纽点的选择（P个 Hub）,航线的连接方式（优先原则、影响因素）,目标函数（运输成本最小、距离最短）,OR in Air Transportation,42,中国民航大学管理学院,目标函数：Min,约束条件：,Cij：从节点i到节点j的单位旅客成本；,N：将要建立的中枢辐射航线网络中所包括的所有机场个数；,Wij：从节点i到节点j的旅客流量（需求量）；,M.E.OKELLY 1987,OR in Air Transportation,43,中国民航大学管理学院,1994,年,J.F.CAMPBELL,提出了,“混合整数线性规划（,mixed integer linear program,，,MILP,）模型”,目标函数：,Min,约束条件：,OR in Air Transportation,44,中国民航大学管理学院,约束条件：,1995年T.AYKIN提出了解决复合航线网络规划模型：,目标函数：,OR in Air Transportation,45,中国民航大学管理学院,枢纽航线网络设计的模型及算法2006 柏明国,朱金福,姚韵,无容量限制的多重分派,p,枢纽中位问题(简记为UMApHM P),指在某个航空运输市场中有,n,个城市(对应,n,个机场),预先给出枢纽数为,p,(,p,一般在25 之间取值)个,枢纽之间相互完全直接相连构成干线网,在网络中担任转运的角色,而其它所有非枢纽之间只能通过枢纽进行周转连接,从而构成支线网中间经过枢纽周转的次数不能超过两次,且一个非枢纽可以和多个枢纽直接连接。问题要求从,n,个城市中选定,p,个做枢纽,并决定非枢纽到枢纽的分派方式,以使得总运输成本最小。,UM PHM P 是N P2hard 问题，利用启发式方法求解,OR in Air Transportation,46,中国民航大学管理学院,UMApHM P 数学模型,式(1)表示共有,p,个枢纽;式(2)、(3)、(4)是客流量守衡方程;,式(5)、(6)为客流量约束。,OR in Air Transportation,47,中国民航大学管理学院,需求、竞争、价格、slot分配等复杂多变的因素未考虑,是Np难度的问题，求解困难,理论研究的热点是算法,当前航线网络规划研究的难点问题,OR in Air Transportation,48,中国民航大学管理学院,Thank,you!,OR in Air Transportation,49,中国民航大学管理学院,