佟玉軍　呂行　李煜　何俊

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

【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.

【關(guān)鍵詞】POI行程推薦； 時(shí)間約束； 遺傳算法

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

【中圖分類號】TP311 【文獻(xiàn)標(biāo)志碼】A 【文章編號】1673-1069（2017）07-0142-02

1 POI行程推薦方法

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

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

2 多目標(biāo)行程推薦算法

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

2.1 算法總體流程

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

2.2 有效行程的創(chuàng)建

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

3 實(shí)驗(yàn)及結(jié)果

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本文實(shí)驗(yàn)基于遼寧省某市真實(shí)的路網(wǎng)數(shù)據(jù)進(jìn)行，主要包含地標(biāo)性建筑物、主要街道及其屬性標(biāo)簽。其中每個(gè)活動(dòng)除包含位置信息以外還包含了活動(dòng)標(biāo)簽、活動(dòng)時(shí)間、活動(dòng)花費(fèi)、活動(dòng)評分等屬性。表1描述了實(shí)驗(yàn)數(shù)據(jù)集。

3.2 SRGATC實(shí)驗(yàn)結(jié)果

因?yàn)镾RGATC是基于遺傳算法進(jìn)行修改的，所以本文針對初始種群大小、迭代次數(shù)、交換概率對行程推薦度的影響進(jìn)行了實(shí)驗(yàn)測試。在圖2中，橫坐標(biāo)為初始種群大小，縱坐標(biāo)為推薦度。隨著初始種群大小的增加，行程的推薦度也在增加，但是當(dāng)初始種群大小增加到1000時(shí)，行程的推薦度就趨于穩(wěn)定了。

4 結(jié)語

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

【參考文獻(xiàn)】

【1】吳清霞.基于用戶興趣和興趣點(diǎn)流行度的個(gè)性化旅游路線推薦[J]. 計(jì)算機(jī)應(yīng)用，2016，36（6）：1762-1766.

【2】 曹孟毅. 基于內(nèi)容相似度的運(yùn)動(dòng)路線推薦[J]. 計(jì)算機(jī)工程與應(yīng)用， 2016，52（9）：33-38.

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

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

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