基于旅客出行爱好的联程路径搜索算法研究

摘  要：随着全球民航业的飞速发展，航线网络变得日益复杂与庞大，为人们出行提供了更多选择。同时，随着生活水平的提高，旅客越来越希望能根据自己的需求选择出行方案。由于旅客选择出行方案的心理复杂，难以建模，因此现有的联程路径搜索算法往往是根据某种指标最优进行路径推荐的，但并不能满足旅客的实际需求。针对这个问题，本文基于旅客历史出行记录数据，提出了一种简单有效的反映旅客出行偏好的联程路径推荐策略以改进现有的联程路径推荐算法。该策略首先对旅客的历史出行记录进行统计，以分析出旅客的出行偏好，然后根据该偏好对网络进行修正，最后在修正的网络中运行现有的联程路径推荐算法以计算出可能满足旅客需求的多条路径。最后对航线网络的测试结果表明，从得到路径的实用性角度看，新策略能够有效地提高现有的联程路径推荐算法。

关键词：航线网络;联程路径搜索;旅客爱好

中图分类号：TP274+.3;TP18      文献标识码：A 文章编号：2096-4706（2019）18-0001-04

Abstract：With the rapid development of the civil aviation industry in the world，the airline network is becoming more complex and huge，which can provide more choice for travelers. At the same time，with the improvement of living standards，passengers increasingly hope to choose travel plans according to their own needs. Because of the complex psychology of passengers in choosing travel plans，it is difficult to model them，so the existing route search algorithms often recommend the route based on the optimal index，but they can not meet the actual needs of passengers. To solve this problem，this paper proposes a simple and effective route recommendation strategy to improve the existing route recommendation algorithm based on the passenger history travel record data. The strategy first counts the passenger’s historical travel records to analyze the passenger’s travel preferences，then revises the network according to the preferences，and finally runs the existing route recommendation algorithm in the revised network to calculate the multiple paths that may meet the passenger’s needs. Finally，the test results of the route network show that the new strategy can effectively improve the existing route recommendation algorithm from the practical point of view.

Keywords：airline network;connecting path search;passenger hobbies

0  引  言

隨着全球航空业的飞速发展，国际航线网络的规模变得日益庞大，在相同的起飞降落城市之间有很多航线可供旅客选择，为人们出行提供了更多的选择。随着科技的进步以及生活水平的提高，飞机在人们生活中越来越普及，成为了人们出行的基本工具之一。而旅客对旅行服务质量的要求也越来越高，他们不仅要知道选择哪条联程路径可以到达目的地，而且要根据自身的要求等选择最合适的联程路径。

如何快速地找出庞大的航线网络中符合旅客出行要求的联程路径是旅行咨询系统中的一个重要问题，也是旅客非常关心的一个问题。目前的联程路径搜索是一个在给定的约束条件下搜索的K条最短路径问题（K Constrained Shortest Path，简称KCSP），即在给定的航线网络中满足一定约束条件下寻找两节点之间的K条最短路径的问题。目前针对KCSP算法的研究，主要有以下三种思路：

（1）对经典的最短路径算法——Dijkstra算法加以改进。Ziang Zhang等在2008年提出用于解决互联网中QoS（Quality of Service）路由问题的多约束剪枝算法MCP[1]，在MCP中每个约束都看作是互相独立的，把约束条件按照优先级进行排序，即最高优先级的约束放在序列最前面，第二优先级的约束放在第二位置，……。然后根据第一个约束条件，用Dijkstra算法求出第一条最短路径p1，接着删除图中p1的包含的边，最后再用Dijkstra算法求得第二条最短路径。由此完成一个约束条件的计算。按照上述方法继续逐次根据其他约束条件计算路径。

