楊朝暉呂欣鍇周涵

(山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南250101)

0 引言

國(guó)民經(jīng)濟(jì)的發(fā)展促使國(guó)內(nèi)交通和旅游業(yè)保持高速增長(zhǎng)，經(jīng)濟(jì)貿(mào)易圈的不斷融合擴(kuò)大也使得商務(wù)人士公務(wù)出行頻繁，“活在路上”已成為一種常態(tài)化生活方式，由此引起了出行數(shù)據(jù)的激增，人們對(duì)路線規(guī)劃和推薦出行方式的軟件需求也日益增大。

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

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

為解決上述問(wèn)題，文章將分布式架構(gòu)應(yīng)用于出行推薦領(lǐng)域，采用Hadoop分布式文件系統(tǒng)HDFS(Hadoop Distributed File System)提供高可靠文件存儲(chǔ)，利用編程模型MapReduce封裝分布式故障恢復(fù)、本地化計(jì)算、并行數(shù)據(jù)處理等細(xì)節(jié)，使用Hadoop與基于分布式文件存儲(chǔ)的數(shù)據(jù)庫(kù)MongoDB完成數(shù)據(jù)存儲(chǔ)和處理，設(shè)計(jì)基于區(qū)域劃分和枚舉優(yōu)化算法的混合交通推薦路線以及基于模糊時(shí)間序列算法的價(jià)格預(yù)測(cè)模塊，以期快速地為用戶提供科學(xué)合理的混合出行方案，為構(gòu)建智能出行系統(tǒng)提供借鑒。

1 混合路線推薦及價(jià)格預(yù)測(cè)核心算法

1.1 混合路線推薦算法

假設(shè)出發(fā)地為A、目的地為B，無(wú)直達(dá)交通工具，故需要中轉(zhuǎn)。全國(guó)大約有600座城市，中轉(zhuǎn)城市共有600種選擇，兩兩城市之間的火車(chē)票和飛機(jī)票各約100張，通過(guò)遍歷所有的方案篩選出符合用戶的出行路線顯然是不合理的，因此，系統(tǒng)根據(jù)區(qū)域劃分思想和枚舉優(yōu)化算法設(shè)計(jì)出基于區(qū)域劃分的路線篩選推薦算法，其運(yùn)算過(guò)程如下:

第1次調(diào)優(yōu)將換乘次數(shù)設(shè)置為1，城市的選擇約有600種，假設(shè)兩兩城市之間的飛機(jī)票和火車(chē)票每天各約有100張，則循環(huán)次數(shù)約為600萬(wàn)次，從用戶的行為上已大幅降低了運(yùn)算次數(shù)，但仍含有較多無(wú)用運(yùn)算。

第2次調(diào)優(yōu)構(gòu)建數(shù)學(xué)模型，由式(1)表示為

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

飛機(jī)票的價(jià)格存在較大浮動(dòng)，火車(chē)票價(jià)格比較穩(wěn)定，里程與價(jià)格成正比，因此，可以乘火車(chē)到達(dá)出發(fā)城市的鄰近城市，再由臨近城市飛到目的城市；或者先乘飛機(jī)飛到目的城市的臨近城市，再乘火車(chē)到達(dá)目的城市。根據(jù)經(jīng)緯度劃分地理區(qū)域，篩選合適城市，再以綜合條件和輸入條件作為判斷依據(jù)篩選出混合出行路線。

具體算法設(shè)計(jì)的步驟如下:

(1)經(jīng)緯度運(yùn)算+區(qū)域劃分+城市篩選

經(jīng)緯度可標(biāo)識(shí)一座城市或進(jìn)行距離運(yùn)算。以出發(fā)城市和目的城市的經(jīng)緯度為參數(shù)，根據(jù)半正矢Haversine公式即可計(jì)算出兩城市之間的距離。

