基于旅客出行愛好的聯程路徑搜索算法研究

摘 ?要：隨著全球民航業(yè)的飛速發(fā)展，航線網絡變得日益復雜與龐大，為人們出行提供了更多選擇。同時，隨著生活水平的提高，旅客越來越希望能根據自己的需求選擇出行方案。由于旅客選擇出行方案的心理復雜，難以建模，因此現有的聯程路徑搜索算法往往是根據某種指標最優(yōu)進行路徑推薦的，但并不能滿足旅客的實際需求。針對這個問題，本文基于旅客歷史出行記錄數據，提出了一種簡單有效的反映旅客出行偏好的聯程路徑推薦策略以改進現有的聯程路徑推薦算法。該策略首先對旅客的歷史出行記錄進行統(tǒng)計，以分析出旅客的出行偏好，然后根據該偏好對網絡進行修正，最后在修正的網絡中運行現有的聯程路徑推薦算法以計算出可能滿足旅客需求的多條路徑。最后對航線網絡的測試結果表明，從得到路徑的實用性角度看，新策略能夠有效地提高現有的聯程路徑推薦算法。

關鍵詞：航線網絡;聯程路徑搜索;旅客愛好

中圖分類號：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 ?引 ?言

隨著全球航空業(yè)的飛速發(fā)展，國際航線網絡的規(guī)模變得日益龐大，在相同的起飛降落城市之間有很多航線可供旅客選擇，為人們出行提供了更多的選擇。隨著科技的進步以及生活水平的提高，飛機在人們生活中越來越普及，成為了人們出行的基本工具之一。而旅客對旅行服務質量的要求也越來越高，他們不僅要知道選擇哪條聯程路徑可以到達目的地，而且要根據自身的要求等選擇最合適的聯程路徑。

如何快速地找出龐大的航線網絡中符合旅客出行要求的聯程路徑是旅行咨詢系統(tǒng)中的一個重要問題，也是旅客非常關心的一個問題。目前的聯程路徑搜索是一個在給定的約束條件下搜索的K條最短路徑問題（K Constrained Shortest Path，簡稱KCSP），即在給定的航線網絡中滿足一定約束條件下尋找兩節(jié)點之間的K條最短路徑的問題。目前針對KCSP算法的研究，主要有以下三種思路：

（1）對經典的最短路徑算法——Dijkstra算法加以改進。Ziang Zhang等在2008年提出用于解決互聯網中QoS（Quality of Service）路由問題的多約束剪枝算法MCP[1]，在MCP中每個約束都看作是互相獨立的，把約束條件按照優(yōu)先級進行排序，即最高優(yōu)先級的約束放在序列最前面，第二優(yōu)先級的約束放在第二位置，……。然后根據第一個約束條件，用Dijkstra算法求出第一條最短路徑p1，接著刪除圖中p1的包含的邊，最后再用Dijkstra算法求得第二條最短路徑。由此完成一個約束條件的計算。按照上述方法繼續(xù)逐次根據其他約束條件計算路徑。

（2）通過對求解KSP（K Shortest Path）問題的算法進行改進來求解KCSP問題。與KCSP相同，KSP問題也是要在給定的網絡中尋找兩節(jié)點之間的K條最短路徑;但與KCSP不同的是，KSP算法在求解時不要求路徑滿足某些條件。因此，在利用KSP算法求解KCSP問題時，需要在算法進行的過程中，不斷地檢查新產生的節(jié)點或路徑是否滿足約束條件以過濾掉不滿足條件的節(jié)點或路徑，如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距離作為節(jié)點評估函數時，A*Prune算法具有很高的準確度。如文獻[8]提出利用分支界限法和A*算法求解概率圖模型中的m個最好解，在與或圖搜索中取得了較好的效果。文獻[9]通過使用A*算法來降低求解KSP問題的EA算法的復雜度。