（2）通过对求解KSP（K Shortest Path）问题的算法进行改进来求解KCSP问题。与KCSP相同，KSP问题也是要在给定的网络中寻找两节点之间的K条最短路径;但与KCSP不同的是，KSP算法在求解时不要求路径满足某些条件。因此，在利用KSP算法求解KCSP问题时，需要在算法进行的过程中，不断地检查新产生的节点或路径是否满足约束条件以过滤掉不满足条件的节点或路径，如2003年，Climaco等[2]提出运用求解KSP问题的MPS算法[3]解决多媒体网络中的多约束路由问题。2010年，Ning Shi[4]提出一个通用的KCSP算法，其基本思想是采用分支策略将KCSP问题划分为多个约束最短路径CSP（Constrained Shortest Path，简称MCP）子问题。而目前存在求解CSP问题的有效算法，进而可以使KCSP问题得到有效的解决。实际上，Ning Shi的通用KCSP算法与文献[2]在总体思路上是一样的。在2013年张春辉[5]利用改进的Yen算法[6]求解出多条最短路径，然后过滤掉不满足约束条件的路径。

（3）利用通用的搜索策略来求解KCSP问题。如Liu等基于A*搜索策略提出了求解KCSP问题的A*Prune算法[7]。作者证明了当以Dijkstra距离作为节点评估函数时，A*Prune算法具有很高的准确度。如文献[8]提出利用分支界限法和A*算法求解概率图模型中的m个最好解，在与或图搜索中取得了较好的效果。文献[9]通过使用A*算法来降低求解KSP问题的EA算法的复杂度。

可见，通用KCSP问题已经得到了相对深入的研究，为联程路径搜索算法的研究奠定了基础。对联程路径搜索算法的研究主要体现在如何利用联程路径的特点来使现有KCSP算法能有效地应用于联程路径搜索。目前联程路径搜索算法中所利用的联程路径的特点一般包括联程路径尽可能短、中转次数不超过某个范围以及路径是无环的。如文献[10]分别基于有界广度优先搜索和A*搜索策略，提出两种快速的KCSP算法，即KCSP_BFS算法和KCSP_Star算法;文献[11]利用分层策略提出了一种联程路径计算方法。

联程路径搜索最终是为旅客服务的，希望能找到最可能满足旅客出行需求的K条路径。所以，求解联程路径搜索问题的一个关键问题是如何建模满足旅客需求的路径。影响旅客选择出行方案的因素众多，包括内在因素如旅客个人喜好，以及外在因素如出行方案的便捷程度等，很难用一个精确的模型來模拟每个旅客的选择心理。现有的策略一般认为长度尽可能短、中转次数尽可能少的路径是最可能满足旅客需求的。因此，所推荐的路径往往是根据某种指标最优的，但在很多情况下并不能满足旅客的实际需求。

针对这个问题，本文提出了一种考虑旅客出行偏好的策略以提高现有的联程路径推荐算法。由于对旅客历史出行记录的统计分析在线下完成，所以新的策略从理论上不会改变原有的联程路径搜索算法的复杂度。

1  联程路径搜索问题

一般，航线网络通常用图G=（V，E）表示，其中V为节点的集合，每个机场对应一个节点;E为边的集合，如果任意两个机场i和机场j之间有直飞航班，则在航线网络图上该两个机场对应的节点之间存在一条边。边的长度为边的两个端点所对应的机场之间的球面距离。由于航班具有方向性，因此航线网络图中的每条边都是有向边。

当p中所有节点都不同时，p被称为无环路径，也称为简单路径。环是从某个节点到其自身的路径，其中除了初始节点与终止节点相同外，其他节点都不相同。

从s到t的路径集合用Pst表示。两条路径p∈Pij，q∈Pjl的拼接p◇q，表示一条由p和q构成的从节点i到节点l的路径。

联程路径搜索问题是要找到G中可能最满足旅客需求的K条路径。

2  基于旅客出行偏好的联程路径推荐策略

基于旅客出行偏好的联程路径推荐策略的基本思想是首先对旅客的历史出行记录进行统计以分析出旅客的出行偏好，然后根据该偏好对网络进行修正，最后在修正的网络中运行现有的联程路径推荐算法以计算出可能满足旅客需求的多条路径。

2.1  旅客出行偏好的获取

对旅客历史出行记录的统计分析能在一定程度上反映旅客的出行偏好。如从A地到B地，某条路径被选择的次数最多，这在一定程度上说明该路径可能更快、中转更方便、更适合大多数人的出行需求。因此，本文采用一定的统计方法对在某段时间内旅客的历史出行记录进行分析，计算出在航线网络图中每条边ek被选择的次数pk。

