張宏海，彭明田，劉開勝

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

互聯(lián)網(wǎng)時代，旅客通過航空公司官網(wǎng)和第三方機票銷售網(wǎng)站自助購票已成為機票訂購主要方式。旅客自助購票過程包括：機票搜索、預訂、支付和出票等多個環(huán)節(jié)。其中運價搜索是最重要的環(huán)節(jié)，其根據(jù)旅客輸入的行程請求，自動搜索并生成可用行程，完成航班可利用艙位的查詢及對應航班艙位的價格計算。旅客在進行運價搜索時，既希望能搜索到低價航班，又希望有足夠豐富的航班選擇，滿足其差異化的出行需求；另一方面用戶對運價搜索系統(tǒng)的處理性能和響應速度要求較高，通常要求系統(tǒng)能在秒級時間內(nèi)返回旅客需求的合理化排序結(jié)果。

在運價搜索系統(tǒng)中，不同旅客行程伴隨不同的始發(fā)地、目的地和聯(lián)程點，也使得在運價計算中不同行程的運價元素（FC, fare component）、價格單元（PU,price unit）和運價行程（JR, journey）也不盡相同。因此，基于航班和運價雙因素的航班運價排列組合搜索中，數(shù)量龐大的全球航班以及航班航段的迥異，使得航班運價組合數(shù)量隨航段數(shù)量的增長呈指數(shù)級增長，其解空間極其龐大。

傳統(tǒng)處理方法是從滿足行程的航班組合開始處理，因此被稱為行程導向運價搜索方法，該方法需要先進行航班搜索，其最大難點是搜索空間大。目前全球每年的航班數(shù)量超過3 000 萬，運價數(shù)量約10 億條。具體到一次運價搜索，以常見的4 個航段往返中轉(zhuǎn)行程為例，假設每個航段的航班數(shù)量為N，則4 段往返行程的航班組合數(shù)量為N4；假設每個航班有N 個可用艙位，則可用艙位組合的數(shù)量也是N4；假設去程和回程各有N 個運價，則運價組合數(shù)量為N2，則整個求解空間為N10。對于航段數(shù)量超過4 段的復雜行程，由于航班組合數(shù)量會隨著航段數(shù)量的增長呈指數(shù)級增長，其解空間會更加龐大。對于NYC 到LON 這樣的繁忙航線，其解空間的數(shù)量甚至超過了30 億。

面對龐大的解空間，行程導向傳統(tǒng)運價搜索方法很難在用戶可接受的響應時間內(nèi)給出理想結(jié)果，且根據(jù)航班信息的剪枝操作雖能縮小解空間，但往往無法給出適用于這些航班組合的最低價格。

基于運價的航班搜索，既能滿足旅客價低質(zhì)優(yōu)的查詢需求，同時也可極大提高航班的搜索效率，是民航運價搜索系統(tǒng)亟待實現(xiàn)的技術。國外對此進行了相關研究，以Demarcken 為首的美國研究團隊通過并行化方式將運價搜索拆分為多個子搜索，對系統(tǒng)進行優(yōu)化和改造[1-3]。該方法在一定程度上提升了系統(tǒng)性能，降低了響應時間，但拆分后的子搜索空間依然很大，無法從根本上解決問題。

為了優(yōu)化不同行程的航班組合，提高航班搜索效率，設計一種運價搜索方案，以價格為導向構造可能的運價組合，在航班信息缺失的情況下先利用經(jīng)驗信息估計運價組合的價格和合理性，最大限度地縮小搜索空間，篩選出運價組合的最優(yōu)解。該搜索方案在航空客票搜索、旅客需求收集整合、航空客運信息整合共享方面具有極大潛力，將有效提高民航客運服務質(zhì)量，獲得更大的社會、經(jīng)濟效益。

1 方案設計

為解決價格導向的航班搜索問題，采用啟發(fā)式搜索算法，利用旅行經(jīng)驗數(shù)據(jù)對潛在行程價格和舒適度進行估計，剔除不合理結(jié)果，篩選出滿足旅客需求的最終結(jié)果。價格導向的民航運價搜索系統(tǒng)包括以下模塊：旅行經(jīng)驗信息、運價索引、運價路徑選擇、運價拆分和運價組合校驗。整體框架如圖1 所示。