在進(jìn)行區(qū)域劃分之前首先要確定劃分半徑，通過(guò)大量數(shù)據(jù)計(jì)算及比較發(fā)現(xiàn)，當(dāng)劃分半徑為兩城市之間距離的1/3時(shí)，時(shí)間與金錢(qián)的整體開(kāi)銷(xiāo)最低。區(qū)域劃分是一個(gè)動(dòng)態(tài)過(guò)程，其原理為:計(jì)算出發(fā)城市和目的城市之間的距離，取其1/3為劃分半徑，分別以出發(fā)城市和目的城市作為中心，以劃分半徑的2倍為對(duì)角線構(gòu)建出2個(gè)矩形區(qū)域，根據(jù)Haversine逆公式和勾股定理分別計(jì)算出2個(gè)矩形四角的經(jīng)緯度。最終篩選出兩個(gè)區(qū)域中所有可能的中轉(zhuǎn)城市，并生成中轉(zhuǎn)城市集合。

(2)混合推薦方案運(yùn)算

選擇中轉(zhuǎn)城市后，遍歷城市需要篩選出飛機(jī)—高鐵或高鐵—飛機(jī)的組合方案。為保證總耗時(shí)和票價(jià)最優(yōu)，首先計(jì)算出直飛的平均價(jià)格和直達(dá)高鐵的最長(zhǎng)花費(fèi)時(shí)間，要求混合票的總價(jià)格(以二等座或者硬座+飛機(jī)票價(jià)格為標(biāo)準(zhǔn))低于飛機(jī)平均價(jià)格，混合路線總耗時(shí)低于最慢的高鐵時(shí)長(zhǎng)。

以“出發(fā)點(diǎn)—中轉(zhuǎn)城市—目的地”的格式窮舉所有火車(chē)票與機(jī)票的組合，條件過(guò)濾篩選出最合理的方案?；旌下肪€推薦方案流程圖如圖1所示。

圖1 混合方案運(yùn)算流程圖

1.2 機(jī)票價(jià)格預(yù)測(cè)算法

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

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

式中fA(·)為ui對(duì)A的隸屬函數(shù)；fA(ui)為ui對(duì)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)稱為定義在該論域上的模糊時(shí)間序列。

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

圖2 Hadoop價(jià)格預(yù)測(cè)算法流程圖

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

以7×7矩陣為例，數(shù)據(jù)清洗的流程如圖3所示，當(dāng)數(shù)據(jù)量足夠大時(shí)可以將矩陣擴(kuò)大。

初始狀態(tài)下輸入一個(gè)輸入矩陣，一次迭代計(jì)算的過(guò)程為:尋找上下界、一次區(qū)間劃分、篩選區(qū)間、二次劃分、記錄區(qū)間最值得到論域；論域經(jīng)過(guò)模糊化處理得到模糊矩陣；尋找待預(yù)測(cè)值；進(jìn)行縱橫擴(kuò)展運(yùn)算；得到兩個(gè)模糊關(guān)系矩陣，在此矩陣中將預(yù)測(cè)值上方與右方合成運(yùn)算，得到預(yù)測(cè)向量；再根據(jù)隸屬度進(jìn)行去模糊化，得到一個(gè)預(yù)測(cè)值。

重復(fù)以上過(guò)程，經(jīng)過(guò)多輪迭代最終得到所有預(yù)測(cè)值。迭代過(guò)程如圖4所示。

圖3 Hadoop數(shù)據(jù)清洗流程圖

圖4 迭代計(jì)算過(guò)程圖

2 混合出行系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

Hadoop分布式架構(gòu)可以將巨大數(shù)據(jù)集分配到多個(gè)計(jì)算機(jī)集群的多個(gè)節(jié)點(diǎn)進(jìn)行存儲(chǔ)，可靠性和容錯(cuò)性高，采取MapReduce分布式數(shù)據(jù)分析處理框架可以并發(fā)分布式的處理大量數(shù)據(jù)集[10]。系統(tǒng)通過(guò)整合HDFS與MongoDB尋求最優(yōu)數(shù)據(jù)存儲(chǔ)方式[11]，為MapReduce選擇輸入數(shù)據(jù)或者輸出結(jié)果，能夠快速準(zhǔn)確地分析處理各種航線的歷史數(shù)據(jù)，減少用戶查詢的等待時(shí)間，提高推薦結(jié)果的準(zhǔn)確性。

