朱家彬，楊永凱，劉 軍

（1.中國民航信息網(wǎng)絡(luò)股份有限公司研發(fā)中心，北京 101318；2.民航旅客服務(wù)智能化應(yīng)用技術(shù)重點實驗室，北京 101318）

中國航信（TravelSky）是國內(nèi)唯一一家民航計算機(jī)訂座系統(tǒng)（CRS，computer reservation system）運營商，在其自主研發(fā)的早期版本的行程計算系統(tǒng)中，作為核心的聯(lián)程航班構(gòu)建模塊是采用基于航線網(wǎng)絡(luò)圖的單向搜索方法實現(xiàn)的。當(dāng)市場上航班數(shù)量較少時，該方法基本可以保證行程查詢的效率和可用性。但是隨著全球民航市場的高速發(fā)展，航空公司和商營航班數(shù)量急劇增長，這種基于航線網(wǎng)絡(luò)圖單向搜索的聯(lián)程航班構(gòu)建方法已經(jīng)逐漸不能滿足旅客和分銷商的行程查詢需求，其不足主要體現(xiàn)在兩個方面。

（1）對于單向搜索算法，無論是單向的K 短路徑搜索算法還是寬度（深度）優(yōu)先搜索算法，擴(kuò)展兩次后結(jié)果會以指數(shù)級發(fā)散，搜索效率相對較低。因此，當(dāng)航線網(wǎng)絡(luò)圖節(jié)點數(shù)量大量增加，或出發(fā)地—目的地（OD，origin-destination）間涉及多次中轉(zhuǎn)的情況時，系統(tǒng)性能較低、響應(yīng)時間較長、用戶體驗度較差。

（2）為了平衡單向搜索算法的性能問題，減少計算量，使用了由直達(dá)航線構(gòu)造的航線網(wǎng)絡(luò)圖進(jìn)行搜索計算。在航線網(wǎng)絡(luò)圖中，兩點之間的連線最多有1 條，表示這兩點間存在直達(dá)航線，計算時先搜索出中轉(zhuǎn)路徑，然后再基于路徑構(gòu)建聯(lián)程航班。航線網(wǎng)絡(luò)圖雖然可以壓縮圖的搜索空間，但由于在搜索路徑時沒有利用航班的具體信息，無法有效應(yīng)用航班屬性對找到的中轉(zhuǎn)路徑進(jìn)行可用性評估，會降低聯(lián)程航班結(jié)果的可用性。

為了解決上述問題，中國航信在對行程計算系統(tǒng)進(jìn)行改造的實踐中，設(shè)計了一種多因素雙向搜索方法，通過將航線網(wǎng)絡(luò)圖升級為航班網(wǎng)絡(luò)圖，引入航班信息、艙位狀態(tài)信息、運價信息等數(shù)據(jù)構(gòu)建多因素約束，并采用雙向搜索算法加速聯(lián)程航班構(gòu)建，從而達(dá)到了高性能和聯(lián)程航班結(jié)果高可用性的系統(tǒng)目標(biāo)[1]。

1 系統(tǒng)設(shè)計

1.1 總體設(shè)計

旅客通過傳統(tǒng)代理人、航空公司官網(wǎng)、在線代理人（OTA，online travel agent）及全球分銷系統(tǒng)（GDS，global distribution system）等渠道訪問行程計算系統(tǒng)，如圖1所示。

圖1 外部交互關(guān)系Fig.1 External interactions

行程計算系統(tǒng)的總體結(jié)構(gòu)包括兩部分，即航班查詢服務(wù)和數(shù)據(jù)更新服務(wù)，如圖2所示。

圖2 總體設(shè)計Fig.2 Overall design

