南方航空运筹学研究与应用.ppt

南方航空南方航空“ “运筹学运筹学” ” 研究与应用研究与应用内容Ø 运筹学介绍 Ø 研究与应用什么是运筹学？-Operations Research -学科：数学分支（管理、决策科学） -目的：决策科学化（主观~客观） -方法：建模、求解关键词：优化Ø 诺贝尔经济学奖（2012）Ø 白云机场~天河序号车辆油耗载重里程成本1 中型20L14T70017472小型15L8T50015613大型25L20T6002413生产资源要素- 物流：货车、货机、网点 - 航空：飞机、机组 - 超市：库存、营业员 - 银行：网点、窗口、资金 - 工厂：生产线、设备、工人 - 医院：窗口、病床为什么需要运筹学？-资源，有限 -降本增效，必须 -不自觉-自觉-定量与定性 -管理精细化问题规模-方案数量：4*6*4=96种航班号起飞目的地机型034309:00墨尔本330309109:00马尼拉320319709:00呼和浩特320340109:00成都738360909:00上海320320709:05西宁320346309:05重庆319033709:10首尔321635909:10南京320349909:15迪庆319038509:30东京77B360509:30长春320304909:50河内320378709:50威海320380309:55杭州321034510:00北京332353110:00上海330航班号起飞目的地机型691507:30阜阳319323607:35桂林321347707:40昆明319372307:45厦门319350507:50福州320394507:50井冈山319302508:00普吉330310108:00北京77A352108:00杭州320352308:00上海77A350908:05济南73G381308:05合肥320394908:05重庆319351308:10南京320372908:10柳州ER4633708:10常州320313308:15天津738航班号起飞目的地机型030108:20悉尼330333908:20梅县ER4034908:25吉隆坡73G391308:25无锡738629908:25黃岩320038908:30大阪77B035308:35新加坡320320508:35兰州320325708:35徐州738363508:35连云港738305508:40仰光319322108:40南阳319329908:50邯郸319351908:50济宁319336308:55洛阳319358508:55安庆ER4 030309:00伦敦332-100方案/天，1014方案/周组合爆炸（Combinatorial explosion）组合爆炸（Combinatorial explosion）如何运用运筹学？（1）问题抽象分析 （2）建立数学模型 （3）求解数学模型什么是数学模型？什么是数学模型？Ø 机组排班问题，等价于一道数学题。

Ø 答案，就是排班方案Ø 这道数学题，就是模型什么是数学模型？min 5x1+5x2+...+12x36+9x37 st x1+x7+x8+x19+x20+x21+x22+x29+x30+x31+x36=1x2+x7+x9+x10+x11+x12+x19+x20+x21+x22+x23+x24+x25+x32+x33+x34+x37=1x3+x8+x9+x13+x14+x15+x19+x23+x24+x25+x26+x27+x29+x30+x32+x33+x35+x36+x37=1x4+x10+x13+x16+x17+x20+x23+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37=1x5+x11+x14+x16+x18+x21+x24+x26+x28+x29+x31+x32+x34+x35+x36+x37=1x6+x12+x15+x17+x18+x22+x25+x27+x28+x30+x31+x33+x34+x35+x36+x37=1x1,...,x37 integer如何建模？Ø 问题“错误”，无法得“正确”答案 Ø 难点：业务、多目标优化 Ø 适用性和扩展性Prob.CrewsTasksRowsColumnsSimplex(h)No.1 37220814121,922,6260.47No.226320813192,343,8170.75No.335627418554,386,2710.48No.458432318599,412,2131.19No.5476237122412,446,2412.00No.6485239123715,761,1562.49如何求解？Ø 解方程、检验结果 Ø 难点：有限时间（超级计算机）-理解业务本质，辅助决策运筹学的应用？Ø 物流业：配送网络、载货量、物流中心 Ø 制造业：生产计划、仓储管理Ø 航空业：飞机、机组、网络、收益国际运筹学联合会 航空运输分会Crew Management CargoStrategic/Network PlanningRevenue Mgmt/Distribution Airline Operations 增加收入 Ø 产品规划、收益管理节约成本 Ø 人力、运行、管理票价管理航班计划维修路径 航班恢复网络规划 机型优化收益管理人员排班购 买飞 机航 线网 络市 场营 销运 行服 务飞 机维 修收 入成 本决策科学化运筹学，在移动互联时代？-沟通，实时 -交互，频繁 -流程，变革-资源优化，模型实时调整 -旅客价值，更多维度南航实践 Ø 2010/09，机组自动排班 Ø 2012/06，机组自动搭班 Ø 2013/06，航线网络规划 Ø 2013/08，机组休息规划 Ø 2013/12，地服资源排班 Ø 飞机排班、机组选班、航班恢复……分子公司次数总任务数系统安排覆盖率时间（小时）17 364（9月）73,39567,63692%80分类2010201120122013 用户需求36484516 系统优化8744020 小计441228536合计（条）287日平均飞行（小时）（广州基地） 日期机长第一副驾手工系统手工系统 6-2166.566.46-225.96.35.96.16-235.765.65.96-245.565.55.86-255.76.25.66.16-265.86.15.866-272.92.82.82.8资源优化、科学决策Ø 同样的时间，提高效率 Ø 同样的人数，任务公平 Ø 同样的飞机，更多航线Ø 搭建平台，讨论制定业务规则算法库Ø 枚举（先生成后优化） Ø 列生成（KSP，SPPRC） Ø 智能算法（遗传）实践经验Ø 航空业务特色（运筹学） Ø 原理本质如何评价（购买）优化系统？Ø 业务 -基准问题（Benchmark Problem） -关键指标：速度、结果Ø 技术 -模型调整难易总结 Ø 运筹学（优化、组合爆炸） Ø 例子（模型、算法） Ø 南航应用实践。