系統(tǒng)通過(guò)爬取火車(chē)票和機(jī)票的數(shù)據(jù)在Hadoop分布式架構(gòu)上進(jìn)行數(shù)據(jù)存儲(chǔ)和處理從而實(shí)現(xiàn)路線推薦和價(jià)格預(yù)測(cè)，接入百度應(yīng)用程序接口實(shí)現(xiàn)繪制地圖與定位；實(shí)現(xiàn)天氣、經(jīng)緯度、對(duì)比、收藏、歷史路線記錄、熱門(mén)路線推薦、7d最低價(jià)展示以及用戶模塊等功能。

2.1 系統(tǒng)架構(gòu)

系統(tǒng)采用C/S架構(gòu)，前端應(yīng)用程序使用VUE+VUE-cli3.0+Axios+Element-UI+Mint-UI組件開(kāi)發(fā)，后端使用Python3.6+Hadoop開(kāi)發(fā)，以Flask微框架提供的路由與接口功能實(shí)現(xiàn)前后端連接，使用MongoDB分布式文件存儲(chǔ)票務(wù)信息，使用MySQL數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)化用戶信息[12]。系統(tǒng)結(jié)構(gòu)完整，運(yùn)行高效，具有較強(qiáng)的防護(hù)能力與處理能力。

以分布式基礎(chǔ)架構(gòu)Hadoop及其相關(guān)組件為基礎(chǔ)，使用客戶端層、傳遞層、聚合層、服務(wù)層的4層架構(gòu)搭建大數(shù)據(jù)集群環(huán)境[13-14]，建立了Hadoop+MongoDB+MySQL存儲(chǔ)策略完成數(shù)據(jù)存儲(chǔ)與數(shù)據(jù)運(yùn)算。Hadoop集群中有一臺(tái)主機(jī)、兩臺(tái)子節(jié)點(diǎn)，當(dāng)系統(tǒng)上傳一個(gè)任務(wù)時(shí)，資源管理YARN將決定使用共同完成該任務(wù)的節(jié)點(diǎn)數(shù)目，并把任務(wù)分發(fā)到每一個(gè)被選中的節(jié)點(diǎn)，多節(jié)點(diǎn)共同執(zhí)行任務(wù)從而獲得運(yùn)算結(jié)果。

硬件模塊共使用4臺(tái)服務(wù)器，其中3臺(tái)搭建Hadoop服務(wù)集群，1臺(tái)部署后端管理系統(tǒng)，每臺(tái)服務(wù)器內(nèi)存16 G、硬盤(pán)500 G，安裝社區(qū)企業(yè)操作系統(tǒng)

CentOS(Community Enterprise Operating System)。

軟件模塊包括HDFS分布式文件系統(tǒng)、計(jì)算框架MapReduce、資源管理YARN、數(shù)據(jù)倉(cāng)庫(kù)工具Hive、分布式NoSQL型數(shù)據(jù)庫(kù)MongoDB等。利用開(kāi)源工具Sqoop將用戶訪問(wèn)日志導(dǎo)入到Hadoop中，借助系統(tǒng)定時(shí)任務(wù)調(diào)度Sqoop實(shí)現(xiàn)增量數(shù)據(jù)定制導(dǎo)入。軟件技術(shù)架構(gòu)如圖5所示。

圖5 軟件技術(shù)架構(gòu)圖

2.2 出行路線推薦模塊的設(shè)計(jì)與實(shí)現(xiàn)

2.2.1 飛機(jī)/火車(chē)余票查詢模塊實(shí)現(xiàn)

