基于ILS-CS優(yōu)化算法的個性化旅游線路研究*

侯　樂，楊輝華,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 (桂林電子科技大學研究生教育創(chuàng)新計劃資助項目).

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡優(yōu)先出版：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優(yōu)化算法的個性化旅游線路研究*

侯樂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 (桂林電子科技大學研究生教育創(chuàng)新計劃資助項目).

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡優(yōu)先出版：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）的優(yōu)化算法，來優(yōu)化旅游線路的時間花費。該算法首先根據(jù)相關目標和約束采用ILS算法求解旅游景點及初始旅游線路，然后在滿足旅游景點時間窗約束及景點總數(shù)不變的情況下采用CS算法進一步最小化旅游線路的時間花費。該研究獲得的線路更符合旅游習慣，并且旅游時間花費更少。通過Daminaos數(shù)據(jù)集和桂林景點數(shù)據(jù)集進行驗證，結果表明該優(yōu)化算法相比于僅使用ILS算法所規(guī)劃出的旅游線路，平均時間花費減少8%，更符合用戶旅游選擇習慣。

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

1　引言

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

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

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

2　問題描述

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

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

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

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

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

3　優(yōu)化模型求解

3.1編碼方案

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

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

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

(?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）將優(yōu)先級按照降序排列得到一條編碼方案

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

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

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

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

3.2適應度函數(shù)

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

該適應度函數(shù)表示對可行解上所有聯(lián)通的節(jié)點計算其總的花費時間，適應度值越小，表示可行解越優(yōu)，若該可行解上聯(lián)通節(jié)點違反時間窗約束，則該可行解的適應度值設為無限大。

3.3ILS-CS算法流程

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

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

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

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

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

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

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

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

（8）當達到最大迭代次數(shù)則輸出最優(yōu)解，否則轉(zhuǎn)（4）進行下一輪搜索。

4　實驗配置及參數(shù)設定

4.1數(shù)據(jù)來源

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

4.2實驗配置

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

（1）ILS-CS算法優(yōu)化效果分析；

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

4.3gap評價準則

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

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

5　實驗結果及分析

5.1ILS-CS算法優(yōu)化效果分析

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

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

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

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

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

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

Table 3 Comparison of optimization gap between two data sets表3　兩種數(shù)據(jù)集的優(yōu)化結果對比

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

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

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

5.2WebGIS上線路展示效果分析

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

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

6　結束語

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

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的并行布谷鳥搜索算法設計與實現(xiàn)[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年于華東理工大學獲得博士學位，現(xiàn)為北京郵電大學自動化學院教授、博士生導師，桂林電子科技大學兼職教授，主要研究領域為智能信息處理，機器學習等。在國內(nèi)外期刊及學術會議上發(fā)表科技論文30余篇，其中被SCI檢索13篇，EI檢索20篇，主持和參與多項國家自然科學基金、廣西自然科學基金、廣西高校優(yōu)秀人才資助計劃等項目。

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年于上海交通大學獲得博士學位，現(xiàn)為桂林電子科技大學教師，主要研究領域為模式識別，機器學習等。發(fā)表學術論文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—），女，湖北武漢人，桂林電子科技大學電子工程與自動化學院碩士研究生，主要研究領域為模式識別，圖像處理等。在國內(nèi)外期刊及學術會議上發(fā)表科技論文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