1.1 旅行經(jīng)驗信息模塊

圖1 系統(tǒng)整體框架圖Tab.1 System architecture

旅行經(jīng)驗信息模塊用于生成旅行經(jīng)驗信息數(shù)據(jù)庫。系統(tǒng)從ATPCO 公司發(fā)布的運價數(shù)據(jù)和OAG（official airline guide）發(fā)布的航班計劃數(shù)據(jù)中計算得到旅行經(jīng)驗數(shù)據(jù)，包括從運價數(shù)據(jù)中提取出的價格信息和從航班數(shù)據(jù)中提取的舒適度信息。旅行經(jīng)驗數(shù)據(jù)作為運價搜索過程中重要的啟發(fā)式信息，用于估計運價組合的綜合價格，過濾不合理的運價組合。另一方面，經(jīng)驗數(shù)據(jù)會按照信息的精確度進行有層次的索引和存儲。隨著搜索的深入，當系統(tǒng)獲得的信息越來越完備時，就可利用更完備的信息索引出更精確的旅行經(jīng)驗信息。令O 為始發(fā)機場，D 為目的機場，A、B 為中轉(zhuǎn)機場，在運價路徑選擇中，旅客最初可能只關心O—A—D 和O—B—D 這兩條路徑哪個更低價，但隨著搜索的深入，會更加關注O—A—D 這條路徑上，不同艙位等級、不同航空公司和不同運價類型對應的最低運價是多少。在旅行經(jīng)驗數(shù)據(jù)的更新方面，對于不同精確度的經(jīng)驗數(shù)據(jù)，當其產(chǎn)生的原始數(shù)據(jù)發(fā)生變化后，會評估經(jīng)驗數(shù)據(jù)是否仍有效，對于不同精確度的經(jīng)驗數(shù)據(jù)，以不同頻率更新相應的經(jīng)驗數(shù)據(jù)庫；影響程度大的經(jīng)驗數(shù)據(jù)更新更加頻繁。

1.2 運價索引模塊

運價索引模塊用來建立運價索引以便快速查找運價。面對數(shù)以億計的運價數(shù)據(jù)，如何快速遍歷和查找運價成為系統(tǒng)性能的關鍵。恰當?shù)亟⑺饕粌H可以快速提取運價數(shù)據(jù)，還能有效壓縮運價的數(shù)據(jù)規(guī)模。系統(tǒng)并不為每一個運價數(shù)據(jù)建立索引，而是首先將具有相同或部分相同校驗規(guī)則的運價聚合成元組，并在元組的基礎上根據(jù)起點終點、航空公司、艙位類型等信息將元組組織為一個具有層次關系的集合，形成運價數(shù)據(jù)搜索樹[4]，如圖2 所示。

圖2 運價搜索樹Tab.2 Airfare search tree

可以看出，運價搜索樹中的每個節(jié)點都對應一個運價組，而其子節(jié)點是具有更多信息的運價組。如上海到北京的運價組節(jié)點下，包含不同艙位類型的子節(jié)點，而每個艙位類型的子節(jié)點下又包含了對應不同航空公司的子節(jié)點。系統(tǒng)歸納每一個節(jié)點內(nèi)運價數(shù)據(jù)的價格信息，并將這些價格信息存儲在旅行經(jīng)驗數(shù)據(jù)庫中。通過此種方式組織運價數(shù)據(jù)，運價搜索就變?yōu)榘磳哟沃鸺壣钊朊恳粚庸?jié)點進行搜索的過程，并可根據(jù)每個節(jié)點的價格和依據(jù)旅行經(jīng)驗信息修正后的綜合價格對運價路徑進行排序和篩選。

1.3 運價路徑選擇模塊

如圖3 所示，運價路徑選擇模塊用來生成潛在的低價路徑，根據(jù)旅客輸入的旅行信息提取相應精確度的運價組最低價格。以運價組對應的O 和D 為節(jié)點、最低價格為邊權構造運價路徑圖。在圖中用最短路徑算法搜索滿足旅客輸入OD 的前N 條最低價格運價路徑，并調(diào)用旅行經(jīng)驗數(shù)據(jù)庫中的調(diào)用經(jīng)驗數(shù)據(jù)計算路徑的綜合價格，篩除不合理的運價路徑。這是對搜索結(jié)果最粗粒度的篩選，系統(tǒng)為每個旅客的查詢請求找出至少一條運價路徑。

