CN105630979B - 航班查询方法及装置、系统 - Google Patents

Abstract

本发明实施例公开了一种航班查询方法及装置、系统，所述方法包括：构建航班网络图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场；在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；对所述行程集合进行筛选评估。本发明实施例解决了航班行程检索的效率低和结果可用度低的问题，很好的保证了航班行程的高可用度和高搜索效率。

Description

航班查询方法及装置、系统

技术领域

本发明涉及数据处理技术，尤其涉及一种航班查询方法及装置、系统。

背景技术

基本的旅客购票流程主要包括航班查询、航班预订以及支付等环节。传统的购票渠道是旅客到代理人或者是航空公司销售柜台处购票。旅客将起飞城市、目的城市、起飞日期等旅行相关需求告知代理人或者销售人员，代理人或销售人员应用代理人订座系统完成航班的查询和预订。随着互联网的兴起，航空公司网上售票平台以及各种第三方的航班销售平台不断涌现，旅客可以通过互联网自助的完成航班的预订和支付。不论是传统的购票渠道还是新兴的互联网购票渠道，后台依托的都是自动化的订座系统(CRS，ComputerizedReservation System)。

基于CRS，旅客输入行程需求，系统会自动为旅客计算生成可用的行程，并且完成航班可利用舱位状态(Availability)的查询及航班舱位价格的计算。随着各种第三方互联网购票平台和比价平台的出现，基于价格的航班搜索占有越来越大的比例，这就要求CRS能够支持基于价格的航班行程搜索，以便更好的支持旅客的个性化查询需求。

由于航班行程搜索计算量大，传统的航班查询方法为了减少计算量，一般基于直飞航班抽象的航线网络图进行搜索，这样构建的航线网络图虽然可以大大压缩图的搜索空间，但是由于没有具体的航班信息，无法有效的对航班行程进行可用度的评估，所以会导致搜索的航班行程结果可用度不高。

并且，传统的航班行程搜索主要应用启发式的K短路径搜索算法或者单向的宽度(深度)优先搜索算法。其中，K段路径搜索算法需要定义评估函数，而评估函数又很难描述用户的航班行程，因此，这种启发式搜索算法的航班行程搜索结果可用度不高；对于单方向的搜索算法，当扩展两次以后会以指数的速度进行发散，搜索效率相对较低。

因此，需要提出一种新的航班查询方法，解决传统航班搜索方法搜索结果可用度不高以及搜索效率低的问题。

发明内容

为解决现有存在的技术问题，本发明实施例提供一种航班查询方法及装置、系统。

为达到上述目的，本发明实施例的技术方案是这样实现的：

一种航班查询方法，所述方法包括：

构建航班网络图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场；

在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；

对所述行程集合进行筛选评估。

其中，在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合，包括：

分别以所述用户行程请求中的出发地和目的地为初始节点，从所述航班网络图的两边进行扩展，得到两个扩展点集合，所述扩展点集合中的扩展点为以所述出发地或目的地为初始节点的所有航班经过的地点；

根据里程制运价信息，分别对所述两个扩展点集合进行剪枝；

取所述两个扩展点集合的交集，生成出发地到目的地的行程集合。

其中，所述里程制运价信息包括：距离限制、中转次数限制、旅行方向限制和/或航班属性限制。

其中，对所述行程集合进行筛选评估，包括：将所述行程集合中的无效行程删除，并对保留下来的行程进行评估排序。

其中，所述评估包括：根据行程中航班可利用状态、旅行时间、中转次数、行程中航空公司之间的联盟关系，对所述行程打分。

一种航班查询服务器，包括：构建模块、双向搜索模块和筛选评估模块；其中，

构建模块，用于构建航班网路图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场；

双向搜索模块，用于在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；

筛选评估模块，用于对所述双向搜索模块得到的行程集合进行筛选评估。

其中，所述双向搜索模块包括：扩展子模块、剪枝子模块和交集子模块；其中，

扩展子模块，用于分别以所述用户行程请求中的出发地和目的地为初始节点，从所述航班网络图的两边进行扩展，得到两个扩展点集合，所述扩展点集合中的扩展点为以所述出发地或目的地为初始节点的所有航班经过的地点；

剪枝子模块，用于根据里程制运价信息，分别对所述扩展子模块得到的两个扩展点集合进行剪枝；

交集子模块，用于取所述剪枝子模块剪枝后的两个扩展点集合的交集，生成出发地到目的地的行程集合。