2.2  网络修正

如上所述，某条路径被选择的次数说明了旅客出行选择的一种偏好。因此，联程路径算法推荐的路径中应该更多地包含这样高频边的路径。为了让现有的联程路径推荐算法更偏向于高频边，根据边的选择频次对网络中边的长度进行了调整，采用的调整策略如下。

从理论角度讲，当某条路径ek被选择的次数sk越高，则该路径被缩短的程度越大，推荐算法对该路径的偏向性越强。

2.3  基于旅客出行偏好的KCSP_BFS算法

本文所提出的基于旅客出行偏好的推荐策略可以用于提高现有的任何联程路径推荐算法。为了说明新策略不会大幅增加现有推荐算法的运行时间，以KCSP_BFS算法为例。KCSP_BFS算法的基本思想是按照广度优先的搜索策略从起始节点开始依次扩展航线网络中的节点，直至节点的深度为4为止。然后根据扩展结果得到从起始节点到目标节点的所有路径，从中选择最短的K条返回。

基于旅客出行偏好的KCSP_BFS算法的伪代码如图1所示。首先统计每条边的出现频率，这一步可以作为算法的预处理在线下完成，其执行时间不会影响算法的整体运行时间。第2步是根据边的出现频率改变边的长度。接下来是根据KCSP_BFS在修正后的网络中计算满足中转次数在一定范围内的、最短的K条路径。即首先将open表和closed表初始化为空（第3步）。将起始节点置入open表中。然后依次取出open表的第一个节点，首先判断该节点的深度是否小于T（当允许的最大中转次数为3时，T为5），如果小于T，则判断其是否为目标节点，如果是目标节点，则直接将其放入closed表中;如果不是目标节点，则对其进行扩展、将其子节点放入open表的末端，并将该扩展的节点从open表移入closed表（第8步）。考虑到当节点的深度为T-1时，其产生的后继节点的深度则为T，这些节点将来不会被扩展，因此，算法没有将这些存放到open表中（第8.2步），这样在降低算法的空间复杂度的同时也降低了算法的时间复杂度。

接着从closed表中的每个目标节点回溯，从起始节点到目标节点的路径，存放到path数组中（第11步）。

最后查找并输出path表中的前K条最短路径（第13步）。

从理论上讲，算法的时间开销主要体现在以下四点：

第一，根据边的出现频率改变边的长度，即伪代码的第2步，假设网络中有n条边，则需要的时间复杂度为O（n）;

第二，扩展节点的过程，即伪代码的第8步，从起始节点开始，扩展到深度为T时需要的时间最多为O（dT-1），其中d为网络中节点的最大度。一般情况下，在航线网络中，h远远小于网络节点数;

第三，检查closed表中目标节点出现了多少次，并根据每个目标节点回溯构造一条从s到t的路径，即伪代码的第11步。由于每条路径最多包含T个节点，即2个中转点和1个初始节点、1个目标节点，则回溯构造路径花费的代价为O（dT-1）;

第四，从所产生的路径中得到K条最短的路径，即伪代码的第14步。产生的路径最多为O（dT-1），因此从中寻找K条最短路径需要的时间为O（KdT-1）。

因此，基于旅客出行偏好的KCSP_BFS算法的时间復杂度为O（KdT-1），与KCSP_BFS算法相同[1]。

3  实验

本节通过实验检验基于旅客出行偏好的KCSP_BFS是否能有效地提高KCSP_BFS。

所采用的航线网络是全球航线网络，其中包括3818个节点、64387条边。所采用的旅客历史出行记录为在2012年从某GDS出票的所有的旅客数据，共包括212172条记录。

在具体实验时将其中的152172条数据作为训练集，对其进行统计以获取旅客的出行偏好;将另外的6万条数据作为测试集，即随机选择测试集中的某次出行记录，假设该记录中旅客实际走的路径为A→B→C，然后统计测试集中所有从A到C的实际路径，从中选择出选择次数最多的K条路径，用集合Pr表示。接着根据基于旅客出行偏好的KCSP_BFS或KCSP_BFS计算出从A到C的前K条最优路径，用集合Pc表示。

