基于時(shí)刻表的民航聯(lián)程路徑算法設(shè)計(jì)實(shí)現(xiàn)

王國(guó)良 紀(jì)曉婧

摘? 要：最近幾年，全球民航業(yè)飛速發(fā)展，航線網(wǎng)絡(luò)變得日益復(fù)雜與龐大；與此同時(shí)，隨著生活節(jié)奏的加快，人們的時(shí)間觀念也越來(lái)越強(qiáng)。因此，在設(shè)計(jì)聯(lián)程搜索算法時(shí)，尤其要考慮時(shí)刻表的重要性，這樣才能夠滿足旅客的時(shí)間要求，才能體現(xiàn)基于時(shí)刻表的聯(lián)程搜索算法的重要意義?；诖耍岢隽艘环N基于時(shí)刻表的策略以優(yōu)化現(xiàn)有的聯(lián)程路徑推薦算法。該策略首先根據(jù)航班時(shí)刻表信息構(gòu)建航線網(wǎng)絡(luò)，其次根據(jù)旅客的出行時(shí)間要求對(duì)航線網(wǎng)絡(luò)進(jìn)行精簡(jiǎn)，最后在修整的網(wǎng)絡(luò)中運(yùn)行聯(lián)程路徑推薦算法并計(jì)算出可能滿足旅客需求的多條路徑。

關(guān)鍵詞：時(shí)刻表；航線網(wǎng)絡(luò)；聯(lián)程路徑

中圖分類(lèi)號(hào)：TP391? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

隨著全球航空業(yè)的飛速發(fā)展，國(guó)際航線網(wǎng)絡(luò)的規(guī)模變得日益龐大，在相同起飛降落城市之間有很多航線可供旅客出行選擇。旅客對(duì)旅行服務(wù)質(zhì)量的要求也越來(lái)越高，旅客不僅想知道他們是如何到達(dá)目的地的，更希望選擇一條或幾條最適合他們的出行路徑。

鑒于目前國(guó)內(nèi)對(duì)基于時(shí)刻表路徑推薦算法研究較少的情況下，本文利用航班時(shí)刻表建立時(shí)間擴(kuò)展網(wǎng)絡(luò)模型，并且考慮了旅客的多標(biāo)準(zhǔn)（如；全程耗時(shí)最短，中轉(zhuǎn)次數(shù)最少，在某一時(shí)間段內(nèi)出行）出行方案，在此基礎(chǔ)上為旅客提供最優(yōu)的K條時(shí)間最短路徑的推薦算法。

該策略首先是旅客根據(jù)自己的需求，決定自己的出行時(shí)間、偏好的航空公司，可以精確到分鐘，接著根據(jù)旅客提供的自己的出行時(shí)間和出發(fā)的城市，然后匹配符合旅客要求條件的航線，依據(jù)有界的深度優(yōu)先算法為旅客推薦出可能滿足旅客需求的多條路徑，由于對(duì)旅客出行的時(shí)間基礎(chǔ)上完成，所以這個(gè)策略從理論上不會(huì)改變?cè)械穆?lián)程路徑搜索算法的復(fù)雜度。

1? 航線網(wǎng)絡(luò)的建立

1.1? 航線網(wǎng)絡(luò)思想

在網(wǎng)絡(luò)中，任意兩個(gè)相連接的節(jié)點(diǎn)表示在這兩個(gè)節(jié)點(diǎn)間有一條相通的路線。通過(guò)用這樣的幾條路線將OD點(diǎn)連接起來(lái)，就形成了一條從源點(diǎn)O到終點(diǎn)D的一條可行路徑。圖1為經(jīng)典的航線網(wǎng)絡(luò)有向圖模型，其中各個(gè)節(jié)點(diǎn)用數(shù)字1，2，3，4，5表示，任意兩個(gè)相連接的節(jié)點(diǎn)用一條有向弧相連，弧上的權(quán)值代表兩個(gè)節(jié)點(diǎn)直接的距離或者是單向的運(yùn)行時(shí)間。從該圖可以看出，從節(jié)點(diǎn)1到節(jié)點(diǎn)3有兩條路線l1，l2，如圖2節(jié)點(diǎn)1到3路線圖所示。