圖3 路徑選擇模塊流程圖Tab.3 Flowchart of routine selection module

1.4 運價拆分模塊

運價拆分模塊用于生成IATA（International Air Transport Association）標準的PU 和JR。系統(tǒng)枚舉所有可能的價格單元，組合成為不同的運價行程，這樣初始的一條運價路徑在這里分化成為不同航空公司、不同艙位類型和不同運價類型的運價行程，拆分規(guī)則遵守IATA 和ATPCO 要求。

如：假設有O—A—D—B—O 行程，將其拆分為FC（OA），F(xiàn)C（AD），F(xiàn)C（DB），F(xiàn)C（BO），則可能的PU和JR 有

1.5 運價組合校驗模塊

運價組合校驗模塊用于產(chǎn)生最終的最優(yōu)運價組合，也是整個系統(tǒng)最復雜、最核心的模塊，其工作流程如圖4 所示，整個流程由3 步組成。

圖4 運價組合校驗模塊的流程圖Tab.4 Flowchart of airfare combination calibration module

步驟1在明確航空公司、艙位類型等信息后，利用更精確的旅行經(jīng)驗信息估計每一種運價行程的綜合價格，按價格對其排序，并剔除不合理的運價行程。系統(tǒng)選擇當前綜合價格最優(yōu)的運價行程，如果該行程中包含未展開的運價組則，則展開該運價組，重新組合為新的運價行程，并重復上述過程計算綜合價格，排序篩選。直到當前的運價行程全部為元組組成。

步驟2系統(tǒng)根據(jù)同一元組中運價對航班的約束要求生成滿足要求的航班。

步驟3在獲得航班信息后，系統(tǒng)根據(jù)航班信息校驗元組中的運價規(guī)則，依據(jù)ATPCO 標準，自下而上分為3 層次校驗，即FC 層、PU 層和JR 層，直到得到通過全部校驗且價格最優(yōu)的運價組合。如果該運價組合的價格高于已知的運價行程價格，則從已知價格最低的運價行程開始繼續(xù)處理，展開該運價行程中的運價組，生成新的運價行程，評估價格，排序篩選，校驗規(guī)則等。直到不再有運價行程價格低于已知的運價組合，系統(tǒng)將得到的運價組合結(jié)果返回給用戶。

目前國際民航業(yè)運價數(shù)據(jù)大約有10 億條，因此如何索引和篩選運價數(shù)據(jù)是運價搜索面對的重要挑戰(zhàn)之一。確定一個運價（fare）是否可用，需要知道一系列信息：fare（OD，Dep/Arr date，cabin，OW/RT，PU，JR，F(xiàn)C，carrier，tariff，routing，rule，...）。如fare（OD）可以索引到一組運價，而fare（OD，Dep/Arr date）則是fare（OD）的一個子集，依此類推，系統(tǒng)知道的信息越完備，可索引到的運價數(shù)量越少，價格越確定，則需要校驗的規(guī)則也越少。這也是為什么傳統(tǒng)的航班搜索要首先生成航班組合，因為有了航班組合才能獲得確定運價的完備信息，從而校驗某個運價是否可用于這個航班組合。但這種方式的缺點也十分明顯，確定完備的信息后，運價的搜索范圍被限制在非常小的區(qū)域內(nèi)，很容易錯過潛在的低價結(jié)果。

從上文對運價數(shù)據(jù)的描述，可發(fā)現(xiàn)運價數(shù)據(jù)很適合用一個搜索樹來描述，各個信息對應樹的各級。系統(tǒng)知道的信息越多相當于可以定位到越深的分支上。而搜索過程正是獲得信息由少到多的過程，相當于逐級打開搜索樹的過程。因此在本方案中系統(tǒng)以搜索樹的形式存儲和建立運價的多級索引，并且計算各級分支中運價的最低價格和索引一起存儲。在搜索過程中，隨著已知信息的增加，系統(tǒng)逐級打開搜索樹，并根據(jù)最低價格進行“剪枝”，篩選出價格較低的分支，沿著這些分支繼續(xù)深入搜索[5-6]。

