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

關(guān)鍵詞：航線網(wǎng)絡(luò);聯(lián)程路徑搜索;旅客愛好

中圖分類號：TP274+.3;TP18 ? ? ?文獻(xiàn)標(biāo)識碼：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ā)展，國際航線網(wǎng)絡(luò)的規(guī)模變得日益龐大，在相同的起飛降落城市之間有很多航線可供旅客選擇，為人們出行提供了更多的選擇。隨著科技的進(jìn)步以及生活水平的提高，飛機(jī)在人們生活中越來越普及，成為了人們出行的基本工具之一。而旅客對旅行服務(wù)質(zhì)量的要求也越來越高，他們不僅要知道選擇哪條聯(lián)程路徑可以到達(dá)目的地，而且要根據(jù)自身的要求等選擇最合適的聯(lián)程路徑。

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

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

（2）通過對求解KSP（K Shortest Path）問題的算法進(jìn)行改進(jìn)來求解KCSP問題。與KCSP相同，KSP問題也是要在給定的網(wǎng)絡(luò)中尋找兩節(jié)點(diǎn)之間的K條最短路徑;但與KCSP不同的是，KSP算法在求解時(shí)不要求路徑滿足某些條件。因此，在利用KSP算法求解KCSP問題時(shí)，需要在算法進(jìn)行的過程中，不斷地檢查新產(chǎn)生的節(jié)點(diǎn)或路徑是否滿足約束條件以過濾掉不滿足條件的節(jié)點(diǎn)或路徑，如2003年，Climaco等[2]提出運(yùn)用求解KSP問題的MPS算法[3]解決多媒體網(wǎng)絡(luò)中的多約束路由問題。2010年，Ning Shi[4]提出一個(gè)通用的KCSP算法，其基本思想是采用分支策略將KCSP問題劃分為多個(gè)約束最短路徑CSP（Constrained Shortest Path，簡稱MCP）子問題。而目前存在求解CSP問題的有效算法，進(jìn)而可以使KCSP問題得到有效的解決。實(shí)際上，Ning Shi的通用KCSP算法與文獻(xiàn)[2]在總體思路上是一樣的。在2013年張春輝[5]利用改進(jìn)的Yen算法[6]求解出多條最短路徑，然后過濾掉不滿足約束條件的路徑。

（3）利用通用的搜索策略來求解KCSP問題。如Liu等基于A*搜索策略提出了求解KCSP問題的A*Prune算法[7]。作者證明了當(dāng)以Dijkstra距離作為節(jié)點(diǎn)評估函數(shù)時(shí)，A*Prune算法具有很高的準(zhǔn)確度。如文獻(xiàn)[8]提出利用分支界限法和A*算法求解概率圖模型中的m個(gè)最好解，在與或圖搜索中取得了較好的效果。文獻(xiàn)[9]通過使用A*算法來降低求解KSP問題的EA算法的復(fù)雜度。

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

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

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

1 ?聯(lián)程路徑搜索問題

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

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

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

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

2 ?基于旅客出行偏好的聯(lián)程路徑推薦策略

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

2.1 ?旅客出行偏好的獲取

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

2.2 ?網(wǎng)絡(luò)修正

如上所述，某條路徑被選擇的次數(shù)說明了旅客出行選擇的一種偏好。因此，聯(lián)程路徑算法推薦的路徑中應(yīng)該更多地包含這樣高頻邊的路徑。為了讓現(xiàn)有的聯(lián)程路徑推薦算法更偏向于高頻邊，根據(jù)邊的選擇頻次對網(wǎng)絡(luò)中邊的長度進(jìn)行了調(diào)整，采用的調(diào)整策略如下。

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

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

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

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

接著從closed表中的每個(gè)目標(biāo)節(jié)點(diǎn)回溯，從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，存放到path數(shù)組中（第11步）。

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

從理論上講，算法的時(shí)間開銷主要體現(xiàn)在以下四點(diǎn)：

第一，根據(jù)邊的出現(xiàn)頻率改變邊的長度，即偽代碼的第2步，假設(shè)網(wǎng)絡(luò)中有n條邊，則需要的時(shí)間復(fù)雜度為O（n）;

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

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

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

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

3 ?實(shí)驗(yàn)

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

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

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

為了具有可比性，本實(shí)驗(yàn)中根據(jù)基于旅客出行偏好的KCSP_BFS或KCSP_BFS都是以C語言開發(fā)的，所有實(shí)驗(yàn)都是在同一軟、硬件環(huán)境下進(jìn)行的：處理器為Intel四核，主頻為2.93Hz，操作系統(tǒng)為Windows 10，物理內(nèi)存為8G。

從測試中隨機(jī)選擇了16條不同的出行路徑對兩算法進(jìn)行了測試，測試結(jié)果如表1所示，其中第2列表示KCSP_BFS算法的準(zhǔn)確度，第3列表示基于旅客出行偏好的KCSP_BFS算法的準(zhǔn)確度。

通過表1可以得到以下三點(diǎn)：

（1）在16條測試路徑中，在2條測試路徑上，KCSP_BFS和基于旅客出行偏好的KCSP_BFS的準(zhǔn)確度相同的分別為第5條和第9條測試路徑。在另外14條測試路徑上，基于旅客出行偏好的KCSP_BFS的準(zhǔn)確度均高于KCSP_BFS。

（2）KCSP_BFS算法在16條測試路徑上的平均準(zhǔn)確度為0.675，基于旅客出行偏好的KCSP_BFS的平均準(zhǔn)確度為0.806。

（3）對于不同的測試路徑，兩種算法的準(zhǔn)確度不同。其準(zhǔn)確度受多種因素的影響，可能主要原因如下：第一，有的測試路徑所對應(yīng)的路徑最多只有K條，如第5條測試路徑其所對應(yīng)的OD對之間只有這K條路徑，所以無論哪種算法得到的也只有這K條，所以兩算法的準(zhǔn)確率都為1。第二，測試路徑對應(yīng)的OD對之間的路徑非常豐富，導(dǎo)致人們的選擇比較分散，這樣兩算法的準(zhǔn)確率就有可能都會(huì)比較低。

可見，從得到路徑的實(shí)用性角度看，新策略能夠有效地提高現(xiàn)有的聯(lián)程路徑推薦算法。

4 ?結(jié) ?論

針對現(xiàn)有聯(lián)程路徑推薦算法不能滿足旅客的實(shí)際需求的問題，鑒于建模旅客出行方案選擇心理的復(fù)雜性，本文為了提高現(xiàn)有聯(lián)程路徑推薦算法，在旅客歷史出行記錄的數(shù)據(jù)上，提出了一種簡單有效的反映旅客出行偏好的聯(lián)程路徑推薦策略。理論上，新的策略不會(huì)改變現(xiàn)有推薦算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，新的策略能夠有效地提高現(xiàn)有的聯(lián)程路徑搜索算法。

參考文獻(xiàn)：

[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] 張春輝.基于實(shí)時(shí)信息的公交乘客出行路徑搜索算法研究 [D].北京：北京交通大學(xué)，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，F(xiàn)LEROVA 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-），男，漢族，河北衡水人，職員，助理工程師，學(xué)士學(xué)位，研究方向：計(jì)算機(jī)軟件、網(wǎng)絡(luò)運(yùn)維。