基于分布式架構的混合出行系統設計與實現

楊朝暉呂欣鍇周涵

(山東建筑大學 計算機科學與技術學院，山東 濟南250101)

0 引言

國民經濟的發展促使國內交通和旅游業保持高速增長，經濟貿易圈的不斷融合擴大也使得商務人士公務出行頻繁，“活在路上”已成為一種常態化生活方式，由此引起了出行數據的激增，人們對路線規劃和推薦出行方式的軟件需求也日益增大。

目前，大多數旅游訂票軟件多為單出行方式，即從始發地至目的地的出行路線中只能包含火車、飛機或汽車中的一種交通工具，缺少在多種出行方式上的路線規劃和智能推薦，無法滿足用戶出行時在出行費用、耗時等方面的個性化綜合需求。某些商務應用平臺雖然功能較多，但是用戶行為數據量大、信息零散、價值較低，用戶仍然無法從中獲取高效準確的出行推薦信息。同時，中國大數據行業已經進入一個高速發展的時代，大數據分析與數據挖掘技術的應用具有更高的實時性，可為行業提供更加精準的決策。因此，為滿足出行的多樣性需求，降低路線制定的盲目性與隨機性[1]，基于海杜普Hadoop分布式架構的混合出行系統是為用戶推薦最優化的個性化混合出行路線的有效方法[2]。

劉凱等[3]提出了利用運籌學方法判斷最優旅游路線，但缺少個性化推薦和對出行時間的要求；艾靜超[4]基于改進協同過濾技術個性化旅游線路推薦方法，結合協同過濾和基于地理位置的推薦模型向旅游者推薦個性化旅游路線，但未涉及價格預測功能。孟楠等[5]針對一條具體航線，對連續追蹤了半年的時間序列數據建立了自回歸移動平均ARMA(Auto Regression Moving Average)模型，利用遺傳算法預測機票價格；林友芳等[6]基于時間片充分挖掘設計了以卷積神經網絡為核心的兩階段機票價格預測模型；華逸群等[7]提出了準確度高的基于模糊時間序列[8]算法的機票價格預測模型，但只是提供了單一航線價格預測，而且由于歷史數據的產生造成了計算量增加，嚴重影響系統效率。以上研究單方面分析了路線推薦或價格預測，而且數據源較少，沒有考慮信息過載情況下系統承載力和效率等問題。

為解決上述問題，文章將分布式架構應用于出行推薦領域，采用Hadoop分布式文件系統HDFS(Hadoop Distributed File System)提供高可靠文件存儲，利用編程模型MapReduce封裝分布式故障恢復、本地化計算、并行數據處理等細節，使用Hadoop與基于分布式文件存儲的數據庫MongoDB完成數據存儲和處理，設計基于區域劃分和枚舉優化算法的混合交通推薦路線以及基于模糊時間序列算法的價格預測模塊，以期快速地為用戶提供科學合理的混合出行方案，為構建智能出行系統提供借鑒。

1 混合路線推薦及價格預測核心算法

1.1 混合路線推薦算法

假設出發地為A、目的地為B，無直達交通工具，故需要中轉。全國大約有600座城市，中轉城市共有600種選擇，兩兩城市之間的火車票和飛機票各約100張，通過遍歷所有的方案篩選出符合用戶的出行路線顯然是不合理的，因此，系統根據區域劃分思想和枚舉優化算法設計出基于區域劃分的路線篩選推薦算法，其運算過程如下:

第1次調優將換乘次數設置為1，城市的選擇約有600種，假設兩兩城市之間的飛機票和火車票每天各約有100張，則循環次數約為600萬次，從用戶的行為上已大幅降低了運算次數，但仍含有較多無用運算。

第2次調優構建數學模型，由式(1)表示為

式中price為火車票價格，元；dis為兩城市的距離，km；price＿per為單位千米的價格，元/km。

飛機票的價格存在較大浮動，火車票價格比較穩定，里程與價格成正比，因此，可以乘火車到達出發城市的鄰近城市，再由臨近城市飛到目的城市；或者先乘飛機飛到目的城市的臨近城市，再乘火車到達目的城市。根據經緯度劃分地理區域，篩選合適城市，再以綜合條件和輸入條件作為判斷依據篩選出混合出行路線。

具體算法設計的步驟如下:

(1)經緯度運算+區域劃分+城市篩選

經緯度可標識一座城市或進行距離運算。以出發城市和目的城市的經緯度為參數，根據半正矢Haversine公式即可計算出兩城市之間的距離。

