基于多因素双向搜索方法的民航行程计算系统

朱家彬，杨永凯，刘 军

（1.中国民航信息网络股份有限公司研发中心，北京 101318；2.民航旅客服务智能化应用技术重点实验室，北京 101318）

中国航信（TravelSky）是国内唯一一家民航计算机订座系统（CRS，computer reservation system）运营商，在其自主研发的早期版本的行程计算系统中，作为核心的联程航班构建模块是采用基于航线网络图的单向搜索方法实现的。当市场上航班数量较少时，该方法基本可以保证行程查询的效率和可用性。但是随着全球民航市场的高速发展，航空公司和商营航班数量急剧增长，这种基于航线网络图单向搜索的联程航班构建方法已经逐渐不能满足旅客和分销商的行程查询需求，其不足主要体现在两个方面。

（1）对于单向搜索算法，无论是单向的K 短路径搜索算法还是宽度（深度）优先搜索算法，扩展两次后结果会以指数级发散，搜索效率相对较低。因此，当航线网络图节点数量大量增加，或出发地—目的地（OD，origin-destination）间涉及多次中转的情况时，系统性能较低、响应时间较长、用户体验度较差。

（2）为了平衡单向搜索算法的性能问题，减少计算量，使用了由直达航线构造的航线网络图进行搜索计算。在航线网络图中，两点之间的连线最多有1 条，表示这两点间存在直达航线，计算时先搜索出中转路径，然后再基于路径构建联程航班。航线网络图虽然可以压缩图的搜索空间，但由于在搜索路径时没有利用航班的具体信息，无法有效应用航班属性对找到的中转路径进行可用性评估，会降低联程航班结果的可用性。……