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

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

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡(luò)優(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.桂林電子科技大學(xué)電子工程與自動化學(xué)院，廣西桂林541004
2.北京郵電大學(xué)自動化學(xué)院，北京100876
3.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004

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

Received 2015-03,Accepted 2015-06.

CNKI網(wǎng)絡(luò)優(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）算法求解旅游線路時間花費(fèi)較長的問題，提出了一種ILS結(jié)合布谷鳥搜索（cuckoo search，CS）的優(yōu)化算法，來優(yōu)化旅游線路的時間花費(fèi)。該算法首先根據(jù)相關(guān)目標(biāo)和約束采用ILS算法求解旅游景點(diǎn)及初始旅游線路，然后在滿足旅游景點(diǎn)時間窗約束及景點(diǎn)總數(shù)不變的情況下采用CS算法進(jìn)一步最小化旅游線路的時間花費(fèi)。該研究獲得的線路更符合旅游習(xí)慣，并且旅游時間花費(fèi)更少。通過Daminaos數(shù)據(jù)集和桂林景點(diǎn)數(shù)據(jù)集進(jìn)行驗(yàn)證，結(jié)果表明該優(yōu)化算法相比于僅使用ILS算法所規(guī)劃出的旅游線路，平均時間花費(fèi)減少8%，更符合用戶旅游選擇習(xí)慣。

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

1　引言

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

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

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

2　問題描述

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

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

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

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

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

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

3.1編碼方案

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

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

（1）生成8個取值范圍為[?2，2]之間的隨機(jī)數(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}。

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

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

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

3.2適應(yīng)度函數(shù)

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

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

3.3ILS-CS算法流程

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

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

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

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

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

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

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

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

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

4　實(shí)驗(yàn)配置及參數(shù)設(shè)定

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

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

4.2實(shí)驗(yàn)配置

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

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

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

4.3gap評價準(zhǔn)則

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

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

5　實(shí)驗(yàn)結(jié)果及分析

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

本文采用時間減少率gap以及行程的時間花費(fèi)作為評價標(biāo)準(zhǔn)來評價基于迭代局部搜索結(jié)合布谷鳥搜索的優(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ī)劃線路花費(fèi)時間；TCS表示CS優(yōu)化后花費(fèi)時間；Cn表示ILS算法規(guī)劃出的線路旅行結(jié)束時間。從表1中可以看出，針對不同的旅游結(jié)束時間規(guī)劃出的旅游線路，優(yōu)化前后的旅游線路點(diǎn)的個數(shù)不變，旅游線路上點(diǎn)的訪問順序發(fā)生變化，而優(yōu)化后的時間花費(fèi)TILS則比優(yōu)化前的時間花費(fèi)TCS有較大的減少，證明了該算法在旅游行程花費(fèi)時間上優(yōu)化的有效性。

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

Table 2 Comparison of visit time表2　景點(diǎn)訪問時間對比

表2為參數(shù)Oi＝540，Ci＝1 080，旅游起點(diǎn)和終點(diǎn)分別為桂林電子科技大學(xué)（東校區(qū)）和桂林火車站所規(guī)劃出的一條旅游線路。其中f表示離開景點(diǎn)的時間，s表示開始訪問景點(diǎn)時間。表中name一欄括號內(nèi)的數(shù)字表示景點(diǎn)的編號，AILS和ACS分別表示優(yōu)化前后的線路序列。通過表中可以看出，經(jīng)過ILS-CS算法優(yōu)化后，每條旅游線路中景點(diǎn)的訪問時間以及旅游線路花費(fèi)的總時間都發(fā)生改變，由式（18）得優(yōu)化后的時間花費(fèi)比優(yōu)化前的時間花費(fèi)gap減少率達(dá)到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)達(dá)到最優(yōu)；另外一種情況是選擇出來的景點(diǎn)的時間窗比較短，導(dǎo)致景點(diǎn)旅游順序的改變，違反景點(diǎn)的時間窗約束，因此無法進(jìn)一步優(yōu)化）。

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

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

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

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

5.2WebGIS上線路展示效果分析

通過對ILS算法規(guī)劃出的旅游線路的研究發(fā)現(xiàn)，線路交叉的現(xiàn)象較多，而經(jīng)過對行程花費(fèi)時間T的優(yōu)化，則可以減少線路花費(fèi)的時間，并有效減少旅游線路交叉現(xiàn)象。圖2為ILS參數(shù)O1＝540，Cn＝1 320時隨機(jī)選取的一條旅游線路。該條線路的ILS初始花費(fèi)時間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值的增大，行程花費(fèi)時間逐漸降低，WebGIS地圖上展示的旅游線路交叉現(xiàn)象也逐漸減少。分析發(fā)現(xiàn)，ILS算法在選擇旅游景點(diǎn)的時候僅考慮盡可能地選擇得分高的點(diǎn)，而沒有考慮到當(dāng)前的景點(diǎn)位置，因此在實(shí)際的旅游路線中會出現(xiàn)線路交叉現(xiàn)象，導(dǎo)致旅游行程時間的浪費(fèi)，而經(jīng)過ILS-CS優(yōu)化后的線路在滿足時間約束的同時并未出現(xiàn)線路交叉的現(xiàn)象，減少了行程花費(fèi)時間，并且更符合人們的旅游習(xí)慣。

6　結(jié)束語

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

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.

附中文參考文獻(xiàn)：

[12]韋向遠(yuǎn),楊輝華,謝譜模.基于CUDA的并行布谷鳥搜索算法設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與探索, 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—），男，河南南陽人，桂林電子科技大學(xué)電子工程與自動化學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R別，機(jī)器學(xué)習(xí)等。

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年于華東理工大學(xué)獲得博士學(xué)位，現(xiàn)為北京郵電大學(xué)自動化學(xué)院教授、博士生導(dǎo)師，桂林電子科技大學(xué)兼職教授，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚?，機(jī)器學(xué)習(xí)等。在國內(nèi)外期刊及學(xué)術(shù)會議上發(fā)表科技論文30余篇，其中被SCI檢索13篇，EI檢索20篇，主持和參與多項(xiàng)國家自然科學(xué)基金、廣西自然科學(xué)基金、廣西高校優(yōu)秀人才資助計(jì)劃等項(xiàng)目。

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年于上海交通大學(xué)獲得博士學(xué)位，現(xiàn)為桂林電子科技大學(xué)教師，主要研究領(lǐng)域?yàn)槟Ｊ阶R別，機(jī)器學(xué)習(xí)等。發(fā)表學(xué)術(shù)論文10余篇，主持和參與多項(xiàng)國家自然科學(xué)基金項(xiàng)目。

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—），男，四川達(dá)縣人，北京郵電大學(xué)自動化學(xué)院博士研究生，桂林電子科技大學(xué)助理研究員，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚恚瑱C(jī)器學(xué)習(xí)等。

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—），女，湖北武漢人，桂林電子科技大學(xué)電子工程與自動化學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R別，圖像處理等。在國內(nèi)外期刊及學(xué)術(shù)會議上發(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

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP301

doi:10.3778/j.issn.1673-9418.1503030