這種網(wǎng)絡(luò)模型在處理中簡(jiǎn)單，但其有明顯的缺陷：每條連線的屬性僅代表相互連接節(jié)點(diǎn)之間的距離或者通過(guò)兩個(gè)節(jié)點(diǎn)所用的時(shí)間。不能反映由于交通工具的不同，那么對(duì)應(yīng)的屬性值也會(huì)隨之變化；各種交通工具在交通運(yùn)輸中所用的時(shí)間和其時(shí)刻表不能很好地展現(xiàn)出來(lái)；這樣位旅客推薦的路線比較單一，如圖2所示，旅客如果不喜歡線路1，那么他只能選擇線路2，但是在實(shí)際的路線中，由于每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著不同交通工具的時(shí)刻表，同一條路線可以對(duì)應(yīng)著不同的時(shí)間路徑。

1.2? 航線網(wǎng)絡(luò)模型的建立

航線網(wǎng)絡(luò)即建立一個(gè)有向圖，圖中的每一個(gè)節(jié)點(diǎn)代表每一個(gè)機(jī)場(chǎng)，邊代表機(jī)場(chǎng)之間的航線，邊的長(zhǎng)度代表距離。結(jié)構(gòu)體節(jié)點(diǎn)中定義變量，ID號(hào)，名字，定義了出發(fā)時(shí)間，到達(dá)時(shí)間，航班號(hào)以及標(biāo)記是否經(jīng)停的變量；而邊的結(jié)構(gòu)體中，存儲(chǔ)了到達(dá)節(jié)點(diǎn)，出發(fā)機(jī)場(chǎng)和到達(dá)機(jī)場(chǎng)的經(jīng)緯度，起飛時(shí)間，到達(dá)時(shí)間，以及航班號(hào)。

本文定義了一個(gè)向量鏈?zhǔn)奖?，即為vector>，先建立一個(gè)向量表，向量表中存放著所有全球3 700多個(gè)機(jī)場(chǎng)，向量表中對(duì)應(yīng)的每一個(gè)機(jī)場(chǎng)建立對(duì)應(yīng)的單鏈表，每個(gè)單鏈表中鏈接的是與該機(jī)場(chǎng)相連接的機(jī)場(chǎng)，并且單鏈表中的機(jī)場(chǎng)中的屬性，包括里面上一個(gè)機(jī)場(chǎng)的起飛時(shí)間，到達(dá)該機(jī)場(chǎng)的降落時(shí)間，以及到達(dá)該機(jī)場(chǎng)的航班號(hào)。通過(guò)push_back（）這個(gè)函數(shù)在list鏈表的末尾添加一個(gè)新元素，循環(huán)添加。最后形成一個(gè)向量鏈?zhǔn)奖?，航線網(wǎng)絡(luò)圖的建立如圖3所示。

2? 航線時(shí)刻表網(wǎng)絡(luò)的簡(jiǎn)化

2.1? 航線時(shí)刻表網(wǎng)絡(luò)的優(yōu)化

由于航線網(wǎng)絡(luò)規(guī)模龐大、航班密集，所以對(duì)于圖1建立的航線網(wǎng)絡(luò)圖是一個(gè)很龐大的圖，對(duì)圖的讀取會(huì)耗費(fèi)一大部分的時(shí)間。針對(duì)此問(wèn)題，在對(duì)航線網(wǎng)絡(luò)進(jìn)行搜索之前首先對(duì)航線的時(shí)刻表網(wǎng)絡(luò)進(jìn)行了優(yōu)化。優(yōu)化策略即根據(jù)旅客輸入的對(duì)航空公司的偏好，對(duì)出發(fā)時(shí)間、到達(dá)時(shí)間的要求刪減網(wǎng)絡(luò)中不滿足要求的節(jié)點(diǎn)和邊。