其中，所述里程制运价信息包括：距离限制、中转次数限制、旅行方向限制和/或航班属性限制。

其中，所述筛选评估模块用于将所述行程集合中的无效行程删除，并对保留下来的行程进行评估排序。

其中，所述筛选评估模块进行评估，包括：根据行程中航班可利用状态、旅行时间、中转次数、行程中航空公司之间的联盟关系，对所述行程打分。

一种航班查询系统，所述系统包括：客户端、数据服务器以及上述的航班查询服务器；其中，客户端，用于接收用户输入的信息，生成用户行程请求并发送给所述航班查询服务器；数据服务器，用于为所述航班查询服务器提供航班信息、舱位状态信息以及包括里程制运价信息的运价相关信息；所述航班查 询服务器的构建模块，用于从所述数据服务器获取最新的航班信息，构建航班网络图；所述航班查询服务器的双向搜索模块，用于从所述数据服务器获取里程制运价信息和舱位状态信息，在所述航班网络图中基于用户行程请求进行双向搜索；以及，所述航班查询服务器的筛选评估模块，还用于将筛选评估后的行程集合返回给所述客户端。

本发明实施例提供的航班查询方法，双向搜索算法的应用，解决了航班行程检索的效率低问题；配合多因素对搜索结果排序删减，解决了结果可用度低的问题，从而很好的保证了航班行程的高可用度和高搜索效率。

此外，在航班行程搜索过程中结合了里程制的运价规则信息和航班舱位可利用状态信息，不仅解决了航班行程搜索效率低的问题，同时也解决了价格敏感的行程需求，实现了高效的低价航班行程的搜索。

附图说明

在附图(其不一定是按比例绘制的)中，相似的附图标记可在不同的视图中描述相似的部件。具有不同字母后缀的相似附图标记可表示相似部件的不同示例。附图以示例而非限制的方式大体示出了本文中所讨论的各个实施例。

图1为本发明实施例航班查询方法的流程示意图；

图2为本发明实施例航班网络图的实例示意图；

图3为本发明实施例的双向宽度优先查找算法的示意图；

图4为本发明实施例航班查询方法的具体实例流程示意图；

图5为本发明实施例用于航班查询的服务器的组成结构示意图；

图6为本发明实施例航班查询系统的组织架构示意图。

具体实施方式

如图1所示，本发明实施例提供的航班查询方法，主要可以包括如下步骤：

步骤101：根据当前的航班信息，构建航班网络图；

具体的，实时获取航空公司发布的直飞航班信息，根据两地之间真实的航班连接信息，构建航班网络图。本发明实施例中，航班查询服务器可以从数据服务器获取最新的航班信息，根据最新的航班信息，构建航班网络图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场。

实际上，航空公司每天会定时更新直飞航班信息，所以航班网络图的构建频度为每天一次。本发明实施例的航班网络图不是抽象的连通图，而是真实的航班连接网络图，也就是说，如果两地之间存在多个航班，则在该航班网络图上对应的两点之间就会在多条边，航班网络图中一条边对应一个航班，边与边之间的连接点表示地点。

步骤102：接收来自客户端的用户行程请求；

用户通过客户端输入自己的行程需求，例如起飞城市(机场)、目的地城市(机场)、起飞日期是用户必须输入的选项。同时，用户也可以指定一些自己偏好的查询条件，其中包括喜好或厌恶的航空公司、喜好或厌恶的中转机场、最晚起飞时间、中转次数、以及转机时间等。客户端根据用户输入的选项，生成 用户行程请求，并将用户行程请求发送给航班查询服务器。也就是说，一个用户行程请求中必然包括起飞城市(机场)、目的地城市(机场)和起飞日期，此外，还可以包括喜好或厌恶的航空公司、喜好或厌恶的中转机场、最晚起飞时间、中转次数、以及转机时间等信息。

步骤103：在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；

这里，航班查询服务器接收客户端发送的用户行程请求后，解析该请求，可以得到查询条件，基于查询条件进行双向搜索。其中，查询条件主要包括用户的起飞城市(机场)、目的地城市(机场)，起飞日期等基本信息。同时，还可以包括用户指定的偏好航空公司、偏好中转点等个性化定制信息。

这里，采用双向的搜索算法，相对于传统航班行程搜索中应用的单向网络搜索算法来说，具有更好的控制了发散，检索效率更高。

步骤104：对所述行程集合进行筛选评估，将筛选评估后的行程集合返回给客户端。