航班查詢服務(wù)主要為行程的搜索提供查詢服務(wù)，當(dāng)有用戶查詢行程時，航班查詢服務(wù)器首先解析用戶的輸入請求，并根據(jù)用戶輸入的O-D 信息、時刻信息等進(jìn)行行程的搜索計算，并將符合用戶查詢條件的行程結(jié)果集合返回給查詢用戶；數(shù)據(jù)更新服務(wù)作為與其他系統(tǒng)交互的接口，主要為行程的生成提供基礎(chǔ)數(shù)據(jù)更新服務(wù)，包括：從航班控制系統(tǒng)（FLT，flight system）接收直飛航班的信息更新，從航班庫存系統(tǒng)（INV，inventory system）接收艙位可利用的狀態(tài)更新，及從運價計算系統(tǒng)（PRIC，pricing system）接收里程制運價的相關(guān)信息。

行程計算系統(tǒng)的總體計算流程主要包括以下4個步驟。

步驟1數(shù)據(jù)預(yù)處理。為提高行程計算過程中聯(lián)程航班的構(gòu)建效率，首先進(jìn)行數(shù)據(jù)預(yù)處理，根據(jù)全市場（或特定市場）的商營直飛航班信息構(gòu)建航班網(wǎng)絡(luò)圖。

步驟2請求輸入。用戶輸入自己的行程需求，包括出發(fā)城市（機(jī)場）、目的城市（機(jī)場）、出發(fā)日期等必選項，同時也可以輸入偏好條件，包括喜好或厭惡的航空公司、喜好或厭惡的中轉(zhuǎn)機(jī)場、最晚起飛時間、中轉(zhuǎn)次數(shù)、轉(zhuǎn)機(jī)時間等?？蛻舳烁鶕?jù)用戶輸入的選項，生成用戶行程請求參數(shù)，并發(fā)送給航班查詢服務(wù)器。

步驟3行程搜索。根據(jù)用戶輸入的請求信息，構(gòu)建多因素約束，應(yīng)用雙向搜索算法進(jìn)行行程搜索計算。

步驟4結(jié)果篩選。對搜索到的行程集合再次進(jìn)行綜合打分，將滿足用戶需求的較優(yōu)結(jié)果返回給用戶。

1.2 航班網(wǎng)絡(luò)圖

航班網(wǎng)絡(luò)圖不同于航線網(wǎng)絡(luò)圖，是基于直達(dá)航班進(jìn)行構(gòu)建的。通過遍歷直達(dá)航班信息，根據(jù)直達(dá)航班的起飛機(jī)場、起飛城市、到達(dá)機(jī)場和到達(dá)城市構(gòu)建航班網(wǎng)絡(luò)圖。航班網(wǎng)絡(luò)圖中的每條邊表示1 個直達(dá)航班，邊與邊之間的連接點表示機(jī)場。如果兩點之間存在1個直達(dá)航班，則在兩點之間增加1 條邊，如果兩點之間存在多個直達(dá)航班則會存在多條邊，如圖3所示。

圖3 航班網(wǎng)絡(luò)圖Fig.3 Flight network map

航班網(wǎng)絡(luò)圖是多因素雙向搜索的基礎(chǔ)。由于航班網(wǎng)絡(luò)圖比較龐大，為了保證行程搜索的高效，可以應(yīng)用鄰接矩陣的方式存儲航班網(wǎng)絡(luò)圖，同時對航班屬性信息進(jìn)行壓縮存儲[2-4]。

1.3 多因素雙向搜索方法

在行程搜索環(huán)節(jié)，主要應(yīng)用的搜索算法是雙向?qū)挾葍?yōu)先搜索算法。該算法首先解決了單向搜索算法搜索效率低的問題，同時，在搜索中應(yīng)用多因素約束的綜合排序打分策略也可以大大提升結(jié)果的可用性。

給定航班網(wǎng)絡(luò)圖G、出發(fā)地O 和目的地D，請求返回的行程數(shù)量為N。整個搜索方法的流程如圖4所示。

圖4 多因素雙向搜索方法流程圖Fig.4 The flowchart of multi-factor bidirectional search

該方法的主要步驟可以概括如下。

1）擴(kuò)展

