基于多因素雙向搜索方法的民航行程計(jì)算系統(tǒng)

朱家彬，楊永凱，劉 軍

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

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

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

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

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

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

1.1 總體設(shè)計(jì)

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

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

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

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

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

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

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

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

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

步驟4結(jié)果篩選。對(duì)搜索到的行程集合再次進(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ī)場(chǎng)、起飛城市、到達(dá)機(jī)場(chǎng)和到達(dá)城市構(gòu)建航班網(wǎng)絡(luò)圖。航班網(wǎng)絡(luò)圖中的每條邊表示1 個(gè)直達(dá)航班，邊與邊之間的連接點(diǎn)表示機(jī)場(chǎng)。如果兩點(diǎn)之間存在1個(gè)直達(dá)航班，則在兩點(diǎn)之間增加1 條邊，如果兩點(diǎn)之間存在多個(gè)直達(dá)航班則會(huì)存在多條邊，如圖3所示。

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

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

1.3 多因素雙向搜索方法

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

給定航班網(wǎng)絡(luò)圖G、出發(fā)地O 和目的地D，請(qǐng)求返回的行程數(shù)量為N。整個(gè)搜索方法的流程如圖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é)點(diǎn)在航班網(wǎng)絡(luò)圖上進(jìn)行邊的搜索，找到以出發(fā)地為初始節(jié)點(diǎn)的所有航班經(jīng)過的路徑集合Li，以及以目的地為初始節(jié)點(diǎn)的所有航班經(jīng)過的路徑集合Ri，Li和Ri中存儲(chǔ)歷史路徑的航班信息和機(jī)場(chǎng)信息。逐級(jí)擴(kuò)展后將會(huì)得到分別以出發(fā)地和目的地為初始節(jié)點(diǎn)的兩個(gè)行程集合L={Li}和R={Ri}。

2）剪枝

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

（a）距離

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

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

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

（c）時(shí)間

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

（d）運(yùn)價(jià)規(guī)則

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

（e）其他

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

3）交集

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

4）檢查

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

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

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

1.4 方法模型

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

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

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

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

1）距離約束條件

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

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

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

式中Zg表示路徑g 的兩個(gè)端點(diǎn)間的商營(yíng)直飛里程。

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

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

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

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

3）時(shí)間約束條件

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

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

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

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

2 工程驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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