这里，航班查询服务器对搜索到的航班行程进行综合打分并筛选，将满足用户需求的较优的结果返回给用户。为了保证结果的可用度同时提高检索效率，本发明实施例应用多因素的综合打分筛选策略。里程制运价规则中对里程制的限制、中转次数限制、旅行时间限制保证了图搜索的收敛，提高检索效率。里程制运价中的运价信息保证了低价行程的生成。航班舱位可利用状态(Availability)、航班的旅行时间、中转次数、以及航空公司之间的联盟关系等 因素综合作用保证搜索结果的可用度。

现有的航班行程搜索算法大多基于直飞航班抽象的网络图进行搜索，即两个点之间不管存在多少直飞航班都只会保留一条线。这样构建的航线图虽然可以大大压缩图的搜索空间，但是由于没有具体的航班信息，无法有效的对航班行程进行可用度的评估，所以会导致搜索的航班行程结果可用度不高。图2描述了本发明实施例基于实时航班构建的航班网络图。本发明实施例中，航班查询服务器通过遍历直飞航班信息，并根据直飞航班的起飞机场、起飞城市、到达机场和到达城市构建航班网络图。其中，航班网络图中的节点(图2中的圈A、B、C、D、E、F)既包含了机场同时也包含了城市，如果直飞航班的机场和城市代码不相同则会在图中增加不同的节点，图2中的边代表两地之间存在的航班，如果两地之间存在多个航班则会存在多条边。这里，航班网络图是航班行程搜索的基础，行程搜索是基于该航班网络图进行双向查找来实现的。考虑到航班网络图涵盖信息量比较庞大，本发明实施例中应用邻接矩阵的方式存储航班网络图，同时将不可能的航班及航班组合从航班网络图中剔除，对航班网络图进行了删减和压缩，以保证行程搜索的高效快速。

传统的航班行程搜索主要应用启发式的K短路径搜索算法或者单向的宽度(深度)优先搜索算法。对于K段路径搜索算法需要定义评估函数，评估行数的好坏直接关系到搜索到的行程质量以及搜索的效率。由于行程的好坏是多因素的，并且与用户的偏好的紧密相关的，所以当用户没有很明确的指明需要的行程时，这就要求航班行程搜索算法能够保留尽可能多的可能，各种极端情况 的行程也需要被保留，比如距离最短但是价格最高，价格很低但旅行时间很长等。同时，还要涵盖价格相对低廉且行程相对便捷的行程，所以很难用一个简单的评估函数进行描述，应用这种启发式搜索算法的航班行程搜索结果可用度不高。对于单方向的搜索算法，当扩展两次以后图会以指数的速度进行发散，搜索效率相对较低。图3描述了本发明实施例中航班行程搜索中应用的双向搜索算法即双向宽度优先查找算法，如图3所示，箭头左边表示传统的单向网络搜索算法，箭头右边表示本发明实施例的双向搜索算法。本发明实施例的双向搜索算法，分别以出发地和目的地为初始节点进行双向搜索计算，能够解决单向搜索算法搜索效率低的问题。

下面对本发明实施例航班查询方法中双向搜索和结果筛选的具体实现过程做详细说明。

如图4所示，本发明实施例中航班查询方法中双向搜索和结果筛选的具体实现过程可以包括如下步骤：

步骤401：根据用户请求检索航班网络图；

步骤402：判断是否需要扩展，如果是，继续步骤403，否则继续步骤411；

这里，扩展的依据是如果进一步扩展后最优的航班行程的分值比已经得到的最差的航班行程的分值还低则不需要进一步扩展，否则需要进一步扩展；如果当前还没有搜索结果，则可以直接开始扩展。

步骤403-408：分别以出发地和目的地为初始节点从航班网络图的两边进行扩展，对两个方向上生成的扩展点集合分别进行剪枝，再对剪枝后的两个扩展 点集合取交集，得到出发地到目的地的行程集合；

这里的扩展是指：根据用户输入的出发地和目的地从航班网络图的两边进行扩展，即分别以出发地和目的地为初始节点在航班网络图上进行边的搜索，找到以出发地为初始节点的所有航班经过的地点、以及以目的地为初始节点的所有航班经过的地点，将这些地点称为扩展点，得到两个扩展点集合。为了尽量降低图的发散，每次扩展都选择邻接点较少的一边进行扩展。例如，可以将得到的扩展点集合分别标记为next_frontier{S_i}和pre_frontier{S_i}，其中S_i中存储有历史航班信息。