利用旅客出行時(shí)間來(lái)優(yōu)化一部分的圖，旅客根據(jù)自己的出行時(shí)間輸入自己的出發(fā)時(shí)間，程序中建立的向量鏈?zhǔn)奖?，?duì)應(yīng)的每個(gè)鏈表中，進(jìn)行時(shí)間的刷選，對(duì)每個(gè)小于旅客出行時(shí)間的每個(gè)鏈表的每個(gè)節(jié)點(diǎn)進(jìn)行簡(jiǎn)化。從而進(jìn)行了整體上網(wǎng)絡(luò)的優(yōu)化。例如，圖4航線網(wǎng)絡(luò)的優(yōu)化中，旅客打算九點(diǎn)出發(fā)，假設(shè)虛線左邊對(duì)應(yīng)的每個(gè)節(jié)點(diǎn)即為機(jī)場(chǎng)，出發(fā)時(shí)間都小于九點(diǎn)，那么對(duì)應(yīng)向量的每個(gè)單鏈表中每個(gè)節(jié)點(diǎn)中小于九點(diǎn)時(shí)刻的節(jié)點(diǎn)，都排除了。從而精簡(jiǎn)了整個(gè)航線網(wǎng)絡(luò)。

2.2? 航線時(shí)刻表網(wǎng)絡(luò)的優(yōu)化的實(shí)現(xiàn)

航線時(shí)刻表網(wǎng)絡(luò)的簡(jiǎn)化過(guò)程，第一次進(jìn)行擴(kuò)展時(shí)，如果是目標(biāo)節(jié)點(diǎn)，則直接將其放入closed表中；如果不是目標(biāo)節(jié)點(diǎn)，則對(duì)其進(jìn)行擴(kuò)展，擴(kuò)展過(guò)程中判斷對(duì)應(yīng)的邊屬性的起飛時(shí)間是否大于旅客的出發(fā)時(shí)間（第2步），如果符合條件，將其子節(jié)點(diǎn)放入open表的末端，并將該擴(kuò)展的節(jié)點(diǎn)從open表移入closed表（第3步）?？紤]到當(dāng)節(jié)點(diǎn)的深度為T(mén)-1時(shí)，其產(chǎn)生的后繼節(jié)點(diǎn)的度則為T(mén)，這些節(jié)點(diǎn)將來(lái)不會(huì)被擴(kuò)展，因此，算法沒(méi)有將這些存放到open表中，當(dāng)循環(huán)找后繼節(jié)點(diǎn)的時(shí)候，擴(kuò)展的時(shí)候判斷對(duì)應(yīng)的邊屬性的起飛時(shí)間是否大于旅客的出發(fā)時(shí)間（第6步），如果符合條件，將其子節(jié)點(diǎn)放入open表的末端。這樣在降低算法的空間復(fù)雜度的同時(shí)也降低了算法的時(shí)間復(fù)雜度。航線時(shí)刻表網(wǎng)絡(luò)的優(yōu)化算法的偽代碼如下：

算法：航線時(shí)刻表網(wǎng)絡(luò)的優(yōu)化

輸入：旅客出發(fā)的時(shí)間t

輸出：旅客最優(yōu)路徑

1? ?將open中第一個(gè)節(jié)點(diǎn)nd彈出，放入closed中;

2? ?擴(kuò)展nd，if（edgeIter的出發(fā)時(shí)間>t）

3? ? ? ?符合條件，將其后繼節(jié)點(diǎn)置入open表末端;

4? while（open非空&&節(jié)點(diǎn)nd的深度

5? ? 將open中第一個(gè)節(jié)點(diǎn)nd彈出，放入closed中;

6? ? if（nd的深度< T-1）

擴(kuò)展nd，if（edgeIter的出發(fā)時(shí)間>t）

將其后繼節(jié)點(diǎn)置入open表末端。

3? 中轉(zhuǎn)城市的時(shí)刻換乘問(wèn)題

3.1? 中轉(zhuǎn)城市的時(shí)刻換乘問(wèn)題的內(nèi)容介紹

目前旅客進(jìn)行城市的中轉(zhuǎn)都是按照自己進(jìn)行選擇，不能有效地實(shí)現(xiàn)自動(dòng)的選擇，本程序中進(jìn)行了全自動(dòng)化設(shè)置，完全為旅客著想，旅客一般都有自己的時(shí)間忍耐程序，不可能中轉(zhuǎn)一個(gè)城市時(shí)，上一個(gè)航班的降落時(shí)間晚于下一航班的起飛時(shí)間，或者上一個(gè)航班的降落后，下一個(gè)航班起飛的時(shí)間遠(yuǎn)遠(yuǎn)大于上一個(gè)航班的降落時(shí)間，這些完全不符合人們旅客出行的規(guī)律。

