基于ILS-CS優化算法的個性化旅游線路研究*

侯　樂，楊輝華,2+，樊永顯，李靈巧,2，蔣淑潔.桂林電子科技大學電子工程與自動化學院，廣西桂林540042.北京郵電大學自動化學院，北京00876.桂林電子科技大學計算機科學與工程學院，廣西桂林54004

* The National Natural Science Foundation of China under Grant Nos. 21365008, 61105004 , 61462018 (國家自然科學基金); the Natural Science Foundation of Guangxi under Grant No. 2012GXNSFAA053230 (廣西自然科學基金); the Scientific Research Fund of Guangxi Education Department under Grant No. LX2014139 (廣西教育廳科研項目); the Innovation Project of Graduate Education of Guilin University of Electronic Technology under Grant No. GDYCSZ201478 (桂林電子科技大學研究生教育創新計劃資助項目).

Received 2015-03,Accepted 2015-06.

CNKI網絡優先出版：2015-06-05, http://www.cnki.net/kcms/detail/11.5602.TP.20150605.1537.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0142-09

?

基于ILS-CS優化算法的個性化旅游線路研究*

侯樂1，楊輝華1,2+，樊永顯3，李靈巧1,2，蔣淑潔1
1.桂林電子科技大學電子工程與自動化學院，廣西桂林541004
2.北京郵電大學自動化學院，北京100876
3.桂林電子科技大學計算機科學與工程學院，廣西桂林541004

* The National Natural Science Foundation of China under Grant Nos. 21365008, 61105004 , 61462018 (國家自然科學基金); the Natural Science Foundation of Guangxi under Grant No. 2012GXNSFAA053230 (廣西自然科學基金); the Scientific Research Fund of Guangxi Education Department under Grant No. LX2014139 (廣西教育廳科研項目); the Innovation Project of Graduate Education of Guilin University of Electronic Technology under Grant No. GDYCSZ201478 (桂林電子科技大學研究生教育創新計劃資助項目).

Received 2015-03,Accepted 2015-06.

CNKI網絡優先出版：2015-06-05, http://www.cnki.net/kcms/detail/11.5602.TP.20150605.1537.002.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0142-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：針對迭代局部搜索（iterated local search，ILS）算法求解旅游線路時間花費較長的問題，提出了一種ILS結合布谷鳥搜索（cuckoo search，CS）的優化算法，來優化旅游線路的時間花費。該算法首先根據相關目標和約束采用ILS算法求解旅游景點及初始旅游線路，然后在滿足旅游景點時間窗約束及景點總數不變的情況下采用CS算法進一步最小化旅游線路的時間花費。該研究獲得的線路更符合旅游習慣，并且旅游時間花費更少。通過Daminaos數據集和桂林景點數據集進行驗證，結果表明該優化算法相比于僅使用ILS算法所規劃出的旅游線路，平均時間花費減少8%，更符合用戶旅游選擇習慣。

關鍵詞：旅游線路規劃；迭代局部搜索；布谷鳥搜索；帶時間窗的定向問題；帶時間窗的旅行商問題

1　引言

隨著經濟社會的發展，旅游業競爭也越來越激烈，如何減少路線安排的盲目性和隨意性，為客戶提供個性化旅游線路，從而提供更多可供用戶選擇的旅游方案已逐步成為目前相關企業以及學科的研究熱點。然而當前的旅游推薦系統通常通過運籌學方法來尋求最優線路，具有如下問題：（1）未考慮組團旅游的需求；（2）未考慮游客的個性化喜好、需求和約束[1]；（3）未考慮用戶選擇的開始與結束地點、預算的花費時間以及當前出發的時間。因此需要根據上述約束利用機器學習的方法提出更為合理、更符合用戶旅游選擇習慣的線路[2]。

