关于机场停机位分配方案模型的研究(20111129).doc

关于机场停机位分配方案模型的研究中南财经政法大学信息管理与信息系统2009级0903班 易盈盈 0909030336摘要：随着信息化社会的高速发展，人们的生活越来越依托于网络技术，本文主要讨论机场停机位分配问题即考虑如何在满足一定约束条件下，借助于网络信息系统为到达和离开机场的航班分配合适的停机位，保证航班正常且高效运行。本文关于机场停机位分配方案构建了3种模型，一是飞机最适应模型；二是乘客最短路径模型；三是二者均衡考虑，构建模型。该模型实施将为我国大部分机场运营管理中的手工机位分配所导致的效率低下问题带来可能的解决方案。实现计算机化机位分配，适应信息化的飞速发展，从而提高机场运营企业资源利用效率，降低运营成本，同时节省人力资源，因此具有重要的研究价值和应用价值。关键词： 机场；停机位分配；模型构建a study on the airport gate allocation model Abstract: With the rapid development of information society, peoples lives are increasingly relying on Internet technology, this article focuses on airport gate allocation problem is to consider how to satisfy certain constraints, by means of network information systems for the airports flight arrival and departure appropriate allocation of parking bays to ensure the normal and efficient flight operation. This article about the airport gate allocation plan to build three different models, one is the best fit model aircraft; two passengers shortest path model; Third, a balanced consideration of both to build the model. The model will be implemented in most of our airport operations management manual seat allocation inefficiencies caused by bringing a possible solution. Computerized machine allocation, to adapt to the rapid development of information technology to improve airport operations business resource efficiency, reduce operating costs, while saving manpower resources, it has important research value and application value.Key words: airport; gate allocation; model building1 引言1.1 背景随着社会经济的快速发展，人们对于乘坐航班出行的需求日益增加，在促进民航规模迅速发展的同时，也使得机场停机位不足与航班数量不断增长的矛盾日益凸显。1.2 现状目前我国民航数量不断增长，人们出行对于飞机等交通工具的依赖也越来越大，这势必会导致空间资源的紧张，虽然可以通过扩大机场，增加设施缓解停机位分配不足的矛盾，但是从长远来看这一方案并不可行。因为一方面扩建机场需要大量的人力物力，对机场周围环境产生影响；另一方面这一方案有时间上的滞后性，由于机场扩建需要一定的工期，这会对现存的营业产生影响。传统的机位分配方案是由人工计算控制没有纳入计算机控制中，这与现代化的速度明显存在矛盾。而根据计算机化的控制合理优化飞机停机位方案，却可以做到高效控制机场资源的配置，节省资源空间。并且由于计算机化的操作，使得人力配备减少，能够大大提高效率。2 问题分析2 2.1 停机位分配问题的约束条件不同航班分配模型在满足的约束条件上不完全相同，有的模型考虑的约束多一些，有的相对少一些。但分配停机位时通常的约束条件有：（1）同一个停机位在同一时间段最多只能停靠一个航班。（2）需为每个航班分配停机位，且至多只能分配一个停机位。（3）航班从开始停靠到离港的时间应大于等于飞机的最短地面服务的时间。（4）连续占用同一停机位的前后航班之间要保持一定的安全时间间隔，以保证航班顺利进出停机位并防止意外发生。（5）应满足机型与机位相互匹配的约束。即大型航班只能使用大型停机位，中型航班可以使用大型或中型停机位，小型航班可以使用所有停机位。2.2 需要解决的问题（1）如何使占用的停机位数最少，使资源的利用率达到最高；（2）如何使乘客行走距离最短，使乘客感受到最便捷的服务；（3）如何采取加权数，综合分析，得到最优化解决方案。3 目标优化3 3.1 停机位分配问题的优化目标典型的停机位分配优化目标如下几种：（1）空间资源率利用最高。（2）最小化旅客总的行走距离。（3）最小化未分配停机位的航班数目。（4）航班等待延误时间最小。3.2 思路过程与框架本论文对机场机位分配优化问题进行系统地研究，并结合我国机场实际运行的情况，针对目前我国机场机位紧张且利用率不高、旅客平均行走距离较长以及航班等待延误现象严重这三个方面的问题，分别以占用停机位数目最少、旅客平均行走距离最短和综合考虑加权最优化目标，建立机位分配模型，采用基于背包问题算法、进程调度算法和改进的方案算法对模型求解。整个过程思路如图1所示：先系统阐述停机位分配问题的背景和现状，结合实际应用指出现存的缺陷和不足，分析问题，提出优化目标，然后针对提出的目标根据已学的知识建立相关模型，构建模型，比较各自的优缺点。提出展望总结。问题分析背景综述机位分配方案建模解决算法机场场地资源利用率最大乘客路径最短折中优化总结与展望 图1 停机位分配方案思路流程图4 模块构建4 4.1 机场场地资源利用率最大模块对于这一模块，本文选取以背包算法为原型。背包问题其实就是一个优化问题，即在所有装包方案中选择一种最为有效精确的装包方案，使背包的体积最少，背包内所装物体价值最大。在这一模型中，机场空间资源就相当于一个背包，要在背包中装下尽可能多的资源，使空间的利用率达到最大，就是使未分配停机位的飞机数达到最少。首先假设机场停机位空间为C，根据飞机达到停机场的先后顺序组成一个有序数组，an1，n2，n3按照飞机机型的不同，将其分为大中小三类型。分别占用空间资源为c1，c2，c3。取一个假设的某段时间t，要在这一段时间使机场空间资源的利用率达到最大。计算在这个时段内航班的到达时间和停靠时间。即要同时考虑时间和空间问题。计算：n1在t1时间到达，停靠时间k1，离开时间t1+k1，占用资源c1，剩余资源空间cn=C-c1；n2在t2时间到达，停靠时间k2（k2(t1+k2)），占用资源c2，离开时间（t2+k2），则剩余资源空间为cn=C-c1-c2；n3在t3时间到达，停靠时间k3，占用资源c3，离开时间t3+k3；if（k3(t1+k1)）cn=C-c1;if（k3(t2+k2)）cn=C-c2;else cn=C-c1-c2;有两航班同时到达：（1）两航班占用同样多的资源，算法同上；（2）两航班占用资源不同ni占用资源ci，nj占用资源cj（cicj），停靠时间同： if（cicn&cjcn) cn=cn-cj;/使资源利用率达到最高 if（cicn） cn=cn-ci; else cn=cn-ci-cj;（3）两航班占用资源不同，停靠时间不同，ni停靠时间ti，离开时间ki+ti，nj停靠时间tj离开时间为kj+tj(titj)：if(ti+ki)(t0+t)&(tj+kj)(t0+t) 方法同2；if（ti+ki）(t0+t)） 方法同2；if（ti+ki）(t0+t)）都不满足条件存入缓存中等待。此种方案考虑在某一时间段内使可用资源的利用达到最大，但是由于t的选取可大可小，也存在着时间上的衔接问题。这是需待改进的。4.2 乘客路径最短模型对于这一模块本文选取无向图为模型。无向图的端点表示候机厅或者停机场的位置，机场停机位到机场候机厅的距离就是由无向图中的某些连通的线段构成，每条线段的权数代表了每一段路径的长度。本文要解决的就是根据各个候机厅的乘客人数分配比，再根据到机场停机位的距离比，计算出使所有乘客的总路径最短的那条路径，即路径最短优先。乘客路径最短模型可以简化为如图2所示：假设有1,2,3,4号候机厅，矩形框代表可选停机位分别为1号、2号、3号，1、2、3、4号候机厅到1号停机位的距离分别为s11，s12，s13，s14，2号候机厅到2号停机位的距离分别为s21，s22，s23，s24依次类推。 12341号s11s24s342号3号s12s14s13图2 乘客路径最短模型无向图此时不考虑空间资源分配问题，并且假设各个候机厅的乘客人数差异性很小可以忽略不计，完全关注求距离最短的算法。如果选择1号停机位，则总距离为s1=s11+s12+s13+s14；若选择2号停机位，则总距离为s2=s21+s22+s23+s24，若选择3号停机位，则总距离为s3=s31+s32+s33+s34。比较选择s1，s2，s3中最小的作为最佳停机位停靠。取bool类型的数组state表示停机位是否被占用，false表示当前状态不可用，true表示当前状态可用。用一个整型值choice表示选择的停机位。计算：if(（s1s2&s1s3&s1s4)&state1=true）state1=false;choice=1;if（s1s2&s1s3&s1s4）&state1=false）if(s2s3&s2&s4)&state2=true) state2=false;choice=2;如果某航班离开停机位了，则：statei=true;4.3 折中优化模块在本模块中，选择的方案是先进行资源利用率最大的算法，确定符合条件的停机位，再在符合条件的停机位中选择乘客路径最短的停机位。计算：在时间t内，有航班将要停靠，此时机场资源C=ci；根据背包算法原理找到了符合条件的停机位1号，2号，3号。假设候机厅有4个分别为1，2，3，4位，4个候机厅到1号停机位的距离分别为s11,s12,s13,s14，总距离s1=s11+s12+s13+s14；到2号停机位的距离分别为s21,s22,s23,s24，总距离为s2=s21+s22+s23+s24；到3号停机位的距离分别为s31,s32,s33,s34，总距离为s3=s31+s32+s33+s34；到4号停机位的距离分别为s41,s42,s43,s44，总距离为s4=s41+s42+s43+s44。同样取bool类型的数组state表示停机位是否被占用，false表示当前状态不可用，true表示当前状态可用。用一个整型值choice表示选择的停机位。计算：if(（s1s2&s1s3&s1s4)&state1=true）state1=false;choice=1;if（s1s2&s1s3&s1s4）&state1=false）if(s2s3&s2&s4)&state2=true) state2=false;choice=2; 5 结论 5 5.1 比较分析第一种算法仅考虑了空间利用率，在仅着眼于空间利用水平上确实不失为一种良好的方案。但是没有考虑到乘客的便利性问题，在实际实施的过程中可能带来乘客的不便利麻烦。而第二种方案则是完全站在乘客的角度，考虑路径资源最少，而忽视了场地资源的浪费。第三种方案，结合了前两种的优点，选取一个折中方案，权衡两者之间的重要性，在适当的场合根据两者的加权选取优化方案。5.2 展望通过对几种算法模型的构建，并且结合实际需要选择实用的方案，使机场停机问题能够得到改善和有效率地解决。但可以看到本文的研究还不够深入，还可以进一步完善的地方主要表现在以下几方面：（1）文中的数学模型还不够全面，有一些约束条件没有考虑到，进一步的工作可以考虑增加更多的约束规则，使停机位分配模型更加完善、更加切合实际情况。（2）文中几种算法采用的都是单目标函数优化，虽然单独考虑某一个目标时结果较好，但无法同时优化多个目标。（3）本文研究工作都是针对航班停机位分配的预分配问题，即在预先知道机场预计到港和离港航班时刻表、停机位使用状态的情况下给出的预分配况中，有很多不可预知的因素（如天气、飞机故障等）会导致航班提前或延迟，有时不得不需要调整停机位的预分配方案，这就属于停机的点后再求解，这是一个值得进一步研究的方向。虽然现有的模型还存在不足，但是可以展望，随着研究的深入和社会科技的发展，人们对于资源节约型社会的重视，停机位分配模型的构建发展会越来越完善。参考文献：1 戴顺南.机场机位分配模型构建及算法实现M.北京:北京交通大学出版社2008,105-1102 Erico Piazza.Increasing Airpor