在進行區域劃分之前首先要確定劃分半徑，通過大量數據計算及比較發現，當劃分半徑為兩城市之間距離的1/3時，時間與金錢的整體開銷最低。區域劃分是一個動態過程，其原理為:計算出發城市和目的城市之間的距離，取其1/3為劃分半徑，分別以出發城市和目的城市作為中心，以劃分半徑的2倍為對角線構建出2個矩形區域，根據Haversine逆公式和勾股定理分別計算出2個矩形四角的經緯度。最終篩選出兩個區域中所有可能的中轉城市，并生成中轉城市集合。

(2)混合推薦方案運算

選擇中轉城市后，遍歷城市需要篩選出飛機—高鐵或高鐵—飛機的組合方案。為保證總耗時和票價最優，首先計算出直飛的平均價格和直達高鐵的最長花費時間，要求混合票的總價格(以二等座或者硬座+飛機票價格為標準)低于飛機平均價格，混合路線總耗時低于最慢的高鐵時長。

以“出發點—中轉城市—目的地”的格式窮舉所有火車票與機票的組合，條件過濾篩選出最合理的方案?；旌下肪€推薦方案流程圖如圖1所示。

圖1 混合方案運算流程圖

1.2 機票價格預測算法

由于高鐵價格相對穩定，機票價格浮動較大，價格預測模塊主要針對機票價格進行分析處理。SONG等[8-9]在模糊理論基礎上第一次提出了模糊時間序列模型；華逸群等[7]采用模糊時間序列的算法完成機票預測模塊，但是由于數據量不足(只有36條航線)，歷史數據的增加導致計算量增加，造成計算失誤大，時間效率低。系統基于分布式架構實現模糊時間序列算法完成機票預測功能則能夠有效地避免上述缺陷。

定義1:假設U為時間序列的論域，將論域劃分為n個長度不限的有序子區間U={u1，u2，…，un}，定義在論域上的模糊集合A由式(2)表示為

式中fA(·)為ui對A的隸屬函數；fA(ui)為ui對A的隸屬度，fA(ui)∈[0，1]，i=1，2，…，n。

定義2:令Y(t)(t=0，1，2，…)為給定論域fi(t)(i=1，2，…)在Y(t)上的模糊集合，由f1(t)，f2(t)，…，fn(t)組成的集合F(t)稱為定義在該論域上的模糊時間序列。

將原始數據通過Hadoop數據清洗，在通過劃分論域、最低價格矩陣、定義模糊集、價格模糊化、預測向量等步驟將得到的價格矩陣去模糊化，最后采用迭代法進行多天價格預測。算法流程如圖2所示。

圖2 Hadoop價格預測算法流程圖

隨著歷史機票數據的增加，計算量不斷上升，數據中可能存在很多缺失。為解決這一問題，根據Hadoop分布式架構的特點，利用MapReduce操作對機票歷史數據進行清洗刷新，采用缺失值填充模型的均值算法，即將信息表中的屬性分為數值屬性和非數值屬性分別處理。如果空值為數值型，根據該屬性在其他所有對象取值的平均值填充該缺失的屬性值；如空值為非數值型，則根據統計學中的眾數原理，采用該屬性在其他所有對象的取值次數最多的值(即出現頻率最高的值)以補齊該缺失的屬性值。在數據的結構化和清洗中進行調優，篩選出需要構成機票預測算法的最低價矩陣，從而提高計算效率。

以7×7矩陣為例，數據清洗的流程如圖3所示，當數據量足夠大時可以將矩陣擴大。

初始狀態下輸入一個輸入矩陣，一次迭代計算的過程為:尋找上下界、一次區間劃分、篩選區間、二次劃分、記錄區間最值得到論域；論域經過模糊化處理得到模糊矩陣；尋找待預測值；進行縱橫擴展運算；得到兩個模糊關系矩陣，在此矩陣中將預測值上方與右方合成運算，得到預測向量；再根據隸屬度進行去模糊化，得到一個預測值。

重復以上過程，經過多輪迭代最終得到所有預測值。迭代過程如圖4所示。

圖3 Hadoop數據清洗流程圖

圖4 迭代計算過程圖

2 混合出行系統設計與實現

Hadoop分布式架構可以將巨大數據集分配到多個計算機集群的多個節點進行存儲，可靠性和容錯性高，采取MapReduce分布式數據分析處理框架可以并發分布式的處理大量數據集[10]。系統通過整合HDFS與MongoDB尋求最優數據存儲方式[11]，為MapReduce選擇輸入數據或者輸出結果，能夠快速準確地分析處理各種航線的歷史數據，減少用戶查詢的等待時間，提高推薦結果的準確性。

系統通過爬取火車票和機票的數據在Hadoop分布式架構上進行數據存儲和處理從而實現路線推薦和價格預測，接入百度應用程序接口實現繪制地圖與定位；實現天氣、經緯度、對比、收藏、歷史路線記錄、熱門路線推薦、7d最低價展示以及用戶模塊等功能。