根據(jù)旅客實(shí)際的需要和航班現(xiàn)實(shí)的延遲現(xiàn)象，程序中規(guī)定換乘的時(shí)間差大于2小時(shí)小于5小時(shí)。如果再小于2小時(shí)，航班延誤會(huì)導(dǎo)致旅客趕不上下一個(gè)航班，時(shí)間大于5小時(shí)，超過(guò)了旅客的心理承受。為了便以理解，下面將舉例說(shuō)明，圖5中轉(zhuǎn)城市的時(shí)刻換乘時(shí)間差中即為2小時(shí)＜t2 - t1＜5小時(shí)。

3.2? 中轉(zhuǎn)城市的時(shí)刻換乘的實(shí)現(xiàn)

與上一節(jié)的中轉(zhuǎn)城市的時(shí)刻換乘問(wèn)題的基礎(chǔ)上，再次添加附加條件，定義結(jié)構(gòu)體的時(shí)候，邊Edge結(jié)構(gòu)體中有出發(fā)時(shí)間，到達(dá)時(shí)間，但Node點(diǎn)中沒(méi)有該數(shù)據(jù)類(lèi)型，只能將邊的變量成員轉(zhuǎn)換成點(diǎn)的變量成員，必須實(shí)現(xiàn)這一點(diǎn)，否則再下次擴(kuò)展的時(shí)候不能時(shí)間的約束，第一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，edgeIter的到達(dá)時(shí)間賦值給新nd的到達(dá)時(shí)間；edgeIter的出發(fā)時(shí)間賦值給新nd的出發(fā)時(shí)間；考慮到當(dāng)節(jié)點(diǎn)的深度為T(mén) - 1時(shí)，其產(chǎn)生的后繼節(jié)點(diǎn)的度則為T(mén)，這些節(jié)點(diǎn)將來(lái)不會(huì)被擴(kuò)展，因此，算法沒(méi)有將這些存放到open表中，當(dāng)循環(huán)找后繼節(jié)點(diǎn)的時(shí)候，擴(kuò)展的時(shí)候判斷對(duì)應(yīng)的邊屬性的起飛時(shí)間是否大于旅客的出發(fā)時(shí)間edgeIter的出發(fā)時(shí)間與nd的到達(dá)時(shí)間的差是否相差2至5小時(shí)（第2步），如果符合條件，將其子節(jié)點(diǎn)放入open表的末端再次重復(fù)。中轉(zhuǎn)城市的時(shí)刻換乘的實(shí)現(xiàn)偽代碼如下：

算法：中轉(zhuǎn)城市的時(shí)刻換乘的實(shí)現(xiàn)

輸入：旅客出發(fā)的時(shí)間t

輸出：旅客最優(yōu)路徑

1? 定義 Node變量成員 到達(dá)時(shí)間，出發(fā)時(shí)間；

2? 擴(kuò)展節(jié)點(diǎn)，if（edgeIter的出發(fā)時(shí)間>t&&edgeIter

的出發(fā)時(shí)間-nd.的到達(dá)時(shí)間>200&&edgeIter的出發(fā)時(shí)間-nd.的到達(dá)時(shí)間<500）

3? 符合條件，將其后繼節(jié)點(diǎn)置入open表末端；

4? edgeIter的到達(dá)時(shí)間賦值給新nd的到達(dá)時(shí)間；

5? edgeIter的出發(fā)時(shí)間賦值給新nd的出發(fā)時(shí)間；

6? 算法終止。

4? 考慮航班的經(jīng)停問(wèn)題

4.1? 航班的經(jīng)停問(wèn)題的介紹

經(jīng)停即為旅客乘坐某航班，在城市中停一下旅客中轉(zhuǎn)的時(shí)候，也考慮一些經(jīng)停的航班，經(jīng)停的航班，不需要換乘。提供的路徑中，標(biāo)記給旅客提示下，提供的K條路徑中標(biāo)記有經(jīng)停。圖中6航班的經(jīng)停問(wèn)題舉例，航班號(hào)M1=M2，則標(biāo)記為經(jīng)停，從而推薦的路徑中，更符合旅客的要求，給予旅客更好的推薦路徑。

4.2? 航班的經(jīng)停問(wèn)題的實(shí)現(xiàn)

