一種新的行程推薦算法研究

佟玉軍　呂行　李煜　何俊

【摘 要】論文在研究POI等行程推薦技術的基礎上，提出了基于遺傳算法和總時間約束的行程推薦算法，并通過實際路網數據，對所提算法的效率、推薦結果合理性等進行了實驗測試，實驗結果表明，論文所提出的推薦算法能夠得到符合用戶期望的合理行程推薦。

【Abstract】 Basing on the research of POI recommended schedule， a schedule recommendation algorithm based on genetic algorithm and total time constraints is proposed， through the actual network data， the algorithms efficiency and result rationality are tested. The results show the new recommendation algorithm can obtain the reasonable travel which meet the users expectations.

【關鍵詞】POI行程推薦； 時間約束； 遺傳算法

【Keywords】POI schedule recommendation； time-constraint； genetic algorithm

【中圖分類號】TP311 【文獻標志碼】A 【文章編號】1673-1069（2017）07-0142-02

1 POI行程推薦方法

POI推薦只能夠根據用戶給定的偏好活動，推薦用戶相對應的活動地點，但是用戶還是需要根據自己的位置和時間的約束來決定去哪個活動地點，即使對位置十分熟悉的用戶這也將是一個比較難的問題，并且還有總時間的限制。在目前的研究中，也有涉及多個活動而且包含活動之間限制的研究[1]。這些研究考慮了多個活動，而且還考慮了活動之間的順序，但是這些研究都忽略了時間因素。

早期的一些研究主要基于GPS軌跡數據，LBSN上的簽到數據等進行[2]，都是通過利用傳統的協同過濾技術來為用戶推薦POI。此外，有些研究工作通過用戶生活和居住的區域來計算用戶之間的相似度[3]，然后將用戶之間的相似度作為傳統的協同過濾技術，即認為來自同一區域的用戶的興趣、喜好相似，從而可以通過分析與給定用戶來自同一區域的其他用戶的行為來預測該用戶的行為。這些POI推薦算法都能夠很好地滿足對于地點的查詢，對于地點和地點之間的關系，如地點之間的先后關系，以及地點之間的路徑等。但日常生活中，用戶不僅需要的是一個點的信息，更多的是想要得到一個完整行程的更多信息[4]。

2 多目標行程推薦算法

本文提出了新的行程推薦算法（Stroke Recommend Algorithm based on Genetic Algorithm and total Time Constraint， SRGATC），對時間約束下的行程規劃問題進行求解。本文的行程有效性包括兩方面的含義：①用戶偏好集合包含于活動類型集合；②行程總時間小于等于約束時間。在此，我們遵循這樣的假設：一般情況下，用戶希望從事興趣活動的時間越多越好，也就說路程活動時間和松弛時間越少越好[5]。

2.1 算法總體流程

基于遺傳算法的行程推薦算法主要分為三個部分，如圖1所示。第一個部分為初始有效行程生成算法，主要根據用戶的輸入得到有效行程，同時使得行程的總時間盡可能小。第二部分為活動插入，基于第一部分得到的有效行程集，再根據各個行程的松弛時間來判斷是否需要進行活動插入策略，從而使得松弛時間更短。第三部分進行候選行程多目標排序，完成推薦。

2.2 有效行程的創建

初始有效行程生成算法分為5個步驟。步驟1：初始化種群，構造染色體并生成一組規模為N的有效路徑，作為時間約束條件下行程規劃問題的一組初始解集。步驟2：計算初始種群的適應值，并確定當前種群中的最優解。步驟3：產生新一代種群。新一代種群由三個部分組成，第一部分用選擇算子作用于上一代種群產生新的個體；第二部分用交叉算子作用于上一代種群產生新的個體；第三部分則是對上一代種群按照一定的概率進行變異操作后加入到這一代種群，這時種群將會達到N至3N 之間。步驟4 ：改進新一代種群。刪除新一代種群中的非有效行程，然后按照有效行程的總時間進行排序，選擇前N個有效行程代表這一代種群。步驟5：評價，判斷是否滿足終止條件，滿足則退出，否則重復步驟3和步驟4。

3 實驗及結果

3.1 實驗環境和數據集

本文實驗基于遼寧省某市真實的路網數據進行，主要包含地標性建筑物、主要街道及其屬性標簽。其中每個活動除包含位置信息以外還包含了活動標簽、活動時間、活動花費、活動評分等屬性。表1描述了實驗數據集。

3.2 SRGATC實驗結果

因為SRGATC是基于遺傳算法進行修改的，所以本文針對初始種群大小、迭代次數、交換概率對行程推薦度的影響進行了實驗測試。在圖2中，橫坐標為初始種群大小，縱坐標為推薦度。隨著初始種群大小的增加，行程的推薦度也在增加，但是當初始種群大小增加到1000時，行程的推薦度就趨于穩定了。

4 結語

本文充分利用時間約束， 在滿足總時間約束條件下，使其能充分的利用時間行程，進而得到所有滿足總時間約束的排序行程，從而最終為用戶推薦最佳行程。

【參考文獻】

【1】吳清霞.基于用戶興趣和興趣點流行度的個性化旅游路線推薦[J]. 計算機應用，2016，36（6）：1762-1766.

【2】 曹孟毅. 基于內容相似度的運動路線推薦[J]. 計算機工程與應用， 2016，52（9）：33-38.

【3】 方瀟.一種基于協同過濾的旅游行程推薦算法[J]. 地理空間信息，2016，14（7）：53-56.

【4】 彭丹平， 王江晴. 一種求解旅行商問題的新算法[J]. 中南民族大學學報（自然科學版），2006，25（1）：79-80.

【5】 趙曦， 葉和平.廣義旅行商問題及其求解[J].東莞理工學院學報，2007（05）：75-80.endprint