最早，針對個性化旅游線路規劃問題，Hagen等人[3]通過分支界定法來實現旅游線路的規劃，該方法計算時間長，且線路規劃不合理。Kramer等人[4]根據每個用戶對同一個景點評分的差異性，提出了個性化的旅游線路規劃，改善了傳統旅游推薦系統通過統計學方法設定單個景點的評分問題。當前，Chao等人將定向問題（orienteering problem，OP）[5]作為個性化旅游線路規劃問題的求解優化方案[6-7]。該問題為NP難問題，不能夠在多項式時間內求出最優解，且未考慮各景點開放和參觀時間。因此Dumas等人針對景點開放時間和參觀時間問題，提出了一種帶時間窗的旅行商問題（travel salesman problem with time windows，TSPTW）的旅游線路規劃。該模型要求所有的景點必須被訪問，因此不適用于時間有限、景點數量多的旅游線路規劃[8]。近期，Vansteenwegen等人[9]采用迭代局部搜索算法來對帶時間窗的定向問題進行求解，該算法能夠在較短的時間內計算出一條較優的線路。Gavalas等人[10]采用聚類和迭代搜索相結合的方法解決帶時間窗的定向問題。但是上述兩種方法規劃出來的旅游線路存在行程花費時間較長的缺點。

根據上述研究所存在的問題，本文提出了一種基于迭代局部搜索（iterated local search，ILS）結合布谷鳥搜索（cuckoo search，CS）的優化算法模型。該模型首先采用ILS求解出旅游景點及初始旅游線路，然后在滿足旅游景點時間窗約束及景點總數不變的情況下，采用CS算法最小化旅游線路的時間花費。該優化算法通過Daminaos數據集和桂林市的部分景點數據集進行驗證，對比于單一使用迭代局部搜索算法所規劃出的旅游線路，具有更好的優化效果。

2　問題描述

給定一個完全有向圖G＝(V，E)，其中V＝{1，2，…，n}是節點集，E＝{(i，j)|i，j∈V}是邊集。每個節點i＝1，2，…，n對應一個得分Si、參觀時間Ti和一個時間窗[Oi，Ci]。邊tij表示從節點i到節點j所需的時間（包括Tj）。因此，帶時間窗的定向問題即找出一條從節點1出發到節點n終止的路徑，使得所經過點的總得分最大化。每個節點至多能訪問一次，路徑中訪問相應點所用的總時間不能超過預先規定的時間預算Tmax。若節點j是節點i的下一個訪問節點，則xij＝1，反之等于0，xij為決策變量。Tmax滿足Tmax＝Cn?O1，帶時間窗的定向問題的數學描述為[5]：

其中，si為訪問節點i的開始時間；M為一個大的常量。式（1）為目標函數，表示路徑上所有滿足xij＝1的點的得分之和最大；式（2）中x1j＝1表示路徑必須從節點1出發，xin＝1表示路徑中n為最后節點；式（3）中xik和xkj表示每個節點至多被訪問一次，不允許節點被重復訪問；式（4）表示若節點i、j聯通，則j的開始時間等于i的開始時間加上節點i、j的距離和i的參觀時間，若節點i、j不聯通，則j的開始時間始終大于si和tij之和，確保節點時間的連通性；式（5）表示路徑中所有聯通節點花費的時間總和（包括節點之間的距離、參觀時間及等待時間）小于時間預算Tmax；式（6）表示節點i的訪問開始時間大于i的開放時間并小于其關閉時間；式（7）表示xij為決策變量，其值為0或1。

優化算法的核心是將ILS算法規劃出的初始旅游線路作為帶時間窗的旅行商問題[8]，使用布谷鳥搜索算法[11]對其進行優化。TSPTW問題可描述為：對于給定的一組節點集合{1，2，…，n}，節點1和節點n分別為起始和終止節點，每個節點i有一參觀時間Ti和一個時間窗[Oi，Ci]，每個節點只能在其時間窗內被訪問。邊tij表示從節點i到節點j所需的時間（包括Tj）。優化目標是給出一條訪問所有節點的路徑，使總的時間花費最少。帶時間窗的旅行商問題的數學描述為：

式（8）為目標函數，表示路徑中所有聯通節點花費時間之和（包括節點之間的距離時間、參觀時間及等待時間）最小；式（9）中x1j＝1表示路徑必須從節點1出發，xin＝1表示路徑中n為最后節點；式（10）中xik和xkj表示每個節點必須訪問一次；式（11）表示節點i的訪問開始時間大于i的開放時間并小于其關閉時間；式（12）表示xij為決策變量，其值為0或1。