根據(jù)用戶輸入的出發(fā)地O 和目的地D 從航班網(wǎng)絡(luò)圖的兩端進(jìn)行擴(kuò)展，即分別以出發(fā)地和目的地為初始節(jié)點在航班網(wǎng)絡(luò)圖上進(jìn)行邊的搜索，找到以出發(fā)地為初始節(jié)點的所有航班經(jīng)過的路徑集合Li，以及以目的地為初始節(jié)點的所有航班經(jīng)過的路徑集合Ri，Li和Ri中存儲歷史路徑的航班信息和機(jī)場信息。逐級擴(kuò)展后將會得到分別以出發(fā)地和目的地為初始節(jié)點的兩個行程集合L={Li}和R={Ri}。

2）剪枝

所謂剪枝即刪除行程集合L 和R 中較差的行程點，目的是減少不必要的擴(kuò)展，從而提高搜索效率，剪枝后生成行程集合L′和R′。剪枝時需要刪除不合理的中轉(zhuǎn)點，減少下次擴(kuò)展時的搜索空間。剪枝過程要盡量避免降低結(jié)果的豐富度。剪枝過程發(fā)生在每次擴(kuò)展后，需要對兩個方向生成的行程分別進(jìn)行剪枝，如果一個方向生成的行程已經(jīng)很差則可以刪除。剪枝過程即多因素約束過程，實踐中可考慮下列幾個因素。

（a）距離

當(dāng)擴(kuò)展點的里程超過里程制運價中關(guān)于中轉(zhuǎn)里程的限制時則刪除該點。為了得到更優(yōu)的行程結(jié)果，對于里程的限制也可以借鑒經(jīng)驗數(shù)據(jù)，例如可以通過限制繞飛率對中轉(zhuǎn)里程進(jìn)行限制，實踐中繞飛率一般不超過2.5。

（b）中轉(zhuǎn)次數(shù)

主要對行程超過一定中轉(zhuǎn)次數(shù)的點進(jìn)行刪減。中轉(zhuǎn)次數(shù)的限制可以根據(jù)經(jīng)驗數(shù)據(jù)進(jìn)行設(shè)置，例如一個完整行程的中轉(zhuǎn)次數(shù)一般不會超過5 次。如果兩地之間存在直飛航班，則多次中轉(zhuǎn)的聯(lián)程航班權(quán)重較低。

（c）時間

中轉(zhuǎn)機(jī)場的最短銜接時間（MCT，minimum connecting time）限制，低于該時長將無法在相應(yīng)機(jī)場實現(xiàn)中轉(zhuǎn)。另外也可以對旅行總時間設(shè)置限制要求。

（d）運價規(guī)則

在里程制運價規(guī)則中對旅行方向進(jìn)行了規(guī)定，只有滿足旅行方向的擴(kuò)展點才被保留。另外運價規(guī)則還對航班的屬性進(jìn)行了限制，例如可以限制整個行程的航班不允許存在航班經(jīng)停。

（e）其他

包括航空聯(lián)盟限制等，不再贅述。

3）交集

將兩個方向的行程集合L′和R′的擴(kuò)展點取交集，如果存在交集則可以組成完整的行程P={Pi}（Pi存儲了完整的行程路徑信息）。

4）檢查

對已經(jīng)得到的行程P 進(jìn)行檢查，檢查的目的是對完整行程進(jìn)行可用性的再度評估及取舍，保證結(jié)果集合的多樣性和便捷性，同時關(guān)注價格，檢查后生成行程集合P′。首先可以根據(jù)需要保留極端最優(yōu)行程，如價格最低、旅行時間最短、所有直飛航班等；其次對所有行程進(jìn)行綜合打分，計算行程的分值并按照分值由高到低存儲，刪除綜合打分低的行程。典型的打分項包括：對艙位可利用狀態(tài)打分（CAV Score，cabin availability score）、對行程的總旅行時間打分（TFT Score，total flight time score）、對行程的中轉(zhuǎn)次數(shù)打分（Connection Score）、對行程中航空公司之間的關(guān)系打分（Alliance Score）等，匯總后獲得總分值。