可見，通用KCSP問題已經得到了相對深入的研究，為聯程路徑搜索算法的研究奠定了基礎。對聯程路徑搜索算法的研究主要體現在如何利用聯程路徑的特點來使現有KCSP算法能有效地應用于聯程路徑搜索。目前聯程路徑搜索算法中所利用的聯程路徑的特點一般包括聯程路徑盡可能短、中轉次數不超過某個范圍以及路徑是無環(huán)的。如文獻[10]分別基于有界廣度優(yōu)先搜索和A*搜索策略，提出兩種快速的KCSP算法，即KCSP_BFS算法和KCSP_Star算法;文獻[11]利用分層策略提出了一種聯程路徑計算方法。

聯程路徑搜索最終是為旅客服務的，希望能找到最可能滿足旅客出行需求的K條路徑。所以，求解聯程路徑搜索問題的一個關鍵問題是如何建模滿足旅客需求的路徑。影響旅客選擇出行方案的因素眾多，包括內在因素如旅客個人喜好，以及外在因素如出行方案的便捷程度等，很難用一個精確的模型來模擬每個旅客的選擇心理?，F有的策略一般認為長度盡可能短、中轉次數盡可能少的路徑是最可能滿足旅客需求的。因此，所推薦的路徑往往是根據某種指標最優(yōu)的，但在很多情況下并不能滿足旅客的實際需求。

針對這個問題，本文提出了一種考慮旅客出行偏好的策略以提高現有的聯程路徑推薦算法。由于對旅客歷史出行記錄的統(tǒng)計分析在線下完成，所以新的策略從理論上不會改變原有的聯程路徑搜索算法的復雜度。

1 ?聯程路徑搜索問題

一般，航線網絡通常用圖G=（V，E）表示，其中V為節(jié)點的集合，每個機場對應一個節(jié)點;E為邊的集合，如果任意兩個機場i和機場j之間有直飛航班，則在航線網絡圖上該兩個機場對應的節(jié)點之間存在一條邊。邊的長度為邊的兩個端點所對應的機場之間的球面距離。由于航班具有方向性，因此航線網絡圖中的每條邊都是有向邊。

當p中所有節(jié)點都不同時，p被稱為無環(huán)路徑，也稱為簡單路徑。環(huán)是從某個節(jié)點到其自身的路徑，其中除了初始節(jié)點與終止節(jié)點相同外，其他節(jié)點都不相同。

從s到t的路徑集合用Pst表示。兩條路徑p∈Pij，q∈Pjl的拼接p◇q，表示一條由p和q構成的從節(jié)點i到節(jié)點l的路徑。

聯程路徑搜索問題是要找到G中可能最滿足旅客需求的K條路徑。

2 ?基于旅客出行偏好的聯程路徑推薦策略

基于旅客出行偏好的聯程路徑推薦策略的基本思想是首先對旅客的歷史出行記錄進行統(tǒng)計以分析出旅客的出行偏好，然后根據該偏好對網絡進行修正，最后在修正的網絡中運行現有的聯程路徑推薦算法以計算出可能滿足旅客需求的多條路徑。

2.1 ?旅客出行偏好的獲取

對旅客歷史出行記錄的統(tǒng)計分析能在一定程度上反映旅客的出行偏好。如從A地到B地，某條路徑被選擇的次數最多，這在一定程度上說明該路徑可能更快、中轉更方便、更適合大多數人的出行需求。因此，本文采用一定的統(tǒng)計方法對在某段時間內旅客的歷史出行記錄進行分析，計算出在航線網絡圖中每條邊ek被選擇的次數pk。

2.2 ?網絡修正

如上所述，某條路徑被選擇的次數說明了旅客出行選擇的一種偏好。因此，聯程路徑算法推薦的路徑中應該更多地包含這樣高頻邊的路徑。為了讓現有的聯程路徑推薦算法更偏向于高頻邊，根據邊的選擇頻次對網絡中邊的長度進行了調整，采用的調整策略如下。

從理論角度講，當某條路徑ek被選擇的次數sk越高，則該路徑被縮短的程度越大，推薦算法對該路徑的偏向性越強。

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

本文所提出的基于旅客出行偏好的推薦策略可以用于提高現有的任何聯程路徑推薦算法。為了說明新策略不會大幅增加現有推薦算法的運行時間，以KCSP_BFS算法為例。KCSP_BFS算法的基本思想是按照廣度優(yōu)先的搜索策略從起始節(jié)點開始依次擴展航線網絡中的節(jié)點，直至節(jié)點的深度為4為止。然后根據擴展結果得到從起始節(jié)點到目標節(jié)點的所有路徑，從中選擇最短的K條返回。