為求解這兩個問題，本文采用迭代局部搜索算法和布谷鳥搜索算法依次求解。首先根據相關約束采用迭代局部搜索算法，最大化總收益，求解出旅游景點和初始旅游線路；然后在旅游景點不變的情況下，采用布谷鳥搜索算法進一步優化時間花費。其中，迭代局部搜索算法的基本原理和流程參見文獻[9]。

3　優化模型求解

3.1編碼方案

本文根據TSPTW問題的特點采用基于優先級的編碼方案，每一個編碼個體根據優先級的大小表示一種可行解[12]。

以ILS規劃出的路徑{1，8，3，6，9，2，5，7，4，100}為例，其中1表示出發節點，100表示結束節點，則只需要對其余的8個節點按照優先級編碼。具體編碼方式如下：

（1）生成8個取值范圍為[?2，2]之間的隨機數

(?1.230 5，0.345 2，1.735 6，?0.253 6，1.467 3，?0.531 6，0.432 1，0.764 6)

（2）將優先級按照降序排列得到一條編碼方案

(1.735 6,1.467 3,0.764 6,0.432 1,0.345 2,?0.253 6，?0.531 6,?1.230 5)則根據上述編碼方案解碼得到的一條可行解為{1，8，3，6，9，2，5，7，4，100}。

以萊維飛行的方式搜索新的鳥巢并進行位置更新[13]，如式（13）所示：

在CS算法中采用Levy搜索路徑，如式（15）所示：

本文取值β＝1.2，u和v服從式（16）的正態分布：

3.2適應度函數

根據基于時間窗的旅行商問題的數學模型，優化目標是該條路徑的節點在滿足約束的條件下花費時間最少，則CS算法的適應度函數如式（17）所示：

該適應度函數表示對可行解上所有聯通的節點計算其總的花費時間，適應度值越小，表示可行解越優，若該可行解上聯通節點違反時間窗約束，則該可行解的適應度值設為無限大。

3.3ILS-CS算法流程

ILS-CS算法求解TSPTW問題的流程[14]如下：

（1）定義適應度函數f(x)，計算ILS初始路徑的花費時間Tinit；

（2）初始化算法基本參數，布谷鳥選擇宿主鳥巢數目n，發現概率pa和最大迭代次數Niter；

（3）布谷鳥隨機選擇鳥巢位置nesti(i＝1，2，…，n)，按照3.1節的編碼方案編碼；

（4）根據Levy飛行更新鳥巢位置nesti，計算鳥巢適應度值，保留適應度值最小的鳥巢；

（5）更新鳥巢nesti的位置，得到新的鳥巢位置newNest；

（6）對新鳥巢中的每個個體，宿主以一定的概率pa放棄當前的鳥巢而新建鳥巢，形成新的種群；

（7）再次計算每個鳥巢的適應度f(x)，保留適應度值小于Tinit的可行解；

（8）當達到最大迭代次數則輸出最優解，否則轉（4）進行下一輪搜索。

4　實驗配置及參數設定

4.1數據來源

本文主要使用兩種數據：一種數據是來源于百度旅游網桂林市景點的數據集合（http：//lvyou.baidu. co m/guilin/jingdian)，簡稱Guilin數據集，其中旅游景點的數目為162個，每個節點的Ti在30～480之間。其中開放時間為0～1 440的節點數量86個。另一種是Daminaos[10]數據集（http：//dgavalas.ct.aegean.gr/ public/op_instainst/），其中節點數為n，分布在100～ 200之間，每個節點的參觀時間Ti在1到120之間，數據50%的節點開放時間為0～1 440，其余的時間窗為Oi＝510，Ci＝1 020，和各自包含有50個測試樣本，兩種數據集均為長時間窗。

4.2實驗配置

實驗環境為一臺處理器為Intel?CoreTMi5-2400 CPU，主頻為3.1 GHz，內存4 GB的臺式機。本文實驗所采用的軟件為Visual Studio 2012及Sql Server 2008，迭代局部搜索算法來源于Vansteenwegen等人[9]，布谷鳥搜索算法來源于Yang等人[11]。本實驗內容包括兩組實驗分析：

