摘 要：随着全球民航业的飞速发展，航线网络变得日益复杂与庞大，为人们出行提供了更多选择。同时，随着生活水平的提高，旅客越来越希望能根据自己的需求选择出行方案。由于旅客选择出行方案的心理复杂，难以建模，因此现有的联程路径搜索算法往往是根据某种指标最优进行路径推荐的，但并不能满足旅客的实际需求。针对这个问题，本文基于旅客历史出行记录数据，提出了一种简单有效的反映旅客出行偏好的联程路径推荐策略以改进现有的联程路径推荐算法。该策略首先对旅客的历史出行记录进行统计，以分析出旅客的出行偏好，然后根据该偏好对网络进行修正，最后在修正的网络中运行现有的联程路径推荐算法以计算出可能满足旅客需求的多条路径。最后对航线网络的测试结果表明，从得到路径的实用性角度看，新策略能够有效地提高现有的联程路径推荐算法。
关键词：航线网络；联程路径搜索；旅客爱好
中图分类号：TP274+.3；TP18 文献标识码：A 文章编号：2096-4706（2019）18-0001-04
Research on Connecting Paths Search Algorithms Based on Passenger’s Travel Hobbies
WANG Guoliang
（Yantai International Airport Group Co.，Ltd.，Yantai 265617，China）
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
参考文献：
[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].IEEETransactions 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]//INFOCOM2001. 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-），男，汉族，河北衡水人，职员，助理工程师，学士学位，研究方向：计算机软件、网络运维。