基于旅客出行偏好的KCSP_BFS算法的偽代碼如圖1所示。首先統(tǒng)計每條邊的出現頻率，這一步可以作為算法的預處理在線下完成，其執(zhí)行時間不會影響算法的整體運行時間。第2步是根據邊的出現頻率改變邊的長度。接下來是根據KCSP_BFS在修正后的網絡中計算滿足中轉次數在一定范圍內的、最短的K條路徑。即首先將open表和closed表初始化為空（第3步）。將起始節(jié)點置入open表中。然后依次取出open表的第一個節(jié)點，首先判斷該節(jié)點的深度是否小于T（當允許的最大中轉次數為3時，T為5），如果小于T，則判斷其是否為目標節(jié)點，如果是目標節(jié)點，則直接將其放入closed表中;如果不是目標節(jié)點，則對其進行擴展、將其子節(jié)點放入open表的末端，并將該擴展的節(jié)點從open表移入closed表（第8步）。考慮到當節(jié)點的深度為T-1時，其產生的后繼節(jié)點的深度則為T，這些節(jié)點將來不會被擴展，因此，算法沒有將這些存放到open表中（第8.2步），這樣在降低算法的空間復雜度的同時也降低了算法的時間復雜度。

接著從closed表中的每個目標節(jié)點回溯，從起始節(jié)點到目標節(jié)點的路徑，存放到path數組中（第11步）。

最后查找并輸出path表中的前K條最短路徑（第13步）。

從理論上講，算法的時間開銷主要體現在以下四點：

第一，根據邊的出現頻率改變邊的長度，即偽代碼的第2步，假設網絡中有n條邊，則需要的時間復雜度為O（n）;

第二，擴展節(jié)點的過程，即偽代碼的第8步，從起始節(jié)點開始，擴展到深度為T時需要的時間最多為O（dT-1），其中d為網絡中節(jié)點的最大度。一般情況下，在航線網絡中，h遠遠小于網絡節(jié)點數;

第三，檢查closed表中目標節(jié)點出現了多少次，并根據每個目標節(jié)點回溯構造一條從s到t的路徑，即偽代碼的第11步。由于每條路徑最多包含T個節(jié)點，即2個中轉點和1個初始節(jié)點、1個目標節(jié)點，則回溯構造路徑花費的代價為O（dT-1）;

第四，從所產生的路徑中得到K條最短的路徑，即偽代碼的第14步。產生的路徑最多為O（dT-1），因此從中尋找K條最短路徑需要的時間為O（KdT-1）。

因此，基于旅客出行偏好的KCSP_BFS算法的時間復雜度為O（KdT-1），與KCSP_BFS算法相同[1]。

3 ?實驗

本節(jié)通過實驗檢驗基于旅客出行偏好的KCSP_BFS是否能有效地提高KCSP_BFS。

所采用的航線網絡是全球航線網絡，其中包括3818個節(jié)點、64387條邊。所采用的旅客歷史出行記錄為在2012年從某GDS出票的所有的旅客數據，共包括212172條記錄。

在具體實驗時將其中的152172條數據作為訓練集，對其進行統(tǒng)計以獲取旅客的出行偏好;將另外的6萬條數據作為測試集，即隨機選擇測試集中的某次出行記錄，假設該記錄中旅客實際走的路徑為A→B→C，然后統(tǒng)計測試集中所有從A到C的實際路徑，從中選擇出選擇次數最多的K條路徑，用集合Pr表示。接著根據基于旅客出行偏好的KCSP_BFS或KCSP_BFS計算出從A到C的前K條最優(yōu)路徑，用集合Pc表示。

為了具有可比性，本實驗中根據基于旅客出行偏好的KCSP_BFS或KCSP_BFS都是以C語言開發(fā)的，所有實驗都是在同一軟、硬件環(huán)境下進行的：處理器為Intel四核，主頻為2.93Hz，操作系統(tǒng)為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-），男，漢族，河北衡水人，職員，助理工程師，學士學位，研究方向：計算機軟件、網絡運維。