基于價(jià)格導(dǎo)向的民航運(yùn)價(jià)搜索方案設(shè)計(jì)

張宏海，彭明田，劉開(kāi)勝

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

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

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

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

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

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

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

1 方案設(shè)計(jì)

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

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

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

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

1.2 運(yùn)價(jià)索引模塊

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

圖2 運(yùn)價(jià)搜索樹(shù)Tab.2 Airfare search tree

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

1.3 運(yùn)價(jià)路徑選擇模塊

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

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

1.4 運(yùn)價(jià)拆分模塊

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

如：假設(shè)有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 運(yùn)價(jià)組合校驗(yàn)?zāi)K

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

圖4 運(yùn)價(jià)組合校驗(yàn)?zāi)K的流程圖Tab.4 Flowchart of airfare combination calibration module

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)例驗(yàn)證

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

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

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

2.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

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

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

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

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

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

3 結(jié)語(yǔ)

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