具體到技術方案實現(xiàn)上，對于步驟1，整個搜索排序過程大量采用了列生成（Column）算法，基于打分和校驗規(guī)則高效地在海量解空間中找到下一個最優(yōu)解。通常而言，運價搜索需要創(chuàng)建所有的組合，對這些組合進行打分排序，然后依次選擇最優(yōu)解，但此種方法效率較低，對于運價搜索系統(tǒng)來說，無法滿足性能要求。通過列生成算法，對每個備選的元組按照一定規(guī)則進行打分并將其放入對應的Column 中，然后按需產(chǎn)生下一個最優(yōu)解，且該最優(yōu)解必須滿足特定的校驗規(guī)則。同時，為提高效率，每產(chǎn)生一個最優(yōu)解，都會判斷后續(xù)備選方案是否還有繼續(xù)處理的必要，如果后續(xù)備選方案預估價格已經(jīng)較高，則無需繼續(xù)處理。

對于步驟2，在針對每個元組生成可用航班的過程中，為進一步提升系統(tǒng)效率，化解業(yè)務復雜度，結(jié)合運價業(yè)務創(chuàng)新性地采用雙向A*啟發(fā)式算法，并利用有向圖策略，將全局網(wǎng)絡簡化為局部網(wǎng)絡壓縮解空間[7-9]。經(jīng)測試，以4 條典型航線和一次中轉(zhuǎn)的求解空間為例，采用雙向A*算法后，其求解空間是采用單向A*算法的6%到8%，大幅壓縮了求解空間，從而提升了系統(tǒng)響應速度，如表1 所示。

表1 兩種算法的結(jié)果集對比Fig.1 Comparison between two algorithms

對于步驟3，在運價數(shù)據(jù)的校驗過程中，可以發(fā)現(xiàn)運價數(shù)據(jù)之間會共用一些規(guī)則，這意味著系統(tǒng)可以把具有相同規(guī)則的運價數(shù)據(jù)聚合成組。系統(tǒng)將此類運價組作為運價搜索樹最底層的葉節(jié)點。系統(tǒng)以該層為分界線，把在其之上的信息稱為篩選信息，把其之下的信息稱為校驗信息。原因很簡單，在這之上系統(tǒng)利用信息分支來篩選運價，而其之下則是根據(jù)信息校驗運價是否可用。至此，系統(tǒng)完成了對運價數(shù)據(jù)的重新組織和索引，數(shù)據(jù)以搜索樹的方式存儲。搜索過程中，系統(tǒng)逐層打開各處運價組，進行組合和篩選[10]。

此外，前述系統(tǒng)利用運價索引的最低價格來估計潛在行程的最終價格，但如果系統(tǒng)僅以價格為考慮因素進行搜索，可能給出不合理或者舒適度很差的結(jié)果。例如旅客查詢北京到上海的航班，系統(tǒng)可能給出經(jīng)迪拜中轉(zhuǎn)的聯(lián)程結(jié)果或經(jīng)成都再經(jīng)武漢兩次中轉(zhuǎn)的結(jié)果。因此在具體實現(xiàn)上，系統(tǒng)要把舒適度和價格綜合起來考慮，可以把舒適度以一定比例轉(zhuǎn)換后加入到價格中，生成一個綜合價格，以此來修正系統(tǒng)對質(zhì)優(yōu)價廉結(jié)果的估計，則綜合價格為

其中：P 為原始價格；p1～pn為影響排序的舒適度因素，包括總經(jīng)停時間、總旅行時間和中轉(zhuǎn)次數(shù)等；w1～wn為p1～pn對應的權重系數(shù)；K 為調(diào)節(jié)系數(shù)，不同場景下調(diào)節(jié)系數(shù)取值不同。例如相對散客，商務旅客對舒適度的要求更高，因此調(diào)節(jié)系數(shù)會較高。

以海南航空公司布魯塞爾到北京的航線為例，出發(fā)日期為2109 年10 月10 日，抽取系統(tǒng)返回的5 個典型航班，搜索結(jié)果如表2 所示。