在輸出出發(fā)機(jī)場(chǎng)到目的機(jī)場(chǎng)的K條最優(yōu)路徑的時(shí)候，每個(gè)經(jīng)停點(diǎn)進(jìn)行標(biāo)記，為了方便記憶，經(jīng)停的航班則設(shè)為1，不經(jīng)停的航班則默認(rèn)為0；對(duì)于循環(huán)輸出的中轉(zhuǎn)的路徑中，每一個(gè)中轉(zhuǎn)機(jī)場(chǎng)，對(duì)其進(jìn)行上一個(gè)到達(dá)該機(jī)場(chǎng)的航班號(hào)，與下一個(gè)由此出發(fā)的航班號(hào)，進(jìn)行判斷，航班的經(jīng)停問(wèn)題的實(shí)現(xiàn)偽代碼如下：

算法：航班的經(jīng)停問(wèn)題的實(shí)現(xiàn)

輸入：經(jīng)停的航班號(hào)

輸出：航線的經(jīng)停點(diǎn)

1? if（edgeIter的航班號(hào)==nd的航班號(hào)）{

2 ? ? nd的經(jīng)停點(diǎn)設(shè)為1; }

3 else{

4 ? ? ? ?nd的經(jīng)停點(diǎn)設(shè)為0； }

5? 算法終止。

5? 旅客的偏好航班選擇內(nèi)容

5.1? 旅客的偏好航班選擇內(nèi)容介紹

該系統(tǒng)在滿足旅客時(shí)間需求的同時(shí)，旅客有的對(duì)于航班的選擇尤其重視，有人偏好國(guó)航，有的偏好東航，每個(gè)旅客有每個(gè)旅客的愛(ài)好。所以，對(duì)于系統(tǒng)中突出旅客對(duì)于航班的偏好尤其重要，這個(gè)系統(tǒng)當(dāng)中，旅客可以對(duì)自己喜愛(ài)的航班進(jìn)行選擇，如果沒(méi)有特別的愛(ài)好，可以選擇全部的航空公司，選擇完畢后，搜索出的K條路徑滿足旅客的路徑。

在整個(gè)過(guò)程中，其實(shí)不能僅僅看重的是時(shí)間，旅客還關(guān)注著自己的愛(ài)好，喜歡選擇自己的航空公司，這樣呢，通過(guò)這個(gè)算法，選擇出來(lái)的多條路徑，更加符合旅客的偏好。

5.2? 旅客的偏好航班選擇實(shí)現(xiàn)

旅客的偏好航班選擇實(shí)現(xiàn)，定義結(jié)構(gòu)體的時(shí)候，邊Edge結(jié)構(gòu)體中有航班號(hào)，但Node點(diǎn)中沒(méi)有該數(shù)據(jù)類(lèi)型，只能將邊的變量成員轉(zhuǎn)換成點(diǎn)的變量成員，必須實(shí)現(xiàn)這一點(diǎn)，否則再下次擴(kuò)展的時(shí)候不能時(shí)間的約束，現(xiàn)在定義一個(gè)變量hangban1，hangban1=（edgeIter-的航班號(hào)）.substr（0，2）;取航班號(hào)的前兩位，即為取到航空公司代碼，第一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，edgeIter的航班號(hào)賦值給新nd的航班號(hào)（第2步）；考慮到當(dāng)節(jié)點(diǎn)的深度為T(mén) - 1時(shí)，其產(chǎn)生的后繼節(jié)點(diǎn)的度則為T(mén)，這些節(jié)點(diǎn)將來(lái)不會(huì)被擴(kuò)展，因此，算法沒(méi)有將這些存放到open表中，當(dāng)循環(huán)找后繼節(jié)點(diǎn)的時(shí)候，擴(kuò)展的時(shí)候判斷航班號(hào)的前兩位是否與旅客選擇的航空公司匹配，如果符合條件，將其子節(jié)點(diǎn)放入open表的末端再次重復(fù)。旅客的偏好航班選擇實(shí)現(xiàn)實(shí)現(xiàn)偽代碼如下：

輸入：旅客喜愛(ài)的航空公司

輸出：旅客最優(yōu)路徑

1? 定義 Node變量成員 航班號(hào);

2? ?hangban1 = （edgeIter-的航班號(hào)）.substr（0，2）;