（1）ILS-CS算法優化效果分析；

（2）WebGIS上線路展示效果分析。

4.3gap評價準則

ILS-CS算法優化的目標是在滿足時間窗約束的條件下找到一條時間花費更短的線路。本文用時間減少率gap評價優化的效果，gap的求解方式如式（18）所示：

式（18）中，gap表示時間減少率；TILS表示ILS算法規劃出線路花費的時間；TCS表示CS對ILS的線路優化后花費的時間；O1表示旅行開始時間。gap值越大表示CS算法的優化效果越好。

5　實驗結果及分析

5.1ILS-CS算法優化效果分析

本文采用時間減少率gap以及行程的時間花費作為評價標準來評價基于迭代局部搜索結合布谷鳥搜索的優化算法個性化旅游路線規劃的優化效果。

表1中前8條和后4條數據分別是使用Guilin數據集和Daminaos數據集規劃出的旅游線路。表中ItineraryILS表示ILS算法規劃出的線路；ItineraryCS表示CS算法規劃出的線路；TILS表示ILS規劃線路花費時間；TCS表示CS優化后花費時間；Cn表示ILS算法規劃出的線路旅行結束時間。從表1中可以看出，針對不同的旅游結束時間規劃出的旅游線路，優化前后的旅游線路點的個數不變，旅游線路上點的訪問順序發生變化，而優化后的時間花費TILS則比優化前的時間花費TCS有較大的減少，證明了該算法在旅游行程花費時間上優化的有效性。

Table 1 Comparison of trip itinerary and spend time表1　優化線路及花費時間對比

Table 2 Comparison of visit time表2　景點訪問時間對比

表2為參數Oi＝540，Ci＝1 080，旅游起點和終點分別為桂林電子科技大學（東校區）和桂林火車站所規劃出的一條旅游線路。其中f表示離開景點的時間，s表示開始訪問景點時間。表中name一欄括號內的數字表示景點的編號，AILS和ACS分別表示優化前后的線路序列。通過表中可以看出，經過ILS-CS算法優化后，每條旅游線路中景點的訪問時間以及旅游線路花費的總時間都發生改變，由式（18）得優化后的時間花費比優化前的時間花費gap減少率達到10.3%。

表3為使用Guilin數據集和Daminaos數據集測試算法優化效果。每個數據集分別測試100條線路樣本。其中Guilin數據集的gap值最小為1.2%，最大為12.6%，方差為0.001 48，說明ILS-CS優化算法優化的效果比較穩定。對Daminaos數據集，gap值最小為0（一種情況該算法旅游時間上已經達到最優；另外一種情況是選擇出來的景點的時間窗比較短，導致景點旅游順序的改變，違反景點的時間窗約束，因此無法進一步優化）。

Table 3 Comparison of optimization gap between two data sets表3　兩種數據集的優化結果對比

Fig.1 Convergence curves for different Cn圖1　不同Cn值的收斂曲線

以下對ILS-CS算法優化的收斂性進行分析，圖1為采用ILS算法O1＝540，Cn參數分別為1 320、1 200、1 080、960，隨機規劃出的8條初始線路使用CS算法優化的收斂曲線圖，圖中每種顏色代表一條旅游線路。CS參數為n＝10，pa＝0.25，評價次數為5 000。從圖中可以得出，對不同的時間約束Cn規劃出的線路，ILS-CS優化算法能夠快速收斂并得到最優的結果。

Fig.2 Trip itinerary for different gap圖2　不同gap值的旅游線路

5.2WebGIS上線路展示效果分析

通過對ILS算法規劃出的旅游線路的研究發現，線路交叉的現象較多，而經過對行程花費時間T的優化，則可以減少線路花費的時間，并有效減少旅游線路交叉現象。圖2為ILS參數O1＝540，Cn＝1 320時隨機選取的一條旅游線路。該條線路的ILS初始花費時間TILS＝1 286.7 min，經過優化后的時間為TCS＝1 252.2 min，時間減少率為3.4%，圖2（a）到圖2（d）是旅游線路gap值為0，1.2%，2.0%，3.4%時的線路在WebGIS上的展示效果。

