基于時刻表的民航聯程路徑算法設計實現
2023-10-27 11:03:41王國良紀曉婧
現代信息科技 2023年17期
王國良 紀曉婧
摘? 要：最近幾年，全球民航業飛速發展，航線網絡變得日益復雜與龐大；與此同時，隨著生活節奏的加快，人們的時間觀念也越來越強。因此，在設計聯程搜索算法時，尤其要考慮時刻表的重要性，這樣才能夠滿足旅客的時間要求，才能體現基于時刻表的聯程搜索算法的重要意義。基于此，提出了一種基于時刻表的策略以優化現有的聯程路徑推薦算法。該策略首先根據航班時刻表信息構建航線網絡，其次根據旅客的出行時間要求對航線網絡進行精簡，最后在修整的網絡中運行聯程路徑推薦算法并計算出可能滿足旅客需求的多條路徑。
關鍵詞：時刻表；航線網絡；聯程路徑
中圖分類號：TP391? 文獻標識碼：A? 文章編號：2096-4706（2023）17-0126-05
Design and Implementation of Civil Aviation Connecting Path Algorithm
Based on Timetable
WANG Guoliang1， JI Xiaojing2
（1.Shandong Airport Management Group Yantai International Airport Co.， Ltd.， Yantai? 265617， China;
2.Yantai Branch of China Telecom Co.， Ltd.， Yantai? 264001， China）
Abstract： In recent years， with the rapid development of global civil aviation industry， the route network has become increasingly complex and huge. At the same time， with the fast speed of life rhythm， people's time concept is gradually strong. Therefore， in the process of designing connecting search algorithm， it is necessary to consider the importance of the timetable， so as to meet the passenger's time requirement and reflect the significance of connecting search algorithm based on timetable. Based on this， this paper proposes a strategy based on timetable in order to improve the existing connecting path recommendation algorithm. According to the flight timetable information， the strategy constructs route network firstly. Secondly， according to the time requirements of the passengers travel， it streamlines the route network. Finally， it runs connecting path recommendation algorithm in the repaired network， and calculates the multiple paths could meet the demand of passengers.
Keywords： timetable; route network; connecting path
0? 引? 言
隨著全球航空業的飛速發展，國際航線網絡的規模變得日益龐大，在相同起飛降落城市之間有很多航線可供旅客出行選擇。旅客對旅行服務質量的要求也越來越高，旅客不僅想知道他們是如何到達目的地的，更希望選擇一條或幾條最適合他們的出行路徑。
鑒于目前國內對基于時刻表路徑推薦算法研究較少的情況下，本文利用航班時刻表建立時間擴展網絡模型，并且考慮了旅客的多標準（如；全程耗時最短，中轉次數最少，在某一時間段內出行）出行方案，在此基礎上為旅客提供最優的K條時間最短路徑的推薦算法。
該策略首先是旅客根據自己的需求，決定自己的出行時間、偏好的航空公司，可以精確到分鐘，接著根據旅客提供的自己的出行時間和出發的城市，然后匹配符合旅客要求條件的航線，依據有界的深度優先算法為旅客推薦出可能滿足旅客需求的多條路徑，由于對旅客出行的時間基礎上完成，所以這個策略從理論上不會改變原有的聯程路徑搜索算法的復雜度。
1? 航線網絡的建立
1.1? 航線網絡思想
在網絡中，任意兩個相連接的節點表示在這兩個節點間有一條相通的路線。通過用這樣的幾條路線將OD點連接起來，就形成了一條從源點O到終點D的一條可行路徑。圖1為經典的航線網絡有向圖模型，其中各個節點用數字1，2，3，4，5表示，任意兩個相連接的節點用一條有向弧相連，弧上的權值代表兩個節點直接的距離或者是單向的運行時間。從該圖可以看出，從節點1到節點3有兩條路線l1，l2，如圖2節點1到3路線圖所示。
這種網絡模型在處理中簡單，但其有明顯的缺陷：每條連線的屬性僅代表相互連接節點之間的距離或者通過兩個節點所用的時間。不能反映由于交通工具的不同，那么對應的屬性值也會隨之變化；各種交通工具在交通運輸中所用的時間和其時刻表不能很好地展現出來；這樣位旅客推薦的路線比較單一，如圖2所示，旅客如果不喜歡線路1，那么他只能選擇線路2，但是在實際的路線中，由于每個節點都對應著不同交通工具的時刻表，同一條路線可以對應著不同的時間路徑。
1.2? 航線網絡模型的建立
航線網絡即建立一個有向圖，圖中的每一個節點代表每一個機場，邊代表機場之間的航線，邊的長度代表距離。結構體節點中定義變量，ID號，名字，定義了出發時間，到達時間，航班號以及標記是否經停的變量；而邊的結構體中，存儲了到達節點，出發機場和到達機場的經緯度，起飛時間，到達時間，以及航班號。
本文定義了一個向量鏈式表，即為vector
2? 航線時刻表網絡的簡化
2.1? 航線時刻表網絡的優化
由于航線網絡規模龐大、航班密集，所以對于圖1建立的航線網絡圖是一個很龐大的圖，對圖的讀取會耗費一大部分的時間。針對此問題，在對航線網絡進行搜索之前首先對航線的時刻表網絡進行了優化。優化策略即根據旅客輸入的對航空公司的偏好，對出發時間、到達時間的要求刪減網絡中不滿足要求的節點和邊。
利用旅客出行時間來優化一部分的圖，旅客根據自己的出行時間輸入自己的出發時間，程序中建立的向量鏈式表，對應的每個鏈表中，進行時間的刷選，對每個小于旅客出行時間的每個鏈表的每個節點進行簡化。從而進行了整體上網絡的優化。例如，圖4航線網絡的優化中，旅客打算九點出發，假設虛線左邊對應的每個節點即為機場，出發時間都小于九點，那么對應向量的每個單鏈表中每個節點中小于九點時刻的節點，都排除了。從而精簡了整個航線網絡。
2.2? 航線時刻表網絡的優化的實現
航線時刻表網絡的簡化過程，第一次進行擴展時，如果是目標節點，則直接將其放入closed表中；如果不是目標節點，則對其進行擴展，擴展過程中判斷對應的邊屬性的起飛時間是否大于旅客的出發時間（第2步），如果符合條件，將其子節點放入open表的末端，并將該擴展的節點從open表移入closed表（第3步）。考慮到當節點的深度為T-1時，其產生的后繼節點的度則為T，這些節點將來不會被擴展，因此，算法沒有將這些存放到open表中，當循環找后繼節點的時候，擴展的時候判斷對應的邊屬性的起飛時間是否大于旅客的出發時間（第6步），如果符合條件，將其子節點放入open表的末端。這樣在降低算法的空間復雜度的同時也降低了算法的時間復雜度。航線時刻表網絡的優化算法的偽代碼如下：
算法：航線時刻表網絡的優化
輸入：旅客出發的時間t
輸出：旅客最優路徑
1? ?將open中第一個節點nd彈出，放入closed中;
2? ?擴展nd，if（edgeIter的出發時間>t）
3? ? ? ?符合條件，將其后繼節點置入open表末端;
4? while（open非空&&節點nd的深度 5? ? 將open中第一個節點nd彈出，放入closed中; 6? ? if（nd的深度< T-1） 擴展nd，if（edgeIter的出發時間>t） 將其后繼節點置入open表末端。 3? 中轉城市的時刻換乘問題 3.1? 中轉城市的時刻換乘問題的內容介紹 目前旅客進行城市的中轉都是按照自己進行選擇，不能有效地實現自動的選擇，本程序中進行了全自動化設置，完全為旅客著想，旅客一般都有自己的時間忍耐程序，不可能中轉一個城市時，上一個航班的降落時間晚于下一航班的起飛時間，或者上一個航班的降落后，下一個航班起飛的時間遠遠大于上一個航班的降落時間，這些完全不符合人們旅客出行的規律。 根據旅客實際的需要和航班現實的延遲現象，程序中規定換乘的時間差大于2小時小于5小時。如果再小于2小時，航班延誤會導致旅客趕不上下一個航班，時間大于5小時，超過了旅客的心理承受。為了便以理解，下面將舉例說明，圖5中轉城市的時刻換乘時間差中即為2小時＜t2 - t1＜5小時。 3.2? 中轉城市的時刻換乘的實現 與上一節的中轉城市的時刻換乘問題的基礎上，再次添加附加條件，定義結構體的時候，邊Edge結構體中有出發時間，到達時間，但Node點中沒有該數據類型，只能將邊的變量成員轉換成點的變量成員，必須實現這一點，否則再下次擴展的時候不能時間的約束，第一個節點進行擴展時，edgeIter的到達時間賦值給新nd的到達時間；edgeIter的出發時間賦值給新nd的出發時間；考慮到當節點的深度為T - 1時，其產生的后繼節點的度則為T，這些節點將來不會被擴展，因此，算法沒有將這些存放到open表中，當循環找后繼節點的時候，擴展的時候判斷對應的邊屬性的起飛時間是否大于旅客的出發時間edgeIter的出發時間與nd的到達時間的差是否相差2至5小時（第2步），如果符合條件，將其子節點放入open表的末端再次重復。中轉城市的時刻換乘的實現偽代碼如下： 算法：中轉城市的時刻換乘的實現 輸入：旅客出發的時間t 輸出：旅客最優路徑 1? 定義 Node變量成員 到達時間，出發時間； 2? 擴展節點，if（edgeIter的出發時間>t&&edgeIter 的出發時間-nd.的到達時間>200&&edgeIter的出發時間-nd.的到達時間<500） 3? 符合條件，將其后繼節點置入open表末端； 4? edgeIter的到達時間賦值給新nd的到達時間； 5? edgeIter的出發時間賦值給新nd的出發時間； 6? 算法終止。 4? 考慮航班的經停問題 4.1? 航班的經停問題的介紹 經停即為旅客乘坐某航班，在城市中停一下旅客中轉的時候，也考慮一些經停的航班，經停的航班，不需要換乘。提供的路徑中，標記給旅客提示下，提供的K條路徑中標記有經停。圖中6航班的經停問題舉例，航班號M1=M2，則標記為經停，從而推薦的路徑中，更符合旅客的要求，給予旅客更好的推薦路徑。 4.2? 航班的經停問題的實現 在輸出出發機場到目的機場的K條最優路徑的時候，每個經停點進行標記，為了方便記憶，經停的航班則設為1，不經停的航班則默認為0；對于循環輸出的中轉的路徑中，每一個中轉機場，對其進行上一個到達該機場的航班號，與下一個由此出發的航班號，進行判斷，航班的經停問題的實現偽代碼如下： 算法：航班的經停問題的實現 輸入：經停的航班號 輸出：航線的經停點 1? if（edgeIter的航班號==nd的航班號）{ 2 ? ? nd的經停點設為1; } 3 else{ 4 ? ? ? ?nd的經停點設為0； } 5? 算法終止。 5? 旅客的偏好航班選擇內容 5.1? 旅客的偏好航班選擇內容介紹 該系統在滿足旅客時間需求的同時，旅客有的對于航班的選擇尤其重視，有人偏好國航，有的偏好東航，每個旅客有每個旅客的愛好。所以，對于系統中突出旅客對于航班的偏好尤其重要，這個系統當中，旅客可以對自己喜愛的航班進行選擇，如果沒有特別的愛好，可以選擇全部的航空公司，選擇完畢后，搜索出的K條路徑滿足旅客的路徑。 在整個過程中，其實不能僅僅看重的是時間，旅客還關注著自己的愛好，喜歡選擇自己的航空公司，這樣呢，通過這個算法，選擇出來的多條路徑，更加符合旅客的偏好。 5.2? 旅客的偏好航班選擇實現 旅客的偏好航班選擇實現，定義結構體的時候，邊Edge結構體中有航班號，但Node點中沒有該數據類型，只能將邊的變量成員轉換成點的變量成員，必須實現這一點，否則再下次擴展的時候不能時間的約束，現在定義一個變量hangban1，hangban1=（edgeIter-的航班號）.substr（0，2）;取航班號的前兩位，即為取到航空公司代碼，第一個節點進行擴展時，edgeIter的航班號賦值給新nd的航班號（第2步）；考慮到當節點的深度為T - 1時，其產生的后繼節點的度則為T，這些節點將來不會被擴展，因此，算法沒有將這些存放到open表中，當循環找后繼節點的時候，擴展的時候判斷航班號的前兩位是否與旅客選擇的航空公司匹配，如果符合條件，將其子節點放入open表的末端再次重復。旅客的偏好航班選擇實現實現偽代碼如下： 輸入：旅客喜愛的航空公司 輸出：旅客最優路徑 1? 定義 Node變量成員 航班號; 2? ?hangban1 = （edgeIter-的航班號）.substr（0，2）; 3? ?if（ hangban1==旅客喜愛的航空公司） 4? 符合條件， 將其后繼節點置入open表末端; 5? ?edgeIter的航班號賦值給新nd的航班號； 6? 以同樣的方式繼續擴展其他的節點。 6? 程序整體實現說明 基于時刻表的聯程路徑搜索與實現，實現了航線網絡的優化，中轉城市的時刻表換乘問題，考慮了航班是否經停還是換乘，進一步添加了旅客的偏好航班的選擇。整個算法的實現，先選擇某GDS出票的所有的旅客數據源，選擇時間最短或者時間最早到達選項，開始輸入出發機場三字碼（比如：PCK），到達機場三字碼，想要得到的K條路徑數，旅客想要出發的時間，喜愛的航空公司（無特殊請輸入ALL），點擊“運行”最后整個程序提供給旅客符合條件的K條路徑。基于時刻表民航聯程路徑系統界面如圖7所示。 7? 結? 論 航線網絡的建立是整個程序的出發點，建立結構體必備點。航線網絡的優化，全球很龐大的機場網絡，如果在搜索之前，能進行簡單的網絡精簡，將建立的鏈式向量表，在單鏈表中進行精簡。考慮到有經停的航班，應該去標記下，起初將該標記的判斷語句，放在了深度優先算法的擴展各節點的過程中。但百密必有一疏，擴展的時候，擴展到目的機場的時候，對于該目的機場的到達航班號無法讀取到。也就是最后一次中轉無法判斷是否經停。鑒于此，又將此判斷語句放于循環輸出路徑的時候，對于path中的每個節點可以進行判斷，最后成功解決。根據所采用的旅客歷史出行記錄為2022年從4月1日到6月1日從某GDS出票的所有的旅客數據，隨機選擇測試集中的某次出行記錄，基于時刻表的旅客乘飛機時間最短的和時間最早到達的聯程路徑搜索算法的準確度匹配性很高。 參考文獻： [1] ZHANG Z A，ZHAO J H. Multi-Constraint-Pruning： an algorithm for Finding K Shortest Paths subject to Multiple Constraints [J/OL].IEICE Proceeding Series，2008，27（2008）：[2023-02-06].https：//www.ieice.org/publications/proceedings/summary.php？iconf=APCC&session_num=15-PM1-C&number=1569125903&year=2008. [2] CLIMACO J C N，CRAVEIRINHA J M F，Pascoal M M B. A bicriterion approach for routing problems in multimedia networks [J].Networks，2003，41（4）：206-220. [3] ERNESTO D Q V M，PASCOAL M M B，SANTOS J L E D. Deviation algorithms for ranking shortest paths [J].The International Journal of Foundations of Computer Science，1999，10（3）：247-263. [4] NING S.K constrained shortest path problem [J].IEEE Transactions on Automation Science and Engineering，2010，1（7）：15-23. [5] 張春輝.基于實時信息的公交乘客出行路徑搜索算法研究 [D].北京：北京交通大學，2012：25-31. [6] YEN J Y. Finding the k shortest loopless paths in a network [J].Management Science，1971，17（11）：712-716. [7] LIU G，RAMAKRISHNAN K G. A*Prune： An Algorithm for Finding K Shortest Paths Subject to Multiple Constraints [C]//Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society （Cat. No.01CH37213），Anchorage：IEEE，2001，2：743-749. [8] QUEIR E，MARTINS V，MARGARIDA M，et al. A new algorithm for ranking loopless paths [EB/OL].[2023-02-03].http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2D92DB49B02F97F944E914EEB1F1534D？doi=10.1.1.46.8238&rep=rep1&type=pdf. [9] HERSHBERGER J，MAXEL M，SUR S. Finding the K shortest simple paths： a new algorithm and its implementation [J/OL].ACM transactions on algorithms，2007，3（4）：[2023-02-03].https：//dl.acm.org/doi/10.1145/1290672.1290682. [10] LI J. An Improved Yen Algorithm based on A* [J].Journal of Computational Information Systems，2012，21（8）：9017-9024. [11] DECHTER R，FLEROVA N，MARINESCU R. Search Algorithms for M Best Solutions for Graphical Models [C]//National Conference on Artificial Intelligence.Toronto：AAAI Press，2012：1895-1901. [12] ALJAZZAR H，LEUE S. K*： A heuristic search algorithm for finding the k shortest paths [J].Artificial Intelligence，2011，175（18）：2129-2154. [13] KOBAYASHI Y，KISHIMOTO A，WATANABE O. Evaluations of Hash Distributed A* in Optimal Sequence Alignment [C]//Proceedings of the Twenty- Second International Joint Conference on Artificial Intelligence，Barcelona：[s.n.]，2011：584-590. [14] LI J F，LI T J. Research on Fast KCSP Algorithms for Searching Connecting Paths in Airline Networks [J].Applied Mechanics & Materials，2014，505-506：1005-1013. [15] 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. [16] 李鐵軍.基于時刻表的旅客出行路徑推薦算法研究 [D].天津：中國民航大學，2015：30-35. 作者簡介：王國良（1990.08—），男，漢族，河北衡水人，高級工程師，學士學位，研究方向：民航大數據；紀曉婧（1989.04—），女，漢族，山東煙臺人，工程師，學士學位，研究方向：大數據、網絡運維。