为了具有可比性，本实验中根据基于旅客出行偏好的KCSP_BFS或KCSP_BFS都是以C语言开发的，所有实验都是在同一软、硬件环境下进行的：处理器为Intel四核，主频为2.93Hz，操作系统为Windows 10，物理内存为8G。

从测试中随机选择了16条不同的出行路径对两算法进行了测试，测试结果如表1所示，其中第2列表示KCSP_BFS算法的准确度，第3列表示基于旅客出行偏好的KCSP_BFS算法的准确度。

通过表1可以得到以下三点：

（1）在16条测试路径中，在2条测试路径上，KCSP_BFS和基于旅客出行偏好的KCSP_BFS的准确度相同的分别为第5条和第9条测试路径。在另外14条测试路径上，基于旅客出行偏好的KCSP_BFS的准确度均高于KCSP_BFS。

（2）KCSP_BFS算法在16条测试路径上的平均准确度为0.675，基于旅客出行偏好的KCSP_BFS的平均准确度为0.806。

（3）对于不同的测试路径，两种算法的准确度不同。其准确度受多种因素的影响，可能主要原因如下：第一，有的测试路径所对应的路径最多只有K条，如第5条测试路径其所对应的OD对之间只有这K条路径，所以无论哪种算法得到的也只有这K条，所以两算法的准确率都为1。第二，测试路径对应的OD对之间的路径非常丰富，导致人们的选择比较分散，这样两算法的准确率就有可能都会比较低。

可见，从得到路径的实用性角度看，新策略能够有效地提高现有的联程路径推荐算法。

4  结  论

针对现有联程路径推荐算法不能满足旅客的实际需求的问题，鉴于建模旅客出行方案选择心理的复杂性，本文为了提高现有联程路径推荐算法，在旅客历史出行记录的数据上，提出了一种简单有效的反映旅客出行偏好的联程路径推荐策略。理论上，新的策略不会改变现有推荐算法的时间复杂度。实验结果表明，新的策略能够有效地提高现有的联程路径搜索算法。

参考文献：

[1] ZHANG Z，ZHAO J. Multi-constraint-pruning：an algorithm for finding K shortest paths subject to multiple constraints [C]//Communications，2008.APCC 2008. 14th Asia-Pacific Conference on. S.l.：s.n.，2008：1-5.

[2] João C.N.Clímaco，José M. F. Craveirinha，Marta M.B.Pascoal. A bicriterion approach for routing problems in multimedia networks [J].Networks，2003，41（4）：206-220.

[3] MARTINS E.Q.V，PASCOAL M.M.B，SANTOS J.L.E. Deviation algorithms for ranking shortest paths [J].International Journal of Foundations of Computer Science，1999，10（3）：247-261.

[4] NING S. K constrained shortest path problem [J].IEEE Transactions on Automation Science and Engineering，2010，7（1）：15-23.

[5] 张春辉.基于实时信息的公交乘客出行路径搜索算法研究 [D].北京：北京交通大学，2013：25-31.

[6] JIN Y. Yen.Finding the K Shortest Loopless Paths in a Network [J].Management Science，1971，17（11）：712-716.

[7] LIU G，RAMAKRISHNAN KG. A*Prune：an algorithm for finding K shortest paths subject to multiple constraints [C]//INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. S.l.：s.n.，2001：743-749.

[8] DECHTER R，FLEROVA N，MARINESCU R. Search Algorithms for M Best Solutions for Graphical Models [C]//Aaai Conference on Artificial Intelligence. 2012：1895-1901.

[9] ALJAZZAR H，LEUE S. K*：A heuristic search algorithm for finding the k shortest paths [J].Artificial Intelligence，2011，175（18）：2129-2154.

[10] LI J F，LI T J. Research on Fast KCSP Algorithms for Searching Connecting Paths in Airline Networks [J].Applied Mechanics and Materials，2014，505-506：1005-1013.

[11] ZHOU W T，HAN B M，YIN H D. Study on the K-Shortest Paths Searching Algorithm of Urban Mass Transit Network Based on the Network Characteristics [J].Applied Mechanics and Materials，2014，505-506：689-697.

作者簡介：王国良（1990.08-），男，汉族，河北衡水人，职员，助理工程师，学士学位，研究方向：计算机软件、网络运维。