剪枝的过程包括：为了提高搜索效率，减少不必要的扩展，需要对扩展点集合进行删减即删除不合理的扩展点，减少下次扩展时的搜索空间。剪枝过程发生在每次扩展后，需要对两个方向生成的扩展点集合分别进行剪枝，如果一个方向生成的扩展点集合已经很差则可以删除。剪枝过程中考虑如下因素之一或其任意组合：距离、中转次数、旅行方向和里程制运价规则。其中，

对于距离的剪枝：查询里程制运价中对里程的限制，当扩展点与初始节点之间的里程已经超过了里程制运价中关于里程的限制时则删除该扩展点，或者需要根据实际情况对MPM进行扩展，以便得到更多的航班行程结果。为了得到更优的航班行程结果，对于具体的里程限制可以借鉴经验数据，不再赘述。

对于中转次数的剪枝：初始点与扩展点之间的中转次数超过限制时删除该扩展点。中转次数的限制可以根据经验数据进行设置，例如一个完整行程的中转次数一般不会超过5次，对于任意超过5次中转的行程将不会被保留。

对于旅行方向的剪枝：在里程制运价规则中对旅行方向进行了规定，只有满足旅行方向的扩展点才被保留。即，对于出发地的扩展点集合，仅保留以出发地到扩展点为旅行方向的扩展点，对于目的地的扩展点集合，仅保留以扩展点到目的地为旅行方向的扩展点。

根据里程制运价规则的剪枝：在里程制运价规则中除了对里程进行限制之外，还对航班的属性进行了限制，例如可以限制整个航班不允许存在航班经停等。例如，可以限制初始节点与扩展点之间的航班不经停，或者限制初始节点与扩展点之间的航班经停次数不超过预设阈值(如1或2等)。

其中，里程制运价信息如距离、中转次数、旅行方向以及里程制运价规则可以从数据服务器中获取，所述数据服务器中包括航班信息的数据库、舱位状态信息的数据库、以及运价相关信息的数据库，里程制运价信息可以从运价相关信息数据库中获得。所谓运价就是定义了行程的价格以及应用该价格的一系列规则限制。里程制运价规则不限制航班行程的具体走法，而是规定了最大允许里程(MPM，Maximum Permitted Mileage)，只有不超过该里程的行程才能应用该价格。里程制运价信息的应用既可以保证查询结果满足用户对价格敏感行程的需求，同时应用里程制规则限制可以很大程度上降低航线图搜索的复杂度，解决了航班行程搜索过程的效率低问题。

本发明实施例中，在搜索的过程中应用多因素混合约束策略高效的剪除可用度低的行程，高效的双向查找算法以及有效的剪枝策略，保证了航班行程的高可用度和搜索效率。

具体的，如图4所示，本发明实施例中得到两个扩展点集合：正向扩展点集合G1{DEP_AIRPORT}(出发地的扩展点集合)和反向扩展点集合G2{ARR_AIRPORT}(目的地的扩展点集合)，步骤403中比较两个扩展点集合的大小，即G1是否小于等于G2，如果是，则执行步骤404-405，正向扩展生成集合G1{CITYS}，并根据里程制运价信息对G1{CITY}剪枝，如果不是，则执行步骤406-407，反向扩展生成集合G2{CITYS}，并根据里程制运价信息对G2{CITY}剪枝。

这里，如果一个方向生成的扩展点集合已经很差(比如，初始节点到扩展点之间不存在直航或中转航班的经停点又超过了限制(3个或以上)等等)则可以删除。

如图4所示，步骤408为取交集，即将两个方向的扩展点集合G1与G2取交集，如果存在交集，则根据两者交集生成出发地到目的地的行程集合；如果不存在交集，则重新执行本步骤，即重新扩展、剪枝、取交集，此过程中对于扩展的限制、剪枝的限制可以放宽。具体过程与上述描述类似，不再赘述。

具体的，取交集可以是比较两个扩展点集合，如果两个扩展点集合存在至少一个相同的扩展点，那么说明存在交集，通过将出发地到扩展点、扩展点到目的地的航班整合，生成出发地到目的地的行程集合。

步骤409-410：对行程集合进行删减，并对保留下来的行程进行评估排序；

具体的，对所述行程集合中已经得到的行程进行检查，检查的主要目的是对完整行程进行评估。

这里，对行程的检查主要包括：

首先，判断得到的行程是否可能是有效行程，将无效行程删除，删除过程与上述的“剪枝”过程相似，不再赘述；