2.1 系統架構

系統采用C/S架構，前端應用程序使用VUE+VUE-cli3.0+Axios+Element-UI+Mint-UI組件開發，后端使用Python3.6+Hadoop開發，以Flask微框架提供的路由與接口功能實現前后端連接，使用MongoDB分布式文件存儲票務信息，使用MySQL數據庫存儲結構化用戶信息[12]。系統結構完整，運行高效，具有較強的防護能力與處理能力。

以分布式基礎架構Hadoop及其相關組件為基礎，使用客戶端層、傳遞層、聚合層、服務層的4層架構搭建大數據集群環境[13-14]，建立了Hadoop+MongoDB+MySQL存儲策略完成數據存儲與數據運算。Hadoop集群中有一臺主機、兩臺子節點，當系統上傳一個任務時，資源管理YARN將決定使用共同完成該任務的節點數目，并把任務分發到每一個被選中的節點，多節點共同執行任務從而獲得運算結果。

硬件模塊共使用4臺服務器，其中3臺搭建Hadoop服務集群，1臺部署后端管理系統，每臺服務器內存16 G、硬盤500 G，安裝社區企業操作系統

CentOS(Community Enterprise Operating System)。

軟件模塊包括HDFS分布式文件系統、計算框架MapReduce、資源管理YARN、數據倉庫工具Hive、分布式NoSQL型數據庫MongoDB等。利用開源工具Sqoop將用戶訪問日志導入到Hadoop中，借助系統定時任務調度Sqoop實現增量數據定制導入。軟件技術架構如圖5所示。

圖5 軟件技術架構圖

2.2 出行路線推薦模塊的設計與實現

2.2.1 飛機/火車余票查詢模塊實現

查詢模塊功能分為飛機直達查詢、火車直達查詢和混合出行查詢。具體實現方式為:通過網絡爬蟲抓取12306網站的火車票信息，同時從攜程網抓取機票信息，將相應的票務信息存儲在數據庫以備后期數據處理工作。通過數據庫查詢語句將票務信息全部獲取進入運行內存，再根據用戶輸入的出發地、目的地、出發日期、出發時間，再結合當前日期和當前時間完成票務信息的條件篩選和實時篩選。搜索流程圖如圖6所示，飛機/火車票的余票查詢結果如圖7所示。

圖6 搜索流程圖

圖7 飛機/火車余票搜索結果圖

2.2.2 混合路線推薦模塊實現

基于1.1節的算法實現路線推薦，并調用百度地圖接口，實現在虛擬地圖上進行路線渲染顯示，并提供公交與打車出行建議。假設需要推薦濟南至沈陽的路線，推薦界面如圖8所示(地圖審圖號:GS(2019)5218｜測繪資質:甲測資字1100930)。

圖8 百度地圖調用界面圖

2.3 價格預測模塊的設計與實現

基于1.2節價格預測算法實現路線實時預測[15]，展示最近7 d的價格波動，為了提高界面響應速度，使用頁面“懶加載”技術，減輕流量負擔與瞬時負載。價格預測界面如圖9所示。

圖9 價格預測界面圖

任意選中兩個方案進行對比，將前端獲取的數據傳遞給后臺的數據進行解析篩選，計算出總花費、路程耗時、出發時間、到達時間，進行邏輯比較，方案對比如圖10所示。由圖可見，不同方案滿足不同的用戶需求，用戶可根據實際情況選擇相應的出行方案。

圖10 方案對比圖

2.4 測試結果

系統經過單元測試和性能測試達到預期設計要求，測試結果見表1。

由表1可知，系統適應全部手機測試終端，安裝和卸載速度快，成功率達100%，界面適應性好，無響應異常，流量耗用低，中央處理器CPU(Central Processing Unit)和圖形處理器GPU(Graphics Processing Unit)占用率低，均達到業界最優水平，響應客戶端的請求速度較快，無卡死閃退等異常情況出現，系統運行速率高，運行結果正確率達100%。

表1 測試結果表

3 結語

文章研究的系統通過使用4層架構搭建分布式大數據基礎環境，采用Hadoop+MongoDB+MySQL聯合存儲策略完成最優海量數據存儲與實時計算，提高了出行數據處理效率與準確度，實現了根據用戶個性化需求提供高效準確的混合出行路線推薦方案和價格預測的功能。系統是一種高性能、高可靠性的實時智慧推薦應用，改善了傳統路線制定的盲目性與隨機性，可為在分布式架構上構建推薦系統提供一定理論基礎和技術支撐。