從圖2中可以看出，隨著gap值的增大，行程花費時間逐漸降低，WebGIS地圖上展示的旅游線路交叉現象也逐漸減少。分析發現，ILS算法在選擇旅游景點的時候僅考慮盡可能地選擇得分高的點，而沒有考慮到當前的景點位置，因此在實際的旅游路線中會出現線路交叉現象，導致旅游行程時間的浪費，而經過ILS-CS優化后的線路在滿足時間約束的同時并未出現線路交叉的現象，減少了行程花費時間，并且更符合人們的旅游習慣。

6　結束語

本文針對個性化旅游線路規劃中存在的時間花費問題，提出了一種基于迭代局部搜索結合布谷鳥搜索的優化算法對旅游線路的時間花費進行優化。本文算法通過相關約束，采用迭代局部搜索算法取得了更符合用戶旅游習慣的線路，再結合布谷鳥優化算法使得旅游的時間花費減少。本文方法使得旅游線路花費時間較優化前有較大的提升，并且規劃出的旅游線路更符合用戶的旅游習慣。該研究可以進一步延伸到將當地的天氣以及實時交通約束考慮在個性化旅游線路規劃中，使其更符合實際旅游的需要。

References：

[1] Cheverst K, Davies N, Mitchell K, et al. Developing a contextaware electronic tourist guide: some issues and experiences[C]// Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Hague, Netherlands, 2000: 17-24.

[2] Malaka R. Artificial intelligence goes mobile[C]//Artificial Intelligence in Mobile Systems—AIMS2000, Workshop in Conjunction with ECAI 2000, 2000: 5-7.

[3] Hagen K, Kramer R, Hermkes M, et al. Semantic matching and heuristic search for a dynamic tour guide[C]//Proceedings of the 2005 International Conference on Information and Communication Technologies in Tourism, Innsbruck, Austria, 2005. Vienna: Springer, 2005: 149-159.

[4] Kramer R, Modsching M, Ten Hagen K. A city guide agent creating and adapting individual sightseeing tours based on field trial results[J]. International Journal of Computational Intelligence Research, 2006, 2(2): 191-206.

[5] Vansteenwegen P, Souffriau W, Oudheusden D V. The orienteering problem: a survey[J]. European Journal of Operational Research, 2011, 209(1): 1-10.

[6] Chao I, Golden B L, Wasil E A. The team orienteering problem[J]. European Journal of Operational Research, 1996, 88 (3): 464-474.

[7] Souffriau W, Vansteenwegen P, Vertommen J, et al.Apersonalized tourist trip design algorithm for mobile tourist guides[J]. Applied Artificial Intelligence, 2008, 22(10): 964-985.

[8] Dumas Y, Desrosiers J, Gelinas E, et al. An optimal algorithm for the traveling salesman problem with time windows[J]. Operations Research, 1995, 43(2): 367-371.

[9] Vansteenwegen P, Souffriau W, Berghe G V, et al. Iterated local search for the team orienteering problem with time windows[J]. Computers & Operations Research, 2009, 36 (12): 3281-3290.

[10] Gavalas D, Konstantopoulos C, Mastakas K, et al. Clusterbased heuristics for the team orienteering problem with time windows[M]//Experimental Algorithms. Berlin, Heidelberg: Springer, 2013: 390-401.

[11] Yang Xinshe, Deb S. Cuckoo search via Lévy flights[C]// Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway, USA: IEEE, 2009: 210-214.