其次，对保留下来的行程进行评估排序，即对每个行程进行评定和综合打分，保证行程集合的多样性和便捷性。首先保留各个极端最优的行程，比如价格最低、旅行时间最短、直飞航班；然后对所有保留行程进行综合打分，计算行程的分值并按照分值由高到低存储，删除综合打分低于分值阈值的行程。

具体的，评分策略如下：首先从航班查询更新服务器获取行程中所有航班的航班可利用状态，对航班可利用状态进行打分，记为Availability Score；计算行程的旅行时间及旅行时间的分值，记为TFT Score；根据行程的中转次数计算连接点数量的分值，记为Connection Score；根据行程中航空公司之间关系计算联盟分值，记为Alliance Score。如此，行程总的分值Total Score＝Availability Score+TFT Score+Connection Score+Alliance Score。也就是说，行程分值为航班可利用状态分值、旅行时间分值、连接点数量分值、以及联盟分值之和。

检查之后，如果行程集合中的行程数量还没有达到结果阈值则需要返回步骤402进一步进行扩展。扩展的依据是如果进一步扩展后最优的航班行程的分值比已经得到的最差的航班行程的分值还低则不需要进一步扩展，否则需要进一步扩展。

步骤411：按照优先级将得到的行程插入到结果集合；

这里，优先级根据排序得到，排序越靠前则优先级越高。按照优先级将行 程集合中的行程插入到结果集合中，最后航班查询服务器将结果集合作为搜索结果返回给客户端，客户端显示给用户，便于用户查看。

本发明实施例提供的航班查询方法，可以应用于航空公司系统以及基于互联网的航班搜索系统(Shopping)中用户对航班行程的查询需求，可以高效进行直飞和联程航班行程查询。

本发明实施例还提供了一种航班查询服务器，如图5所示，包括：构建模块51、双向搜索模块52和筛选评估模块53；其中，

构建模块51，用于构建航班网路图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场；

双向搜索模块52，用于在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；

筛选评估模块53，用于对所述双向搜索模块52得到的行程集合进行筛选评估。

具体地，所述双向搜索模块52可以包括：扩展子模块、剪枝子模块和交集子模块；其中，扩展子模块，用于分别以所述用户行程请求中的出发地和目的地为初始节点，从所述航班网络图的两边进行扩展，得到两个扩展点集合，所述扩展点集合中的扩展点为以所述出发地或目的地为初始节点的所有航班经过的地点；剪枝子模块，用于根据里程制运价信息，分别对所述扩展子模块得到的两个扩展点集合进行剪枝；交集子模块，用于取所述剪枝子模块剪枝后的两个扩展点集合的交集，生成出发地到目的地的行程集合。这里，所述里程制运 价信息包括：距离限制、中转次数限制、旅行方向限制和/或航班属性限制。

具体地，所述筛选评估模块53可以用于将所述行程集合中的无效行程删除，并对保留下来的行程进行评估排序。这里，所述筛选评估模块进行评估，包括：根据行程中航班可利用状态、旅行时间、中转次数、行程中航空公司之间的联盟关系，对所述行程打分。

此外，本发明实施例还提供了一种航班查询系统，如图6所示为该系统的逻辑架构图，该系统包括：客户端61、数据服务器62以及上述的航班查询服务器63。实际应用中，航班查询服务器63主要为航班行程的搜索提供查询服务，多进程部署，每个进程可以独立完成整个业务处理请求。当有用户请求行程时，客户端生成用户行程请求并上报给航班查询服务器63，航班查询服务器63首先解析用户行程请求，根据其中的起飞地城市(机场)、目的地城市(机场)、起飞日期等信息进行行程查询，将符合用户查询条件的有限的行程结果集合返回给客户端61，供用户查看。数据服务器63作为与其他系统交互的接口，主要为行程的生成提供基础数据的更新和查询，其中包括直飞航班信息的更新，提供航班舱位可利用状态的查询以及里程制运价相关信息的查询。

其中，客户端61，用于接收用户输入的信息，生成用户行程请求并发送给所述航班查询服务器，具体实现过程参见上述方法描述，不再赘述；数据服务器62，用于为所述航班查询服务器提供航班信息、舱位状态信息以及包括里程制运价信息的运价相关信息；所述航班查询服务器63的构建模块，具体用于从所述数据服务器62获取最新的航班信息，构建航班网络图；所述航班查询服务 器63的双向搜索模块，具体用于从所述数据服务器获取里程制运价信息和舱位状态信息，在所述航班网络图中基于用户行程请求进行双向搜索；以及，所述航班查询服务器63的筛选评估模块，还用于将筛选评估后的行程集合返回给所述客户端。