5）判斷是否需要進(jìn)一步擴(kuò)展

如果已經(jīng)搜索到的行程數(shù)量還沒有達(dá)到返回結(jié)果的數(shù)量限制，即|P′|

1.4 方法模型

多因素雙向搜索方法描述可以簡化為如下數(shù)學(xué)模型。

航班網(wǎng)絡(luò)圖抽象為有向圖G=，其中：V={v1，v2，…，vn}為節(jié)點集，n 為網(wǎng)絡(luò)圖中節(jié)點的個數(shù)；E={e1，e2，…，em}為邊集，m 為網(wǎng)絡(luò)圖中邊的條數(shù)。

正向搜索：指定O=v1為搜索起點，寬度遍歷其作為出度點的邊，然后再以得到的邊集查找對應(yīng)的入度點，這樣就得到路徑集L1={v1e1v2，v1e2v2，v1e3v3，…}，然后以路徑集中各路徑終點為起點重復(fù)以上步驟，并在查找過程中刪除有重復(fù)點的路徑，得到路徑集L2={v1e1v2e4v4，v1e2v2e4v4，v1e3v3e5v4，…}。重復(fù)以上步驟A 次，可以得到路徑集合L={L1，L2，…，LA}。反向搜索：指定D=vn為搜索起點，進(jìn)行反向遍歷，最終得到路徑集合R={R1，R2，…，RA}?；贠、D 兩個端點，同時分別執(zhí)行正向搜索和反向搜索，可得到路徑集L 和R，設(shè)定VL∈L 為L 的路徑終點集合，VR∈R 為R 的路徑終點集合，如果VL∩VR≠ ，則可以獲得完整行程P。

多因素約束條件：在雙向搜索過程中，每步均通過多因素約束進(jìn)行剪枝，以控制發(fā)散。

1）距離約束條件

針對O、D，查詢其里程制運價中總里程限制，設(shè)為M，則約束條件如下

式中：g=〈Vg，Eg〉表示搜索過程中產(chǎn)生的1 條路徑；de表示路徑中邊e 的里程。

繞飛率約束一般限制為2.5，則

式中Zg表示路徑g 的兩個端點間的商營直飛里程。

2）中轉(zhuǎn)次數(shù)約束條件

中轉(zhuǎn)次數(shù)一般不超過5 次，即

Hg-2≤2.5 ?g∈L∪R∪P

式中Hg表示路徑g 上所有節(jié)點的數(shù)量。

3）時間約束條件

設(shè)定te和tv表示路徑g 上e 邊的飛行時長和兩個銜接邊在v 點上的銜接時長，Cv表示v 點的MCT 時間限制，T 表示O、D 間總旅行時長限制，則

此外還可以根據(jù)運價規(guī)則、航空聯(lián)盟等設(shè)置約束條件，以盡快達(dá)到剪枝的目的[8-10]。

在上述約束條件的基礎(chǔ)上，針對完整行程集合P，確定打分規(guī)則進(jìn)行評分篩選，則路徑g 的評分公式如下

式中：Sg為路徑g 的總分?jǐn)?shù)；sq為路徑g 的第q 項分?jǐn)?shù)；Q 為評分項。

2 工程驗證

基于上述設(shè)計方案，在工程上進(jìn)行了編碼實現(xiàn)和比較驗證，主要驗證基于航線網(wǎng)絡(luò)圖的單向搜索方法與基于航班網(wǎng)絡(luò)圖的多因素雙向搜索方法在搜索性能和結(jié)果可用性方面的差異。具體的開發(fā)環(huán)境和部署環(huán)境如表1所示。

表1 工程實踐的應(yīng)用環(huán)境Tab.1 IT environment of practice

首先應(yīng)用性能測試工具LoadRunner 模擬用戶并發(fā)查詢場景，分別對單向搜索方法與多因素雙向搜索方法進(jìn)行搜索性能的比較。