查詢模塊功能分為飛機(jī)直達(dá)查詢、火車(chē)直達(dá)查詢和混合出行查詢。具體實(shí)現(xiàn)方式為:通過(guò)網(wǎng)絡(luò)爬蟲(chóng)抓取12306網(wǎng)站的火車(chē)票信息，同時(shí)從攜程網(wǎng)抓取機(jī)票信息，將相應(yīng)的票務(wù)信息存儲(chǔ)在數(shù)據(jù)庫(kù)以備后期數(shù)據(jù)處理工作。通過(guò)數(shù)據(jù)庫(kù)查詢語(yǔ)句將票務(wù)信息全部獲取進(jìn)入運(yùn)行內(nèi)存，再根據(jù)用戶輸入的出發(fā)地、目的地、出發(fā)日期、出發(fā)時(shí)間，再結(jié)合當(dāng)前日期和當(dāng)前時(shí)間完成票務(wù)信息的條件篩選和實(shí)時(shí)篩選。搜索流程圖如圖6所示，飛機(jī)/火車(chē)票的余票查詢結(jié)果如圖7所示。

圖6 搜索流程圖

圖7 飛機(jī)/火車(chē)余票搜索結(jié)果圖

2.2.2 混合路線推薦模塊實(shí)現(xiàn)

基于1.1節(jié)的算法實(shí)現(xiàn)路線推薦，并調(diào)用百度地圖接口，實(shí)現(xiàn)在虛擬地圖上進(jìn)行路線渲染顯示，并提供公交與打車(chē)出行建議。假設(shè)需要推薦濟(jì)南至沈陽(yáng)的路線，推薦界面如圖8所示(地圖審圖號(hào):GS(2019)5218｜測(cè)繪資質(zhì):甲測(cè)資字1100930)。

圖8 百度地圖調(diào)用界面圖

2.3 價(jià)格預(yù)測(cè)模塊的設(shè)計(jì)與實(shí)現(xiàn)

基于1.2節(jié)價(jià)格預(yù)測(cè)算法實(shí)現(xiàn)路線實(shí)時(shí)預(yù)測(cè)[15]，展示最近7 d的價(jià)格波動(dòng)，為了提高界面響應(yīng)速度，使用頁(yè)面“懶加載”技術(shù)，減輕流量負(fù)擔(dān)與瞬時(shí)負(fù)載。價(jià)格預(yù)測(cè)界面如圖9所示。

圖9 價(jià)格預(yù)測(cè)界面圖

任意選中兩個(gè)方案進(jìn)行對(duì)比，將前端獲取的數(shù)據(jù)傳遞給后臺(tái)的數(shù)據(jù)進(jìn)行解析篩選，計(jì)算出總花費(fèi)、路程耗時(shí)、出發(fā)時(shí)間、到達(dá)時(shí)間，進(jìn)行邏輯比較，方案對(duì)比如圖10所示。由圖可見(jiàn)，不同方案滿足不同的用戶需求，用戶可根據(jù)實(shí)際情況選擇相應(yīng)的出行方案。

圖10 方案對(duì)比圖

2.4 測(cè)試結(jié)果

系統(tǒng)經(jīng)過(guò)單元測(cè)試和性能測(cè)試達(dá)到預(yù)期設(shè)計(jì)要求，測(cè)試結(jié)果見(jiàn)表1。

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

表1 測(cè)試結(jié)果表

3 結(jié)語(yǔ)

文章研究的系統(tǒng)通過(guò)使用4層架構(gòu)搭建分布式大數(shù)據(jù)基礎(chǔ)環(huán)境，采用Hadoop+MongoDB+MySQL聯(lián)合存儲(chǔ)策略完成最優(yōu)海量數(shù)據(jù)存儲(chǔ)與實(shí)時(shí)計(jì)算，提高了出行數(shù)據(jù)處理效率與準(zhǔn)確度，實(shí)現(xiàn)了根據(jù)用戶個(gè)性化需求提供高效準(zhǔn)確的混合出行路線推薦方案和價(jià)格預(yù)測(cè)的功能。系統(tǒng)是一種高性能、高可靠性的實(shí)時(shí)智慧推薦應(yīng)用，改善了傳統(tǒng)路線制定的盲目性與隨機(jī)性，可為在分布式架構(gòu)上構(gòu)建推薦系統(tǒng)提供一定理論基礎(chǔ)和技術(shù)支撐。