实际应用中，本发明实施例通过航班行程查询、运价规则、航班舱位可利用状态等的协同工作，在航班查询系统中应用运价规则和航班舱位可利用状态的相关信息，指导行程查询的生成。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用硬件实施例、软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备 以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。

Claims (9)

1.一种航班查询方法，其特征在于，所述方法包括：

构建航班网络图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场，其中，如果两地之间存在多个航班，则在所述航班网络图上对应的两点之间就会再多条边；

在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合，包括：根据用户请求检索航班网络图；判断是否需要扩展，如果需要扩展则分别以所述用户行程请求中的出发地和目的地为初始节点，从所述航班网络图的两边进行扩展，得到两个扩展点集合，所述扩展点集合中的扩展点为以所述出发地或目的地为初始节点的所有航班经过的地点；在每一次扩展之后，根据里程制运价信息，分别对所述两个扩展点集合进行剪枝；取所述两个扩展点集合的交集，生成出发地到目的地的行程集合；

对所述行程集合进行筛选评估。

2.根据权利要求1所述的方法，其特征在于：所述里程制运价信息包括：距离限制、中转次数限制、旅行方向限制和/或航班属性限制。

3.根据权利要求1所述的方法，其特征在于，对所述行程集合进行筛选评估，包括：将所述行程集合中的无效行程删除，并对保留下来的行程进行评估排序。

4.根据权利要求3所述的方法，其特征在于，所述评估包括：根据行程中航班可利用状态、旅行时间、中转次数、行程中航空公司之间的联盟关系，对所述行程打分。

5.一种航班查询服务器，其特征在于，包括：构建模块、双向搜索模块和筛选评估模块；其中，

构建模块，用于构建航班网路图，所述航班网络图的一条边表示一个航班，边与边之间的连接点表示一个地点或一个机场，其中，如果两地之间存在多个航班，则在所述航班网络图上对应的两点之间就会再 多条边；

双向搜索模块，用于在所述航班网络图中基于用户行程请求进行双向搜索，得到行程集合；

筛选评估模块，用于对所述双向搜索模块得到的行程集合进行筛选评估；

其中，所述双向搜索模块包括：扩展子模块、剪枝子模块和交集子模块；其中，扩展子模块，用于判断是否需要扩展，如果需要扩展则分别以所述用户行程请求中的出发地和目的地为初始节点，从所述航班网络图的两边进行扩展，得到两个扩展点集合，所述扩展点集合中的扩展点为以所述出发地或目的地为初始节点的所有航班经过的地点；剪枝子模块，用于在每一次扩展之后，根据里程制运价信息，分别对所述扩展子模块得到的两个扩展点集合进行剪枝；交集子模块，用于取所述剪枝子模块剪枝后的两个扩展点集合的交集，生成出发地到目的地的行程集合。

6.根据权利要求5所述的航班查询服务器，其特征在于：所述里程制运价信息包括：距离限制、中转次数限制、旅行方向限制和/或航班属性限制。

7.根据权利要求5所述的航班查询服务器，其特征在于：

所述筛选评估模块用于将所述行程集合中的无效行程删除，并对保留下来的行程进行评估排序。

8.根据权利要求7所述的航班查询服务器，其特征在于，所述筛选评估模块进行评估，包括：根据行程中航班可利用状态、旅行时间、中转次数、行程中航空公司之间的联盟关系，对所述行程打分。

9.一种航班查询系统，其特征在于，所述系统包括：客户端、数据服务器以及如权利要求5至8任一项所述的航班查询服务器；其中，

客户端，用于接收用户输入的信息，生成用户行程请求并发送给所述航班查询服务器；

数据服务器，用于为所述航班查询服务器提供航班信息、舱位状态信息以及包括里程制运价信息的运价相关信息；

所述航班查询服务器的构建模块，用于从所述数据服务器获取最新的航班信息，构建航班网络图；

所述航班查询服务器的双向搜索模块，用于从所述数据服务器获取里程制运价信息和舱位状态信息，在所述航班网络图中基于用户行程请求进行双向搜索；以及，

所述航班查询服务器的筛选评估模块，还用于将筛选评估后的行程集合返回给所述客户端。

Images