根據(jù)CRS 系統(tǒng)的實際請求隨機(jī)選取多組國內(nèi)、國際航線作為輸入集合，配置查詢5 條路徑的聯(lián)程航班結(jié)果進(jìn)行30 min 壓力測試，限制最大中轉(zhuǎn)次數(shù)不超過5 次，航班最大銜接時間不超過24 h。測試中啟動10臺查詢服務(wù)器，并發(fā)用戶數(shù)為50。

測試一采用單向搜索方法。根據(jù)市場航線數(shù)據(jù)構(gòu)建國內(nèi)航線網(wǎng)絡(luò)圖（167 個節(jié)點，2 460 條邊）及國際航線網(wǎng)絡(luò)圖（3 538 個節(jié)點，45 838 條邊）。單向搜索模式下，隨機(jī)選取200 對不同的國內(nèi)O-D，查詢5 條聯(lián)程路徑結(jié)果的平均響應(yīng)時間為0.122 s，隨機(jī)選取1 000對不同的國際O-D，查詢5 條聯(lián)程路徑結(jié)果的平均響應(yīng)時間為9.878 s。

測試二采用多因素雙向搜索方法。根據(jù)市場航班數(shù)據(jù)構(gòu)建國內(nèi)航班網(wǎng)絡(luò)圖（167 個節(jié)點，12 300 條邊）和國際航班網(wǎng)絡(luò)圖（3 538 個節(jié)點，225 300 條邊）。多因素雙向搜索模式下，隨機(jī)選取200 對不同的國內(nèi)OD，查詢5 條聯(lián)程路徑結(jié)果的平均響應(yīng)時間為0.187 s，隨機(jī)選取1 000 對不同的國際O-D，查詢5 條聯(lián)程路徑結(jié)果的平均響應(yīng)時間為0.212 s。

測試一、二的性能對比結(jié)果如表2所示（測試用時為30 min）。

表2 單雙向搜索結(jié)果對比Tab.2 Comparison of one-way and bidirectional search results

測試結(jié)果表明：當(dāng)網(wǎng)絡(luò)圖的節(jié)點數(shù)量較多時，單向搜索響應(yīng)時間的增長比較明顯，而雙向搜索響應(yīng)時間的增長是可控的。

在上述搜索性能比較的基礎(chǔ)上，對搜索過程中產(chǎn)生的聯(lián)程航班結(jié)果按照系統(tǒng)綜合評分方法進(jìn)行可用性評分比較。隨機(jī)選取了1 000 個測試結(jié)果進(jìn)行可用性綜合評分（評分項包括CAV Score、TFT Score、Connection Score、Alliance Score，每項滿分為1，總分滿分為4）對比分析，評分分布如表3所示。結(jié)果表明：多因素雙向搜索方法的聯(lián)程航班結(jié)果在可用性方面的綜合評分遠(yuǎn)優(yōu)于單向搜索方法[11-12]。

表3 結(jié)果評分分布Tab.3 Distribution of results total score

3 結(jié)語

綜上所述，通過雙向搜索與多因素約束相結(jié)合的方式，將航線網(wǎng)絡(luò)圖擴(kuò)展為航班網(wǎng)絡(luò)圖，設(shè)計了一種民航行程計算系統(tǒng)。

雖然多因素雙向搜索方法在流程上和工程實現(xiàn)上比單向搜索方法要復(fù)雜一些，航班網(wǎng)絡(luò)圖的復(fù)雜程度也遠(yuǎn)大于航線網(wǎng)絡(luò)圖，增加了行程計算系統(tǒng)建設(shè)的難度。但是多因素雙向搜索方法保證了搜索性能和結(jié)果的可用性，從而完美解決了單向搜索方法在面臨搜索空間變大后所產(chǎn)生的搜索效率低下和結(jié)果可用性不高的問題。此外，本方案在工程實踐中也具有較大應(yīng)用價值。