可以看出，按照綜合價格排序的結(jié)果明顯更加合理，例如直達航班HU492 的綜合價格更低，會優(yōu)先顯示給旅客，而兩次中轉(zhuǎn)的聯(lián)程航班HU 8506 HU7992 HU497，雖然價格最低，但由于飛行時間過長，導致其綜合價格過高，所以會排在后面。

綜上所述，在運價搜索過程中，旅行經(jīng)驗信息是系統(tǒng)用來估計結(jié)果優(yōu)劣的重要啟發(fā)式信息。系統(tǒng)通過估計運價的最低價格搜索潛在的低運價路徑，又利用對舒適度的估計篩選不合理的運價路徑，并通過綜合價格修正系統(tǒng)的估計。

表2 航班搜索結(jié)果排序示例Fig.2 Flight sorting example

2 實例驗證

2.1 數(shù)據(jù)采集與實驗環(huán)境

數(shù)據(jù)分析表明，系統(tǒng)的主要查詢請求為國內(nèi)始發(fā)的國際航線，其中95%為單程和往返程。因此，驗證數(shù)據(jù)集選擇400 條國內(nèi)始發(fā)國際的熱門航線，行程類型為單程和往返程，請求類型為多航空公司，1 名成人乘客，旅行日期范圍為2019 年8 月至2020 年7 月。

為驗證基于價格方案的運價搜索性能，在工程上進行了編碼實現(xiàn)和實踐驗證，采用C++語言編寫程序，在Linux Redhat v6.5 系統(tǒng)上運行，主機采用X86 服務器，16 核CPU，內(nèi)存512G，硬盤2.9T SSD。

2.2 實驗評價指標

目前基于價格的運價搜索系統(tǒng)已在生產(chǎn)環(huán)境部署，用于為航空公司和代理人網(wǎng)站提供運價搜索服務。

在測試指標的選擇上，需要從多個指標綜合衡量。通過客戶調(diào)研和數(shù)據(jù)分析，不同旅客對航班的關注點不同：散客對于價格敏感，希望系統(tǒng)能夠返回更低的價格；商務旅客對于價格不敏感，希望系統(tǒng)能夠返回更加豐富的結(jié)果，滿足其出行需求。此外，所有旅客都希望系統(tǒng)能夠快速返回搜索結(jié)果。因此，在工程驗證上，選取以下3 個關鍵指標，作為判斷方案優(yōu)劣的因素：①響應時間（s），一個運價搜索請求返回結(jié)果的響應時間；②結(jié)果豐富度，一個運價搜索請求返回結(jié)果的數(shù)量；③低價命中率（%），一個運價搜索請求返回結(jié)果最低價格的概率。

實驗采用上述數(shù)據(jù)集，依次對基于價格的運價搜索方法（Price-based）和基于行程的運價搜索方法（Travel-based）進行測試，結(jié)果如表3 所示。

可以看出，從“響應時間”指標來看，Price-based方法的單程請求響應時間為1.12 s，僅為Travel-based方法的28.41%；且往返程請求響應時間為2.31 s，僅為Travel-based 方法的32.26%；從“結(jié)果豐富度”指標來看，Price-based 方法平均結(jié)果數(shù)為491，Travel-based方法為199，是傳統(tǒng)基于行程導向方法的2.46 倍；從“低價命中率”指標來看，Price-based 方法的低價命中率為83.7%，比傳統(tǒng)方法提高了38.16%。通過驗證結(jié)果可以看到，相比基于行程的運價搜索方法，基于價格的運價搜索方法在平均結(jié)果數(shù)量大幅增加的情況下，響應時間有效縮短，低價命中率也明顯提升，證明其成效顯著。

表3 不同方法不同指標的結(jié)果對比Tab.3 Comparison between different algorithms and indices

3 結(jié)語

基于價格的啟發(fā)式運價搜索方法，利用旅行經(jīng)驗數(shù)據(jù)對潛在行程價格和舒適度進行估計，篩選出滿足旅客需求的最終結(jié)果，解決了有限時間內(nèi)對海量數(shù)據(jù)空間求運價最優(yōu)解的難題，為民航運價搜索的快速響應和高效率執(zhí)行提供了有效的解決方案。該算法的推廣將有效提高民航客運服務質(zhì)量，促進行業(yè)社會和經(jīng)濟效益的提升。