[12] Wei Xiangyuan,Yang Huihua, Xie Pumo. Research and implementation of parallel cuckoo search based on CUDA[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(6): 665-673.

[13] Durgun ?, Yildiz AR. Structural design optimization of vehicle components using cuckoo search algorithm[J]. Materials Testing, 2012, 54(3): 185-188.

[14] Yang Xinshe, Deb S. Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 1(4): 330-343.

附中文參考文獻：

[12]韋向遠,楊輝華,謝譜模.基于CUDA的并行布谷鳥搜索算法設計與實現[J].計算機科學與探索, 2014, 8(6): 665-673.

HOU Le was born in 1988. He is an M.S. candidate at School of Electronic Engineering and Automation, Guilin University of Electronic Technology. His research interests include pattern recognition and machine learning, etc.

侯樂（1988—），男，河南南陽人，桂林電子科技大學電子工程與自動化學院碩士研究生，主要研究領域為模式識別，機器學習等。

YANG Huihua was born in 1972. He received the Ph.D. degree from East China University of Science and Technology in 2005. Now he is a professor and Ph.D. supervisor at Beijing University of Posts and Telecommunications, and an adjunct professor at Guilin University of Electronic Technology. His research interests include intelligent information processing and machine learning, etc.

楊輝華（1972—），男，湖南常德人，2005年于華東理工大學獲得博士學位，現為北京郵電大學自動化學院教授、博士生導師，桂林電子科技大學兼職教授，主要研究領域為智能信息處理，機器學習等。在國內外期刊及學術會議上發表科技論文30余篇，其中被SCI檢索13篇，EI檢索20篇，主持和參與多項國家自然科學基金、廣西自然科學基金、廣西高校優秀人才資助計劃等項目。

FAN Yongxian was born in 1977. He received the Ph.D. degree from Shanghai Jiao Tong University in 2013. Now he is a lecturer at Guilin University of Electronic Technology. His research interests include pattern recognition and machine learning, etc.

樊永顯（1977—），男，河南平頂山人，2013年于上海交通大學獲得博士學位，現為桂林電子科技大學教師，主要研究領域為模式識別，機器學習等。發表學術論文10余篇，主持和參與多項國家自然科學基金項目。

LI Lingqiao was born in 1986. He is a Ph.D. candidate at School of Automation, Beijing University of Posts and Telecommunications. His research interests include intelligent information processing and machine learning, etc.

李靈巧（1986—），男，四川達縣人，北京郵電大學自動化學院博士研究生，桂林電子科技大學助理研究員，主要研究領域為智能信息處理，機器學習等。

JIANG Shujie was born in 1989. She is an M.S. candidate at School of Electronic Engineering and Automation, Guilin University of Electronic Technology. Her research interests include pattern recognition and image processing, etc.蔣淑潔（1989—），女，湖北武漢人，桂林電子科技大學電子工程與自動化學院碩士研究生，主要研究領域為模式識別，圖像處理等。在國內外期刊及學術會議上發表科技論文5篇，其中被SCI檢索3篇，EI檢索2篇。

Research on Personalized Trip Itinerary Based on ILS-CS Optimization*

HOU Le1, YANG Huihua1,2+, FAN Yongxian3, LI Lingqiao1,2, JIANG Shujie1
1. School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
2. School of Automation, Beijing University of Posts and Telecommunications, Beijing 100876, China
3. SchoolofComputerScienceandEngineering,GuilinUniversityofElectronicTechnology,Guilin,Guangxi541004,China
+ Corresponding author: E-mail: yhh@bupt.edu.cn

HOU Le, YANG Huihua, FAN Yongxian, et al. Research on personalized trip itinerary based on ILS-CS optimization. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：142-150.

Abstract:For the long travel time on trip itinerary planned by iterated local search (ILS), this paper proposes an optimization algorithm based on iterated local search with cuckoo search optimization to reduce the travel time. Firstly, this algorithm adopts ILS algorithm for solving an initial trip itinerary and several tourist attractions with some relevant objectives and constraints. Then, under the circumstance of no changing the time windows and the number of tourist attractions, this paper utilizes CS algorithm to minimize the travel time. The tourist route is obtained by above methods in this paper. It is more conform to travel habits and less travel time than existed ones. The experimental results on Daminaos and Guilin city data sets show that the average travel time of the proposed method reduces bybook=143,ebook=1478%, compared with only using ILS algorithm in itinerary optimization, and planning the itinerary for personalized tourists is more in line with user's choice.

Key words:trip itinerary planning; iterated local search; cuckoo search; orienteering problem with time windows; travel salesman problem with time windows

文獻標志碼：A

中圖分類號：TP301

doi:10.3778/j.issn.1673-9418.1503030