3? ?if（ hangban1==旅客喜愛(ài)的航空公司）

4? 符合條件， 將其后繼節(jié)點(diǎn)置入open表末端;

5? ?edgeIter的航班號(hào)賦值給新nd的航班號(hào)；

6? 以同樣的方式繼續(xù)擴(kuò)展其他的節(jié)點(diǎn)。

6? 程序整體實(shí)現(xiàn)說(shuō)明

基于時(shí)刻表的聯(lián)程路徑搜索與實(shí)現(xiàn)，實(shí)現(xiàn)了航線網(wǎng)絡(luò)的優(yōu)化，中轉(zhuǎn)城市的時(shí)刻表?yè)Q乘問(wèn)題，考慮了航班是否經(jīng)停還是換乘，進(jìn)一步添加了旅客的偏好航班的選擇。整個(gè)算法的實(shí)現(xiàn)，先選擇某GDS出票的所有的旅客數(shù)據(jù)源，選擇時(shí)間最短或者時(shí)間最早到達(dá)選項(xiàng)，開(kāi)始輸入出發(fā)機(jī)場(chǎng)三字碼（比如：PCK），到達(dá)機(jī)場(chǎng)三字碼，想要得到的K條路徑數(shù)，旅客想要出發(fā)的時(shí)間，喜愛(ài)的航空公司（無(wú)特殊請(qǐng)輸入ALL），點(diǎn)擊“運(yùn)行”最后整個(gè)程序提供給旅客符合條件的K條路徑?；跁r(shí)刻表民航聯(lián)程路徑系統(tǒng)界面如圖7所示。

7? 結(jié)? 論

航線網(wǎng)絡(luò)的建立是整個(gè)程序的出發(fā)點(diǎn)，建立結(jié)構(gòu)體必備點(diǎn)。航線網(wǎng)絡(luò)的優(yōu)化，全球很龐大的機(jī)場(chǎng)網(wǎng)絡(luò)，如果在搜索之前，能進(jìn)行簡(jiǎn)單的網(wǎng)絡(luò)精簡(jiǎn)，將建立的鏈?zhǔn)较蛄勘?，在單鏈表中進(jìn)行精簡(jiǎn)?？紤]到有經(jīng)停的航班，應(yīng)該去標(biāo)記下，起初將該標(biāo)記的判斷語(yǔ)句，放在了深度優(yōu)先算法的擴(kuò)展各節(jié)點(diǎn)的過(guò)程中。但百密必有一疏，擴(kuò)展的時(shí)候，擴(kuò)展到目的機(jī)場(chǎng)的時(shí)候，對(duì)于該目的機(jī)場(chǎng)的到達(dá)航班號(hào)無(wú)法讀取到。也就是最后一次中轉(zhuǎn)無(wú)法判斷是否經(jīng)停。鑒于此，又將此判斷語(yǔ)句放于循環(huán)輸出路徑的時(shí)候，對(duì)于path中的每個(gè)節(jié)點(diǎn)可以進(jìn)行判斷，最后成功解決。根據(jù)所采用的旅客歷史出行記錄為2022年從4月1日到6月1日從某GDS出票的所有的旅客數(shù)據(jù)，隨機(jī)選擇測(cè)試集中的某次出行記錄，基于時(shí)刻表的旅客乘飛機(jī)時(shí)間最短的和時(shí)間最早到達(dá)的聯(lián)程路徑搜索算法的準(zhǔn)確度匹配性很高。

參考文獻(xiàn)：

[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] 張春輝.基于實(shí)時(shí)信息的公交乘客出行路徑搜索算法研究 [D].北京：北京交通大學(xué)，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，F(xiàn)LEROVA 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] 李鐵軍.基于時(shí)刻表的旅客出行路徑推薦算法研究 [D].天津：中國(guó)民航大學(xué)，2015：30-35.

作者簡(jiǎn)介：王國(guó)良（1990.08—），男，漢族，河北衡水人，高級(jí)工程師，學(xué)士學(xué)位，研究方向：民航大數(shù)據(jù)；紀(jì)曉婧（1989.04—），女，漢族，山東煙臺(tái)人，工程師，學(xué)士學(xué)位，研究方向：大數(shù)據(jù)、網(wǎng)絡(luò)運(yùn)維。